Coverage Report

Created: 2017-03-28 09:59

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/CodeGen/Utils.cpp
Line
Count
Source (jump to first uncovered line)
1
//===--- Utils.cpp - Utility functions for the code generation --*- C++ -*-===//
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 contains utility functions for the code generation.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/CodeGen/Utils.h"
15
#include "polly/CodeGen/IRBuilder.h"
16
#include "polly/ScopInfo.h"
17
#include "llvm/Analysis/LoopInfo.h"
18
#include "llvm/Analysis/RegionInfo.h"
19
#include "llvm/Support/Debug.h"
20
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
21
22
using namespace llvm;
23
24
// Alternative to llvm::SplitCriticalEdge.
25
//
26
// Creates a new block which branches to Succ. The edge to split is redirected
27
// to the new block.
28
//
29
// The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
30
// not critical.
31
// The issue with llvm::SplitEdge is that it does not always create the middle
32
// block, but reuses Prev/Succ if it can. We always want a new middle block.
33
static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
34
                             const char *Suffix, DominatorTree *DT,
35
774
                             LoopInfo *LI, RegionInfo *RI) {
36
774
  assert(Prev && Succ);
37
774
38
774
  // Before:
39
774
  //   \    /     /   //
40
774
  //    Prev     /    //
41
774
  //     |  \___/     //
42
774
  //     |   ___      //
43
774
  //     |  /   \     //
44
774
  //    Succ     \    //
45
774
  //   /    \     \   //
46
774
47
774
  // The algorithm to update DominatorTree and LoopInfo of
48
774
  // llvm::SplitCriticalEdge is more efficient than
49
774
  // llvm::SplitBlockPredecessors, which is more general. In the future we might
50
774
  // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
51
774
  // check; or Copy&Pase it here.
52
774
  BasicBlock *MiddleBlock = SplitBlockPredecessors(
53
774
      Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);
54
774
55
774
  if (
RI774
)
{774
56
774
    Region *PrevRegion = RI->getRegionFor(Prev);
57
774
    Region *SuccRegion = RI->getRegionFor(Succ);
58
774
    if (
PrevRegion->contains(MiddleBlock)774
)
{774
59
774
      RI->setRegionFor(MiddleBlock, PrevRegion);
60
0
    } else {
61
0
      RI->setRegionFor(MiddleBlock, SuccRegion);
62
0
    }
63
774
  }
64
774
65
774
  // After:
66
774
  //   \    /     /   //
67
774
  //    Prev     /    //
68
774
  //     |  \___/     //
69
774
  //     |            //
70
774
  // MiddleBlock      //
71
774
  //     |   ___      //
72
774
  //     |  /   \     //
73
774
  //    Succ     \    //
74
774
  //   /    \     \   //
75
774
76
774
  return MiddleBlock;
77
774
}
78
79
258
BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
80
258
  Region &R = S.getRegion();
81
258
  PollyIRBuilder Builder(S.getEntry());
82
258
  DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
83
258
  RegionInfo &RI = P->getAnalysis<RegionInfoPass>().getRegionInfo();
84
258
  LoopInfo &LI = P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
85
258
86
258
  // Before:
87
258
  //
88
258
  //      \   /      //
89
258
  //    EnteringBB   //
90
258
  //   _____|_____   //
91
258
  //  /  EntryBB  \  //
92
258
  //  |  (region) |  //
93
258
  //  \_ExitingBB_/  //
94
258
  //        |        //
95
258
  //      ExitBB     //
96
258
  //      /    \     //
97
258
98
258
  // Create a fork block.
99
258
  BasicBlock *EnteringBB = S.getEnteringBlock();
100
258
  BasicBlock *EntryBB = S.getEntry();
101
258
  assert(EnteringBB && "Must be a simple region");
102
258
  BasicBlock *SplitBlock =
103
258
      splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI);
104
258
  SplitBlock->setName("polly.split_new_and_old");
105
258
106
258
  // If EntryBB is the exit block of the region that includes Prev, exclude
107
258
  // SplitBlock from that region by making it itself the exit block. This is
108
258
  // trivially possible because there is just one edge to EnteringBB.
109
258
  // This is necessary because we will add an outgoing edge from SplitBlock,
110
258
  // which would violate the single exit block requirement of PrevRegion.
111
258
  Region *PrevRegion = RI.getRegionFor(EnteringBB);
112
261
  while (
PrevRegion->getExit() == EntryBB261
)
{3
113
3
    PrevRegion->replaceExit(SplitBlock);
114
3
    PrevRegion = PrevRegion->getParent();
115
3
  }
