<html><head><meta http-equiv="Content-Type" content="text/html charset=windows-1252"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;">On Jul 2, 2013, at 2:35 PM, Ghassan Shobaki <<a href="mailto:ghassan_shobaki@yahoo.com">ghassan_shobaki@yahoo.com</a>> wrote:<br><div><br><blockquote type="cite"><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto;">Thank you for the answers! We are currently trying to test the MI scheduler. We are using LLVM 3.3 with Dragon Egg 3.3 on an x86-64 machine. So far, we have run one SPEC CPU2006 test with the MI scheduler enabled using the option -fplugin-arg-dragonegg-llvm-option='-enable-misched:true' with -O3. This enables the machine scheduler in addition to the SD scheduler. We have verified this by adding print messages to the source code of both schedulers. In terms of correctness, enabling the MI scheduler did not cause any failure. However, in terms of performance, we have seen a mix of small positive and negative differences with the geometric mean difference being near zero. The maximum improvement that we have seen is 3% on the Gromacs benchmark. Is this consistent with your test results?<br></div></div></blockquote><div><br></div><div>I haven’t benchmarked fortran. On x86-64, I regularly see wild swings in performance, 10-20% for small codegen changes (small benchmarks with a primary hot loop). This is not a natural consequence of scheduling, unless spill code changed in the hot loop (rare on x86-64). Quite often, a somewhat random change in copy coalescing results in different register allocation and code layout. The results are chaotic and very platform (linker) and microarchitecture specific. Large benchmarks are immune to wild swings, but the small changes you see could just be the accumulation of chaotic behavior of individual loops. It’s hard for me to draw conclusions without looking at hardware counters and isolating the data to individual loops.</div><div><br></div><div>The MI scheduler’s generic heuristics are much more about avoiding worst-case scheduling in pathological situations (very large unrolled loops) than it is about tuning for a microarchitecture. People who want to do that may want to plugin their own scheduling strategy. The precise machine model and register pressure information is all there now.</div><div><br></div><div>The broadest statement I can make is that we should not unnecessarily spill within loops (with rare exceptions). If you see that, file a bug. I know there are still situations that we don’t handle well, but haven’t had a compelling enough reason to add the complexity to the generic heuristics. If good test cases come in, then I’ll do that.</div><br><blockquote type="cite"><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto;">We have then tried to run a test in which the MI scheduler is enabled but the SD scheduler is disabled (or neutralized) by adding the option: -fplugin-arg-dragonegg-llvm-option='-pre-RA-sched:source' to the flags that we have used in the first test. However, this did not work; we got the following error message:<br><br>GCC_4.6.4_DIR/install/bin/gcc -c -o lbm.o -DSPEC_CPU -DNDEBUG -O3 -march=core2 -mtune=core2 -fplugin='DRAGON_EGG_DIR/dragonegg.so' -fplugin-arg-dragonegg-llvm-option='-enable-misched:true' -fplugin-arg-dragonegg-llvm-option='-pre-RA-sched:source' -DSPEC_CPU_LP64 lbm.c<br>cc1: for the -pre-RA-sched option: may only occur zero or one times!<br>specmake: *** [lbm.o] Error 1<br><div><br><span></span></div><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span>What does this message mean?<span class="Apple-converted-space"> </span><br></span></div><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span>Is this a bug or we are doing something wrong?<span class="Apple-converted-space"> </span><br></span></div></div></div></blockquote><div dir="auto"><br></div>I’m not sure why the driver is telling you this. Maybe someone familiar with dragonegg can help?</div><div><br></div><div>You can always rebuild llvm with the enableMachineScheduler() hook implemented.</div><div><a rel="nofollow" target="_blank" href="http://article.gmane.org/gmane.comp.compilers.llvm.devel/63242/match=machinescheduler" style="font-family: 'times new roman', 'new york', times, serif; font-size: 12pt; background-color: rgb(255, 255, 255);">http://article.gmane.org/gmane.comp.compilers.llvm.devel/63242/match=machinescheduler</a></div><div><br></div><div>Then -enable-misched=true/false simply toggles MI Sched without changing anything else.</div><div><br></div><div><blockquote type="cite"><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto;"><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span>How can we test the MI scheduler by itself?<span class="Apple-converted-space"> </span><br></span></div><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span>Is it interesting to test 3.3 or there are interesting features that were added to the trunk after branching 3.3? In the latter case, we are willing to test the trunk.<br></span></div></div></div></blockquote><div><br></div><div>It doesn’t look like my June checkins made it into 3.3. If you’re enabling MI Sched, and actually evaluating performance of the default heuristics, then it’s best to use trunk.</div><div><br></div><div>-Andy</div><br><blockquote type="cite"><div style="font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: auto; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; widows: auto; word-spacing: 0px; -webkit-text-stroke-width: 0px;"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt; position: static; z-index: auto;"><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span><br></span></div><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><span>Thanks<br></span></div><div style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br></div><div class="yui_3_7_2_31_1372778022180_110" id="yiv8191019934yui_3_7_2_1_1372440933443_2094" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Ghassan Shobaki<br></div><div class="yui_3_7_2_31_1372778022180_111" id="yiv8191019934yui_3_7_2_1_1372440933443_2093" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Assistant Professor<span class="Apple-converted-space"> </span><br></div><div class="yui_3_7_2_31_1372778022180_112" id="yiv8191019934yui_3_7_2_1_1372440933443_2092" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Department of Computer Science<span class="Apple-converted-space"> </span><br></div><div class="yui_3_7_2_31_1372778022180_113" id="yiv8191019934yui_3_7_2_1_1372440933443_2091" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Princess Sumaya University for Technology<span class="Apple-converted-space"> </span><br></div><div class="yui_3_7_2_31_1372778022180_114" id="yiv8191019934yui_3_7_2_1_1372440933443_2090" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Amman, Jordan</div><div class="yui_3_7_2_31_1372778022180_115" id="yiv8191019934yui_3_7_2_1_1372440933443_2109" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br></div><div><br></div><div style="font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div style="font-family: 'times new roman', 'new york', times, serif; font-size: 12pt;"><div dir="ltr"><hr size="1"><font face="Arial" size="2"><b><span style="font-weight: bold;">From:</span></b><span class="Apple-converted-space"> </span>Andrew Trick <<a href="mailto:atrick@apple.com">atrick@apple.com</a>><br><b><span style="font-weight: bold;">To:</span></b><span class="Apple-converted-space"> </span>Ghassan Shobaki <<a href="mailto:ghassan_shobaki@yahoo.com">ghassan_shobaki@yahoo.com</a>><span class="Apple-converted-space"> </span><br><b><span style="font-weight: bold;">Cc:</span></b><span class="Apple-converted-space"> </span>"<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>><span class="Apple-converted-space"> </span><br><b><span style="font-weight: bold;">Sent:</span></b><span class="Apple-converted-space"> </span>Monday, July 1, 2013 8:10 PM<br><b><span style="font-weight: bold;">Subject:</span></b><span class="Apple-converted-space"> </span>Re: MI Scheduler vs SD Scheduler?<br></font></div><div class="y_msg_container"><br><div id="yiv8191019934"><div><br>Sent from my iPhone</div><div><br>On Jun 28, 2013, at 2:38 PM, Ghassan Shobaki <<a rel="nofollow" ymailto="mailto:ghassan_shobaki@yahoo.com" target="_blank" href="mailto:ghassan_shobaki@yahoo.com">ghassan_shobaki@yahoo.com</a>> wrote:<br><br></div><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_29_1372440933443_39">Hi,</div><div id="yiv8191019934yui_3_7_2_29_1372440933443_97"><br></div><div id="yiv8191019934yui_3_7_2_29_1372440933443_92" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">We are currently in the process of upgrading from LLVM 2.9 to LLVM 3.3. We are working on instruction scheduling (mainly for register pressure reduction). I have been following the llvmdev mailing list and have learned that a machine instruction (MI) scheduler has been implemented to replace (or work with?) the selection DAG (SD) scheduler. However, I could not find any document that describes the new MI scheduler and how it differs from and relates to the SD scheduler.</div></div></div></div></blockquote><div><br></div><div>MI is now the place to implement any heuristics for profitable scheduling. SD scheduler will be directly replaced by a new pass that orders the DAG as close as it can to IR order. We currently emulate this with -pre-RA-sched=source.</div><div>The only thing necessarily different about MI sched is that it runs after reg coalescing and before reg alloc, and maintains live interval analysis. As a result, register pressure tracking is more accurate. It also uses a new target interface for precise register pressure. </div><div>MI sched is intended to be a convenient place to implement target specific scheduling. There is a generic implementation that uses standard heuristics to reduce register pressure and balance latency and CPU resources. That is what you currently get when you enable MI sched for x86. </div><div>The generic heuristics are implemented as a priority function that makes a greedy choice over the ready instructions based on the current pressure and the resources and latency of the scheduled and unscheduled set of instructions.</div><div>An DAG subtree analysis also exists (ScheduleDFS), which can be used for register pressure avoidance. This isn't hooked up to the generic heuristics yet for lack of interesting test cases.</div><div><br></div><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_29_1372440933443_92" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">So, I would appreciate any pointer to a document (or a blog) that may help us understand the difference and the relation between the two schedulers and figure out how to deal with them. We are trying to answer the following questions:<span class="Apple-converted-space"> </span><br id="yiv8191019934yui_3_7_2_29_1372440933443_555"></div><div id="yiv8191019934yui_3_7_2_29_1372440933443_552" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br>- A comment at the top of the file ScheduleDAGInstrs says that this file implements re-scheduling of machine instructions. So, what does re-scheduling mean?</div></div></div></div></blockquote><div><br></div><span>Rescheduling just means optional scheduling. That's really what the comment should say. It's important to know that MI sched can be skipped for faster compilation. </span><div><span><br></span><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_29_1372440933443_552" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Does it mean that the real scheduling algorithms (such as reg pressure reduction) are currently implemented in the SD scheduler, while the MI scheduler does some kind of complementary work (fine tuning) at a lower level representation of the code?<span class="Apple-converted-space"> </span><br>And what's the future plan? Is it to move the real scheduling algorithms into the MI scheduler and get rid of the SD scheduler? Will that happen in 3.4 or later?<br></div></div></div></div></blockquote><div><br></div>I would like to get rid of the SD scheduler so we can reduce compile time by streamline the scheduling data structures and interfaces. There may be some objection to doing that in 3.4 if projects haven't been able to migrate. It will be deprecated though. </div><div><br><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_29_1372440933443_552" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br id="yiv8191019934yui_3_7_2_29_1372440933443_559"></div><div id="yiv8191019934yui_3_7_2_29_1372440933443_556" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">- Based on our initial investigation of the default behavior at -O3 on x86-64, it appears that the SD scheduler is called while the MI scheduler is not. That's consistent with the above interpretation of re-scheduling, but I'd appreciate any advice on what we should do at this point. Should we integrate our work (an alternate register pressure reduction scheduler) into the SD scheduler or the MI scheduler?<br></div></div></div></div></blockquote><div><br></div><div>Please refer to my recent messages on llvmdev regarding enabling MI scheduling by default on x86. </div><div><a rel="nofollow" target="_blank" href="http://article.gmane.org/gmane.comp.compilers.llvm.devel/63242/match=machinescheduler">http://article.gmane.org/gmane.comp.compilers.llvm.devel/63242/match=machinescheduler</a></div><div><br></div><div>I suggest integrating with the MachineScheduler pass.</div><div>There are many places to plug in. MachineSchedRegistry provides the hook. At that point you can define your own ScheduleDAGInstrs or ScheduleDAGMI subclass. People who only want to define new heuristics should reuse ScheduleDAGMI directly and only define their own MachineSchedStrategy.</div><div><br></div><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_29_1372440933443_556" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2088" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">- Our SPEC testing on x86-64 has shown a significant performance improvement of LLVM 3.3 relative to LLVM 2.9 (about 5% in geomean on INT2006 and 15% in geomean on FP2006), but our spill code measurements have shown that LLVM 3.3 generates significantly more spill code on most benchmarks. We will be doing more investigation on this, but are there any known facts that explain this behavior? Is this caused by a known regression in scheduling and/or allocation (which I doubt) or by the implementation (or enabling) of some new optimization(s) that naturally increase(s) register pressure?</div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2098" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br></div></div></div></div></blockquote>There is not a particular known regression. It's not surprising that optimizations increase pressure.</div><div><br></div><div>Andy</div><div><br><blockquote type="cite"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934"><div style="background-color: rgb(255, 255, 255); font-family: arial, helvetica, sans-serif; font-size: 12pt;"><div id="yiv8191019934yui_3_7_2_1_1372440933443_2097" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Thank you in advance!</div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2096" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;"><br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2094" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Ghassan Shobaki<br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2093" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Assistant Professor<span class="Apple-converted-space"> </span><br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2092" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Department of Computer Science<span class="Apple-converted-space"> </span><br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2091" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Princess Sumaya University for Technology<span class="Apple-converted-space"> </span><br></div><div id="yiv8191019934yui_3_7_2_1_1372440933443_2090" style="font-size: 16px; font-family: arial, helvetica, sans-serif; background-color: transparent; font-style: normal;">Amman, Jordan</div></div></div></div></blockquote></div></div></div></div></div></div></div></blockquote></div><br></body></html>