Hi Philip, Thank you very much for your comments. I think I’ve discovered a root cause. The problem was in linking bit code archive files with the module. At some point, std::set<Module*> is used and iterated over. I believe this was the reason why e.g. It worked consistently with ASLR turned off and produced non-deterministic output otherwise. I changed that bit to use vector instead and now it seems to be working as expected. I wouldn’t be surprised if this is already fixed / changed in some newer version of LLVM and I agree I should upgrade :) Thank you very much for help, Best regards Tomek On 03/06/2014 17:15, "Philip Reames" <listmail at philipreames.com> wrote:> >On 06/03/2014 02:50 AM, Kuchta, Tomasz wrote: >> Hi Philip, >> >> I would like to ask a follow-up question about code generation. >> Do you know if is expected that if we take the same bit code modules and >> link them together in the same order (programatically), but on different >> machines (assuming the same version of LLVM and >> roughly the same OS), the output may differ with respect to order of >> function definitions inside module? >This falls in to the category of "not really surprising". There's enough >variation between machines that it's not uncommon for an otherwise >mostly-deterministic process to behave slightly differently. I wouldn't >call the change in order "expected", but it also doesn't sound like an >obvious bug. > >Also, from what you said previously, you're working with a very old >version of LLVM. Most of my own experience is with newer versions so it >may be my expectations are badly off. I'd really recommend you upgrade. >You'll get much more applicable advice. :) >> >> Thank you very much in advance for help, >> >> Best regards >> Tomasz Kuchta >> >> On 29/05/2014 22:22, "Kuchta, Tomasz" <t.kuchta12 at imperial.ac.uk> wrote: >> >>> Hi Philip, >>> >>> Thank you very much for the reply. I need to add one important detail - >>> currently I¹m working on an outdated version of >>> LLVM, so I will need to first make sure that it also appears on the >>> current one. >>> >>> The use case that I have in mind is to be able to uniquely identify >>> instruction in the bit code. >>> For example let¹s say we have an ³add² instruction in some function >>>and I >>> want to know that this is the same >>> instruction in two separate runs. If the function is put in some >>>different >>> place as a result of inserting function and linking in the second run, >>> how would I identify that instruction? It seems to me that cannot rely >>>on >>> the offset of the instruction within the binary and I cannot rely on >>>the >>> instruction count. >Have you considered trying either metadata or using an intrinsic >function as a marker for the interesting instruction? Depending on your >use case, either might work. (f.y.i. I believe Metadata has changed >radically since earlier versions.) >>> The problem in my case was that for the same source code base, I was >>> getting different resulting LLVM IR when doing the same >>> sequence of getOrInsertFunction and linking with other bit code >>>modules on >>> each of runs. >>> >>> Thank you, >>> Tomek >>> >>> On 29/05/2014 19:34, "Philip Reames" <listmail at philipreames.com> wrote: >>> >>>> On 05/29/2014 11:06 AM, Tim Northover wrote: >>>>> Hi Tomek, >>>>> >>>>>> I¹ve got a question about Module::getOrInsertFunction(). >>>>>> I got an impression that it is not deterministic where exactly in >>>>>>the >>>>>> bit >>>>>> code module the new function will be inserted. >>>>> Looking at the code (not exhaustively), it seems a new function will >>>>> always be added to the end of a module. >>>>> >>>>> Documenting that probably wouldn't be a terrible idea, but it >>>>> shouldn't affect anything except the human-readability of LLVM IR. >>>>>Are >>>>> you trying to do something where it is actually causing problems? >>>>> >>>>> Cheers. >>>>> >>>>> Tim. >>>> I would argue in favor of leaving this explicitly undocumented. I >>>>don't >>>> see the use case in knowing where in a module it got added, and it >>>> restricts future implementations in ways we can't predict. Documenting >>>> that it must be deterministic is fine. Documenting where it decides >>>>to >>>> place it is not. >>>> >>>> Tomek, could you spell out why you need the position? Maybe there's >>>> another option here. >>>> >>>> Philip >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >
On 06/04/2014 02:32 AM, Kuchta, Tomasz wrote:> Hi Philip, > > Thank you very much for your comments. > I think I’ve discovered a root cause. The problem was in linking bit code > archive files with the module. > At some point, std::set<Module*> is used and iterated over. I believe this > was the reason why e.g. It worked consistently with > ASLR turned off and produced non-deterministic output otherwise. I changed > that bit to use vector instead and now it seems to > be working as expected. I wouldn’t be surprised if this is already fixed / > changed in some newer version of LLVM and I agree I should upgrade :)Would you mind checking to see if the current TOT uses the set representation? If so, please file a bug with an explanation of the ordering problem involving ASLR. Linking should be stable.> > Thank you very much for help, > Best regards > Tomek > > On 03/06/2014 17:15, "Philip Reames" <listmail at philipreames.com> wrote: > >> On 06/03/2014 02:50 AM, Kuchta, Tomasz wrote: >>> Hi Philip, >>> >>> I would like to ask a follow-up question about code generation. >>> Do you know if is expected that if we take the same bit code modules and >>> link them together in the same order (programatically), but on different >>> machines (assuming the same version of LLVM and >>> roughly the same OS), the output may differ with respect to order of >>> function definitions inside module? >> This falls in to the category of "not really surprising". There's enough >> variation between machines that it's not uncommon for an otherwise >> mostly-deterministic process to behave slightly differently. I wouldn't >> call the change in order "expected", but it also doesn't sound like an >> obvious bug. >> >> Also, from what you said previously, you're working with a very old >> version of LLVM. Most of my own experience is with newer versions so it >> may be my expectations are badly off. I'd really recommend you upgrade. >> You'll get much more applicable advice. :) >>> Thank you very much in advance for help, >>> >>> Best regards >>> Tomasz Kuchta >>> >>> On 29/05/2014 22:22, "Kuchta, Tomasz" <t.kuchta12 at imperial.ac.uk> wrote: >>> >>>> Hi Philip, >>>> >>>> Thank you very much for the reply. I need to add one important detail - >>>> currently I¹m working on an outdated version of >>>> LLVM, so I will need to first make sure that it also appears on the >>>> current one. >>>> >>>> The use case that I have in mind is to be able to uniquely identify >>>> instruction in the bit code. >>>> For example let¹s say we have an ³add² instruction in some function >>>> and I >>>> want to know that this is the same >>>> instruction in two separate runs. If the function is put in some >>>> different >>>> place as a result of inserting function and linking in the second run, >>>> how would I identify that instruction? It seems to me that cannot rely >>>> on >>>> the offset of the instruction within the binary and I cannot rely on >>>> the >>>> instruction count. >> Have you considered trying either metadata or using an intrinsic >> function as a marker for the interesting instruction? Depending on your >> use case, either might work. (f.y.i. I believe Metadata has changed >> radically since earlier versions.) >>>> The problem in my case was that for the same source code base, I was >>>> getting different resulting LLVM IR when doing the same >>>> sequence of getOrInsertFunction and linking with other bit code >>>> modules on >>>> each of runs. >>>> >>>> Thank you, >>>> Tomek >>>> >>>> On 29/05/2014 19:34, "Philip Reames" <listmail at philipreames.com> wrote: >>>> >>>>> On 05/29/2014 11:06 AM, Tim Northover wrote: >>>>>> Hi Tomek, >>>>>> >>>>>>> I¹ve got a question about Module::getOrInsertFunction(). >>>>>>> I got an impression that it is not deterministic where exactly in >>>>>>> the >>>>>>> bit >>>>>>> code module the new function will be inserted. >>>>>> Looking at the code (not exhaustively), it seems a new function will >>>>>> always be added to the end of a module. >>>>>> >>>>>> Documenting that probably wouldn't be a terrible idea, but it >>>>>> shouldn't affect anything except the human-readability of LLVM IR. >>>>>> Are >>>>>> you trying to do something where it is actually causing problems? >>>>>> >>>>>> Cheers. >>>>>> >>>>>> Tim. >>>>> I would argue in favor of leaving this explicitly undocumented. I >>>>> don't >>>>> see the use case in knowing where in a module it got added, and it >>>>> restricts future implementations in ways we can't predict. Documenting >>>>> that it must be deterministic is fine. Documenting where it decides >>>>> to >>>>> place it is not. >>>>> >>>>> Tomek, could you spell out why you need the position? Maybe there's >>>>> another option here. >>>>> >>>>> Philip >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On 4 June 2014 10:32, Kuchta, Tomasz <t.kuchta12 at imperial.ac.uk> wrote:> Hi Philip, > > Thank you very much for your comments. > I think I’ve discovered a root cause. The problem was in linking bit code > archive files with the module. > At some point, std::set<Module*> is used and iterated over.If there is a std::set<Module*> this sounds like the old linking code (Linker::LinkInFile). That code was removed in LLVM3.3 and it is no longer possible to link archives of bitcode modules directly using the LLVM API. I implemented a hacky replacement[1] in upstream KLEE. So if you upgrade you might find this works fine Tomek. However I fundamentally believe KLEE's approach is wrong here because I think linking and most optimisations should be done outside of KLEE but I'm not really interested in fixing this right now. [1] https://github.com/klee/klee/blob/master/lib/Module/ModuleUtil.cpp#L345 Thanks, -- Dan Liew PhD Student - Imperial College London
Hi Philip, Dan, Thank you very much for you comments. The exact place was: Archive::findModulesDefiningSymbols() function, that is called from Linker::LinkInArchive. I am using LLVM version 2.9. I couldn¹t find either of these two functions in LLVM3.4, but as Dan suggests, this functionality was removed in 3.3, so that should be correct now. Thanks! Tomek On 05/06/2014 00:20, "Dan Liew" <dan at su-root.co.uk> wrote:>On 4 June 2014 10:32, Kuchta, Tomasz <t.kuchta12 at imperial.ac.uk> wrote: >> Hi Philip, >> >> Thank you very much for your comments. >> I think I¹ve discovered a root cause. The problem was in linking bit >>code >> archive files with the module. >> At some point, std::set<Module*> is used and iterated over. > >If there is a std::set<Module*> this sounds like the old linking code >(Linker::LinkInFile). That code was removed in LLVM3.3 and it is no >longer possible to link archives of bitcode modules directly using the >LLVM API. > >I implemented a hacky replacement[1] in upstream KLEE. So if you >upgrade you might find this works fine Tomek. > >However I fundamentally believe KLEE's approach is wrong here because >I think linking and most optimisations should be done outside of KLEE >but I'm not really interested in fixing this right now. > > >[1] >https://github.com/klee/klee/blob/master/lib/Module/ModuleUtil.cpp#L345 > >Thanks, >-- >Dan Liew >PhD Student - Imperial College London