<div dir="rtl"><div dir="ltr">Hi Jim,</div><div dir="ltr"><br></div><div dir="ltr">Clearly searching for name should not be linear in modules but with a map of some kind.</div><div dir="ltr"><br></div><div dir="ltr">After compilation to IR each module has a StringMap symbol table.</div>
<div dir="ltr">After compiling to MC and loading the object file, the dynamic linker has a StringMap symbol table for all loaded modules.</div><div dir="ltr"><br></div><div dir="ltr">In the usual use case you'll load module(s) into MCJIT and then compile / link them and all is well, no linear search.</div>
<div dir="ltr"><br></div><div dir="ltr">The linear-search use case happens when the MCJIT sort-of lazy compiles: it gets a list of many, possibly 1000s of function-modules (one function per module) but had not bothered to compile them to MC and load them since they were not used yet. It will do so only when needed. In this case, if asked to find a function it will (currently) linear search for it module by module.</div>
<div dir="ltr"><br></div><div dir="ltr">The solution would be to construct a StringMap for the later use-case, however in the first use-case it's a wasted effort since all modules are going to be loaded anyhow and the dynamic linker will build its own map.</div>
<div dir="ltr"><br></div><div dir="ltr">MCJIT doesn't know the use-case and so one solution would be to lazy build the map only when first asked to search, assuming more searches will follow. This may be wrong assumption so maybe the better solution is to have a flag or optional function to build this map at the programmer decision who does know the use-case.</div>
<div dir="ltr"><br></div><div dir="ltr">One possible optimization would be for the MCJIT not to build from scratch but merge the modules stringmaps into one large virtual stringmap - I don't know if it's possible with this data structure or cheaper than reconstructing. This data structure would also have to erasing the modules which are compiled.</div>
<div dir="ltr"><br></div><div dir="ltr">Yaron<br></div><div dir="ltr"><br></div>
<div class="gmail_extra"><br><br><div class="gmail_quote"><div dir="ltr">2013/10/22 Jim Grosbach <span dir="ltr"><<a href="mailto:grosbach@apple.com" target="_blank">grosbach@apple.com</a>></span></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div style="word-wrap:break-word">I don’t follow. Why are we looking at the module at all? That query should work even (especially) after the Module is deleted. We should be able to have a local symbol table that’s a DenseMap or something similar to resolve from names to target addresses. That map would be updated as part of the compilation when the object’s symbol table gets read.<span><font color="#888888"><div>
<br></div></font></span><div><span><font color="#888888">-Jim</font></span><div><div><br><div><br><div><div>On Oct 21, 2013, at 4:55 PM, Kaylor, Andrew <<a href="mailto:andrew.kaylor@intel.com" target="_blank">andrew.kaylor@intel.com</a>> wrote:</div>
<br><blockquote type="cite"><div lang="EN-US" link="blue" vlink="purple" style="font-family:Helvetica;font-size:12px;font-style:normal;font-variant:normal;font-weight:normal;letter-spacing:normal;line-height:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px">
<div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">There’s probably a lot that we could do, but I can’t think of anything easy.<u></u><u></u></span></div>
<div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">Basically every time we need to look up a symbol by name we’re going to each module and saying “Do you have this symbol?” It would likely be much better if we grabbed the function names from the module and did the search ourselves so that we could keep some information about the things that didn’t match and optimize the next search.<u></u><u></u></span></div>
<div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">-Andy<u></u><u></u></span></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span></div>
<div><div style="border-style:solid none none;border-top-color:rgb(181,196,223);border-top-width:1pt;padding:3pt 0in 0in"><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><b><span style="font-size:10pt;font-family:Tahoma,sans-serif">From:</span></b><span style="font-size:10pt;font-family:Tahoma,sans-serif"><span> </span>Jim Grosbach [<a href="mailto:grosbach@apple.com" target="_blank">mailto:grosbach@apple.com</a>]<span> </span><br>
<b>Sent:</b><span> </span>Monday, October 21, 2013 4:39 PM<br><b>To:</b><span> </span>Kaylor, Andrew; Yaron Keren<br><b>Cc:</b><span> </span><<a href="mailto:llvmdev@cs.uiuc.edu" target="_blank">llvmdev@cs.uiuc.edu</a>><br>
<b>Subject:</b><span> </span>Re: [LLVMdev] An enhancement for MCJIT::getFunctionAddress<u></u><u></u></span></div></div></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<u></u> <u></u></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">The search is linear? If that’s really true, we should fix that.<u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<u></u> <u></u></div><div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">On Oct 21, 2013, at 10:14 AM, Kaylor, Andrew <<a href="mailto:andrew.kaylor@intel.com" style="color:purple;text-decoration:underline" target="_blank">andrew.kaylor@intel.com</a>> wrote:<u></u><u></u></div>
</div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><br><br><u></u><u></u></div><div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I should have read this before sending my previous reply. :-)</span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">I’m not a big fan of default parameters, but some form of what you are suggesting may be useful. See my other comments on this topic in the other reply.</span><u></u><u></u></div>
</div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></div></div>
<div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)">-Andy</span><u></u><u></u></div></div>
<div>
<div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:11pt;font-family:Calibri,sans-serif;color:rgb(31,73,125)"> </span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><b><span style="font-size:10pt;font-family:Tahoma,sans-serif">From:</span></b><span><span style="font-size:10pt;font-family:Tahoma,sans-serif"> </span></span><span style="font-size:10pt;font-family:Tahoma,sans-serif">Yaron Keren [<a href="mailto:yaron.keren@gmail.com" style="color:purple;text-decoration:underline" target="_blank">mailto:yaron.keren@gmail.com</a>]<span> </span><br>
<b>Sent:</b><span> </span>Saturday, October 19, 2013 3:17 PM<br><b>To:</b><span> </span>Kaylor, Andrew; <<a href="mailto:llvmdev@cs.uiuc.edu" style="color:purple;text-decoration:underline" target="_blank">llvmdev@cs.uiuc.edu</a>><br>
<b>Subject:</b><span> </span>An enhancement for MCJIT::getFunctionAddress</span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div>
</div><div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">In MCJIT, the old JIT functions are deprecated in favor of getFunctionAddress. <u></u><u></u></div></div><div>
<div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">Code like:<u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<u></u><u></u></div></div><div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-family:'Courier New'"> llvm::Function *F = M->getFunction(FuncName);</span><u></u><u></u></div>
</div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"><span style="font-family:'Courier New'"> void *FN = EE->getPointerToFunction(F);</span><u></u><u></u></div>
</div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
should be rewritten as<u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-family:'Courier New'"> uint64_t FN = EE->getFunctionAddress(FuncName);</span><u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">While functionally identical, in case the correct module is known the new version will be much slower, linear with the number of added (but not loaded) modules, since it has to (possibly) search for the correct module while old code directly searches the correct module.<u></u><u></u></div>
</div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
To solve the issue, getFunctionAddress could get an optional Module "hint" (=NULL by default) which - if provided - will make getSymbolAddress skip calling findModuleForSymbol (a very slow operation) and instead directly use the Module provided.<u></u><u></u></div>
</div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
Yaron<u></u><u></u></div></div><div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif"> <u></u><u></u></div></div></div></div><div style="margin:0in 0in 0.0001pt;font-size:12pt;font-family:'Times New Roman',serif">
<span style="font-size:9pt;font-family:Helvetica,sans-serif">_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu" style="color:purple;text-decoration:underline" target="_blank">LLVMdev@cs.uiuc.edu</a><span> </span> <a href="http://llvm.cs.uiuc.edu/" style="color:purple;text-decoration:underline" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="color:purple;text-decoration:underline" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a></span></div></div></div></div></div></div></blockquote>
</div><br></div></div></div></div></div></blockquote></div><br></div></div>