116
258
  RI.setRegionFor(SplitBlock, PrevRegion);
117
258
118
258
  // Create a join block
119
258
  BasicBlock *ExitingBB = S.getExitingBlock();
120
258
  BasicBlock *ExitBB = S.getExit();
121
258
  assert(ExitingBB && "Must be a simple region");
122
258
  BasicBlock *MergeBlock =
123
258
      splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI);
124
258
  MergeBlock->setName("polly.merge_new_and_old");
125
258
126
258
  // Exclude the join block from the region.
127
258
  R.replaceExitRecursive(MergeBlock);
128
258
  RI.setRegionFor(MergeBlock, R.getParent());
129
258
130
258
  //      \   /      //
131
258
  //    EnteringBB   //
132
258
  //        |        //
133
258
  //    SplitBlock   //
134
258
  //   _____|_____   //
135
258
  //  /  EntryBB  \  //
136
258
  //  |  (region) |  //
137
258
  //  \_ExitingBB_/  //
138
258
  //        |        //
139
258
  //    MergeBlock   //
140
258
  //        |        //
141
258
  //      ExitBB     //
142
258
  //      /    \     //
143
258
144
258
  // Create the start and exiting block.
145
258
  Function *F = SplitBlock->getParent();
146
258
  BasicBlock *StartBlock =
147
258
      BasicBlock::Create(F->getContext(), "polly.start", F);
148
258
  BasicBlock *ExitingBlock =
149
258
      BasicBlock::Create(F->getContext(), "polly.exiting", F);
150
258
  SplitBlock->getTerminator()->eraseFromParent();
151
258
  Builder.SetInsertPoint(SplitBlock);
152
258
  Builder.CreateCondBr(RTC, StartBlock, S.getEntry());
153
258
  if (Loop *
L258
= LI.getLoopFor(SplitBlock))
{25
154
25
    L->addBasicBlockToLoop(StartBlock, LI);
155
25
    L->addBasicBlockToLoop(ExitingBlock, LI);
156
25
  }
157
258
  DT.addNewBlock(StartBlock, SplitBlock);
158
258
  DT.addNewBlock(ExitingBlock, StartBlock);
159
258
  RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock));
160
258
  RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock));
161
258
162
258
  //      \   /                    //
163
258
  //    EnteringBB                 //
164
258
  //        |                      //
165
258
  //    SplitBlock---------\       //
166
258
  //   _____|_____         |       //
167
258
  //  /  EntryBB  \    StartBlock  //
168
258
  //  |  (region) |        |       //
169
258
  //  \_ExitingBB_/   ExitingBlock //
170
258
  //        |                      //
171
258
  //    MergeBlock                 //
172
258
  //        |                      //
173
258
  //      ExitBB                   //
174
258
  //      /    \                   //
175
258
176
258
  // Connect start block to exiting block.
177
258
  Builder.SetInsertPoint(StartBlock);
178
258
  Builder.CreateBr(ExitingBlock);
179
258
  DT.changeImmediateDominator(ExitingBlock, StartBlock);
180
258
181
258
  // Connect exiting block to join block.
182
258
  Builder.SetInsertPoint(ExitingBlock);
183
258
  Builder.CreateBr(MergeBlock);
184
258
  DT.changeImmediateDominator(MergeBlock, SplitBlock);
185
258
186
258
  //      \   /                    //
187
258
  //    EnteringBB                 //
188
258
  //        |                      //
189
258
  //    SplitBlock---------\       //
190
258
  //   _____|_____         |       //
191
258
  //  /  EntryBB  \    StartBlock  //
192
258
  //  |  (region) |        |       //
193
258
  //  \_ExitingBB_/   ExitingBlock //
194
258
  //        |              |       //
195
258
  //    MergeBlock---------/       //
196
258
  //        |                      //
197
258
  //      ExitBB                   //
198
258
  //      /    \                   //
199
258
  //
200
258
201
258
  // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
202
258
  splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI);
203
258
204
258
  //      \   /                    //
205
258
  //    EnteringBB                 //
206
258
  //        |                      //
207
258
  //    SplitBlock---------\       //
208
258
  //        |              |       //
209
258
  //    PreEntryBB         |       //
210
258
  //   _____|_____         |       //
211
258
  //  /  EntryBB  \    StartBlock  //
212
258
  //  |  (region) |        |       //
213
258
  //  \_ExitingBB_/   ExitingBlock //
214
258
  //        |              |       //
215
258
  //    MergeBlock---------/       //
216
258
  //        |                      //
217
258
  //      ExitBB                   //
218
258
  //      /    \                   //
219
258
220
258
  return StartBlock;
221
258
}