lib/Support/ScopHelper.cpp

   1 //===- ScopHelper.cpp - Some Helper Functions for Scop.  ------------------===//
   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 // Small functions that help with Scop and LLVM-IR.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/Support/ScopHelper.h"
  15 #include "polly/ScopInfo.h"
  16 #include "llvm/Analysis/AliasAnalysis.h"
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Analysis/RegionInfo.h"
  19 #include "llvm/Analysis/ScalarEvolution.h"
  20 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  21 #include "llvm/IR/CFG.h"
  22 #include "llvm/Support/Debug.h"
  23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  24
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "polly-scop-helper"
  28
  29 // Helper function for Scop
  30 // TODO: Add assertion to not allow parameter to be null
  31 //===----------------------------------------------------------------------===//
  32 // Temporary Hack for extended region tree.
  33 // Cast the region to loop if there is a loop have the same header and exit.
  34 Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
  35   BasicBlock *entry = R.getEntry();
  36
  37   if (!LI.isLoopHeader(entry))
  38     return 0;
  39
  40   Loop *L = LI.getLoopFor(entry);
  41
  42   BasicBlock *exit = L->getExitBlock();
  43
  44   // Is the loop with multiple exits?
  45   if (!exit)
  46     return 0;
  47
  48   if (exit != R.getExit()) {
  49     // SubRegion/ParentRegion with the same entry.
  50     assert((R.getNode(R.getEntry())->isSubRegion() ||
  51             R.getParent()->getEntry() == entry) &&
  52            "Expect the loop is the smaller or bigger region");
  53     return 0;
  54   }
  55
  56   return L;
  57 }
  58
  59 Value *polly::getPointerOperand(Instruction &Inst) {
  60   if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
  61     return load->getPointerOperand();
  62   else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
  63     return store->getPointerOperand();
  64   else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
  65     return gep->getPointerOperand();
  66
  67   return 0;
  68 }
  69
  70 Type *polly::getAccessInstType(Instruction *AccInst) {
  71   if (StoreInst *Store = dyn_cast<StoreInst>(AccInst))
  72     return Store->getValueOperand()->getType();
  73   return AccInst->getType();
  74 }
  75
  76 bool polly::hasInvokeEdge(const PHINode *PN) {
  77   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
  78     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
  79       if (II->getParent() == PN->getIncomingBlock(i))
  80         return true;
  81
  82   return false;
  83 }
  84
  85 BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
  86   BasicBlock *BB = R->getExit();
  87
  88   SmallVector<BasicBlock *, 4> Preds;
  89   for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
  90     if (R->contains(*PI))
  91       Preds.push_back(*PI);
  92
  93   auto *AA = P->getAnalysisIfAvailable<AliasAnalysis>();
  94   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
  95   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
  96   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
  97   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
  98
  99   return SplitBlockPredecessors(BB, Preds, ".region", AA, DT, LI);
 100 }
 101
 102 static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
 103                                       BasicBlock *NewEntry) {
 104   if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
 105     Stmt->setBasicBlock(NewEntry);
 106
 107   S->getRegion().replaceEntryRecursive(NewEntry);
 108 }
 109
 110 BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
 111   Region *R = &S->getRegion();
 112
 113   // The entering block for the region.
 114   BasicBlock *EnteringBB = R->getEnteringBlock();
 115   BasicBlock *OldEntry = R->getEntry();
 116   BasicBlock *NewEntry = nullptr;
 117
 118   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 119   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
 120   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
 121   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
 122
 123   // Create single entry edge if the region has multiple entry edges.
 124   if (!EnteringBB) {
 125     NewEntry = SplitBlock(OldEntry, OldEntry->begin(), DT, LI);
 126     EnteringBB = OldEntry;
 127   }
 128
 129   // Create an unconditional entry edge.
 130   if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
 131     BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry;
 132     BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, DT, LI);
 133
 134     // Once the edge between EnteringBB and EntryBB is split, two cases arise.
 135     // The first is simple. The new block is inserted between EnteringBB and
 136     // EntryBB. In this case no further action is needed. However it might
 137     // happen (if the splitted edge is not critical) that the new block is
 138     // inserted __after__ EntryBB causing the following situation:
 139     //
 140     // EnteringBB
 141     //    _|_
 142     //    | |
 143     //    |  \-> some_other_BB_not_in_R
 144     //    V
 145     // EntryBB
 146     //    |
 147     //    V
 148     // SplitEdgeBB
 149     //
 150     // In this case we need to swap the role of EntryBB and SplitEdgeBB.
 151
 152     // Check which case SplitEdge produced:
 153     if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) {
 154       // First (simple) case.
 155       EnteringBB = SplitEdgeBB;
 156     } else {
 157       // Second (complicated) case.
 158       NewEntry = SplitEdgeBB;
 159       EnteringBB = EntryBB;
 160     }
 161
 162     EnteringBB->setName("polly.entering.block");
 163   }
 164
 165   if (NewEntry)
 166     replaceScopAndRegionEntry(S, OldEntry, NewEntry);
 167
 168   // Create single exit edge if the region has multiple exit edges.
 169   if (!R->getExitingBlock()) {
 170     BasicBlock *NewExit = createSingleExitEdge(R, P);
 171
 172     for (auto &&SubRegion : *R)
 173       SubRegion->replaceExitRecursive(NewExit);
 174   }
 175
 176   return EnteringBB;
 177 }
 178
 179 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
 180   // Find first non-alloca instruction. Every basic block has a non-alloc
 181   // instruction, as every well formed basic block has a terminator.
 182   BasicBlock::iterator I = EntryBlock->begin();
 183   while (isa<AllocaInst>(I))
 184     ++I;
 185
 186   auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
 187   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
 188   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
 189   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
 190
 191   // SplitBlock updates DT, DF and LI.
 192   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, DT, LI);
 193   if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
 194     RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
 195 }