Home | History | Annotate | Download | only in Utils 
      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 }
    148