• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- LoopRotation.cpp - Loop Rotation Pass ------------------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file implements Loop Rotation Pass.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #define DEBUG_TYPE "loop-rotate"
15 #include "llvm/Transforms/Scalar.h"
16 #include "llvm/Function.h"
17 #include "llvm/IntrinsicInst.h"
18 #include "llvm/Analysis/CodeMetrics.h"
19 #include "llvm/Analysis/LoopPass.h"
20 #include "llvm/Analysis/InstructionSimplify.h"
21 #include "llvm/Analysis/ScalarEvolution.h"
22 #include "llvm/Transforms/Utils/Local.h"
23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
24 #include "llvm/Transforms/Utils/SSAUpdater.h"
25 #include "llvm/Transforms/Utils/ValueMapper.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/ADT/Statistic.h"
28 using namespace llvm;
29 
30 #define MAX_HEADER_SIZE 16
31 
32 STATISTIC(NumRotated, "Number of loops rotated");
33 namespace {
34 
35   class LoopRotate : public LoopPass {
36   public:
37     static char ID; // Pass ID, replacement for typeid
LoopRotate()38     LoopRotate() : LoopPass(ID) {
39       initializeLoopRotatePass(*PassRegistry::getPassRegistry());
40     }
41 
42     // LCSSA form makes instruction renaming easier.
getAnalysisUsage(AnalysisUsage & AU) const43     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
44       AU.addPreserved<DominatorTree>();
45       AU.addRequired<LoopInfo>();
46       AU.addPreserved<LoopInfo>();
47       AU.addRequiredID(LoopSimplifyID);
48       AU.addPreservedID(LoopSimplifyID);
49       AU.addRequiredID(LCSSAID);
50       AU.addPreservedID(LCSSAID);
51       AU.addPreserved<ScalarEvolution>();
52     }
53 
54     bool runOnLoop(Loop *L, LPPassManager &LPM);
55     bool rotateLoop(Loop *L);
56 
57   private:
58     LoopInfo *LI;
59   };
60 }
61 
62 char LoopRotate::ID = 0;
63 INITIALIZE_PASS_BEGIN(LoopRotate, "loop-rotate", "Rotate Loops", false, false)
INITIALIZE_PASS_DEPENDENCY(LoopInfo)64 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
65 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
66 INITIALIZE_PASS_DEPENDENCY(LCSSA)
67 INITIALIZE_PASS_END(LoopRotate, "loop-rotate", "Rotate Loops", false, false)
68 
69 Pass *llvm::createLoopRotatePass() { return new LoopRotate(); }
70 
71 /// Rotate Loop L as many times as possible. Return true if
72 /// the loop is rotated at least once.
runOnLoop(Loop * L,LPPassManager & LPM)73 bool LoopRotate::runOnLoop(Loop *L, LPPassManager &LPM) {
74   LI = &getAnalysis<LoopInfo>();
75 
76   // One loop can be rotated multiple times.
77   bool MadeChange = false;
78   while (rotateLoop(L))
79     MadeChange = true;
80 
81   return MadeChange;
82 }
83 
84 /// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
85 /// old header into the preheader.  If there were uses of the values produced by
86 /// these instruction that were outside of the loop, we have to insert PHI nodes
87 /// to merge the two values.  Do this now.
RewriteUsesOfClonedInstructions(BasicBlock * OrigHeader,BasicBlock * OrigPreheader,ValueToValueMapTy & ValueMap)88 static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
89                                             BasicBlock *OrigPreheader,
90                                             ValueToValueMapTy &ValueMap) {
91   // Remove PHI node entries that are no longer live.
92   BasicBlock::iterator I, E = OrigHeader->end();
93   for (I = OrigHeader->begin(); PHINode *PN = dyn_cast<PHINode>(I); ++I)
94     PN->removeIncomingValue(PN->getBasicBlockIndex(OrigPreheader));
95 
96   // Now fix up users of the instructions in OrigHeader, inserting PHI nodes
97   // as necessary.
98   SSAUpdater SSA;
99   for (I = OrigHeader->begin(); I != E; ++I) {
100     Value *OrigHeaderVal = I;
101 
102     // If there are no uses of the value (e.g. because it returns void), there
103     // is nothing to rewrite.
104     if (OrigHeaderVal->use_empty())
105       continue;
106 
107     Value *OrigPreHeaderVal = ValueMap[OrigHeaderVal];
108 
109     // The value now exits in two versions: the initial value in the preheader
110     // and the loop "next" value in the original header.
111     SSA.Initialize(OrigHeaderVal->getType(), OrigHeaderVal->getName());
112     SSA.AddAvailableValue(OrigHeader, OrigHeaderVal);
113     SSA.AddAvailableValue(OrigPreheader, OrigPreHeaderVal);
114 
115     // Visit each use of the OrigHeader instruction.
116     for (Value::use_iterator UI = OrigHeaderVal->use_begin(),
117          UE = OrigHeaderVal->use_end(); UI != UE; ) {
118       // Grab the use before incrementing the iterator.
119       Use &U = UI.getUse();
120 
121       // Increment the iterator before removing the use from the list.
122       ++UI;
123 
124       // SSAUpdater can't handle a non-PHI use in the same block as an
125       // earlier def. We can easily handle those cases manually.
126       Instruction *UserInst = cast<Instruction>(U.getUser());
127       if (!isa<PHINode>(UserInst)) {
128         BasicBlock *UserBB = UserInst->getParent();
129 
130         // The original users in the OrigHeader are already using the
131         // original definitions.
132         if (UserBB == OrigHeader)
133           continue;
134 
135         // Users in the OrigPreHeader need to use the value to which the
136         // original definitions are mapped.
137         if (UserBB == OrigPreheader) {
138           U = OrigPreHeaderVal;
139           continue;
140         }
141       }
142 
143       // Anything else can be handled by SSAUpdater.
144       SSA.RewriteUse(U);
145     }
146   }
147 }
148 
149 /// Rotate loop LP. Return true if the loop is rotated.
rotateLoop(Loop * L)150 bool LoopRotate::rotateLoop(Loop *L) {
151   // If the loop has only one block then there is not much to rotate.
152   if (L->getBlocks().size() == 1)
153     return false;
154 
155   BasicBlock *OrigHeader = L->getHeader();
156 
157   BranchInst *BI = dyn_cast<BranchInst>(OrigHeader->getTerminator());
158   if (BI == 0 || BI->isUnconditional())
159     return false;
160 
161   // If the loop header is not one of the loop exiting blocks then
162   // either this loop is already rotated or it is not
163   // suitable for loop rotation transformations.
164   if (!L->isLoopExiting(OrigHeader))
165     return false;
166 
167   // Updating PHInodes in loops with multiple exits adds complexity.
168   // Keep it simple, and restrict loop rotation to loops with one exit only.
169   // In future, lift this restriction and support for multiple exits if
170   // required.
171   SmallVector<BasicBlock*, 8> ExitBlocks;
172   L->getExitBlocks(ExitBlocks);
173   if (ExitBlocks.size() > 1)
174     return false;
175 
176   // Check size of original header and reject loop if it is very big.
177   {
178     CodeMetrics Metrics;
179     Metrics.analyzeBasicBlock(OrigHeader);
180     if (Metrics.NumInsts > MAX_HEADER_SIZE)
181       return false;
182   }
183 
184   // Now, this loop is suitable for rotation.
185   BasicBlock *OrigPreheader = L->getLoopPreheader();
186   BasicBlock *OrigLatch = L->getLoopLatch();
187 
188   // If the loop could not be converted to canonical form, it must have an
189   // indirectbr in it, just give up.
190   if (OrigPreheader == 0 || OrigLatch == 0)
191     return false;
192 
193   // Anything ScalarEvolution may know about this loop or the PHI nodes
194   // in its header will soon be invalidated.
195   if (ScalarEvolution *SE = getAnalysisIfAvailable<ScalarEvolution>())
196     SE->forgetLoop(L);
197 
198   // Find new Loop header. NewHeader is a Header's one and only successor
199   // that is inside loop.  Header's other successor is outside the
200   // loop.  Otherwise loop is not suitable for rotation.
201   BasicBlock *Exit = BI->getSuccessor(0);
202   BasicBlock *NewHeader = BI->getSuccessor(1);
203   if (L->contains(Exit))
204     std::swap(Exit, NewHeader);
205   assert(NewHeader && "Unable to determine new loop header");
206   assert(L->contains(NewHeader) && !L->contains(Exit) &&
207          "Unable to determine loop header and exit blocks");
208 
209   // This code assumes that the new header has exactly one predecessor.
210   // Remove any single-entry PHI nodes in it.
211   assert(NewHeader->getSinglePredecessor() &&
212          "New header doesn't have one pred!");
213   FoldSingleEntryPHINodes(NewHeader);
214 
215   // Begin by walking OrigHeader and populating ValueMap with an entry for
216   // each Instruction.
217   BasicBlock::iterator I = OrigHeader->begin(), E = OrigHeader->end();
218   ValueToValueMapTy ValueMap;
219 
220   // For PHI nodes, the value available in OldPreHeader is just the
221   // incoming value from OldPreHeader.
222   for (; PHINode *PN = dyn_cast<PHINode>(I); ++I)
223     ValueMap[PN] = PN->getIncomingValueForBlock(OrigPreheader);
224 
225   // For the rest of the instructions, either hoist to the OrigPreheader if
226   // possible or create a clone in the OldPreHeader if not.
227   TerminatorInst *LoopEntryBranch = OrigPreheader->getTerminator();
228   while (I != E) {
229     Instruction *Inst = I++;
230 
231     // If the instruction's operands are invariant and it doesn't read or write
232     // memory, then it is safe to hoist.  Doing this doesn't change the order of
233     // execution in the preheader, but does prevent the instruction from
234     // executing in each iteration of the loop.  This means it is safe to hoist
235     // something that might trap, but isn't safe to hoist something that reads
236     // memory (without proving that the loop doesn't write).
237     if (L->hasLoopInvariantOperands(Inst) &&
238         !Inst->mayReadFromMemory() && !Inst->mayWriteToMemory() &&
239         !isa<TerminatorInst>(Inst) && !isa<DbgInfoIntrinsic>(Inst)) {
240       Inst->moveBefore(LoopEntryBranch);
241       continue;
242     }
243 
244     // Otherwise, create a duplicate of the instruction.
245     Instruction *C = Inst->clone();
246 
247     // Eagerly remap the operands of the instruction.
248     RemapInstruction(C, ValueMap,
249                      RF_NoModuleLevelChanges|RF_IgnoreMissingEntries);
250 
251     // With the operands remapped, see if the instruction constant folds or is
252     // otherwise simplifyable.  This commonly occurs because the entry from PHI
253     // nodes allows icmps and other instructions to fold.
254     Value *V = SimplifyInstruction(C);
255     if (V && LI->replacementPreservesLCSSAForm(C, V)) {
256       // If so, then delete the temporary instruction and stick the folded value
257       // in the map.
258       delete C;
259       ValueMap[Inst] = V;
260     } else {
261       // Otherwise, stick the new instruction into the new block!
262       C->setName(Inst->getName());
263       C->insertBefore(LoopEntryBranch);
264       ValueMap[Inst] = C;
265     }
266   }
267 
268   // Along with all the other instructions, we just cloned OrigHeader's
269   // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
270   // successors by duplicating their incoming values for OrigHeader.
271   TerminatorInst *TI = OrigHeader->getTerminator();
272   for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
273     for (BasicBlock::iterator BI = TI->getSuccessor(i)->begin();
274          PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
275       PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
276 
277   // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
278   // OrigPreHeader's old terminator (the original branch into the loop), and
279   // remove the corresponding incoming values from the PHI nodes in OrigHeader.
280   LoopEntryBranch->eraseFromParent();
281 
282   // If there were any uses of instructions in the duplicated block outside the
283   // loop, update them, inserting PHI nodes as required
284   RewriteUsesOfClonedInstructions(OrigHeader, OrigPreheader, ValueMap);
285 
286   // NewHeader is now the header of the loop.
287   L->moveToHeader(NewHeader);
288   assert(L->getHeader() == NewHeader && "Latch block is our new header");
289 
290 
291   // At this point, we've finished our major CFG changes.  As part of cloning
292   // the loop into the preheader we've simplified instructions and the
293   // duplicated conditional branch may now be branching on a constant.  If it is
294   // branching on a constant and if that constant means that we enter the loop,
295   // then we fold away the cond branch to an uncond branch.  This simplifies the
296   // loop in cases important for nested loops, and it also means we don't have
297   // to split as many edges.
298   BranchInst *PHBI = cast<BranchInst>(OrigPreheader->getTerminator());
299   assert(PHBI->isConditional() && "Should be clone of BI condbr!");
300   if (!isa<ConstantInt>(PHBI->getCondition()) ||
301       PHBI->getSuccessor(cast<ConstantInt>(PHBI->getCondition())->isZero())
302           != NewHeader) {
303     // The conditional branch can't be folded, handle the general case.
304     // Update DominatorTree to reflect the CFG change we just made.  Then split
305     // edges as necessary to preserve LoopSimplify form.
306     if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
307       // Since OrigPreheader now has the conditional branch to Exit block, it is
308       // the dominator of Exit.
309       DT->changeImmediateDominator(Exit, OrigPreheader);
310       DT->changeImmediateDominator(NewHeader, OrigPreheader);
311 
312       // Update OrigHeader to be dominated by the new header block.
313       DT->changeImmediateDominator(OrigHeader, OrigLatch);
314     }
315 
316     // Right now OrigPreHeader has two successors, NewHeader and ExitBlock, and
317     // thus is not a preheader anymore.  Split the edge to form a real preheader.
318     BasicBlock *NewPH = SplitCriticalEdge(OrigPreheader, NewHeader, this);
319     NewPH->setName(NewHeader->getName() + ".lr.ph");
320 
321     // Preserve canonical loop form, which means that 'Exit' should have only one
322     // predecessor.
323     BasicBlock *ExitSplit = SplitCriticalEdge(L->getLoopLatch(), Exit, this);
324     ExitSplit->moveBefore(Exit);
325   } else {
326     // We can fold the conditional branch in the preheader, this makes things
327     // simpler. The first step is to remove the extra edge to the Exit block.
328     Exit->removePredecessor(OrigPreheader, true /*preserve LCSSA*/);
329     BranchInst *NewBI = BranchInst::Create(NewHeader, PHBI);
330     NewBI->setDebugLoc(PHBI->getDebugLoc());
331     PHBI->eraseFromParent();
332 
333     // With our CFG finalized, update DomTree if it is available.
334     if (DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>()) {
335       // Update OrigHeader to be dominated by the new header block.
336       DT->changeImmediateDominator(NewHeader, OrigPreheader);
337       DT->changeImmediateDominator(OrigHeader, OrigLatch);
338     }
339   }
340 
341   assert(L->getLoopPreheader() && "Invalid loop preheader after loop rotation");
342   assert(L->getLoopLatch() && "Invalid loop latch after loop rotation");
343 
344   // Now that the CFG and DomTree are in a consistent state again, try to merge
345   // the OrigHeader block into OrigLatch.  This will succeed if they are
346   // connected by an unconditional branch.  This is just a cleanup so the
347   // emitted code isn't too gross in this common case.
348   MergeBlockIntoPredecessor(OrigHeader, this);
349 
350   ++NumRotated;
351   return true;
352 }
353 
354