1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
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 defines a utility class to perform loop versioning.  The versioned
11 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
12 // emits checks to prove this.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Analysis/LoopAccessAnalysis.h"
17 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/Dominators.h"
19 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
20 #include "llvm/Transforms/Utils/Cloning.h"
21 #include "llvm/Transforms/Utils/LoopVersioning.h"
22 
23 using namespace llvm;
24 
25 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
26                                DominatorTree *DT,
27                                const SmallVector<int, 8> *PtrToPartition)
28     : VersionedLoop(L), NonVersionedLoop(nullptr),
29       PtrToPartition(PtrToPartition), LAI(LAI), LI(LI), DT(DT) {
30   assert(L->getExitBlock() && "No single exit block");
31   assert(L->getLoopPreheader() && "No preheader");
32 }
33 
34 bool LoopVersioning::needsRuntimeChecks() const {
35   return LAI.getRuntimePointerChecking()->needsAnyChecking(PtrToPartition);
36 }
37 
38 void LoopVersioning::versionLoop(Pass *P) {
39   Instruction *FirstCheckInst;
40   Instruction *MemRuntimeCheck;
41   // Add the memcheck in the original preheader (this is empty initially).
42   BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
43   std::tie(FirstCheckInst, MemRuntimeCheck) =
44       LAI.addRuntimeCheck(MemCheckBB->getTerminator(), PtrToPartition);
45   assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
46 
47   // Rename the block to make the IR more readable.
48   MemCheckBB->setName(VersionedLoop->getHeader()->getName() + ".lver.memcheck");
49 
50   // Create empty preheader for the loop (and after cloning for the
51   // non-versioned loop).
52   BasicBlock *PH = SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
53   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
54 
55   // Clone the loop including the preheader.
56   //
57   // FIXME: This does not currently preserve SimplifyLoop because the exit
58   // block is a join between the two loops.
59   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
60   NonVersionedLoop =
61       cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap, ".lver.orig",
62                              LI, DT, NonVersionedLoopBlocks);
63   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
64 
65   // Insert the conditional branch based on the result of the memchecks.
66   Instruction *OrigTerm = MemCheckBB->getTerminator();
67   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
68                      VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
69                      OrigTerm);
70   OrigTerm->eraseFromParent();
71 
72   // The loops merge in the original exit block.  This is now dominated by the
73   // memchecking block.
74   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
75 }
76 
77 void LoopVersioning::addPHINodes(
78     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
79   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
80   assert(PHIBlock && "No single successor to loop exit block");
81 
82   for (auto *Inst : DefsUsedOutside) {
83     auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
84     PHINode *PN;
85 
86     // First see if we have a single-operand PHI with the value defined by the
87     // original loop.
88     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
89       assert(PN->getNumOperands() == 1 &&
90              "Exit block should only have on predecessor");
91       if (PN->getIncomingValue(0) == Inst)
92         break;
93     }
94     // If not create it.
95     if (!PN) {
96       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
97                            PHIBlock->begin());
98       for (auto *User : Inst->users())
99         if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
100           User->replaceUsesOfWith(Inst, PN);
101       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
102     }
103     // Add the new incoming value from the non-versioned loop.
104     PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());
105   }
106 }
107