1 //===-- UnrollLoopPeel.cpp - Loop peeling utilities -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file implements some loop unrolling utilities for peeling loops
11 // with dynamically inferred (from PGO) trip counts. See LoopUnroll.cpp for
12 // unrolling loops with compile-time constant trip counts.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/Analysis/LoopIterator.h"
18 #include "llvm/Analysis/LoopPass.h"
19 #include "llvm/Analysis/ScalarEvolution.h"
20 #include "llvm/Analysis/TargetTransformInfo.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/Dominators.h"
23 #include "llvm/IR/MDBuilder.h"
24 #include "llvm/IR/Metadata.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 #include "llvm/Transforms/Scalar.h"
29 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
30 #include "llvm/Transforms/Utils/Cloning.h"
31 #include "llvm/Transforms/Utils/LoopUtils.h"
32 #include "llvm/Transforms/Utils/UnrollLoop.h"
37 #define DEBUG_TYPE "loop-unroll"
38 STATISTIC(NumPeeled, "Number of loops peeled");
40 static cl::opt<unsigned> UnrollPeelMaxCount(
41 "unroll-peel-max-count", cl::init(7), cl::Hidden,
42 cl::desc("Max average trip count which will cause loop peeling."));
44 static cl::opt<unsigned> UnrollForcePeelCount(
45 "unroll-force-peel-count", cl::init(0), cl::Hidden,
46 cl::desc("Force a peel count regardless of profiling information."));
48 // Check whether we are capable of peeling this loop.
49 static bool canPeel(Loop *L) {
50 // Make sure the loop is in simplified form
51 if (!L->isLoopSimplifyForm())
54 // Only peel loops that contain a single exit
55 if (!L->getExitingBlock() || !L->getUniqueExitBlock())
61 // Return the number of iterations we want to peel off.
62 void llvm::computePeelCount(Loop *L, unsigned LoopSize,
63 TargetTransformInfo::UnrollingPreferences &UP) {
68 // Only try to peel innermost loops.
72 // If the user provided a peel count, use that.
73 bool UserPeelCount = UnrollForcePeelCount.getNumOccurrences() > 0;
75 DEBUG(dbgs() << "Force-peeling first " << UnrollForcePeelCount
77 UP.PeelCount = UnrollForcePeelCount;
81 // If we don't know the trip count, but have reason to believe the average
82 // trip count is low, peeling should be beneficial, since we will usually
83 // hit the peeled section.
84 // We only do this in the presence of profile information, since otherwise
85 // our estimates of the trip count are not reliable enough.
86 if (UP.AllowPeeling && L->getHeader()->getParent()->getEntryCount()) {
87 Optional<unsigned> PeelCount = getLoopEstimatedTripCount(L);
91 DEBUG(dbgs() << "Profile-based estimated trip count is " << *PeelCount
95 if ((*PeelCount <= UnrollPeelMaxCount) &&
96 (LoopSize * (*PeelCount + 1) <= UP.Threshold)) {
97 DEBUG(dbgs() << "Peeling first " << *PeelCount << " iterations.\n");
98 UP.PeelCount = *PeelCount;
101 DEBUG(dbgs() << "Requested peel count: " << *PeelCount << "\n");
102 DEBUG(dbgs() << "Max peel count: " << UnrollPeelMaxCount << "\n");
103 DEBUG(dbgs() << "Peel cost: " << LoopSize * (*PeelCount + 1) << "\n");
104 DEBUG(dbgs() << "Max peel cost: " << UP.Threshold << "\n");
111 /// \brief Update the branch weights of the latch of a peeled-off loop
113 /// This sets the branch weights for the latch of the recently peeled off loop
114 /// iteration correctly.
115 /// Our goal is to make sure that:
116 /// a) The total weight of all the copies of the loop body is preserved.
117 /// b) The total weight of the loop exit is preserved.
118 /// c) The body weight is reasonably distributed between the peeled iterations.
120 /// \param Header The copy of the header block that belongs to next iteration.
121 /// \param LatchBR The copy of the latch branch that belongs to this iteration.
122 /// \param IterNumber The serial number of the iteration that was just
124 /// \param AvgIters The average number of iterations we expect the loop to have.
125 /// \param[in,out] PeeledHeaderWeight The total number of dynamic loop
126 /// iterations that are unaccounted for. As an input, it represents the number
127 /// of times we expect to enter the header of the iteration currently being
128 /// peeled off. The output is the number of times we expect to enter the
129 /// header of the next iteration.
130 static void updateBranchWeights(BasicBlock *Header, BranchInst *LatchBR,
131 unsigned IterNumber, unsigned AvgIters,
132 uint64_t &PeeledHeaderWeight) {
134 // FIXME: Pick a more realistic distribution.
135 // Currently the proportion of weight we assign to the fall-through
136 // side of the branch drops linearly with the iteration number, and we use
137 // a 0.9 fudge factor to make the drop-off less sharp...
138 if (PeeledHeaderWeight) {
139 uint64_t FallThruWeight =
140 PeeledHeaderWeight * ((float)(AvgIters - IterNumber) / AvgIters * 0.9);
141 uint64_t ExitWeight = PeeledHeaderWeight - FallThruWeight;
142 PeeledHeaderWeight -= ExitWeight;
144 unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
145 MDBuilder MDB(LatchBR->getContext());
147 HeaderIdx ? MDB.createBranchWeights(ExitWeight, FallThruWeight)
148 : MDB.createBranchWeights(FallThruWeight, ExitWeight);
149 LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
153 /// \brief Clones the body of the loop L, putting it between \p InsertTop and \p
155 /// \param IterNumber The serial number of the iteration currently being
157 /// \param Exit The exit block of the original loop.
158 /// \param[out] NewBlocks A list of the the blocks in the newly created clone
159 /// \param[out] VMap The value map between the loop and the new clone.
160 /// \param LoopBlocks A helper for DFS-traversal of the loop.
161 /// \param LVMap A value-map that maps instructions from the original loop to
162 /// instructions in the last peeled-off iteration.
163 static void cloneLoopBlocks(Loop *L, unsigned IterNumber, BasicBlock *InsertTop,
164 BasicBlock *InsertBot, BasicBlock *Exit,
165 SmallVectorImpl<BasicBlock *> &NewBlocks,
166 LoopBlocksDFS &LoopBlocks, ValueToValueMapTy &VMap,
167 ValueToValueMapTy &LVMap, LoopInfo *LI) {
169 BasicBlock *Header = L->getHeader();
170 BasicBlock *Latch = L->getLoopLatch();
171 BasicBlock *PreHeader = L->getLoopPreheader();
173 Function *F = Header->getParent();
174 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
175 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
176 Loop *ParentLoop = L->getParentLoop();
178 // For each block in the original loop, create a new copy,
179 // and update the value map with the newly created values.
180 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
181 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, ".peel", F);
182 NewBlocks.push_back(NewBB);
185 ParentLoop->addBasicBlockToLoop(NewBB, *LI);
190 // Hook-up the control flow for the newly inserted blocks.
191 // The new header is hooked up directly to the "top", which is either
192 // the original loop preheader (for the first iteration) or the previous
193 // iteration's exiting block (for every other iteration)
194 InsertTop->getTerminator()->setSuccessor(0, cast<BasicBlock>(VMap[Header]));
196 // Similarly, for the latch:
197 // The original exiting edge is still hooked up to the loop exit.
198 // The backedge now goes to the "bottom", which is either the loop's real
199 // header (for the last peeled iteration) or the copied header of the next
200 // iteration (for every other iteration)
201 BranchInst *LatchBR =
202 cast<BranchInst>(cast<BasicBlock>(VMap[Latch])->getTerminator());
203 unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
204 LatchBR->setSuccessor(HeaderIdx, InsertBot);
205 LatchBR->setSuccessor(1 - HeaderIdx, Exit);
207 // The new copy of the loop body starts with a bunch of PHI nodes
208 // that pick an incoming value from either the preheader, or the previous
209 // loop iteration. Since this copy is no longer part of the loop, we
210 // resolve this statically:
211 // For the first iteration, we use the value from the preheader directly.
212 // For any other iteration, we replace the phi with the value generated by
213 // the immediately preceding clone of the loop body (which represents
214 // the previous iteration).
215 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
216 PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
217 if (IterNumber == 0) {
218 VMap[&*I] = NewPHI->getIncomingValueForBlock(PreHeader);
220 Value *LatchVal = NewPHI->getIncomingValueForBlock(Latch);
221 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
222 if (LatchInst && L->contains(LatchInst))
223 VMap[&*I] = LVMap[LatchInst];
225 VMap[&*I] = LatchVal;
227 cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
230 // Fix up the outgoing values - we need to add a value for the iteration
231 // we've just created. Note that this must happen *after* the incoming
232 // values are adjusted, since the value going out of the latch may also be
233 // a value coming into the header.
234 for (BasicBlock::iterator I = Exit->begin(); isa<PHINode>(I); ++I) {
235 PHINode *PHI = cast<PHINode>(I);
236 Value *LatchVal = PHI->getIncomingValueForBlock(Latch);
237 Instruction *LatchInst = dyn_cast<Instruction>(LatchVal);
238 if (LatchInst && L->contains(LatchInst))
239 LatchVal = VMap[LatchVal];
240 PHI->addIncoming(LatchVal, cast<BasicBlock>(VMap[Latch]));
243 // LastValueMap is updated with the values for the current loop
244 // which are used the next time this function is called.
245 for (const auto &KV : VMap)
246 LVMap[KV.first] = KV.second;
249 /// \brief Peel off the first \p PeelCount iterations of loop \p L.
251 /// Note that this does not peel them off as a single straight-line block.
252 /// Rather, each iteration is peeled off separately, and needs to check the
254 /// For loops that dynamically execute \p PeelCount iterations or less
255 /// this provides a benefit, since the peeled off iterations, which account
256 /// for the bulk of dynamic execution, can be further simplified by scalar
258 bool llvm::peelLoop(Loop *L, unsigned PeelCount, LoopInfo *LI,
259 ScalarEvolution *SE, DominatorTree *DT,
260 bool PreserveLCSSA) {
264 LoopBlocksDFS LoopBlocks(L);
265 LoopBlocks.perform(LI);
267 BasicBlock *Header = L->getHeader();
268 BasicBlock *PreHeader = L->getLoopPreheader();
269 BasicBlock *Latch = L->getLoopLatch();
270 BasicBlock *Exit = L->getUniqueExitBlock();
272 Function *F = Header->getParent();
274 // Set up all the necessary basic blocks. It is convenient to split the
275 // preheader into 3 parts - two blocks to anchor the peeled copy of the loop
276 // body, and a new preheader for the "real" loop.
278 // Peeling the first iteration transforms.
284 // If (cond) goto Header
291 // If (!cond) goto Exit
297 // If (cond) goto Header
300 // Each following iteration will split the current bottom anchor in two,
301 // and put the new copy of the loop body between these two blocks. That is,
302 // after peeling another iteration from the example above, we'll split
303 // InsertBot, and get:
307 // If (!cond) goto Exit
310 // If (!cond) goto Exit
316 // If (cond) goto Header
319 BasicBlock *InsertTop = SplitEdge(PreHeader, Header, DT, LI);
320 BasicBlock *InsertBot =
321 SplitBlock(InsertTop, InsertTop->getTerminator(), DT, LI);
322 BasicBlock *NewPreHeader =
323 SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
325 InsertTop->setName(Header->getName() + ".peel.begin");
326 InsertBot->setName(Header->getName() + ".peel.next");
327 NewPreHeader->setName(PreHeader->getName() + ".peel.newph");
329 ValueToValueMapTy LVMap;
331 // If we have branch weight information, we'll want to update it for the
332 // newly created branches.
333 BranchInst *LatchBR =
334 cast<BranchInst>(cast<BasicBlock>(Latch)->getTerminator());
335 unsigned HeaderIdx = (LatchBR->getSuccessor(0) == Header ? 0 : 1);
337 uint64_t TrueWeight, FalseWeight;
338 uint64_t ExitWeight = 0, CurHeaderWeight = 0;
339 if (LatchBR->extractProfMetadata(TrueWeight, FalseWeight)) {
340 ExitWeight = HeaderIdx ? TrueWeight : FalseWeight;
341 // The # of times the loop body executes is the sum of the exit block
342 // weight and the # of times the backedges are taken.
343 CurHeaderWeight = TrueWeight + FalseWeight;
346 // For each peeled-off iteration, make a copy of the loop.
347 for (unsigned Iter = 0; Iter < PeelCount; ++Iter) {
348 SmallVector<BasicBlock *, 8> NewBlocks;
349 ValueToValueMapTy VMap;
351 // Subtract the exit weight from the current header weight -- the exit
352 // weight is exactly the weight of the previous iteration's header.
353 // FIXME: due to the way the distribution is constructed, we need a
354 // guard here to make sure we don't end up with non-positive weights.
355 if (ExitWeight < CurHeaderWeight)
356 CurHeaderWeight -= ExitWeight;
360 cloneLoopBlocks(L, Iter, InsertTop, InsertBot, Exit,
361 NewBlocks, LoopBlocks, VMap, LVMap, LI);
362 updateBranchWeights(InsertBot, cast<BranchInst>(VMap[LatchBR]), Iter,
363 PeelCount, ExitWeight);
365 InsertTop = InsertBot;
366 InsertBot = SplitBlock(InsertBot, InsertBot->getTerminator(), DT, LI);
367 InsertBot->setName(Header->getName() + ".peel.next");
369 F->getBasicBlockList().splice(InsertTop->getIterator(),
370 F->getBasicBlockList(),
371 NewBlocks[0]->getIterator(), F->end());
373 // Remap to use values from the current iteration instead of the
375 remapInstructionsInBlocks(NewBlocks, VMap);
378 // Now adjust the phi nodes in the loop header to get their initial values
379 // from the last peeled-off iteration instead of the preheader.
380 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
381 PHINode *PHI = cast<PHINode>(I);
382 Value *NewVal = PHI->getIncomingValueForBlock(Latch);
383 Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
384 if (LatchInst && L->contains(LatchInst))
385 NewVal = LVMap[LatchInst];
387 PHI->setIncomingValue(PHI->getBasicBlockIndex(NewPreHeader), NewVal);
390 // Adjust the branch weights on the loop exit.
392 // The backedge count is the difference of current header weight and
393 // current loop exit weight. If the current header weight is smaller than
394 // the current loop exit weight, we mark the loop backedge weight as 1.
395 uint64_t BackEdgeWeight = 0;
396 if (ExitWeight < CurHeaderWeight)
397 BackEdgeWeight = CurHeaderWeight - ExitWeight;
400 MDBuilder MDB(LatchBR->getContext());
402 HeaderIdx ? MDB.createBranchWeights(ExitWeight, BackEdgeWeight)
403 : MDB.createBranchWeights(BackEdgeWeight, ExitWeight);
404 LatchBR->setMetadata(LLVMContext::MD_prof, WeightNode);
407 // If the loop is nested, we changed the parent loop, update SE.
408 if (Loop *ParentLoop = L->getParentLoop())
409 SE->forgetLoop(ParentLoop);