LoopVersioning.cpp revision 296417
1286425Sdim//===- LoopVersioning.cpp - Utility to version a loop ---------------------===// 2286425Sdim// 3286425Sdim// The LLVM Compiler Infrastructure 4286425Sdim// 5286425Sdim// This file is distributed under the University of Illinois Open Source 6286425Sdim// License. See LICENSE.TXT for details. 7286425Sdim// 8286425Sdim//===----------------------------------------------------------------------===// 9286425Sdim// 10286425Sdim// This file defines a utility class to perform loop versioning. The versioned 11286425Sdim// loop speculates that otherwise may-aliasing memory accesses don't overlap and 12286425Sdim// emits checks to prove this. 13286425Sdim// 14286425Sdim//===----------------------------------------------------------------------===// 15286425Sdim 16296417Sdim#include "llvm/Transforms/Utils/LoopVersioning.h" 17286425Sdim#include "llvm/Analysis/LoopAccessAnalysis.h" 18286425Sdim#include "llvm/Analysis/LoopInfo.h" 19296417Sdim#include "llvm/Analysis/ScalarEvolutionExpander.h" 20286425Sdim#include "llvm/IR/Dominators.h" 21286425Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 22286425Sdim#include "llvm/Transforms/Utils/Cloning.h" 23286425Sdim 24286425Sdimusing namespace llvm; 25286425Sdim 26286425SdimLoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, 27296417Sdim DominatorTree *DT, ScalarEvolution *SE, 28296417Sdim bool UseLAIChecks) 29296417Sdim : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT), 30296417Sdim SE(SE) { 31286425Sdim assert(L->getExitBlock() && "No single exit block"); 32286425Sdim assert(L->getLoopPreheader() && "No preheader"); 33296417Sdim if (UseLAIChecks) { 34296417Sdim setAliasChecks(LAI.getRuntimePointerChecking()->getChecks()); 35296417Sdim setSCEVChecks(LAI.PSE.getUnionPredicate()); 36296417Sdim } 37286425Sdim} 38286425Sdim 39296417Sdimvoid LoopVersioning::setAliasChecks( 40296417Sdim const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) { 41296417Sdim AliasChecks = std::move(Checks); 42286425Sdim} 43286425Sdim 44296417Sdimvoid LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) { 45296417Sdim Preds = std::move(Check); 46296417Sdim} 47296417Sdim 48296417Sdimvoid LoopVersioning::versionLoop( 49296417Sdim const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 50286425Sdim Instruction *FirstCheckInst; 51286425Sdim Instruction *MemRuntimeCheck; 52296417Sdim Value *SCEVRuntimeCheck; 53296417Sdim Value *RuntimeCheck = nullptr; 54296417Sdim 55286425Sdim // Add the memcheck in the original preheader (this is empty initially). 56296417Sdim BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader(); 57286425Sdim std::tie(FirstCheckInst, MemRuntimeCheck) = 58296417Sdim LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks); 59286425Sdim assert(MemRuntimeCheck && "called even though needsAnyChecking = false"); 60286425Sdim 61296417Sdim const SCEVUnionPredicate &Pred = LAI.PSE.getUnionPredicate(); 62296417Sdim SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(), 63296417Sdim "scev.check"); 64296417Sdim SCEVRuntimeCheck = 65296417Sdim Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator()); 66296417Sdim auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck); 67296417Sdim 68296417Sdim // Discard the SCEV runtime check if it is always true. 69296417Sdim if (CI && CI->isZero()) 70296417Sdim SCEVRuntimeCheck = nullptr; 71296417Sdim 72296417Sdim if (MemRuntimeCheck && SCEVRuntimeCheck) { 73296417Sdim RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck, 74296417Sdim SCEVRuntimeCheck, "ldist.safe"); 75296417Sdim if (auto *I = dyn_cast<Instruction>(RuntimeCheck)) 76296417Sdim I->insertBefore(RuntimeCheckBB->getTerminator()); 77296417Sdim } else 78296417Sdim RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck; 79296417Sdim 80296417Sdim assert(RuntimeCheck && "called even though we don't need " 81296417Sdim "any runtime checks"); 82296417Sdim 83286425Sdim // Rename the block to make the IR more readable. 84296417Sdim RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() + 85296417Sdim ".lver.check"); 86286425Sdim 87286425Sdim // Create empty preheader for the loop (and after cloning for the 88286425Sdim // non-versioned loop). 89296417Sdim BasicBlock *PH = 90296417Sdim SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI); 91286425Sdim PH->setName(VersionedLoop->getHeader()->getName() + ".ph"); 92286425Sdim 93286425Sdim // Clone the loop including the preheader. 94286425Sdim // 95286425Sdim // FIXME: This does not currently preserve SimplifyLoop because the exit 96286425Sdim // block is a join between the two loops. 97286425Sdim SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks; 98286425Sdim NonVersionedLoop = 99296417Sdim cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap, 100296417Sdim ".lver.orig", LI, DT, NonVersionedLoopBlocks); 101286425Sdim remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap); 102286425Sdim 103286425Sdim // Insert the conditional branch based on the result of the memchecks. 104296417Sdim Instruction *OrigTerm = RuntimeCheckBB->getTerminator(); 105286425Sdim BranchInst::Create(NonVersionedLoop->getLoopPreheader(), 106296417Sdim VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm); 107286425Sdim OrigTerm->eraseFromParent(); 108286425Sdim 109286425Sdim // The loops merge in the original exit block. This is now dominated by the 110286425Sdim // memchecking block. 111296417Sdim DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB); 112296417Sdim 113296417Sdim // Adds the necessary PHI nodes for the versioned loops based on the 114296417Sdim // loop-defined values used outside of the loop. 115296417Sdim addPHINodes(DefsUsedOutside); 116286425Sdim} 117286425Sdim 118286425Sdimvoid LoopVersioning::addPHINodes( 119286425Sdim const SmallVectorImpl<Instruction *> &DefsUsedOutside) { 120286425Sdim BasicBlock *PHIBlock = VersionedLoop->getExitBlock(); 121286425Sdim assert(PHIBlock && "No single successor to loop exit block"); 122286425Sdim 123286425Sdim for (auto *Inst : DefsUsedOutside) { 124286425Sdim auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]); 125286425Sdim PHINode *PN; 126286425Sdim 127286425Sdim // First see if we have a single-operand PHI with the value defined by the 128286425Sdim // original loop. 129286425Sdim for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) { 130286425Sdim assert(PN->getNumOperands() == 1 && 131286425Sdim "Exit block should only have on predecessor"); 132286425Sdim if (PN->getIncomingValue(0) == Inst) 133286425Sdim break; 134286425Sdim } 135286425Sdim // If not create it. 136286425Sdim if (!PN) { 137286425Sdim PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver", 138296417Sdim &PHIBlock->front()); 139286425Sdim for (auto *User : Inst->users()) 140286425Sdim if (!VersionedLoop->contains(cast<Instruction>(User)->getParent())) 141286425Sdim User->replaceUsesOfWith(Inst, PN); 142286425Sdim PN->addIncoming(Inst, VersionedLoop->getExitingBlock()); 143286425Sdim } 144286425Sdim // Add the new incoming value from the non-versioned loop. 145286425Sdim PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock()); 146286425Sdim } 147286425Sdim} 148