1//===-- LoopUnrollAndJam.cpp - Loop unrolling utilities -------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements loop unroll and jam as a routine, much like
10// LoopUnroll.cpp implements loop unroll.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/ArrayRef.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallPtrSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/Analysis/AssumptionCache.h"
23#include "llvm/Analysis/DependenceAnalysis.h"
24#include "llvm/Analysis/DomTreeUpdater.h"
25#include "llvm/Analysis/LoopInfo.h"
26#include "llvm/Analysis/LoopIterator.h"
27#include "llvm/Analysis/MustExecute.h"
28#include "llvm/Analysis/OptimizationRemarkEmitter.h"
29#include "llvm/Analysis/ScalarEvolution.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/DebugInfoMetadata.h"
32#include "llvm/IR/DebugLoc.h"
33#include "llvm/IR/DiagnosticInfo.h"
34#include "llvm/IR/Dominators.h"
35#include "llvm/IR/Function.h"
36#include "llvm/IR/Instruction.h"
37#include "llvm/IR/Instructions.h"
38#include "llvm/IR/IntrinsicInst.h"
39#include "llvm/IR/User.h"
40#include "llvm/IR/Value.h"
41#include "llvm/IR/ValueHandle.h"
42#include "llvm/IR/ValueMap.h"
43#include "llvm/Support/Casting.h"
44#include "llvm/Support/Debug.h"
45#include "llvm/Support/ErrorHandling.h"
46#include "llvm/Support/GenericDomTree.h"
47#include "llvm/Support/raw_ostream.h"
48#include "llvm/Transforms/Utils/BasicBlockUtils.h"
49#include "llvm/Transforms/Utils/Cloning.h"
50#include "llvm/Transforms/Utils/LoopUtils.h"
51#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
52#include "llvm/Transforms/Utils/UnrollLoop.h"
53#include "llvm/Transforms/Utils/ValueMapper.h"
54#include <assert.h>
55#include <memory>
56#include <vector>
57
58using namespace llvm;
59
60#define DEBUG_TYPE "loop-unroll-and-jam"
61
62STATISTIC(NumUnrolledAndJammed, "Number of loops unroll and jammed");
63STATISTIC(NumCompletelyUnrolledAndJammed, "Number of loops unroll and jammed");
64
65typedef SmallPtrSet<BasicBlock *, 4> BasicBlockSet;
66
67// Partition blocks in an outer/inner loop pair into blocks before and after
68// the loop
69static bool partitionLoopBlocks(Loop &L, BasicBlockSet &ForeBlocks,
70 BasicBlockSet &AftBlocks, DominatorTree &DT) {
71 Loop *SubLoop = L.getSubLoops()[0];
72 BasicBlock *SubLoopLatch = SubLoop->getLoopLatch();
73
74 for (BasicBlock *BB : L.blocks()) {
75 if (!SubLoop->contains(BB)) {
76 if (DT.dominates(A: SubLoopLatch, B: BB))
77 AftBlocks.insert(Ptr: BB);
78 else
79 ForeBlocks.insert(Ptr: BB);
80 }
81 }
82
83 // Check that all blocks in ForeBlocks together dominate the subloop
84 // TODO: This might ideally be done better with a dominator/postdominators.
85 BasicBlock *SubLoopPreHeader = SubLoop->getLoopPreheader();
86 for (BasicBlock *BB : ForeBlocks) {
87 if (BB == SubLoopPreHeader)
88 continue;
89 Instruction *TI = BB->getTerminator();
90 for (BasicBlock *Succ : successors(I: TI))
91 if (!ForeBlocks.count(Ptr: Succ))
92 return false;
93 }
94
95 return true;
96}
97
98/// Partition blocks in a loop nest into blocks before and after each inner
99/// loop.
100static bool partitionOuterLoopBlocks(
101 Loop &Root, Loop &JamLoop, BasicBlockSet &JamLoopBlocks,
102 DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,
103 DenseMap<Loop *, BasicBlockSet> &AftBlocksMap, DominatorTree &DT) {
104 JamLoopBlocks.insert_range(R: JamLoop.blocks());
105
106 for (Loop *L : Root.getLoopsInPreorder()) {
107 if (L == &JamLoop)
108 break;
109
110 if (!partitionLoopBlocks(L&: *L, ForeBlocks&: ForeBlocksMap[L], AftBlocks&: AftBlocksMap[L], DT))
111 return false;
112 }
113
114 return true;
115}
116
117// TODO Remove when UnrollAndJamLoop changed to support unroll and jamming more
118// than 2 levels loop.
119static bool partitionOuterLoopBlocks(Loop *L, Loop *SubLoop,
120 BasicBlockSet &ForeBlocks,
121 BasicBlockSet &SubLoopBlocks,
122 BasicBlockSet &AftBlocks,
123 DominatorTree *DT) {
124 SubLoopBlocks.insert_range(R: SubLoop->blocks());
125 return partitionLoopBlocks(L&: *L, ForeBlocks, AftBlocks, DT&: *DT);
126}
127
128// Looks at the phi nodes in Header for values coming from Latch. For these
129// instructions and all their operands calls Visit on them, keeping going for
130// all the operands in AftBlocks. Returns false if Visit returns false,
131// otherwise returns true. This is used to process the instructions in the
132// Aft blocks that need to be moved before the subloop. It is used in two
133// places. One to check that the required set of instructions can be moved
134// before the loop. Then to collect the instructions to actually move in
135// moveHeaderPhiOperandsToForeBlocks.
136template <typename T>
137static bool processHeaderPhiOperands(BasicBlock *Header, BasicBlock *Latch,
138 BasicBlockSet &AftBlocks, T Visit) {
139 SmallPtrSet<Instruction *, 8> VisitedInstr;
140
141 std::function<bool(Instruction * I)> ProcessInstr = [&](Instruction *I) {
142 if (!VisitedInstr.insert(Ptr: I).second)
143 return true;
144
145 if (AftBlocks.count(Ptr: I->getParent()))
146 for (auto &U : I->operands())
147 if (Instruction *II = dyn_cast<Instruction>(Val&: U))
148 if (!ProcessInstr(II))
149 return false;
150
151 return Visit(I);
152 };
153
154 for (auto &Phi : Header->phis()) {
155 Value *V = Phi.getIncomingValueForBlock(BB: Latch);
156 if (Instruction *I = dyn_cast<Instruction>(Val: V))
157 if (!ProcessInstr(I))
158 return false;
159 }
160
161 return true;
162}
163
164// Move the phi operands of Header from Latch out of AftBlocks to InsertLoc.
165static void moveHeaderPhiOperandsToForeBlocks(BasicBlock *Header,
166 BasicBlock *Latch,
167 BasicBlock::iterator InsertLoc,
168 BasicBlockSet &AftBlocks) {
169 // We need to ensure we move the instructions in the correct order,
170 // starting with the earliest required instruction and moving forward.
171 processHeaderPhiOperands(Header, Latch, AftBlocks,
172 Visit: [&AftBlocks, &InsertLoc](Instruction *I) {
173 if (AftBlocks.count(Ptr: I->getParent()))
174 I->moveBefore(InsertPos: InsertLoc);
175 return true;
176 });
177}
178
179/*
180 This method performs Unroll and Jam. For a simple loop like:
181 for (i = ..)
182 Fore(i)
183 for (j = ..)
184 SubLoop(i, j)
185 Aft(i)
186
187 Instead of doing normal inner or outer unrolling, we do:
188 for (i = .., i+=2)
189 Fore(i)
190 Fore(i+1)
191 for (j = ..)
192 SubLoop(i, j)
193 SubLoop(i+1, j)
194 Aft(i)
195 Aft(i+1)
196
197 So the outer loop is essetially unrolled and then the inner loops are fused
198 ("jammed") together into a single loop. This can increase speed when there
199 are loads in SubLoop that are invariant to i, as they become shared between
200 the now jammed inner loops.
201
202 We do this by spliting the blocks in the loop into Fore, Subloop and Aft.
203 Fore blocks are those before the inner loop, Aft are those after. Normal
204 Unroll code is used to copy each of these sets of blocks and the results are
205 combined together into the final form above.
206
207 isSafeToUnrollAndJam should be used prior to calling this to make sure the
208 unrolling will be valid. Checking profitablility is also advisable.
209
210 If EpilogueLoop is non-null, it receives the epilogue loop (if it was
211 necessary to create one and not fully unrolled).
212*/
213LoopUnrollResult
214llvm::UnrollAndJamLoop(Loop *L, unsigned Count, unsigned TripCount,
215 unsigned TripMultiple, bool UnrollRemainder,
216 LoopInfo *LI, ScalarEvolution *SE, DominatorTree *DT,
217 AssumptionCache *AC, const TargetTransformInfo *TTI,
218 OptimizationRemarkEmitter *ORE, Loop **EpilogueLoop) {
219
220 // When we enter here we should have already checked that it is safe
221 BasicBlock *Header = L->getHeader();
222 assert(Header && "No header.");
223 assert(L->getSubLoops().size() == 1);
224 Loop *SubLoop = *L->begin();
225
226 // Don't enter the unroll code if there is nothing to do.
227 if (TripCount == 0 && Count < 2) {
228 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; almost nothing to do\n");
229 return LoopUnrollResult::Unmodified;
230 }
231
232 assert(Count > 0);
233 assert(TripMultiple > 0);
234 assert(TripCount == 0 || TripCount % TripMultiple == 0);
235
236 // Are we eliminating the loop control altogether?
237 bool CompletelyUnroll = (Count == TripCount);
238
239 // We use the runtime remainder in cases where we don't know trip multiple
240 if (TripMultiple % Count != 0) {
241 if (!UnrollRuntimeLoopRemainder(L, Count, /*AllowExpensiveTripCount*/ false,
242 /*UseEpilogRemainder*/ true,
243 UnrollRemainder, /*ForgetAllSCEV*/ false,
244 LI, SE, DT, AC, TTI, PreserveLCSSA: true,
245 SCEVExpansionBudget: SCEVCheapExpansionBudget, RuntimeUnrollMultiExit: EpilogueLoop)) {
246 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; remainder loop could not be "
247 "generated when assuming runtime trip count\n");
248 return LoopUnrollResult::Unmodified;
249 }
250 }
251
252 // Notify ScalarEvolution that the loop will be substantially changed,
253 // if not outright eliminated.
254 if (SE) {
255 SE->forgetLoop(L);
256 SE->forgetBlockAndLoopDispositions();
257 }
258
259 using namespace ore;
260 // Report the unrolling decision.
261 if (CompletelyUnroll) {
262 LLVM_DEBUG(dbgs() << "COMPLETELY UNROLL AND JAMMING loop %"
263 << Header->getName() << " with trip count " << TripCount
264 << "!\n");
265 ORE->emit(OptDiag: OptimizationRemark(DEBUG_TYPE, "FullyUnrolled", L->getStartLoc(),
266 L->getHeader())
267 << "completely unroll and jammed loop with "
268 << NV("UnrollCount", TripCount) << " iterations");
269 } else {
270 auto DiagBuilder = [&]() {
271 OptimizationRemark Diag(DEBUG_TYPE, "PartialUnrolled", L->getStartLoc(),
272 L->getHeader());
273 return Diag << "unroll and jammed loop by a factor of "
274 << NV("UnrollCount", Count);
275 };
276
277 LLVM_DEBUG(dbgs() << "UNROLL AND JAMMING loop %" << Header->getName()
278 << " by " << Count);
279 if (TripMultiple != 1) {
280 LLVM_DEBUG(dbgs() << " with " << TripMultiple << " trips per branch");
281 ORE->emit(RemarkBuilder: [&]() {
282 return DiagBuilder() << " with " << NV("TripMultiple", TripMultiple)
283 << " trips per branch";
284 });
285 } else {
286 LLVM_DEBUG(dbgs() << " with run-time trip count");
287 ORE->emit(RemarkBuilder: [&]() { return DiagBuilder() << " with run-time trip count"; });
288 }
289 LLVM_DEBUG(dbgs() << "!\n");
290 }
291
292 BasicBlock *Preheader = L->getLoopPreheader();
293 BasicBlock *LatchBlock = L->getLoopLatch();
294 assert(Preheader && "No preheader");
295 assert(LatchBlock && "No latch block");
296 CondBrInst *BI = cast<CondBrInst>(Val: LatchBlock->getTerminator());
297 bool ContinueOnTrue = L->contains(BB: BI->getSuccessor(i: 0));
298 BasicBlock *LoopExit = BI->getSuccessor(i: ContinueOnTrue);
299 bool SubLoopContinueOnTrue = SubLoop->contains(
300 BB: SubLoop->getLoopLatch()->getTerminator()->getSuccessor(Idx: 0));
301
302 // Partition blocks in an outer/inner loop pair into blocks before and after
303 // the loop
304 BasicBlockSet SubLoopBlocks;
305 BasicBlockSet ForeBlocks;
306 BasicBlockSet AftBlocks;
307 partitionOuterLoopBlocks(L, SubLoop, ForeBlocks, SubLoopBlocks, AftBlocks,
308 DT);
309
310 // We keep track of the entering/first and exiting/last block of each of
311 // Fore/SubLoop/Aft in each iteration. This helps make the stapling up of
312 // blocks easier.
313 std::vector<BasicBlock *> ForeBlocksFirst;
314 std::vector<BasicBlock *> ForeBlocksLast;
315 std::vector<BasicBlock *> SubLoopBlocksFirst;
316 std::vector<BasicBlock *> SubLoopBlocksLast;
317 std::vector<BasicBlock *> AftBlocksFirst;
318 std::vector<BasicBlock *> AftBlocksLast;
319 ForeBlocksFirst.push_back(x: Header);
320 ForeBlocksLast.push_back(x: SubLoop->getLoopPreheader());
321 SubLoopBlocksFirst.push_back(x: SubLoop->getHeader());
322 SubLoopBlocksLast.push_back(x: SubLoop->getExitingBlock());
323 AftBlocksFirst.push_back(x: SubLoop->getExitBlock());
324 AftBlocksLast.push_back(x: L->getExitingBlock());
325 // Maps Blocks[0] -> Blocks[It]
326 ValueToValueMapTy LastValueMap;
327
328 // Move any instructions from fore phi operands from AftBlocks into Fore.
329 moveHeaderPhiOperandsToForeBlocks(
330 Header, Latch: LatchBlock, InsertLoc: ForeBlocksLast[0]->getTerminator()->getIterator(),
331 AftBlocks);
332
333 // The current on-the-fly SSA update requires blocks to be processed in
334 // reverse postorder so that LastValueMap contains the correct value at each
335 // exit.
336 LoopBlocksDFS DFS(L);
337 DFS.perform(LI);
338 // Stash the DFS iterators before adding blocks to the loop.
339 LoopBlocksDFS::RPOIterator BlockBegin = DFS.beginRPO();
340 LoopBlocksDFS::RPOIterator BlockEnd = DFS.endRPO();
341
342 // When a FSDiscriminator is enabled, we don't need to add the multiply
343 // factors to the discriminators.
344 if (Header->getParent()->shouldEmitDebugInfoForProfiling() &&
345 !EnableFSDiscriminator)
346 for (BasicBlock *BB : L->getBlocks())
347 for (Instruction &I : *BB)
348 if (!I.isDebugOrPseudoInst())
349 if (const DILocation *DIL = I.getDebugLoc()) {
350 auto NewDIL = DIL->cloneByMultiplyingDuplicationFactor(DF: Count);
351 if (NewDIL)
352 I.setDebugLoc(*NewDIL);
353 else
354 LLVM_DEBUG(dbgs()
355 << "Failed to create new discriminator: "
356 << DIL->getFilename() << " Line: " << DIL->getLine());
357 }
358
359 // Copy all blocks
360 for (unsigned It = 1; It != Count; ++It) {
361 SmallVector<BasicBlock *, 8> NewBlocks;
362 // Maps Blocks[It] -> Blocks[It-1]
363 DenseMap<Value *, Value *> PrevItValueMap;
364 SmallDenseMap<const Loop *, Loop *, 4> NewLoops;
365 NewLoops[L] = L;
366 NewLoops[SubLoop] = SubLoop;
367
368 for (LoopBlocksDFS::RPOIterator BB = BlockBegin; BB != BlockEnd; ++BB) {
369 ValueToValueMapTy VMap;
370 BasicBlock *New = CloneBasicBlock(BB: *BB, VMap, NameSuffix: "." + Twine(It));
371 Header->getParent()->insert(Position: Header->getParent()->end(), BB: New);
372
373 // Tell LI about New.
374 addClonedBlockToLoopInfo(OriginalBB: *BB, ClonedBB: New, LI, NewLoops);
375
376 if (ForeBlocks.count(Ptr: *BB)) {
377 if (*BB == ForeBlocksFirst[0])
378 ForeBlocksFirst.push_back(x: New);
379 if (*BB == ForeBlocksLast[0])
380 ForeBlocksLast.push_back(x: New);
381 } else if (SubLoopBlocks.count(Ptr: *BB)) {
382 if (*BB == SubLoopBlocksFirst[0])
383 SubLoopBlocksFirst.push_back(x: New);
384 if (*BB == SubLoopBlocksLast[0])
385 SubLoopBlocksLast.push_back(x: New);
386 } else if (AftBlocks.count(Ptr: *BB)) {
387 if (*BB == AftBlocksFirst[0])
388 AftBlocksFirst.push_back(x: New);
389 if (*BB == AftBlocksLast[0])
390 AftBlocksLast.push_back(x: New);
391 } else {
392 llvm_unreachable("BB being cloned should be in Fore/Sub/Aft");
393 }
394
395 // Update our running maps of newest clones
396 auto &Last = LastValueMap[*BB];
397 PrevItValueMap[New] = (It == 1 ? *BB : Last);
398 Last = New;
399 for (ValueToValueMapTy::iterator VI = VMap.begin(), VE = VMap.end();
400 VI != VE; ++VI) {
401 auto &LVM = LastValueMap[VI->first];
402 PrevItValueMap[VI->second] =
403 const_cast<Value *>(It == 1 ? VI->first : LVM);
404 LVM = VI->second;
405 }
406
407 NewBlocks.push_back(Elt: New);
408
409 // Update DomTree:
410 if (*BB == ForeBlocksFirst[0])
411 DT->addNewBlock(BB: New, DomBB: ForeBlocksLast[It - 1]);
412 else if (*BB == SubLoopBlocksFirst[0])
413 DT->addNewBlock(BB: New, DomBB: SubLoopBlocksLast[It - 1]);
414 else if (*BB == AftBlocksFirst[0])
415 DT->addNewBlock(BB: New, DomBB: AftBlocksLast[It - 1]);
416 else {
417 // Each set of blocks (Fore/Sub/Aft) will have the same internal domtree
418 // structure.
419 auto BBDomNode = DT->getNode(BB: *BB);
420 auto BBIDom = BBDomNode->getIDom();
421 BasicBlock *OriginalBBIDom = BBIDom->getBlock();
422 assert(OriginalBBIDom);
423 assert(LastValueMap[cast<Value>(OriginalBBIDom)]);
424 DT->addNewBlock(
425 BB: New, DomBB: cast<BasicBlock>(Val&: LastValueMap[cast<Value>(Val: OriginalBBIDom)]));
426 }
427 }
428
429 // Remap all instructions in the most recent iteration
430 remapInstructionsInBlocks(Blocks: NewBlocks, VMap&: LastValueMap);
431 for (BasicBlock *NewBlock : NewBlocks) {
432 for (Instruction &I : *NewBlock) {
433 if (auto *II = dyn_cast<AssumeInst>(Val: &I))
434 AC->registerAssumption(CI: II);
435 }
436 }
437
438 // Alter the ForeBlocks phi's, pointing them at the latest version of the
439 // value from the previous iteration's phis
440 for (PHINode &Phi : ForeBlocksFirst[It]->phis()) {
441 Value *OldValue = Phi.getIncomingValueForBlock(BB: AftBlocksLast[It]);
442 assert(OldValue && "should have incoming edge from Aft[It]");
443 Value *NewValue = OldValue;
444 if (Value *PrevValue = PrevItValueMap[OldValue])
445 NewValue = PrevValue;
446
447 assert(Phi.getNumOperands() == 2);
448 Phi.setIncomingBlock(i: 0, BB: ForeBlocksLast[It - 1]);
449 Phi.setIncomingValue(i: 0, V: NewValue);
450 Phi.removeIncomingValue(Idx: 1);
451 }
452 }
453
454 // Now that all the basic blocks for the unrolled iterations are in place,
455 // finish up connecting the blocks and phi nodes. At this point LastValueMap
456 // is the last unrolled iterations values.
457
458 // Update Phis in BB from OldBB to point to NewBB and use the latest value
459 // from LastValueMap
460 auto updatePHIBlocksAndValues = [](BasicBlock *BB, BasicBlock *OldBB,
461 BasicBlock *NewBB,
462 ValueToValueMapTy &LastValueMap) {
463 for (PHINode &Phi : BB->phis()) {
464 for (unsigned b = 0; b < Phi.getNumIncomingValues(); ++b) {
465 if (Phi.getIncomingBlock(i: b) == OldBB) {
466 Value *OldValue = Phi.getIncomingValue(i: b);
467 if (Value *LastValue = LastValueMap[OldValue])
468 Phi.setIncomingValue(i: b, V: LastValue);
469 Phi.setIncomingBlock(i: b, BB: NewBB);
470 break;
471 }
472 }
473 }
474 };
475 // Move all the phis from Src into Dest
476 auto movePHIs = [](BasicBlock *Src, BasicBlock *Dest) {
477 BasicBlock::iterator insertPoint = Dest->getFirstNonPHIIt();
478 while (PHINode *Phi = dyn_cast<PHINode>(Val: Src->begin()))
479 Phi->moveBefore(BB&: *Dest, I: insertPoint);
480 };
481
482 // Update the PHI values outside the loop to point to the last block
483 updatePHIBlocksAndValues(LoopExit, AftBlocksLast[0], AftBlocksLast.back(),
484 LastValueMap);
485
486 // Update ForeBlocks successors and phi nodes
487 UncondBrInst *ForeTerm =
488 cast<UncondBrInst>(Val: ForeBlocksLast.back()->getTerminator());
489 ForeTerm->setSuccessor(SubLoopBlocksFirst[0]);
490
491 if (CompletelyUnroll) {
492 while (PHINode *Phi = dyn_cast<PHINode>(Val: ForeBlocksFirst[0]->begin())) {
493 Phi->replaceAllUsesWith(V: Phi->getIncomingValueForBlock(BB: Preheader));
494 Phi->eraseFromParent();
495 }
496 } else {
497 // Update the PHI values to point to the last aft block
498 updatePHIBlocksAndValues(ForeBlocksFirst[0], AftBlocksLast[0],
499 AftBlocksLast.back(), LastValueMap);
500 }
501
502 for (unsigned It = 1; It != Count; It++) {
503 // Remap ForeBlock successors from previous iteration to this
504 UncondBrInst *ForeTerm =
505 cast<UncondBrInst>(Val: ForeBlocksLast[It - 1]->getTerminator());
506 ForeTerm->setSuccessor(ForeBlocksFirst[It]);
507 }
508
509 // Subloop successors and phis
510 CondBrInst *SubTerm =
511 cast<CondBrInst>(Val: SubLoopBlocksLast.back()->getTerminator());
512 SubTerm->setSuccessor(idx: !SubLoopContinueOnTrue, NewSucc: SubLoopBlocksFirst[0]);
513 SubTerm->setSuccessor(idx: SubLoopContinueOnTrue, NewSucc: AftBlocksFirst[0]);
514 SubLoopBlocksFirst[0]->replacePhiUsesWith(Old: ForeBlocksLast[0],
515 New: ForeBlocksLast.back());
516 SubLoopBlocksFirst[0]->replacePhiUsesWith(Old: SubLoopBlocksLast[0],
517 New: SubLoopBlocksLast.back());
518
519 for (unsigned It = 1; It != Count; It++) {
520 // Replace the conditional branch of the previous iteration subloop with an
521 // unconditional one to this one
522 CondBrInst *SubTerm =
523 cast<CondBrInst>(Val: SubLoopBlocksLast[It - 1]->getTerminator());
524 UncondBrInst::Create(IfTrue: SubLoopBlocksFirst[It], InsertBefore: SubTerm->getIterator());
525 SubTerm->eraseFromParent();
526
527 SubLoopBlocksFirst[It]->replacePhiUsesWith(Old: ForeBlocksLast[It],
528 New: ForeBlocksLast.back());
529 SubLoopBlocksFirst[It]->replacePhiUsesWith(Old: SubLoopBlocksLast[It],
530 New: SubLoopBlocksLast.back());
531 movePHIs(SubLoopBlocksFirst[It], SubLoopBlocksFirst[0]);
532 }
533
534 // Aft blocks successors and phis
535 CondBrInst *AftTerm = cast<CondBrInst>(Val: AftBlocksLast.back()->getTerminator());
536 if (CompletelyUnroll) {
537 UncondBrInst::Create(IfTrue: LoopExit, InsertBefore: AftTerm->getIterator());
538 AftTerm->eraseFromParent();
539 } else {
540 AftTerm->setSuccessor(idx: !ContinueOnTrue, NewSucc: ForeBlocksFirst[0]);
541 assert(AftTerm->getSuccessor(ContinueOnTrue) == LoopExit &&
542 "Expecting the ContinueOnTrue successor of AftTerm to be LoopExit");
543 }
544 AftBlocksFirst[0]->replacePhiUsesWith(Old: SubLoopBlocksLast[0],
545 New: SubLoopBlocksLast.back());
546
547 for (unsigned It = 1; It != Count; It++) {
548 // Replace the conditional branch of the previous iteration subloop with an
549 // unconditional one to this one
550 CondBrInst *AftTerm =
551 cast<CondBrInst>(Val: AftBlocksLast[It - 1]->getTerminator());
552 UncondBrInst::Create(IfTrue: AftBlocksFirst[It], InsertBefore: AftTerm->getIterator());
553 AftTerm->eraseFromParent();
554
555 AftBlocksFirst[It]->replacePhiUsesWith(Old: SubLoopBlocksLast[It],
556 New: SubLoopBlocksLast.back());
557 movePHIs(AftBlocksFirst[It], AftBlocksFirst[0]);
558 }
559
560 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
561 // Dominator Tree. Remove the old links between Fore, Sub and Aft, adding the
562 // new ones required.
563 if (Count != 1) {
564 SmallVector<DominatorTree::UpdateType, 4> DTUpdates;
565 DTUpdates.emplace_back(Args: DominatorTree::UpdateKind::Delete, Args&: ForeBlocksLast[0],
566 Args&: SubLoopBlocksFirst[0]);
567 DTUpdates.emplace_back(Args: DominatorTree::UpdateKind::Delete,
568 Args&: SubLoopBlocksLast[0], Args&: AftBlocksFirst[0]);
569
570 DTUpdates.emplace_back(Args: DominatorTree::UpdateKind::Insert,
571 Args&: ForeBlocksLast.back(), Args&: SubLoopBlocksFirst[0]);
572 DTUpdates.emplace_back(Args: DominatorTree::UpdateKind::Insert,
573 Args&: SubLoopBlocksLast.back(), Args&: AftBlocksFirst[0]);
574 DTU.applyUpdatesPermissive(Updates: DTUpdates);
575 }
576
577 // Merge adjacent basic blocks, if possible.
578 SmallPtrSet<BasicBlock *, 16> MergeBlocks;
579 MergeBlocks.insert_range(R&: ForeBlocksLast);
580 MergeBlocks.insert_range(R&: SubLoopBlocksLast);
581 MergeBlocks.insert_range(R&: AftBlocksLast);
582
583 MergeBlockSuccessorsIntoGivenBlocks(MergeBlocks, L, DTU: &DTU, LI);
584
585 // Apply updates to the DomTree.
586 DT = &DTU.getDomTree();
587
588 // At this point, the code is well formed. We now do a quick sweep over the
589 // inserted code, doing constant propagation and dead code elimination as we
590 // go.
591 simplifyLoopAfterUnroll(L: SubLoop, SimplifyIVs: true, LI, SE, DT, AC, TTI);
592 simplifyLoopAfterUnroll(L, SimplifyIVs: !CompletelyUnroll && Count > 1, LI, SE, DT, AC,
593 TTI);
594
595 NumCompletelyUnrolledAndJammed += CompletelyUnroll;
596 ++NumUnrolledAndJammed;
597
598 // Update LoopInfo if the loop is completely removed.
599 if (CompletelyUnroll)
600 LI->erase(L);
601
602#ifndef NDEBUG
603 // We shouldn't have done anything to break loop simplify form or LCSSA.
604 Loop *OutestLoop = SubLoop->getParentLoop()
605 ? SubLoop->getParentLoop()->getParentLoop()
606 ? SubLoop->getParentLoop()->getParentLoop()
607 : SubLoop->getParentLoop()
608 : SubLoop;
609 assert(DT->verify());
610 LI->verify(*DT);
611 assert(OutestLoop->isRecursivelyLCSSAForm(*DT, *LI));
612 if (!CompletelyUnroll)
613 assert(L->isLoopSimplifyForm());
614 assert(SubLoop->isLoopSimplifyForm());
615 SE->verify();
616#endif
617
618 return CompletelyUnroll ? LoopUnrollResult::FullyUnrolled
619 : LoopUnrollResult::PartiallyUnrolled;
620}
621
622static bool getLoadsAndStores(BasicBlockSet &Blocks,
623 SmallVector<Instruction *, 4> &MemInstr) {
624 // Scan the BBs and collect legal loads and stores.
625 // Returns false if non-simple loads/stores are found.
626 for (BasicBlock *BB : Blocks) {
627 for (Instruction &I : *BB) {
628 if (auto *Ld = dyn_cast<LoadInst>(Val: &I)) {
629 if (!Ld->isSimple())
630 return false;
631 MemInstr.push_back(Elt: &I);
632 } else if (auto *St = dyn_cast<StoreInst>(Val: &I)) {
633 if (!St->isSimple())
634 return false;
635 MemInstr.push_back(Elt: &I);
636 } else if (I.mayReadOrWriteMemory()) {
637 return false;
638 }
639 }
640 }
641 return true;
642}
643
644static bool preservesForwardDependence(Instruction *Src, Instruction *Dst,
645 unsigned UnrollLevel, unsigned JamLevel,
646 bool Sequentialized, Dependence *D) {
647 // UnrollLevel might carry the dependency Src --> Dst
648 // Does a different loop after unrolling?
649 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
650 ++CurLoopDepth) {
651 auto JammedDir = D->getDirection(Level: CurLoopDepth);
652 if (JammedDir == Dependence::DVEntry::LT)
653 return true;
654
655 if (JammedDir & Dependence::DVEntry::GT)
656 return false;
657 }
658
659 return true;
660}
661
662static bool preservesBackwardDependence(Instruction *Src, Instruction *Dst,
663 unsigned UnrollLevel, unsigned JamLevel,
664 bool Sequentialized, Dependence *D) {
665 // UnrollLevel might carry the dependency Dst --> Src
666 for (unsigned CurLoopDepth = UnrollLevel + 1; CurLoopDepth <= JamLevel;
667 ++CurLoopDepth) {
668 auto JammedDir = D->getDirection(Level: CurLoopDepth);
669 if (JammedDir == Dependence::DVEntry::GT)
670 return true;
671
672 if (JammedDir & Dependence::DVEntry::LT)
673 return false;
674 }
675
676 // Backward dependencies are only preserved if not interleaved.
677 return Sequentialized;
678}
679
680// Check whether it is semantically safe Src and Dst considering any potential
681// dependency between them.
682//
683// @param UnrollLevel The level of the loop being unrolled
684// @param JamLevel The level of the loop being jammed; if Src and Dst are on
685// different levels, the outermost common loop counts as jammed level
686//
687// @return true if is safe and false if there is a dependency violation.
688static bool checkDependency(Instruction *Src, Instruction *Dst,
689 unsigned UnrollLevel, unsigned JamLevel,
690 bool Sequentialized, DependenceInfo &DI) {
691 assert(UnrollLevel <= JamLevel &&
692 "Expecting JamLevel to be at least UnrollLevel");
693
694 if (Src == Dst)
695 return true;
696 // Ignore Input dependencies.
697 if (isa<LoadInst>(Val: Src) && isa<LoadInst>(Val: Dst))
698 return true;
699
700 // Check whether unroll-and-jam may violate a dependency.
701 // By construction, every dependency will be lexicographically non-negative
702 // (if it was, it would violate the current execution order), such as
703 // (0,0,>,*,*)
704 // Unroll-and-jam changes the GT execution of two executions to the same
705 // iteration of the chosen unroll level. That is, a GT dependence becomes a GE
706 // dependence (or EQ, if we fully unrolled the loop) at the loop's position:
707 // (0,0,>=,*,*)
708 // Now, the dependency is not necessarily non-negative anymore, i.e.
709 // unroll-and-jam may violate correctness.
710 std::unique_ptr<Dependence> D = DI.depends(Src, Dst);
711 if (!D)
712 return true;
713 assert(D->isOrdered() && "Expected an output, flow or anti dep.");
714
715 if (D->isConfused()) {
716 LLVM_DEBUG(dbgs() << " Confused dependency between:\n"
717 << " " << *Src << "\n"
718 << " " << *Dst << "\n");
719 return false;
720 }
721
722 // If outer levels (levels enclosing the loop being unroll-and-jammed) have a
723 // non-equal direction, then the locations accessed in the inner levels cannot
724 // overlap in memory. We assumes the indexes never overlap into neighboring
725 // dimensions.
726 for (unsigned CurLoopDepth = 1; CurLoopDepth < UnrollLevel; ++CurLoopDepth)
727 if (!(D->getDirection(Level: CurLoopDepth) & Dependence::DVEntry::EQ))
728 return true;
729
730 auto UnrollDirection = D->getDirection(Level: UnrollLevel);
731
732 // If the distance carried by the unrolled loop is 0, then after unrolling
733 // that distance will become non-zero resulting in non-overlapping accesses in
734 // the inner loops.
735 if (UnrollDirection == Dependence::DVEntry::EQ)
736 return true;
737
738 if (UnrollDirection & Dependence::DVEntry::LT &&
739 !preservesForwardDependence(Src, Dst, UnrollLevel, JamLevel,
740 Sequentialized, D: D.get()))
741 return false;
742
743 if (UnrollDirection & Dependence::DVEntry::GT &&
744 !preservesBackwardDependence(Src, Dst, UnrollLevel, JamLevel,
745 Sequentialized, D: D.get()))
746 return false;
747
748 return true;
749}
750
751static bool
752checkDependencies(Loop &Root, const BasicBlockSet &SubLoopBlocks,
753 const DenseMap<Loop *, BasicBlockSet> &ForeBlocksMap,
754 const DenseMap<Loop *, BasicBlockSet> &AftBlocksMap,
755 DependenceInfo &DI, LoopInfo &LI) {
756 SmallVector<BasicBlockSet, 8> AllBlocks;
757 for (Loop *L : Root.getLoopsInPreorder())
758 if (ForeBlocksMap.contains(Val: L))
759 AllBlocks.push_back(Elt: ForeBlocksMap.lookup(Val: L));
760 AllBlocks.push_back(Elt: SubLoopBlocks);
761 for (Loop *L : Root.getLoopsInPreorder())
762 if (AftBlocksMap.contains(Val: L))
763 AllBlocks.push_back(Elt: AftBlocksMap.lookup(Val: L));
764
765 unsigned LoopDepth = Root.getLoopDepth();
766 SmallVector<Instruction *, 4> EarlierLoadsAndStores;
767 SmallVector<Instruction *, 4> CurrentLoadsAndStores;
768 for (BasicBlockSet &Blocks : AllBlocks) {
769 CurrentLoadsAndStores.clear();
770 if (!getLoadsAndStores(Blocks, MemInstr&: CurrentLoadsAndStores))
771 return false;
772
773 Loop *CurLoop = LI.getLoopFor(BB: (*Blocks.begin())->front().getParent());
774 unsigned CurLoopDepth = CurLoop->getLoopDepth();
775
776 for (auto *Earlier : EarlierLoadsAndStores) {
777 Loop *EarlierLoop = LI.getLoopFor(BB: Earlier->getParent());
778 unsigned EarlierDepth = EarlierLoop->getLoopDepth();
779 unsigned CommonLoopDepth = std::min(a: EarlierDepth, b: CurLoopDepth);
780 for (auto *Later : CurrentLoadsAndStores) {
781 if (!checkDependency(Src: Earlier, Dst: Later, UnrollLevel: LoopDepth, JamLevel: CommonLoopDepth, Sequentialized: false,
782 DI))
783 return false;
784 }
785 }
786
787 size_t NumInsts = CurrentLoadsAndStores.size();
788 for (size_t I = 0; I < NumInsts; ++I) {
789 for (size_t J = I; J < NumInsts; ++J) {
790 if (!checkDependency(Src: CurrentLoadsAndStores[I], Dst: CurrentLoadsAndStores[J],
791 UnrollLevel: LoopDepth, JamLevel: CurLoopDepth, Sequentialized: true, DI))
792 return false;
793 }
794 }
795
796 EarlierLoadsAndStores.append(in_start: CurrentLoadsAndStores.begin(),
797 in_end: CurrentLoadsAndStores.end());
798 }
799 return true;
800}
801
802static bool isEligibleLoopForm(const Loop &Root) {
803 // Root must have a child.
804 if (Root.getSubLoops().size() != 1)
805 return false;
806
807 const Loop *L = &Root;
808 do {
809 // All loops in Root need to be in simplify and rotated form.
810 if (!L->isLoopSimplifyForm())
811 return false;
812
813 if (!L->isRotatedForm())
814 return false;
815
816 if (L->getHeader()->hasAddressTaken()) {
817 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Address taken\n");
818 return false;
819 }
820
821 unsigned SubLoopsSize = L->getSubLoops().size();
822 if (SubLoopsSize == 0)
823 return true;
824
825 // Only one child is allowed.
826 if (SubLoopsSize != 1)
827 return false;
828
829 // Only loops with a single exit block can be unrolled and jammed.
830 // The function getExitBlock() is used for this check, rather than
831 // getUniqueExitBlock() to ensure loops with mulitple exit edges are
832 // disallowed.
833 if (!L->getExitBlock()) {
834 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single exit "
835 "blocks can be unrolled and jammed.\n");
836 return false;
837 }
838
839 // Only loops with a single exiting block can be unrolled and jammed.
840 if (!L->getExitingBlock()) {
841 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; only loops with single "
842 "exiting blocks can be unrolled and jammed.\n");
843 return false;
844 }
845
846 L = L->getSubLoops()[0];
847 } while (L);
848
849 return true;
850}
851
852static Loop *getInnerMostLoop(Loop *L) {
853 while (!L->getSubLoops().empty())
854 L = L->getSubLoops()[0];
855 return L;
856}
857
858bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
859 DependenceInfo &DI, LoopInfo &LI) {
860 if (!isEligibleLoopForm(Root: *L)) {
861 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Ineligible loop form\n");
862 return false;
863 }
864
865 /* We currently handle outer loops like this:
866 |
867 ForeFirst <------\ }
868 Blocks | } ForeBlocks of L
869 ForeLast | }
870 | |
871 ... |
872 | |
873 ForeFirst <----\ | }
874 Blocks | | } ForeBlocks of a inner loop of L
875 ForeLast | | }
876 | | |
877 JamLoopFirst <\ | | }
878 Blocks | | | } JamLoopBlocks of the innermost loop
879 JamLoopLast -/ | | }
880 | | |
881 AftFirst | | }
882 Blocks | | } AftBlocks of a inner loop of L
883 AftLast ------/ | }
884 | |
885 ... |
886 | |
887 AftFirst | }
888 Blocks | } AftBlocks of L
889 AftLast --------/ }
890 |
891
892 There are (theoretically) any number of blocks in ForeBlocks, SubLoopBlocks
893 and AftBlocks, providing that there is one edge from Fores to SubLoops,
894 one edge from SubLoops to Afts and a single outer loop exit (from Afts).
895 In practice we currently limit Aft blocks to a single block, and limit
896 things further in the profitablility checks of the unroll and jam pass.
897
898 Because of the way we rearrange basic blocks, we also require that
899 the Fore blocks of L on all unrolled iterations are safe to move before the
900 blocks of the direct child of L of all iterations. So we require that the
901 phi node looping operands of ForeHeader can be moved to at least the end of
902 ForeEnd, so that we can arrange cloned Fore Blocks before the subloop and
903 match up Phi's correctly.
904
905 i.e. The old order of blocks used to be
906 (F1)1 (F2)1 J1_1 J1_2 (A2)1 (A1)1 (F1)2 (F2)2 J2_1 J2_2 (A2)2 (A1)2.
907 It needs to be safe to transform this to
908 (F1)1 (F1)2 (F2)1 (F2)2 J1_1 J1_2 J2_1 J2_2 (A2)1 (A2)2 (A1)1 (A1)2.
909
910 There are then a number of checks along the lines of no calls, no
911 exceptions, inner loop IV is consistent, etc. Note that for loops requiring
912 runtime unrolling, UnrollRuntimeLoopRemainder can also fail in
913 UnrollAndJamLoop if the trip count cannot be easily calculated.
914 */
915
916 // Split blocks into Fore/SubLoop/Aft based on dominators
917 Loop *JamLoop = getInnerMostLoop(L);
918 BasicBlockSet SubLoopBlocks;
919 DenseMap<Loop *, BasicBlockSet> ForeBlocksMap;
920 DenseMap<Loop *, BasicBlockSet> AftBlocksMap;
921 if (!partitionOuterLoopBlocks(Root&: *L, JamLoop&: *JamLoop, JamLoopBlocks&: SubLoopBlocks, ForeBlocksMap,
922 AftBlocksMap, DT)) {
923 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Incompatible loop layout\n");
924 return false;
925 }
926
927 // Aft blocks may need to move instructions to fore blocks, which becomes more
928 // difficult if there are multiple (potentially conditionally executed)
929 // blocks. For now we just exclude loops with multiple aft blocks.
930 if (AftBlocksMap[L].size() != 1) {
931 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Can't currently handle "
932 "multiple blocks after the loop\n");
933 return false;
934 }
935
936 // Check inner loop backedge count is consistent on all iterations of the
937 // outer loop
938 if (any_of(Range: L->getLoopsInPreorder(), P: [&SE](Loop *SubLoop) {
939 return !hasIterationCountInvariantInParent(L: SubLoop, SE);
940 })) {
941 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "
942 "not consistent on each iteration\n");
943 return false;
944 }
945
946 // Check the loop safety info for exceptions.
947 SimpleLoopSafetyInfo LSI;
948 LSI.computeLoopSafetyInfo(CurLoop: L);
949 if (LSI.anyBlockMayThrow()) {
950 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");
951 return false;
952 }
953
954 // We've ruled out the easy stuff and now need to check that there are no
955 // interdependencies which may prevent us from moving the:
956 // ForeBlocks before Subloop and AftBlocks.
957 // Subloop before AftBlocks.
958 // ForeBlock phi operands before the subloop
959
960 // Make sure we can move all instructions we need to before the subloop
961 BasicBlock *Header = L->getHeader();
962 BasicBlock *Latch = L->getLoopLatch();
963 BasicBlockSet AftBlocks = AftBlocksMap[L];
964 Loop *SubLoop = L->getSubLoops()[0];
965 if (!processHeaderPhiOperands(
966 Header, Latch, AftBlocks, Visit: [&AftBlocks, &SubLoop](Instruction *I) {
967 if (SubLoop->contains(BB: I->getParent()))
968 return false;
969 if (AftBlocks.count(Ptr: I->getParent())) {
970 // If we hit a phi node in afts we know we are done (probably
971 // LCSSA)
972 if (isa<PHINode>(Val: I))
973 return false;
974 // Can't move instructions with side effects or memory
975 // reads/writes
976 if (I->mayHaveSideEffects() || I->mayReadOrWriteMemory())
977 return false;
978 }
979 // Keep going
980 return true;
981 })) {
982 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; can't move required "
983 "instructions after subloop to before it\n");
984 return false;
985 }
986
987 // Check for memory dependencies which prohibit the unrolling we are doing.
988 // Because of the way we are unrolling Fore/Sub/Aft blocks, we need to check
989 // there are no dependencies between Fore-Sub, Fore-Aft, Sub-Aft and Sub-Sub.
990 if (!checkDependencies(Root&: *L, SubLoopBlocks, ForeBlocksMap, AftBlocksMap, DI,
991 LI)) {
992 LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; failed dependency check\n");
993 return false;
994 }
995
996 return true;
997}
998