lib/Transforms/Utils/LoopVersioning.cpp

   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
  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
  39 void LoopVersioning::setAliasChecks(
  40     const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
  41   AliasChecks = std::move(Checks);
  42 }
  43
  44 void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) {
  45   Preds = std::move(Check);
  46 }
  47
  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
 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 }