<div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial">I have found that the extremely expensive compile-time overhead comes from the string buffer operation for "INVALID" MACRO in the polly-detect pass.<br>Attached is a hack patch file that simply remove the string buffer operation. This patch file can significantly reduce compile-time overhead when compiling big source code. For example, for oggen*8.ll, the compile time is reduced from 40.5261 ( 51.2%) to 5.8813s (15.9%) with this patch file.<br><br>However, this patch file does not solve this problem. It only shows the reason why polly-detect pass leads to significant compile-time overhead.<br><br>Best wishes,<br>Star Tan. <br><div></div><div id="divNeteaseMailCard"></div><br>At 2013-07-14 17:26:19,"Star Tan" <<a href="mailto:tanmx_star@yeah.net">tanmx_star@yeah.net</a>> wrote:<br> <blockquote id="isReply!
Content" style="PADDING-LEFT: 1ex; MARGIN: 0px 0px 0px 0.8ex; BORDER-LEFT: #ccc 1px solid"><div style="line-height:1.7;color:#000000;font-size:14px;font-family:arial"><br><pre>At 2013-07-14 13:20:42,"Tobias Grosser" <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>> wrote:
>On 07/13/2013 09:18 PM, Star Tan wrote:
>>
>>
>> At 2013-07-14 02:30:07,"Tobias Grosser" <<a href="mailto:tobias@grosser.es">tobias@grosser.es</a>> wrote:
>>> On 07/13/2013 10:13 AM, Star Tan wrote:
>>>> Hi Tobias,
>>>
>>> Hi Star,
>[...]
>>> Before we write a patch, we should do some profiling to understand where
>>> the overhead comes from. I propose you generate oggenc*16 or even
>>> oggen*32 to ensure we get to about 90% Polly-Detect overhead.
>>>
>>> I would then run Polly under linux 'perf'. Using 'perf record polly-opt
>>> ...' and then 'perf report'. If we are lucky, this points us exactly to
>>> the function we spend all the time in.
>>>
>>> Cheers,
>>> Tobias
>>
>> Thanks for your very useful suggestion.
>> I have profiled the oggenc*16 and oggenc*32 and the results are listed as follows:
>>
>> oggenc*16: polly-detect compile-time percentage is 71.3%. The top five functions reported by perf are:
>> 48.97% opt opt [.] llvm::TypeFinder::run(llvm::Module const&, bool)
>> 7.43% opt opt [.] llvm::TypeFinder::incorporateType(llvm::Type*)
>> 7.36% opt opt [.] llvm::TypeFinder::incorporateValue(llvm::Value const*)
>> 4.04% opt libc-2.17.so [.] 0x0000000000138bea
>> 2.06% opt [kernel.kallsyms] [k] 0xffffffff81043e6a
>>
>> oggenc*32: polly-detect compile-time percentage is 82.9%. The top five functions reported by perf are:
>> 57.44% opt opt [.] llvm::TypeFinder::run(llvm::Module const&, bool)
>> 11.51% opt opt [.] llvm::TypeFinder::incorporateType(llvm::Type*)
>> 7.54% opt opt [.] llvm::TypeFinder::incorporateValue(llvm::Value const*)
>> 2.66% opt libc-2.17.so [.] 0x0000000000138c02
>> 2.26% opt opt [.] llvm::SlotTracker::processModule()
>>
>> It is surprise that all compile-time for TypeFinder is added into the compile-time for Polly-detect, but I cannot find the any call instructions to TypeFinder in Polly-detect.
>
>Yes, this does not seem very conclusive. We probably need a call graph
>to see where those are called.
>
>Did you try running 'perf record' with the '-g' option? This should give
>you callgraph information, that should be very helpful to track down the
>callers in Polly. Also, if you prefer a graphical view of the
>results, you may want to have a look at Gprof2Dot [1]. Finally, if this
>all does not work, just running Polly in gdb and randomly breaking a
>couple of times (manual sampling), may possibly hint you to the right place.
><br><br>I also tried perf with -g, but it report nothing useful. the result of perf -g is:<br>- 48.70% opt opt [.] llvm::TypeFinder::run(llvm::Module const&, bool) `<br> - llvm::TypeFinder::run(llvm::Module const&, bool) <br> + 43.34% 0 <br> - 1.78% 0x480031<br> + llvm::LoadInst::~LoadInst() <br> - 1.41% 0x460031<br> + llvm::LoadInst::~LoadInst()<br> - 1.01% 0x18<br> llvm::BranchInst::~BranchInst() <br> 0x8348007d97fa3d8d<br> - 0.87% 0x233<br> + llvm::GetElementPtrInst::~GetElementPtrInst() <br> - 0.57% 0x39<br> + llvm::SExtInst::~SExtInst() <br> - 0.54% 0x460032<br> + llvm::StoreInst::~StoreInst()<br><br><br>GDB is a useful tool! Thanks for Sebastian's advice!<br><br> By setting a break point on llvm::TypeFinder::run(llvm::Module const&, bool), I find most of calling cases are issued from!
the following two callsites:<br>0xb7c1c5d2 in polly::ScopDetection::isValidMemoryAccess(llvm::Instruction&, polly::ScopDetection::DetectionContext&) const ()<br>0xb7c1d754 in polly::ScopDetection::isValidInstruction(llvm::Instruction&, polly::ScopDetection::DetectionContext&) const ()<br> <br>The detailed backtrace of "isValidMemoryAccess" is:<br> #0 0x0907b780 in llvm::TypeFinder::run(llvm::Module const&, bool) ()<br>#1 0x08f76ebe in llvm::TypePrinting::incorporateTypes(llvm::Module const&) ()<br>#2 0x08f76fc9 in llvm::AssemblyWriter::init() ()<br>#3 0x08f77176 in llvm::AssemblyWriter::AssemblyWriter(llvm::formatted_raw_ostream&, llvm::SlotTracker&, llvm::Module const*, llvm::AssemblyAnnotationWriter*) ()<br>#4 0x08f79d1a in llvm::Value::print(llvm::raw_ostream&, llvm::AssemblyAnnotationWriter*) const ()<br>#5 0xb7c1d044 in polly::ScopDetection::isValidInstruction(llvm::Instruction&, polly::ScopDetection::DetectionContex!
t&) const ()<br> from /home/star/llvm/llvm_build/tools/polly/Rel
ease+Asserts/lib/LLVMPolly.so<br>#6 0xb7c1ea75 in polly::ScopDetection::allBlocksValid(polly::ScopDetection::DetectionContext&) const ()<br> from /home/star/llvm/llvm_build/tools/polly/Release+Asserts/lib/LLVMPolly.so<br>#7 0xb7c1f4aa in polly::ScopDetection::isValidRegion(polly::ScopDetection::DetectionContext&) const ()<br> from /home/star/llvm/llvm_build/tools/polly/Release+Asserts/lib/LLVMPolly.so<br>#8 0xb7c1fd16 in polly::ScopDetection::findScops(llvm::Region&) ()<br> from /home/star/llvm/llvm_build/tools/polly/Release+Asserts/lib/LLVMPolly.so<br>#9 0xb7c1fd81 in polly::ScopDetection::findScops(llvm::Region&) ()<br> from /home/star/llvm/llvm_build/tools/polly/Release+Asserts/lib/LLVMPolly.so<br>#10 0xb7c206f7 in polly::ScopDetection::runOnFunction(llvm::Function&) ()<br> from /home/star/llvm/llvm_build/tools/polly/Release+Asserts/lib/LLVMPolly.so<br>#11 0x09065fdd in llvm::FPPassManager::runOnFunction(llvm::Function&) ()<br>#12 0x0!
9067e2b in llvm::FunctionPassManagerImpl::run(llvm::Function&) ()<br>#13 0x09067f6d in llvm::FunctionPassManager::run(llvm::Function&) ()<br>#14 0x081e6040 in main ()<br><br><br> >Also, can you upload the .ll file somewhere, such that I can access it?
>(Please do not attach it to the email)
<br>I have attached the source code of oggenc.c and oggen.ll in the bug r16624:<br>http://llvm.org/bugs/show_bug.cgi?id=16624<br><br>Best wishes,<br>Star Tan<br><br><br><br></pre></div></blockquote></div></div>