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/Analysis/ScalarEvolutionExpander.h"
21 #include "llvm/IR/Dominators.h"
22 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
23 #include "llvm/Transforms/Utils/Cloning.h"
24 
25 using namespace llvm;
26 
27 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
28                                DominatorTree *DT, ScalarEvolution *SE,
29                                bool UseLAIChecks)
30     : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
31       SE(SE) {
32   assert(L->getExitBlock() && "No single exit block");
33   assert(L->getLoopPreheader() && "No preheader");
34   if (UseLAIChecks) {
35     setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
36     setSCEVChecks(LAI.Preds);
37   }
38 }
39 
40 void LoopVersioning::setAliasChecks(
41     const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
42   AliasChecks = std::move(Checks);
43 }
44 
45 void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) {
46   Preds = std::move(Check);
47 }
48 
49 void LoopVersioning::versionLoop(
50     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
51   Instruction *FirstCheckInst;
52   Instruction *MemRuntimeCheck;
53   Value *SCEVRuntimeCheck;
54   Value *RuntimeCheck = nullptr;
55 
56   // Add the memcheck in the original preheader (this is empty initially).
57   BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
58   std::tie(FirstCheckInst, MemRuntimeCheck) =
59       LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
60   assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
61 
62   const SCEVUnionPredicate &Pred = LAI.Preds;
63   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
64                    "scev.check");
65   SCEVRuntimeCheck =
66       Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
67   auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
68 
69   // Discard the SCEV runtime check if it is always true.
70   if (CI && CI->isZero())
71     SCEVRuntimeCheck = nullptr;
72 
73   if (MemRuntimeCheck && SCEVRuntimeCheck) {
74     RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
75                                           SCEVRuntimeCheck, "ldist.safe");
76     if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
77       I->insertBefore(RuntimeCheckBB->getTerminator());
78   } else
79     RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
80 
81   assert(RuntimeCheck && "called even though we don't need "
82                          "any runtime checks");
83 
84   // Rename the block to make the IR more readable.
85   RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
86                           ".lver.check");
87 
88   // Create empty preheader for the loop (and after cloning for the
89   // non-versioned loop).
90   BasicBlock *PH =
91       SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI);
92   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
93 
94   // Clone the loop including the preheader.
95   //
96   // FIXME: This does not currently preserve SimplifyLoop because the exit
97   // block is a join between the two loops.
98   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
99   NonVersionedLoop =
100       cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
101                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
102   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
103 
104   // Insert the conditional branch based on the result of the memchecks.
105   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
106   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
107                      VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
108   OrigTerm->eraseFromParent();
109 
110   // The loops merge in the original exit block.  This is now dominated by the
111   // memchecking block.
112   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
113 
114   // Adds the necessary PHI nodes for the versioned loops based on the
115   // loop-defined values used outside of the loop.
116   addPHINodes(DefsUsedOutside);
117 }
118 
119 void LoopVersioning::addPHINodes(
120     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
121   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
122   assert(PHIBlock && "No single successor to loop exit block");
123 
124   for (auto *Inst : DefsUsedOutside) {
125     auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
126     PHINode *PN;
127 
128     // First see if we have a single-operand PHI with the value defined by the
129     // original loop.
130     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
131       assert(PN->getNumOperands() == 1 &&
132              "Exit block should only have on predecessor");
133       if (PN->getIncomingValue(0) == Inst)
134         break;
135     }
136     // If not create it.
137     if (!PN) {
138       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
139                            &PHIBlock->front());
140       for (auto *User : Inst->users())
141         if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
142           User->replaceUsesOfWith(Inst, PN);
143       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
144     }
145     // Add the new incoming value from the non-versioned loop.
146     PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());
147   }
148 }
149