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