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