Bug Summary

File:lib/Transforms/Utils/LoopUnrollRuntime.cpp
Warning:line 600, column 26
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name LoopUnrollRuntime.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-eagerly-assume -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-7/lib/clang/7.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils -I /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/include -I /build/llvm-toolchain-snapshot-7~svn329677/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/x86_64-linux-gnu/c++/7.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/7.3.0/../../../../include/c++/7.3.0/backward -internal-isystem /usr/include/clang/7.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-7/lib/clang/7.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-7~svn329677/build-llvm/lib/Transforms/Utils -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2018-04-11-031539-24776-1 -x c++ /build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp
1//===-- UnrollLoopRuntime.cpp - Runtime Loop unrolling utilities ----------===//
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 some loop unrolling utilities for loops with run-time
11// trip counts. See LoopUnroll.cpp for unrolling loops with compile-time
12// trip counts.
13//
14// The functions in this file are used to generate extra code when the
15// run-time trip count modulo the unroll factor is not 0. When this is the
16// case, we need to generate code to execute these 'left over' iterations.
17//
18// The current strategy generates an if-then-else sequence prior to the
19// unrolled loop to execute the 'left over' iterations before or after the
20// unrolled loop.
21//
22//===----------------------------------------------------------------------===//
23
24#include "llvm/ADT/SmallSet.h"
25#include "llvm/ADT/Statistic.h"
26#include "llvm/Analysis/AliasAnalysis.h"
27#include "llvm/Analysis/LoopIterator.h"
28#include "llvm/Analysis/ScalarEvolution.h"
29#include "llvm/Analysis/ScalarEvolutionExpander.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/Dominators.h"
32#include "llvm/IR/Metadata.h"
33#include "llvm/IR/Module.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/raw_ostream.h"
36#include "llvm/Transforms/Utils.h"
37#include "llvm/Transforms/Utils/BasicBlockUtils.h"
38#include "llvm/Transforms/Utils/Cloning.h"
39#include "llvm/Transforms/Utils/LoopUtils.h"
40#include "llvm/Transforms/Utils/UnrollLoop.h"
41#include <algorithm>
42
43using namespace llvm;
44
45#define DEBUG_TYPE"loop-unroll" "loop-unroll"
46
47STATISTIC(NumRuntimeUnrolled,static llvm::Statistic NumRuntimeUnrolled = {"loop-unroll", "NumRuntimeUnrolled"
, "Number of loops unrolled with run-time trip counts", {0}, {
false}}
48 "Number of loops unrolled with run-time trip counts")static llvm::Statistic NumRuntimeUnrolled = {"loop-unroll", "NumRuntimeUnrolled"
, "Number of loops unrolled with run-time trip counts", {0}, {
false}}
;
49static cl::opt<bool> UnrollRuntimeMultiExit(
50 "unroll-runtime-multi-exit", cl::init(false), cl::Hidden,
51 cl::desc("Allow runtime unrolling for loops with multiple exits, when "
52 "epilog is generated"));
53
54/// Connect the unrolling prolog code to the original loop.
55/// The unrolling prolog code contains code to execute the
56/// 'extra' iterations if the run-time trip count modulo the
57/// unroll count is non-zero.
58///
59/// This function performs the following:
60/// - Create PHI nodes at prolog end block to combine values
61/// that exit the prolog code and jump around the prolog.
62/// - Add a PHI operand to a PHI node at the loop exit block
63/// for values that exit the prolog and go around the loop.
64/// - Branch around the original loop if the trip count is less
65/// than the unroll factor.
66///
67static void ConnectProlog(Loop *L, Value *BECount, unsigned Count,
68 BasicBlock *PrologExit,
69 BasicBlock *OriginalLoopLatchExit,
70 BasicBlock *PreHeader, BasicBlock *NewPreHeader,
71 ValueToValueMapTy &VMap, DominatorTree *DT,
72 LoopInfo *LI, bool PreserveLCSSA) {
73 BasicBlock *Latch = L->getLoopLatch();
74 assert(Latch && "Loop must have a latch")(static_cast <bool> (Latch && "Loop must have a latch"
) ? void (0) : __assert_fail ("Latch && \"Loop must have a latch\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 74, __extension__ __PRETTY_FUNCTION__))
;
75 BasicBlock *PrologLatch = cast<BasicBlock>(VMap[Latch]);
76
77 // Create a PHI node for each outgoing value from the original loop
78 // (which means it is an outgoing value from the prolog code too).
79 // The new PHI node is inserted in the prolog end basic block.
80 // The new PHI node value is added as an operand of a PHI node in either
81 // the loop header or the loop exit block.
82 for (BasicBlock *Succ : successors(Latch)) {
83 for (PHINode &PN : Succ->phis()) {
84 // Add a new PHI node to the prolog end block and add the
85 // appropriate incoming values.
86 PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
87 PrologExit->getFirstNonPHI());
88 // Adding a value to the new PHI node from the original loop preheader.
89 // This is the value that skips all the prolog code.
90 if (L->contains(&PN)) {
91 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader),
92 PreHeader);
93 } else {
94 NewPN->addIncoming(UndefValue::get(PN.getType()), PreHeader);
95 }
96
97 Value *V = PN.getIncomingValueForBlock(Latch);
98 if (Instruction *I = dyn_cast<Instruction>(V)) {
99 if (L->contains(I)) {
100 V = VMap.lookup(I);
101 }
102 }
103 // Adding a value to the new PHI node from the last prolog block
104 // that was created.
105 NewPN->addIncoming(V, PrologLatch);
106
107 // Update the existing PHI node operand with the value from the
108 // new PHI node. How this is done depends on if the existing
109 // PHI node is in the original loop block, or the exit block.
110 if (L->contains(&PN)) {
111 PN.setIncomingValue(PN.getBasicBlockIndex(NewPreHeader), NewPN);
112 } else {
113 PN.addIncoming(NewPN, PrologExit);
114 }
115 }
116 }
117
118 // Make sure that created prolog loop is in simplified form
119 SmallVector<BasicBlock *, 4> PrologExitPreds;
120 Loop *PrologLoop = LI->getLoopFor(PrologLatch);
121 if (PrologLoop) {
122 for (BasicBlock *PredBB : predecessors(PrologExit))
123 if (PrologLoop->contains(PredBB))
124 PrologExitPreds.push_back(PredBB);
125
126 SplitBlockPredecessors(PrologExit, PrologExitPreds, ".unr-lcssa", DT, LI,
127 PreserveLCSSA);
128 }
129
130 // Create a branch around the original loop, which is taken if there are no
131 // iterations remaining to be executed after running the prologue.
132 Instruction *InsertPt = PrologExit->getTerminator();
133 IRBuilder<> B(InsertPt);
134
135 assert(Count != 0 && "nonsensical Count!")(static_cast <bool> (Count != 0 && "nonsensical Count!"
) ? void (0) : __assert_fail ("Count != 0 && \"nonsensical Count!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 135, __extension__ __PRETTY_FUNCTION__))
;
136
137 // If BECount <u (Count - 1) then (BECount + 1) % Count == (BECount + 1)
138 // This means %xtraiter is (BECount + 1) and all of the iterations of this
139 // loop were executed by the prologue. Note that if BECount <u (Count - 1)
140 // then (BECount + 1) cannot unsigned-overflow.
141 Value *BrLoopExit =
142 B.CreateICmpULT(BECount, ConstantInt::get(BECount->getType(), Count - 1));
143 // Split the exit to maintain loop canonicalization guarantees
144 SmallVector<BasicBlock *, 4> Preds(predecessors(OriginalLoopLatchExit));
145 SplitBlockPredecessors(OriginalLoopLatchExit, Preds, ".unr-lcssa", DT, LI,
146 PreserveLCSSA);
147 // Add the branch to the exit block (around the unrolled loop)
148 B.CreateCondBr(BrLoopExit, OriginalLoopLatchExit, NewPreHeader);
149 InsertPt->eraseFromParent();
150 if (DT)
151 DT->changeImmediateDominator(OriginalLoopLatchExit, PrologExit);
152}
153
154/// Connect the unrolling epilog code to the original loop.
155/// The unrolling epilog code contains code to execute the
156/// 'extra' iterations if the run-time trip count modulo the
157/// unroll count is non-zero.
158///
159/// This function performs the following:
160/// - Update PHI nodes at the unrolling loop exit and epilog loop exit
161/// - Create PHI nodes at the unrolling loop exit to combine
162/// values that exit the unrolling loop code and jump around it.
163/// - Update PHI operands in the epilog loop by the new PHI nodes
164/// - Branch around the epilog loop if extra iters (ModVal) is zero.
165///
166static void ConnectEpilog(Loop *L, Value *ModVal, BasicBlock *NewExit,
167 BasicBlock *Exit, BasicBlock *PreHeader,
168 BasicBlock *EpilogPreHeader, BasicBlock *NewPreHeader,
169 ValueToValueMapTy &VMap, DominatorTree *DT,
170 LoopInfo *LI, bool PreserveLCSSA) {
171 BasicBlock *Latch = L->getLoopLatch();
172 assert(Latch && "Loop must have a latch")(static_cast <bool> (Latch && "Loop must have a latch"
) ? void (0) : __assert_fail ("Latch && \"Loop must have a latch\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 172, __extension__ __PRETTY_FUNCTION__))
;
173 BasicBlock *EpilogLatch = cast<BasicBlock>(VMap[Latch]);
174
175 // Loop structure should be the following:
176 //
177 // PreHeader
178 // NewPreHeader
179 // Header
180 // ...
181 // Latch
182 // NewExit (PN)
183 // EpilogPreHeader
184 // EpilogHeader
185 // ...
186 // EpilogLatch
187 // Exit (EpilogPN)
188
189 // Update PHI nodes at NewExit and Exit.
190 for (PHINode &PN : NewExit->phis()) {
191 // PN should be used in another PHI located in Exit block as
192 // Exit was split by SplitBlockPredecessors into Exit and NewExit
193 // Basicaly it should look like:
194 // NewExit:
195 // PN = PHI [I, Latch]
196 // ...
197 // Exit:
198 // EpilogPN = PHI [PN, EpilogPreHeader]
199 //
200 // There is EpilogPreHeader incoming block instead of NewExit as
201 // NewExit was spilt 1 more time to get EpilogPreHeader.
202 assert(PN.hasOneUse() && "The phi should have 1 use")(static_cast <bool> (PN.hasOneUse() && "The phi should have 1 use"
) ? void (0) : __assert_fail ("PN.hasOneUse() && \"The phi should have 1 use\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 202, __extension__ __PRETTY_FUNCTION__))
;
203 PHINode *EpilogPN = cast<PHINode>(PN.use_begin()->getUser());
204 assert(EpilogPN->getParent() == Exit && "EpilogPN should be in Exit block")(static_cast <bool> (EpilogPN->getParent() == Exit &&
"EpilogPN should be in Exit block") ? void (0) : __assert_fail
("EpilogPN->getParent() == Exit && \"EpilogPN should be in Exit block\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 204, __extension__ __PRETTY_FUNCTION__))
;
205
206 // Add incoming PreHeader from branch around the Loop
207 PN.addIncoming(UndefValue::get(PN.getType()), PreHeader);
208
209 Value *V = PN.getIncomingValueForBlock(Latch);
210 Instruction *I = dyn_cast<Instruction>(V);
211 if (I && L->contains(I))
212 // If value comes from an instruction in the loop add VMap value.
213 V = VMap.lookup(I);
214 // For the instruction out of the loop, constant or undefined value
215 // insert value itself.
216 EpilogPN->addIncoming(V, EpilogLatch);
217
218 assert(EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 &&(static_cast <bool> (EpilogPN->getBasicBlockIndex(EpilogPreHeader
) >= 0 && "EpilogPN should have EpilogPreHeader incoming block"
) ? void (0) : __assert_fail ("EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 && \"EpilogPN should have EpilogPreHeader incoming block\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 219, __extension__ __PRETTY_FUNCTION__))
219 "EpilogPN should have EpilogPreHeader incoming block")(static_cast <bool> (EpilogPN->getBasicBlockIndex(EpilogPreHeader
) >= 0 && "EpilogPN should have EpilogPreHeader incoming block"
) ? void (0) : __assert_fail ("EpilogPN->getBasicBlockIndex(EpilogPreHeader) >= 0 && \"EpilogPN should have EpilogPreHeader incoming block\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 219, __extension__ __PRETTY_FUNCTION__))
;
220 // Change EpilogPreHeader incoming block to NewExit.
221 EpilogPN->setIncomingBlock(EpilogPN->getBasicBlockIndex(EpilogPreHeader),
222 NewExit);
223 // Now PHIs should look like:
224 // NewExit:
225 // PN = PHI [I, Latch], [undef, PreHeader]
226 // ...
227 // Exit:
228 // EpilogPN = PHI [PN, NewExit], [VMap[I], EpilogLatch]
229 }
230
231 // Create PHI nodes at NewExit (from the unrolling loop Latch and PreHeader).
232 // Update corresponding PHI nodes in epilog loop.
233 for (BasicBlock *Succ : successors(Latch)) {
234 // Skip this as we already updated phis in exit blocks.
235 if (!L->contains(Succ))
236 continue;
237 for (PHINode &PN : Succ->phis()) {
238 // Add new PHI nodes to the loop exit block and update epilog
239 // PHIs with the new PHI values.
240 PHINode *NewPN = PHINode::Create(PN.getType(), 2, PN.getName() + ".unr",
241 NewExit->getFirstNonPHI());
242 // Adding a value to the new PHI node from the unrolling loop preheader.
243 NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
244 // Adding a value to the new PHI node from the unrolling loop latch.
245 NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
246
247 // Update the existing PHI node operand with the value from the new PHI
248 // node. Corresponding instruction in epilog loop should be PHI.
249 PHINode *VPN = cast<PHINode>(VMap[&PN]);
250 VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
251 }
252 }
253
254 Instruction *InsertPt = NewExit->getTerminator();
255 IRBuilder<> B(InsertPt);
256 Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
257 assert(Exit && "Loop must have a single exit block only")(static_cast <bool> (Exit && "Loop must have a single exit block only"
) ? void (0) : __assert_fail ("Exit && \"Loop must have a single exit block only\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 257, __extension__ __PRETTY_FUNCTION__))
;
258 // Split the epilogue exit to maintain loop canonicalization guarantees
259 SmallVector<BasicBlock*, 4> Preds(predecessors(Exit));
260 SplitBlockPredecessors(Exit, Preds, ".epilog-lcssa", DT, LI,
261 PreserveLCSSA);
262 // Add the branch to the exit block (around the unrolling loop)
263 B.CreateCondBr(BrLoopExit, EpilogPreHeader, Exit);
264 InsertPt->eraseFromParent();
265 if (DT)
266 DT->changeImmediateDominator(Exit, NewExit);
267
268 // Split the main loop exit to maintain canonicalization guarantees.
269 SmallVector<BasicBlock*, 4> NewExitPreds{Latch};
270 SplitBlockPredecessors(NewExit, NewExitPreds, ".loopexit", DT, LI,
271 PreserveLCSSA);
272}
273
274/// Create a clone of the blocks in a loop and connect them together.
275/// If CreateRemainderLoop is false, loop structure will not be cloned,
276/// otherwise a new loop will be created including all cloned blocks, and the
277/// iterator of it switches to count NewIter down to 0.
278/// The cloned blocks should be inserted between InsertTop and InsertBot.
279/// If loop structure is cloned InsertTop should be new preheader, InsertBot
280/// new loop exit.
281/// Return the new cloned loop that is created when CreateRemainderLoop is true.
282static Loop *
283CloneLoopBlocks(Loop *L, Value *NewIter, const bool CreateRemainderLoop,
284 const bool UseEpilogRemainder, const bool UnrollRemainder,
285 BasicBlock *InsertTop,
286 BasicBlock *InsertBot, BasicBlock *Preheader,
287 std::vector<BasicBlock *> &NewBlocks, LoopBlocksDFS &LoopBlocks,
288 ValueToValueMapTy &VMap, DominatorTree *DT, LoopInfo *LI) {
289 StringRef suffix = UseEpilogRemainder ? "epil" : "prol";
290 BasicBlock *Header = L->getHeader();
291 BasicBlock *Latch = L->getLoopLatch();
292 Function *F = Header->getParent();
293 LoopBlocksDFS::RPOIterator BlockBegin = LoopBlocks.beginRPO();
294 LoopBlocksDFS::RPOIterator BlockEnd = LoopBlocks.endRPO();
295 Loop *ParentLoop = L->getParentLoop();
296 NewLoopsMap NewLoops;
297 NewLoops[ParentLoop] = ParentLoop;
298 if (!CreateRemainderLoop)
299 NewLoops[L] = ParentLoop;
300
301 // For each block in the original loop, create a new copy,
302 // and update the value map with the newly created values.
303 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
304 BasicBlock *NewBB = CloneBasicBlock(*BB, VMap, "." + suffix, F);
305 NewBlocks.push_back(NewBB);
306
307 // If we're unrolling the outermost loop, there's no remainder loop,
308 // and this block isn't in a nested loop, then the new block is not
309 // in any loop. Otherwise, add it to loopinfo.
310 if (CreateRemainderLoop || LI->getLoopFor(*BB) != L || ParentLoop)
311 addClonedBlockToLoopInfo(*BB, NewBB, LI, NewLoops);
312
313 VMap[*BB] = NewBB;
314 if (Header == *BB) {
315 // For the first block, add a CFG connection to this newly
316 // created block.
317 InsertTop->getTerminator()->setSuccessor(0, NewBB);
318 }
319
320 if (DT) {
321 if (Header == *BB) {
322 // The header is dominated by the preheader.
323 DT->addNewBlock(NewBB, InsertTop);
324 } else {
325 // Copy information from original loop to unrolled loop.
326 BasicBlock *IDomBB = DT->getNode(*BB)->getIDom()->getBlock();
327 DT->addNewBlock(NewBB, cast<BasicBlock>(VMap[IDomBB]));
328 }
329 }
330
331 if (Latch == *BB) {
332 // For the last block, if CreateRemainderLoop is false, create a direct
333 // jump to InsertBot. If not, create a loop back to cloned head.
334 VMap.erase((*BB)->getTerminator());
335 BasicBlock *FirstLoopBB = cast<BasicBlock>(VMap[Header]);
336 BranchInst *LatchBR = cast<BranchInst>(NewBB->getTerminator());
337 IRBuilder<> Builder(LatchBR);
338 if (!CreateRemainderLoop) {
339 Builder.CreateBr(InsertBot);
340 } else {
341 PHINode *NewIdx = PHINode::Create(NewIter->getType(), 2,
342 suffix + ".iter",
343 FirstLoopBB->getFirstNonPHI());
344 Value *IdxSub =
345 Builder.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
346 NewIdx->getName() + ".sub");
347 Value *IdxCmp =
348 Builder.CreateIsNotNull(IdxSub, NewIdx->getName() + ".cmp");
349 Builder.CreateCondBr(IdxCmp, FirstLoopBB, InsertBot);
350 NewIdx->addIncoming(NewIter, InsertTop);
351 NewIdx->addIncoming(IdxSub, NewBB);
352 }
353 LatchBR->eraseFromParent();
354 }
355 }
356
357 // Change the incoming values to the ones defined in the preheader or
358 // cloned loop.
359 for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
360 PHINode *NewPHI = cast<PHINode>(VMap[&*I]);
361 if (!CreateRemainderLoop) {
362 if (UseEpilogRemainder) {
363 unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
364 NewPHI->setIncomingBlock(idx, InsertTop);
365 NewPHI->removeIncomingValue(Latch, false);
366 } else {
367 VMap[&*I] = NewPHI->getIncomingValueForBlock(Preheader);
368 cast<BasicBlock>(VMap[Header])->getInstList().erase(NewPHI);
369 }
370 } else {
371 unsigned idx = NewPHI->getBasicBlockIndex(Preheader);
372 NewPHI->setIncomingBlock(idx, InsertTop);
373 BasicBlock *NewLatch = cast<BasicBlock>(VMap[Latch]);
374 idx = NewPHI->getBasicBlockIndex(Latch);
375 Value *InVal = NewPHI->getIncomingValue(idx);
376 NewPHI->setIncomingBlock(idx, NewLatch);
377 if (Value *V = VMap.lookup(InVal))
378 NewPHI->setIncomingValue(idx, V);
379 }
380 }
381 if (CreateRemainderLoop) {
382 Loop *NewLoop = NewLoops[L];
383 assert(NewLoop && "L should have been cloned")(static_cast <bool> (NewLoop && "L should have been cloned"
) ? void (0) : __assert_fail ("NewLoop && \"L should have been cloned\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 383, __extension__ __PRETTY_FUNCTION__))
;
384
385 // Only add loop metadata if the loop is not going to be completely
386 // unrolled.
387 if (UnrollRemainder)
388 return NewLoop;
389
390 // Add unroll disable metadata to disable future unrolling for this loop.
391 NewLoop->setLoopAlreadyUnrolled();
392 return NewLoop;
393 }
394 else
395 return nullptr;
396}
397
398/// Returns true if we can safely unroll a multi-exit/exiting loop. OtherExits
399/// is populated with all the loop exit blocks other than the LatchExit block.
400static bool
401canSafelyUnrollMultiExitLoop(Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits,
402 BasicBlock *LatchExit, bool PreserveLCSSA,
403 bool UseEpilogRemainder) {
404
405 // We currently have some correctness constrains in unrolling a multi-exit
406 // loop. Check for these below.
407
408 // We rely on LCSSA form being preserved when the exit blocks are transformed.
409 if (!PreserveLCSSA)
410 return false;
411 SmallVector<BasicBlock *, 4> Exits;
412 L->getUniqueExitBlocks(Exits);
413 for (auto *BB : Exits)
414 if (BB != LatchExit)
415 OtherExits.push_back(BB);
416
417 // TODO: Support multiple exiting blocks jumping to the `LatchExit` when
418 // UnrollRuntimeMultiExit is true. This will need updating the logic in
419 // connectEpilog/connectProlog.
420 if (!LatchExit->getSinglePredecessor()) {
421 DEBUG(dbgs() << "Bailout for multi-exit handling when latch exit has >1 "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
"predecessor.\n"; } } while (false)
422 "predecessor.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Bailout for multi-exit handling when latch exit has >1 "
"predecessor.\n"; } } while (false)
;
423 return false;
424 }
425 // FIXME: We bail out of multi-exit unrolling when epilog loop is generated
426 // and L is an inner loop. This is because in presence of multiple exits, the
427 // outer loop is incorrect: we do not add the EpilogPreheader and exit to the
428 // outer loop. This is automatically handled in the prolog case, so we do not
429 // have that bug in prolog generation.
430 if (UseEpilogRemainder && L->getParentLoop())
431 return false;
432
433 // All constraints have been satisfied.
434 return true;
435}
436
437/// Returns true if we can profitably unroll the multi-exit loop L. Currently,
438/// we return true only if UnrollRuntimeMultiExit is set to true.
439static bool canProfitablyUnrollMultiExitLoop(
440 Loop *L, SmallVectorImpl<BasicBlock *> &OtherExits, BasicBlock *LatchExit,
441 bool PreserveLCSSA, bool UseEpilogRemainder) {
442
443#if !defined(NDEBUG)
444 SmallVector<BasicBlock *, 8> OtherExitsDummyCheck;
445 assert(canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit,(static_cast <bool> (canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck
, LatchExit, PreserveLCSSA, UseEpilogRemainder) && "Should be safe to unroll before checking profitability!"
) ? void (0) : __assert_fail ("canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit, PreserveLCSSA, UseEpilogRemainder) && \"Should be safe to unroll before checking profitability!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 447, __extension__ __PRETTY_FUNCTION__))
446 PreserveLCSSA, UseEpilogRemainder) &&(static_cast <bool> (canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck
, LatchExit, PreserveLCSSA, UseEpilogRemainder) && "Should be safe to unroll before checking profitability!"
) ? void (0) : __assert_fail ("canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit, PreserveLCSSA, UseEpilogRemainder) && \"Should be safe to unroll before checking profitability!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 447, __extension__ __PRETTY_FUNCTION__))
447 "Should be safe to unroll before checking profitability!")(static_cast <bool> (canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck
, LatchExit, PreserveLCSSA, UseEpilogRemainder) && "Should be safe to unroll before checking profitability!"
) ? void (0) : __assert_fail ("canSafelyUnrollMultiExitLoop(L, OtherExitsDummyCheck, LatchExit, PreserveLCSSA, UseEpilogRemainder) && \"Should be safe to unroll before checking profitability!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 447, __extension__ __PRETTY_FUNCTION__))
;
448#endif
449
450 // Priority goes to UnrollRuntimeMultiExit if it's supplied.
451 if (UnrollRuntimeMultiExit.getNumOccurrences())
452 return UnrollRuntimeMultiExit;
453
454 // The main pain point with multi-exit loop unrolling is that once unrolled,
455 // we will not be able to merge all blocks into a straight line code.
456 // There are branches within the unrolled loop that go to the OtherExits.
457 // The second point is the increase in code size, but this is true
458 // irrespective of multiple exits.
459
460 // Note: Both the heuristics below are coarse grained. We are essentially
461 // enabling unrolling of loops that have a single side exit other than the
462 // normal LatchExit (i.e. exiting into a deoptimize block).
463 // The heuristics considered are:
464 // 1. low number of branches in the unrolled version.
465 // 2. high predictability of these extra branches.
466 // We avoid unrolling loops that have more than two exiting blocks. This
467 // limits the total number of branches in the unrolled loop to be atmost
468 // the unroll factor (since one of the exiting blocks is the latch block).
469 SmallVector<BasicBlock*, 4> ExitingBlocks;
470 L->getExitingBlocks(ExitingBlocks);
471 if (ExitingBlocks.size() > 2)
472 return false;
473
474 // The second heuristic is that L has one exit other than the latchexit and
475 // that exit is a deoptimize block. We know that deoptimize blocks are rarely
476 // taken, which also implies the branch leading to the deoptimize block is
477 // highly predictable.
478 return (OtherExits.size() == 1 &&
479 OtherExits[0]->getTerminatingDeoptimizeCall());
480 // TODO: These can be fine-tuned further to consider code size or deopt states
481 // that are captured by the deoptimize exit block.
482 // Also, we can extend this to support more cases, if we actually
483 // know of kinds of multiexit loops that would benefit from unrolling.
484}
485
486/// Insert code in the prolog/epilog code when unrolling a loop with a
487/// run-time trip-count.
488///
489/// This method assumes that the loop unroll factor is total number
490/// of loop bodies in the loop after unrolling. (Some folks refer
491/// to the unroll factor as the number of *extra* copies added).
492/// We assume also that the loop unroll factor is a power-of-two. So, after
493/// unrolling the loop, the number of loop bodies executed is 2,
494/// 4, 8, etc. Note - LLVM converts the if-then-sequence to a switch
495/// instruction in SimplifyCFG.cpp. Then, the backend decides how code for
496/// the switch instruction is generated.
497///
498/// ***Prolog case***
499/// extraiters = tripcount % loopfactor
500/// if (extraiters == 0) jump Loop:
501/// else jump Prol:
502/// Prol: LoopBody;
503/// extraiters -= 1 // Omitted if unroll factor is 2.
504/// if (extraiters != 0) jump Prol: // Omitted if unroll factor is 2.
505/// if (tripcount < loopfactor) jump End:
506/// Loop:
507/// ...
508/// End:
509///
510/// ***Epilog case***
511/// extraiters = tripcount % loopfactor
512/// if (tripcount < loopfactor) jump LoopExit:
513/// unroll_iters = tripcount - extraiters
514/// Loop: LoopBody; (executes unroll_iter times);
515/// unroll_iter -= 1
516/// if (unroll_iter != 0) jump Loop:
517/// LoopExit:
518/// if (extraiters == 0) jump EpilExit:
519/// Epil: LoopBody; (executes extraiters times)
520/// extraiters -= 1 // Omitted if unroll factor is 2.
521/// if (extraiters != 0) jump Epil: // Omitted if unroll factor is 2.
522/// EpilExit:
523
524bool llvm::UnrollRuntimeLoopRemainder(Loop *L, unsigned Count,
525 bool AllowExpensiveTripCount,
526 bool UseEpilogRemainder,
527 bool UnrollRemainder,
528 LoopInfo *LI, ScalarEvolution *SE,
529 DominatorTree *DT, AssumptionCache *AC,
530 bool PreserveLCSSA) {
531 DEBUG(dbgs() << "Trying runtime unrolling on Loop: \n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Trying runtime unrolling on Loop: \n"
; } } while (false)
;
532 DEBUG(L->dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { L->dump(); } } while (false)
;
533 DEBUG(UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n" :do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
: dbgs() << "Using prolog remainder.\n"; } } while (false
)
534 dbgs() << "Using prolog remainder.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { UseEpilogRemainder ? dbgs() << "Using epilog remainder.\n"
: dbgs() << "Using prolog remainder.\n"; } } while (false
)
;
535
536 // Make sure the loop is in canonical form.
537 if (!L->isLoopSimplifyForm()) {
1
Assuming the condition is false
2
Taking false branch
538 DEBUG(dbgs() << "Not in simplify form!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Not in simplify form!\n";
} } while (false)
;
539 return false;
540 }
541
542 // Guaranteed by LoopSimplifyForm.
543 BasicBlock *Latch = L->getLoopLatch();
544 BasicBlock *Header = L->getHeader();
3
'Header' initialized here
545
546 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
547 unsigned ExitIndex = LatchBR->getSuccessor(0) == Header ? 1 : 0;
4
Assuming pointer value is null
5
'?' condition is true
548 BasicBlock *LatchExit = LatchBR->getSuccessor(ExitIndex);
549 // Cloning the loop basic blocks (`CloneLoopBlocks`) requires that one of the
550 // targets of the Latch be an exit block out of the loop. This needs
551 // to be guaranteed by the callers of UnrollRuntimeLoopRemainder.
552 assert(!L->contains(LatchExit) &&(static_cast <bool> (!L->contains(LatchExit) &&
"one of the loop latch successors should be the exit block!"
) ? void (0) : __assert_fail ("!L->contains(LatchExit) && \"one of the loop latch successors should be the exit block!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 553, __extension__ __PRETTY_FUNCTION__))
553 "one of the loop latch successors should be the exit block!")(static_cast <bool> (!L->contains(LatchExit) &&
"one of the loop latch successors should be the exit block!"
) ? void (0) : __assert_fail ("!L->contains(LatchExit) && \"one of the loop latch successors should be the exit block!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 553, __extension__ __PRETTY_FUNCTION__))
;
554 // These are exit blocks other than the target of the latch exiting block.
555 SmallVector<BasicBlock *, 4> OtherExits;
556 bool isMultiExitUnrollingEnabled =
557 canSafelyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
558 UseEpilogRemainder) &&
559 canProfitablyUnrollMultiExitLoop(L, OtherExits, LatchExit, PreserveLCSSA,
560 UseEpilogRemainder);
561 // Support only single exit and exiting block unless multi-exit loop unrolling is enabled.
562 if (!isMultiExitUnrollingEnabled &&
8
Taking false branch
563 (!L->getExitingBlock() || OtherExits.size())) {
6
Assuming the condition is false
7
Assuming the condition is false
564 DEBUG(do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
"enabled!\n"; } } while (false)
565 dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
"enabled!\n"; } } while (false)
566 << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
"enabled!\n"; } } while (false)
567 "enabled!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Multiple exit/exiting blocks in loop and multi-exit unrolling not "
"enabled!\n"; } } while (false)
;
568 return false;
569 }
570 // Use Scalar Evolution to compute the trip count. This allows more loops to
571 // be unrolled than relying on induction var simplification.
572 if (!SE)
9
Assuming 'SE' is non-null
10
Taking false branch
573 return false;
574
575 // Only unroll loops with a computable trip count, and the trip count needs
576 // to be an int value (allowing a pointer type is a TODO item).
577 // We calculate the backedge count by using getExitCount on the Latch block,
578 // which is proven to be the only exiting block in this loop. This is same as
579 // calculating getBackedgeTakenCount on the loop (which computes SCEV for all
580 // exiting blocks).
581 const SCEV *BECountSC = SE->getExitCount(L, Latch);
582 if (isa<SCEVCouldNotCompute>(BECountSC) ||
11
Assuming the condition is false
12
Taking false branch
583 !BECountSC->getType()->isIntegerTy()) {
584 DEBUG(dbgs() << "Could not compute exit block SCEV\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Could not compute exit block SCEV\n"
; } } while (false)
;
585 return false;
586 }
587
588 unsigned BEWidth = cast<IntegerType>(BECountSC->getType())->getBitWidth();
589
590 // Add 1 since the backedge count doesn't include the first loop iteration.
591 const SCEV *TripCountSC =
592 SE->getAddExpr(BECountSC, SE->getConstant(BECountSC->getType(), 1));
593 if (isa<SCEVCouldNotCompute>(TripCountSC)) {
13
Assuming the condition is false
14
Taking false branch
594 DEBUG(dbgs() << "Could not compute trip count SCEV.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Could not compute trip count SCEV.\n"
; } } while (false)
;
595 return false;
596 }
597
598 BasicBlock *PreHeader = L->getLoopPreheader();
599 BranchInst *PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
600 const DataLayout &DL = Header->getModule()->getDataLayout();
15
Called C++ object pointer is null
601 SCEVExpander Expander(*SE, DL, "loop-unroll");
602 if (!AllowExpensiveTripCount &&
603 Expander.isHighCostExpansion(TripCountSC, L, PreHeaderBR)) {
604 DEBUG(dbgs() << "High cost for expanding trip count scev!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "High cost for expanding trip count scev!\n"
; } } while (false)
;
605 return false;
606 }
607
608 // This constraint lets us deal with an overflowing trip count easily; see the
609 // comment on ModVal below.
610 if (Log2_32(Count) > BEWidth) {
611 DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Count failed constraint on overflow trip count calculation.\n"
; } } while (false)
612 << "Count failed constraint on overflow trip count calculation.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Count failed constraint on overflow trip count calculation.\n"
; } } while (false)
;
613 return false;
614 }
615
616 // Loop structure is the following:
617 //
618 // PreHeader
619 // Header
620 // ...
621 // Latch
622 // LatchExit
623
624 BasicBlock *NewPreHeader;
625 BasicBlock *NewExit = nullptr;
626 BasicBlock *PrologExit = nullptr;
627 BasicBlock *EpilogPreHeader = nullptr;
628 BasicBlock *PrologPreHeader = nullptr;
629
630 if (UseEpilogRemainder) {
631 // If epilog remainder
632 // Split PreHeader to insert a branch around loop for unrolling.
633 NewPreHeader = SplitBlock(PreHeader, PreHeader->getTerminator(), DT, LI);
634 NewPreHeader->setName(PreHeader->getName() + ".new");
635 // Split LatchExit to create phi nodes from branch above.
636 SmallVector<BasicBlock*, 4> Preds(predecessors(LatchExit));
637 NewExit = SplitBlockPredecessors(LatchExit, Preds, ".unr-lcssa",
638 DT, LI, PreserveLCSSA);
639 // NewExit gets its DebugLoc from LatchExit, which is not part of the
640 // original Loop.
641 // Fix this by setting Loop's DebugLoc to NewExit.
642 auto *NewExitTerminator = NewExit->getTerminator();
643 NewExitTerminator->setDebugLoc(Header->getTerminator()->getDebugLoc());
644 // Split NewExit to insert epilog remainder loop.
645 EpilogPreHeader = SplitBlock(NewExit, NewExitTerminator, DT, LI);
646 EpilogPreHeader->setName(Header->getName() + ".epil.preheader");
647 } else {
648 // If prolog remainder
649 // Split the original preheader twice to insert prolog remainder loop
650 PrologPreHeader = SplitEdge(PreHeader, Header, DT, LI);
651 PrologPreHeader->setName(Header->getName() + ".prol.preheader");
652 PrologExit = SplitBlock(PrologPreHeader, PrologPreHeader->getTerminator(),
653 DT, LI);
654 PrologExit->setName(Header->getName() + ".prol.loopexit");
655 // Split PrologExit to get NewPreHeader.
656 NewPreHeader = SplitBlock(PrologExit, PrologExit->getTerminator(), DT, LI);
657 NewPreHeader->setName(PreHeader->getName() + ".new");
658 }
659 // Loop structure should be the following:
660 // Epilog Prolog
661 //
662 // PreHeader PreHeader
663 // *NewPreHeader *PrologPreHeader
664 // Header *PrologExit
665 // ... *NewPreHeader
666 // Latch Header
667 // *NewExit ...
668 // *EpilogPreHeader Latch
669 // LatchExit LatchExit
670
671 // Calculate conditions for branch around loop for unrolling
672 // in epilog case and around prolog remainder loop in prolog case.
673 // Compute the number of extra iterations required, which is:
674 // extra iterations = run-time trip count % loop unroll factor
675 PreHeaderBR = cast<BranchInst>(PreHeader->getTerminator());
676 Value *TripCount = Expander.expandCodeFor(TripCountSC, TripCountSC->getType(),
677 PreHeaderBR);
678 Value *BECount = Expander.expandCodeFor(BECountSC, BECountSC->getType(),
679 PreHeaderBR);
680 IRBuilder<> B(PreHeaderBR);
681 Value *ModVal;
682 // Calculate ModVal = (BECount + 1) % Count.
683 // Note that TripCount is BECount + 1.
684 if (isPowerOf2_32(Count)) {
685 // When Count is power of 2 we don't BECount for epilog case, however we'll
686 // need it for a branch around unrolling loop for prolog case.
687 ModVal = B.CreateAnd(TripCount, Count - 1, "xtraiter");
688 // 1. There are no iterations to be run in the prolog/epilog loop.
689 // OR
690 // 2. The addition computing TripCount overflowed.
691 //
692 // If (2) is true, we know that TripCount really is (1 << BEWidth) and so
693 // the number of iterations that remain to be run in the original loop is a
694 // multiple Count == (1 << Log2(Count)) because Log2(Count) <= BEWidth (we
695 // explicitly check this above).
696 } else {
697 // As (BECount + 1) can potentially unsigned overflow we count
698 // (BECount % Count) + 1 which is overflow safe as BECount % Count < Count.
699 Value *ModValTmp = B.CreateURem(BECount,
700 ConstantInt::get(BECount->getType(),
701 Count));
702 Value *ModValAdd = B.CreateAdd(ModValTmp,
703 ConstantInt::get(ModValTmp->getType(), 1));
704 // At that point (BECount % Count) + 1 could be equal to Count.
705 // To handle this case we need to take mod by Count one more time.
706 ModVal = B.CreateURem(ModValAdd,
707 ConstantInt::get(BECount->getType(), Count),
708 "xtraiter");
709 }
710 Value *BranchVal =
711 UseEpilogRemainder ? B.CreateICmpULT(BECount,
712 ConstantInt::get(BECount->getType(),
713 Count - 1)) :
714 B.CreateIsNotNull(ModVal, "lcmp.mod");
715 BasicBlock *RemainderLoop = UseEpilogRemainder ? NewExit : PrologPreHeader;
716 BasicBlock *UnrollingLoop = UseEpilogRemainder ? NewPreHeader : PrologExit;
717 // Branch to either remainder (extra iterations) loop or unrolling loop.
718 B.CreateCondBr(BranchVal, RemainderLoop, UnrollingLoop);
719 PreHeaderBR->eraseFromParent();
720 if (DT) {
721 if (UseEpilogRemainder)
722 DT->changeImmediateDominator(NewExit, PreHeader);
723 else
724 DT->changeImmediateDominator(PrologExit, PreHeader);
725 }
726 Function *F = Header->getParent();
727 // Get an ordered list of blocks in the loop to help with the ordering of the
728 // cloned blocks in the prolog/epilog code
729 LoopBlocksDFS LoopBlocks(L);
730 LoopBlocks.perform(LI);
731
732 //
733 // For each extra loop iteration, create a copy of the loop's basic blocks
734 // and generate a condition that branches to the copy depending on the
735 // number of 'left over' iterations.
736 //
737 std::vector<BasicBlock *> NewBlocks;
738 ValueToValueMapTy VMap;
739
740 // For unroll factor 2 remainder loop will have 1 iterations.
741 // Do not create 1 iteration loop.
742 bool CreateRemainderLoop = (Count != 2);
743
744 // Clone all the basic blocks in the loop. If Count is 2, we don't clone
745 // the loop, otherwise we create a cloned loop to execute the extra
746 // iterations. This function adds the appropriate CFG connections.
747 BasicBlock *InsertBot = UseEpilogRemainder ? LatchExit : PrologExit;
748 BasicBlock *InsertTop = UseEpilogRemainder ? EpilogPreHeader : PrologPreHeader;
749 Loop *remainderLoop = CloneLoopBlocks(
750 L, ModVal, CreateRemainderLoop, UseEpilogRemainder, UnrollRemainder,
751 InsertTop, InsertBot,
752 NewPreHeader, NewBlocks, LoopBlocks, VMap, DT, LI);
753
754 // Insert the cloned blocks into the function.
755 F->getBasicBlockList().splice(InsertBot->getIterator(),
756 F->getBasicBlockList(),
757 NewBlocks[0]->getIterator(),
758 F->end());
759
760 // Now the loop blocks are cloned and the other exiting blocks from the
761 // remainder are connected to the original Loop's exit blocks. The remaining
762 // work is to update the phi nodes in the original loop, and take in the
763 // values from the cloned region. Also update the dominator info for
764 // OtherExits and their immediate successors, since we have new edges into
765 // OtherExits.
766 SmallSet<BasicBlock*, 8> ImmediateSuccessorsOfExitBlocks;
767 for (auto *BB : OtherExits) {
768 for (auto &II : *BB) {
769
770 // Given we preserve LCSSA form, we know that the values used outside the
771 // loop will be used through these phi nodes at the exit blocks that are
772 // transformed below.
773 if (!isa<PHINode>(II))
774 break;
775 PHINode *Phi = cast<PHINode>(&II);
776 unsigned oldNumOperands = Phi->getNumIncomingValues();
777 // Add the incoming values from the remainder code to the end of the phi
778 // node.
779 for (unsigned i =0; i < oldNumOperands; i++){
780 Value *newVal = VMap.lookup(Phi->getIncomingValue(i));
781 // newVal can be a constant or derived from values outside the loop, and
782 // hence need not have a VMap value. Also, since lookup already generated
783 // a default "null" VMap entry for this value, we need to populate that
784 // VMap entry correctly, with the mapped entry being itself.
785 if (!newVal) {
786 newVal = Phi->getIncomingValue(i);
787 VMap[Phi->getIncomingValue(i)] = Phi->getIncomingValue(i);
788 }
789 Phi->addIncoming(newVal,
790 cast<BasicBlock>(VMap[Phi->getIncomingBlock(i)]));
791 }
792 }
793#if defined(EXPENSIVE_CHECKS) && !defined(NDEBUG)
794 for (BasicBlock *SuccBB : successors(BB)) {
795 assert(!(any_of(OtherExits,(static_cast <bool> (!(any_of(OtherExits, [SuccBB](BasicBlock
*EB) { return EB == SuccBB; }) || SuccBB == LatchExit) &&
"Breaks the definition of dedicated exits!") ? void (0) : __assert_fail
("!(any_of(OtherExits, [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) || SuccBB == LatchExit) && \"Breaks the definition of dedicated exits!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 798, __extension__ __PRETTY_FUNCTION__))
796 [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) ||(static_cast <bool> (!(any_of(OtherExits, [SuccBB](BasicBlock
*EB) { return EB == SuccBB; }) || SuccBB == LatchExit) &&
"Breaks the definition of dedicated exits!") ? void (0) : __assert_fail
("!(any_of(OtherExits, [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) || SuccBB == LatchExit) && \"Breaks the definition of dedicated exits!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 798, __extension__ __PRETTY_FUNCTION__))
797 SuccBB == LatchExit) &&(static_cast <bool> (!(any_of(OtherExits, [SuccBB](BasicBlock
*EB) { return EB == SuccBB; }) || SuccBB == LatchExit) &&
"Breaks the definition of dedicated exits!") ? void (0) : __assert_fail
("!(any_of(OtherExits, [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) || SuccBB == LatchExit) && \"Breaks the definition of dedicated exits!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 798, __extension__ __PRETTY_FUNCTION__))
798 "Breaks the definition of dedicated exits!")(static_cast <bool> (!(any_of(OtherExits, [SuccBB](BasicBlock
*EB) { return EB == SuccBB; }) || SuccBB == LatchExit) &&
"Breaks the definition of dedicated exits!") ? void (0) : __assert_fail
("!(any_of(OtherExits, [SuccBB](BasicBlock *EB) { return EB == SuccBB; }) || SuccBB == LatchExit) && \"Breaks the definition of dedicated exits!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 798, __extension__ __PRETTY_FUNCTION__))
;
799 }
800#endif
801 // Update the dominator info because the immediate dominator is no longer the
802 // header of the original Loop. BB has edges both from L and remainder code.
803 // Since the preheader determines which loop is run (L or directly jump to
804 // the remainder code), we set the immediate dominator as the preheader.
805 if (DT) {
806 DT->changeImmediateDominator(BB, PreHeader);
807 // Also update the IDom for immediate successors of BB. If the current
808 // IDom is the header, update the IDom to be the preheader because that is
809 // the nearest common dominator of all predecessors of SuccBB. We need to
810 // check for IDom being the header because successors of exit blocks can
811 // have edges from outside the loop, and we should not incorrectly update
812 // the IDom in that case.
813 for (BasicBlock *SuccBB: successors(BB))
814 if (ImmediateSuccessorsOfExitBlocks.insert(SuccBB).second) {
815 if (DT->getNode(SuccBB)->getIDom()->getBlock() == Header) {
816 assert(!SuccBB->getSinglePredecessor() &&(static_cast <bool> (!SuccBB->getSinglePredecessor()
&& "BB should be the IDom then!") ? void (0) : __assert_fail
("!SuccBB->getSinglePredecessor() && \"BB should be the IDom then!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 817, __extension__ __PRETTY_FUNCTION__))
817 "BB should be the IDom then!")(static_cast <bool> (!SuccBB->getSinglePredecessor()
&& "BB should be the IDom then!") ? void (0) : __assert_fail
("!SuccBB->getSinglePredecessor() && \"BB should be the IDom then!\""
, "/build/llvm-toolchain-snapshot-7~svn329677/lib/Transforms/Utils/LoopUnrollRuntime.cpp"
, 817, __extension__ __PRETTY_FUNCTION__))
;
818 DT->changeImmediateDominator(SuccBB, PreHeader);
819 }
820 }
821 }
822 }
823
824 // Loop structure should be the following:
825 // Epilog Prolog
826 //
827 // PreHeader PreHeader
828 // NewPreHeader PrologPreHeader
829 // Header PrologHeader
830 // ... ...
831 // Latch PrologLatch
832 // NewExit PrologExit
833 // EpilogPreHeader NewPreHeader
834 // EpilogHeader Header
835 // ... ...
836 // EpilogLatch Latch
837 // LatchExit LatchExit
838
839 // Rewrite the cloned instruction operands to use the values created when the
840 // clone is created.
841 for (BasicBlock *BB : NewBlocks) {
842 for (Instruction &I : *BB) {
843 RemapInstruction(&I, VMap,
844 RF_NoModuleLevelChanges | RF_IgnoreMissingLocals);
845 }
846 }
847
848 if (UseEpilogRemainder) {
849 // Connect the epilog code to the original loop and update the
850 // PHI functions.
851 ConnectEpilog(L, ModVal, NewExit, LatchExit, PreHeader,
852 EpilogPreHeader, NewPreHeader, VMap, DT, LI,
853 PreserveLCSSA);
854
855 // Update counter in loop for unrolling.
856 // I should be multiply of Count.
857 IRBuilder<> B2(NewPreHeader->getTerminator());
858 Value *TestVal = B2.CreateSub(TripCount, ModVal, "unroll_iter");
859 BranchInst *LatchBR = cast<BranchInst>(Latch->getTerminator());
860 B2.SetInsertPoint(LatchBR);
861 PHINode *NewIdx = PHINode::Create(TestVal->getType(), 2, "niter",
862 Header->getFirstNonPHI());
863 Value *IdxSub =
864 B2.CreateSub(NewIdx, ConstantInt::get(NewIdx->getType(), 1),
865 NewIdx->getName() + ".nsub");
866 Value *IdxCmp;
867 if (LatchBR->getSuccessor(0) == Header)
868 IdxCmp = B2.CreateIsNotNull(IdxSub, NewIdx->getName() + ".ncmp");
869 else
870 IdxCmp = B2.CreateIsNull(IdxSub, NewIdx->getName() + ".ncmp");
871 NewIdx->addIncoming(TestVal, NewPreHeader);
872 NewIdx->addIncoming(IdxSub, Latch);
873 LatchBR->setCondition(IdxCmp);
874 } else {
875 // Connect the prolog code to the original loop and update the
876 // PHI functions.
877 ConnectProlog(L, BECount, Count, PrologExit, LatchExit, PreHeader,
878 NewPreHeader, VMap, DT, LI, PreserveLCSSA);
879 }
880
881 // If this loop is nested, then the loop unroller changes the code in the
882 // parent loop, so the Scalar Evolution pass needs to be run again.
883 if (Loop *ParentLoop = L->getParentLoop())
884 SE->forgetLoop(ParentLoop);
885
886 // Canonicalize to LoopSimplifyForm both original and remainder loops. We
887 // cannot rely on the LoopUnrollPass to do this because it only does
888 // canonicalization for parent/subloops and not the sibling loops.
889 if (OtherExits.size() > 0) {
890 // Generate dedicated exit blocks for the original loop, to preserve
891 // LoopSimplifyForm.
892 formDedicatedExitBlocks(L, DT, LI, PreserveLCSSA);
893 // Generate dedicated exit blocks for the remainder loop if one exists, to
894 // preserve LoopSimplifyForm.
895 if (remainderLoop)
896 formDedicatedExitBlocks(remainderLoop, DT, LI, PreserveLCSSA);
897 }
898
899 if (remainderLoop && UnrollRemainder) {
900 DEBUG(dbgs() << "Unrolling remainder loop\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("loop-unroll")) { dbgs() << "Unrolling remainder loop\n"
; } } while (false)
;
901 UnrollLoop(remainderLoop, /*Count*/ Count - 1, /*TripCount*/ Count - 1,
902 /*Force*/ false, /*AllowRuntime*/ false,
903 /*AllowExpensiveTripCount*/ false, /*PreserveCondBr*/ true,
904 /*PreserveOnlyFirst*/ false, /*TripMultiple*/ 1,
905 /*PeelCount*/ 0, /*UnrollRemainder*/ false, LI, SE, DT, AC,
906 /*ORE*/ nullptr, PreserveLCSSA);
907 }
908
909 NumRuntimeUnrolled++;
910 return true;
911}