blob: 1b7b9a217d0590443373621752871e424d274aeb [file] [log] [blame]
Tobias Grosser75805372011-04-29 06:27:02 +00001//===- 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"
Tobias Grosser8edce4e2013-04-16 08:04:42 +000015#include "polly/ScopInfo.h"
Tobias Grosser75805372011-04-29 06:27:02 +000016#include "llvm/Analysis/LoopInfo.h"
17#include "llvm/Analysis/RegionInfo.h"
18#include "llvm/Analysis/ScalarEvolution.h"
19#include "llvm/Analysis/ScalarEvolutionExpressions.h"
Chandler Carruthc3478b92014-03-04 11:47:37 +000020#include "llvm/IR/CFG.h"
Chandler Carruth95fef942014-04-22 03:30:19 +000021#include "llvm/Support/Debug.h"
Tobias Grosser75805372011-04-29 06:27:02 +000022#include "llvm/Transforms/Utils/BasicBlockUtils.h"
23
Tobias Grosser75805372011-04-29 06:27:02 +000024using namespace llvm;
25
Chandler Carruth95fef942014-04-22 03:30:19 +000026#define DEBUG_TYPE "polly-scop-helper"
27
Tobias Grosser75805372011-04-29 06:27:02 +000028// Helper function for Scop
29// TODO: Add assertion to not allow parameter to be null
30//===----------------------------------------------------------------------===//
31// Temporary Hack for extended region tree.
32// Cast the region to loop if there is a loop have the same header and exit.
33Loop *polly::castToLoop(const Region &R, LoopInfo &LI) {
34 BasicBlock *entry = R.getEntry();
35
36 if (!LI.isLoopHeader(entry))
37 return 0;
38
39 Loop *L = LI.getLoopFor(entry);
40
41 BasicBlock *exit = L->getExitBlock();
42
43 // Is the loop with multiple exits?
Tobias Grosserd535f552013-02-14 16:42:45 +000044 if (!exit)
45 return 0;
Tobias Grosser75805372011-04-29 06:27:02 +000046
47 if (exit != R.getExit()) {
48 // SubRegion/ParentRegion with the same entry.
Tobias Grosserd535f552013-02-14 16:42:45 +000049 assert((R.getNode(R.getEntry())->isSubRegion() ||
50 R.getParent()->getEntry() == entry) &&
51 "Expect the loop is the smaller or bigger region");
Tobias Grosser75805372011-04-29 06:27:02 +000052 return 0;
53 }
54
55 return L;
56}
57
58Value *polly::getPointerOperand(Instruction &Inst) {
59 if (LoadInst *load = dyn_cast<LoadInst>(&Inst))
60 return load->getPointerOperand();
61 else if (StoreInst *store = dyn_cast<StoreInst>(&Inst))
62 return store->getPointerOperand();
63 else if (GetElementPtrInst *gep = dyn_cast<GetElementPtrInst>(&Inst))
64 return gep->getPointerOperand();
65
66 return 0;
67}
68
Johannes Doerfert80ef1102014-11-07 08:31:31 +000069Type *polly::getAccessInstType(Instruction *AccInst) {
70 if (StoreInst *Store = dyn_cast<StoreInst>(AccInst))
71 return Store->getValueOperand()->getType();
72 return AccInst->getType();
73}
74
Tobias Grosser75805372011-04-29 06:27:02 +000075bool polly::hasInvokeEdge(const PHINode *PN) {
76 for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
77 if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
78 if (II->getParent() == PN->getIncomingBlock(i))
79 return true;
80
81 return false;
82}
83
Tobias Grosser75805372011-04-29 06:27:02 +000084BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
85 BasicBlock *BB = R->getExit();
86
Tobias Grosserd535f552013-02-14 16:42:45 +000087 SmallVector<BasicBlock *, 4> Preds;
Tobias Grosser75805372011-04-29 06:27:02 +000088 for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
89 if (R->contains(*PI))
90 Preds.push_back(*PI);
91
Benjamin Kramer66af99e2011-12-09 21:34:43 +000092 return SplitBlockPredecessors(BB, Preds, ".region", P);
Tobias Grosser75805372011-04-29 06:27:02 +000093}
94
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +000095static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
96 BasicBlock *NewEntry) {
Johannes Doerfert7c494212014-10-31 23:13:39 +000097 if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
98 Stmt->setBasicBlock(NewEntry);
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +000099
100 S->getRegion().replaceEntryRecursive(NewEntry);
101}
102
Johannes Doerfert38262242014-09-10 14:50:23 +0000103BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000104 Region *R = &S->getRegion();
105
Johannes Doerfert38262242014-09-10 14:50:23 +0000106 // The entering block for the region.
107 BasicBlock *EnteringBB = R->getEnteringBlock();
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +0000108 BasicBlock *OldEntry = R->getEntry();
109 BasicBlock *NewEntry = nullptr;
Johannes Doerfert38262242014-09-10 14:50:23 +0000110
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000111 // Create single entry edge if the region has multiple entry edges.
Johannes Doerfert38262242014-09-10 14:50:23 +0000112 if (!EnteringBB) {
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +0000113 NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P);
Johannes Doerfert38262242014-09-10 14:50:23 +0000114 EnteringBB = OldEntry;
115 }
116
117 // Create an unconditional entry edge.
118 if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +0000119 BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry;
120 BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, P);
121
122 // Once the edge between EnteringBB and EntryBB is split, two cases arise.
123 // The first is simple. The new block is inserted between EnteringBB and
124 // EntryBB. In this case no further action is needed. However it might
125 // happen (if the splitted edge is not critical) that the new block is
126 // inserted __after__ EntryBB causing the following situation:
127 //
128 // EnteringBB
Johannes Doerfert3cb63722014-10-07 14:34:13 +0000129 // _|_
130 // | |
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +0000131 // | \-> some_other_BB_not_in_R
132 // V
133 // EntryBB
134 // |
135 // V
136 // SplitEdgeBB
137 //
138 // In this case we need to swap the role of EntryBB and SplitEdgeBB.
139
140 // Check which case SplitEdge produced:
141 if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) {
142 // First (simple) case.
143 EnteringBB = SplitEdgeBB;
144 } else {
145 // Second (complicated) case.
146 NewEntry = SplitEdgeBB;
147 EnteringBB = EntryBB;
148 }
149
Johannes Doerfert38262242014-09-10 14:50:23 +0000150 EnteringBB->setName("polly.entering.block");
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000151 }
152
Johannes Doerfert0fe35dd2014-09-15 18:34:45 +0000153 if (NewEntry)
154 replaceScopAndRegionEntry(S, OldEntry, NewEntry);
155
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000156 // Create single exit edge if the region has multiple exit edges.
157 if (!R->getExitingBlock()) {
158 BasicBlock *NewExit = createSingleExitEdge(R, P);
159
Tobias Grosser083d3d32014-06-28 08:59:45 +0000160 for (auto &&SubRegion : *R)
161 SubRegion->replaceExitRecursive(NewExit);
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000162 }
Johannes Doerfert38262242014-09-10 14:50:23 +0000163
164 return EnteringBB;
Tobias Grosser8edce4e2013-04-16 08:04:42 +0000165}
166
Tobias Grosser75805372011-04-29 06:27:02 +0000167void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
168 // Find first non-alloca instruction. Every basic block has a non-alloc
169 // instruction, as every well formed basic block has a terminator.
170 BasicBlock::iterator I = EntryBlock->begin();
Tobias Grosserd535f552013-02-14 16:42:45 +0000171 while (isa<AllocaInst>(I))
172 ++I;
Tobias Grosser75805372011-04-29 06:27:02 +0000173
174 // SplitBlock updates DT, DF and LI.
175 BasicBlock *NewEntry = SplitBlock(EntryBlock, I, P);
Matt Arsenault8ca36812014-07-19 18:40:17 +0000176 if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
177 RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
Tobias Grosser75805372011-04-29 06:27:02 +0000178}