Hello LLVM developers,<br><div class="gmail_quote"><br>I have a few questions regarding the passes that are run after instruction selection and before register allocation. I am writing a scheduling pass (modulo scheduling). Before I ask my questions, I will first try to explain the approach I am taking.<br>
<br>- Currently, I am running the passes in the following order. <br><br>(-debug-pass=Structure output)<br> Remove unreachable machine basic blocks<br>
Live Variable Analysis<br> Eliminate PHI nodes for register allocation<br> Two-Address instruction pass<br> Process Implicit Definitions.<br> MachineDominator Tree Construction<br> Machine Natural Loop Construction<br>
Modulo scheduing <== modulo scheduling pass inserted here<br> Slot index numbering<br> Live Interval Analysis<br> MachineDominator Tree Construction<br> Machine Natural Loop Construction<br> Simple Register Coalescing<br>
Calculate spill weights<br> Live Stack Slot Analysis<br> Virtual Register Map<br> Linear Scan Register Allocator<br><br>- The scheduling pass can schedule only single basic block loops. It only looks for loops that have 1 or 2 basic blocks (the number of BBs depends on whether or not the loop header and the latch are the same MBB). Basic blocks outside the loop remain unchanged except for the ones that preceed and succeed the loop. Also, basic blocks for prologue and epilogue are added to the CFG.<br>
<br>- Prior to scheduling, redundant moves that were generated by the phi-elimination pass and two-address instruction pass are removed and the basic block in the loop is simplified as much as possible. For example, the header BB of a loop is transformed as follows (note that information in LiveVariables is not updated, so there may exist inconsistencies): <br>
<br>BB2: preheader, BB3: header & latch, BB4: exit<br><br>(before transformation)<br>BB#2: derived from LLVM BB %entry.bb_crit_edge<br>
Predecessors according to CFG: BB#0<br> %reg1025<def> = MOVr %reg1034<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1024<def> = MOVr %reg1033<kill>, pred:14, pred:%reg0, opt:%reg0<br>
%reg1036<def> = MOVi 0, pred:14, pred:%reg0, opt:%reg0<br> %reg1038<def> = MOVr %reg1024<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1039<def> = MOVr %reg1025<kill>, pred:14, pred:%reg0, opt:%reg0<br>
%reg1040<def> = MOVr %reg1036<kill>, pred:14, pred:%reg0, opt:%reg0<br> Successors according to CFG: BB#3<br><br>BB#3: derived from LLVM BB %bb<br> Predecessors according to CFG: BB#2 BB#3<br> %reg1026<def> = MOVr %reg1038<kill>, pred:14, pred:%reg0, opt:%reg0<br>
%reg1027<def> = MOVr %reg1039<kill>, pred:14, pred:%reg0, opt:%reg0<br>
%reg1028<def> = MOVr %reg1040<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1030<def> = MOVr %reg1027<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1037<def>, %reg1030<def> = LDR_POST %reg1030, %reg0, 4, pred:14, pred:%reg0<br>
%reg1029<def> = ADDrr %reg1037<kill>, %reg1028, pred:14, pred:%reg0, opt:%reg0<br> %reg1031<def> = SUBri %reg1026<kill>, 1, pred:14, pred:%reg0, opt:%reg0<br> CMPzri %reg1031, 0, pred:14, pred:%reg0, %CPSR<imp-def><br>
%reg1038<def> = MOVr %reg1031<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1039<def> = MOVr %reg1030<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1040<def> = MOVr %reg1029<kill>, pred:14, pred:%reg0, opt:%reg0<br>
Bcc <BB#3>, pred:1, pred:%CPSR<kill><br> Successors according to CFG: BB#4 BB#3<br><br>BB#4: derived from LLVM BB %bb.bb2_crit_edge<br> Predecessors according to CFG: BB#3<br> %reg1041<def> = MOVr %reg1028<kill>, pred:14, pred:%reg0, opt:%reg0<br>
Successors according to CFG: BB#5<br><br>(after transformation)<br>BB#3: <br> %reg1028<def> = MOVr %reg1040<kill>, pred:14, pred:%reg0, opt:%reg0<br> %reg1037<def>, %reg1039<def> = LDR_POST %reg1039, %reg0, 4, pred:14, pred:%reg0<br>
%reg1040<def> = ADDrr %reg1037<kill>, %reg1028, pred:14, pred:%reg0, opt:%reg0<br> %reg1038<def> = SUBri %reg1038<kill>, 1, pred:14, pred:%reg0, opt:%reg0<br> CMPzri %reg1038, 0, pred:14, pred:%reg0, %CPSR<imp-def><br>
Bcc <BB#3>, pred:1, pred:%CPSR<kill><br>$138 = void<br><br><br>Here are my questions:<br>1. Which passes after the scheduling pass can be run without modification? I suspect LiveIntervalAnalysis will not be able to handle the transformed BB judging from the way it handles two-address code and phijoins. Will the other passes need to be changed as well?<br>
<br>
2. Is the scheduling pass inserted in the right position? Currently the scheduling pass is run right before Slot index numbering and LiveInterval analysis, since I thought it would required a lot of work to fix the indexes and intervals if the scheduling pass were run after these two passes. <br>
<br>3. If the scheduling pass does local register allocation too, is there a way to tell the register allocation pass that is run later not to touch it? <br><br>Any advice, comments and suggestions are appreciated.<br><br>
Thank you. <br><br>
</div><br>