1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
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"
25 LoopVersioning::LoopVersioning(
26 SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks,
27 const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT,
28 const SmallVector<int, 8> *PtrToPartition)
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");
35 void LoopVersioning::versionLoop(Pass *P) {
36 Instruction *FirstCheckInst;
37 Instruction *MemRuntimeCheck;
38 // Add the memcheck in the original preheader (this is empty initially).
39 BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
40 std::tie(FirstCheckInst, MemRuntimeCheck) =
41 LAI.addRuntimeCheck(MemCheckBB->getTerminator(), Checks);
42 assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
44 // Rename the block to make the IR more readable.
45 MemCheckBB->setName(VersionedLoop->getHeader()->getName() + ".lver.memcheck");
47 // Create empty preheader for the loop (and after cloning for the
48 // non-versioned loop).
49 BasicBlock *PH = SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
50 PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
52 // Clone the loop including the preheader.
54 // FIXME: This does not currently preserve SimplifyLoop because the exit
55 // block is a join between the two loops.
56 SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
58 cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap, ".lver.orig",
59 LI, DT, NonVersionedLoopBlocks);
60 remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
62 // Insert the conditional branch based on the result of the memchecks.
63 Instruction *OrigTerm = MemCheckBB->getTerminator();
64 BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
65 VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
67 OrigTerm->eraseFromParent();
69 // The loops merge in the original exit block. This is now dominated by the
71 DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
74 void LoopVersioning::addPHINodes(
75 const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
76 BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
77 assert(PHIBlock && "No single successor to loop exit block");
79 for (auto *Inst : DefsUsedOutside) {
80 auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
83 // First see if we have a single-operand PHI with the value defined by the
85 for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
86 assert(PN->getNumOperands() == 1 &&
87 "Exit block should only have on predecessor");
88 if (PN->getIncomingValue(0) == Inst)
93 PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
95 for (auto *User : Inst->users())
96 if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
97 User->replaceUsesOfWith(Inst, PN);
98 PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
100 // Add the new incoming value from the non-versioned loop.
101 PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());