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/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"
  22
  23 using namespace llvm;
  24
  25 LoopVersioning::LoopVersioning(
  26     SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks,
  27     const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI, DominatorTree *DT)
  28     : VersionedLoop(L), NonVersionedLoop(nullptr), Checks(std::move(Checks)),
  29       LAI(LAI), LI(LI), DT(DT) {
  30   assert(L->getExitBlock() && "No single exit block");
  31   assert(L->getLoopPreheader() && "No preheader");
  32 }
  33
  34 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAInfo, Loop *L,
  35                                LoopInfo *LI, DominatorTree *DT)
  36     : VersionedLoop(L), NonVersionedLoop(nullptr),
  37       Checks(LAInfo.getRuntimePointerChecking()->getChecks()), LAI(LAInfo),
  38       LI(LI), DT(DT) {
  39   assert(L->getExitBlock() && "No single exit block");
  40   assert(L->getLoopPreheader() && "No preheader");
  41 }
  42
  43 void LoopVersioning::versionLoop(
  44     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
  45   Instruction *FirstCheckInst;
  46   Instruction *MemRuntimeCheck;
  47   // Add the memcheck in the original preheader (this is empty initially).
  48   BasicBlock *MemCheckBB = VersionedLoop->getLoopPreheader();
  49   std::tie(FirstCheckInst, MemRuntimeCheck) =
  50       LAI.addRuntimeChecks(MemCheckBB->getTerminator(), Checks);
  51   assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
  52
  53   // Rename the block to make the IR more readable.
  54   MemCheckBB->setName(VersionedLoop->getHeader()->getName() + ".lver.memcheck");
  55
  56   // Create empty preheader for the loop (and after cloning for the
  57   // non-versioned loop).
  58   BasicBlock *PH = SplitBlock(MemCheckBB, MemCheckBB->getTerminator(), DT, LI);
  59   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
  60
  61   // Clone the loop including the preheader.
  62   //
  63   // FIXME: This does not currently preserve SimplifyLoop because the exit
  64   // block is a join between the two loops.
  65   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
  66   NonVersionedLoop =
  67       cloneLoopWithPreheader(PH, MemCheckBB, VersionedLoop, VMap, ".lver.orig",
  68                              LI, DT, NonVersionedLoopBlocks);
  69   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
  70
  71   // Insert the conditional branch based on the result of the memchecks.
  72   Instruction *OrigTerm = MemCheckBB->getTerminator();
  73   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
  74                      VersionedLoop->getLoopPreheader(), MemRuntimeCheck,
  75                      OrigTerm);
  76   OrigTerm->eraseFromParent();
  77
  78   // The loops merge in the original exit block.  This is now dominated by the
  79   // memchecking block.
  80   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), MemCheckBB);
  81
  82   // Adds the necessary PHI nodes for the versioned loops based on the
  83   // loop-defined values used outside of the loop.
  84   addPHINodes(DefsUsedOutside);
  85 }
  86
  87 void LoopVersioning::addPHINodes(
  88     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
  89   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
  90   assert(PHIBlock && "No single successor to loop exit block");
  91
  92   for (auto *Inst : DefsUsedOutside) {
  93     auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
  94     PHINode *PN;
  95
  96     // First see if we have a single-operand PHI with the value defined by the
  97     // original loop.
  98     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
  99       assert(PN->getNumOperands() == 1 &&
 100              "Exit block should only have on predecessor");
 101       if (PN->getIncomingValue(0) == Inst)
 102         break;
 103     }
 104     // If not create it.
 105     if (!PN) {
 106       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
 107                            &PHIBlock->front());
 108       for (auto *User : Inst->users())
 109         if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
 110           User->replaceUsesOfWith(Inst, PN);
 111       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
 112     }
 113     // Add the new incoming value from the non-versioned loop.
 114     PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());
 115   }
 116 }