Coverage Report

Created: 2017-06-28 17:40

/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
840
                             LoopInfo *LI, RegionInfo *RI) {
36
840
  assert(Prev && Succ);
37
840
38
840
  // Before:
39
840
  //   \    /     /   //
40
840
  //    Prev     /    //
41
840
  //     |  \___/     //
42
840
  //     |   ___      //
43
840
  //     |  /   \     //
44
840
  //    Succ     \    //
45
840
  //   /    \     \   //
46
840
47
840
  // The algorithm to update DominatorTree and LoopInfo of
48
840
  // llvm::SplitCriticalEdge is more efficient than
49
840
  // llvm::SplitBlockPredecessors, which is more general. In the future we might
50
840
  // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
51
840
  // check; or Copy&Pase it here.
52
840
  BasicBlock *MiddleBlock = SplitBlockPredecessors(
53
840
      Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);
54
840
55
840
  if (
RI840
)
{840
56
840
    Region *PrevRegion = RI->getRegionFor(Prev);
57
840
    Region *SuccRegion = RI->getRegionFor(Succ);
58
840
    if (
PrevRegion->contains(MiddleBlock)840
)
{840
59
840
      RI->setRegionFor(MiddleBlock, PrevRegion);
60
0
    } else {
61
0
      RI->setRegionFor(MiddleBlock, SuccRegion);
62
0
    }
63
840
  }
64
840
65
840
  // After:
66
840
  //   \    /     /   //
67
840
  //    Prev     /    //
68
840
  //     |  \___/     //
69
840
  //     |            //
70
840
  // MiddleBlock      //
71
840
  //     |   ___      //
72
840
  //     |  /   \     //
73
840
  //    Succ     \    //
74
840
  //   /    \     \   //
75
840
76
840
  return MiddleBlock;
77
840
}
78
79
polly::BBPair polly::executeScopConditionally(Scop &S, Value *RTC,
80
                                              DominatorTree &DT, RegionInfo &RI,
81
280
                                              LoopInfo &LI) {
82
280
  Region &R = S.getRegion();
83
280
  PollyIRBuilder Builder(S.getEntry());
84
280
85
280
  // Before:
86
280
  //
87
280
  //      \   /      //
88
280
  //    EnteringBB   //
89
280
  //   _____|_____   //
90
280
  //  /  EntryBB  \  //
91
280
  //  |  (region) |  //
92
280
  //  \_ExitingBB_/  //
93
280
  //        |        //
94
280
  //      ExitBB     //
95
280
  //      /    \     //
96
280
97
280
  // Create a fork block.
98
280
  BasicBlock *EnteringBB = S.getEnteringBlock();
99
280
  BasicBlock *EntryBB = S.getEntry();
100
280
  assert(EnteringBB && "Must be a simple region");
101
280
  BasicBlock *SplitBlock =
102
280
      splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI);
103
280
  SplitBlock->setName("polly.split_new_and_old");
104
280
105
280
  // If EntryBB is the exit block of the region that includes Prev, exclude
106
280
  // SplitBlock from that region by making it itself the exit block. This is
107
280
  // trivially possible because there is just one edge to EnteringBB.
108
280
  // This is necessary because we will add an outgoing edge from SplitBlock,
109
280
  // which would violate the single exit block requirement of PrevRegion.
110
280
  Region *PrevRegion = RI.getRegionFor(EnteringBB);
111
283
  while (
PrevRegion->getExit() == EntryBB283
)
{3
112
3
    PrevRegion->replaceExit(SplitBlock);
113
3
    PrevRegion = PrevRegion->getParent();
114
3
  }
115
280
  RI.setRegionFor(SplitBlock, PrevRegion);
116
280
117
280
  // Create a join block
118
280
  BasicBlock *ExitingBB = S.getExitingBlock();
119
280
  BasicBlock *ExitBB = S.getExit();
120
280
  assert(ExitingBB && "Must be a simple region");
121
280
  BasicBlock *MergeBlock =
122
280
      splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI);
123
280
  MergeBlock->setName("polly.merge_new_and_old");
124
280
125
280
  // Exclude the join block from the region.
126
280
  R.replaceExitRecursive(MergeBlock);
127
280
  RI.setRegionFor(MergeBlock, R.getParent());
128
280
129
280
  //      \   /      //
130
280
  //    EnteringBB   //
131
280
  //        |        //
132
280
  //    SplitBlock   //
133
280
  //   _____|_____   //
134
280
  //  /  EntryBB  \  //
135
280
  //  |  (region) |  //
136
280
  //  \_ExitingBB_/  //
137
280
  //        |        //
138
280
  //    MergeBlock   //
139
280
  //        |        //
140
280
  //      ExitBB     //
141
280
  //      /    \     //
142
280
143
280
  // Create the start and exiting block.
144
280
  Function *F = SplitBlock->getParent();
145
280
  BasicBlock *StartBlock =
146
280
      BasicBlock::Create(F->getContext(), "polly.start", F);
147
280
  BasicBlock *ExitingBlock =
148
280
      BasicBlock::Create(F->getContext(), "polly.exiting", F);
149
280
  SplitBlock->getTerminator()->eraseFromParent();
150
280
  Builder.SetInsertPoint(SplitBlock);
151
280
  Builder.CreateCondBr(RTC, StartBlock, S.getEntry());
152
280
  if (Loop *
L280
= LI.getLoopFor(SplitBlock))
{25
153
25
    L->addBasicBlockToLoop(StartBlock, LI);
154
25
    L->addBasicBlockToLoop(ExitingBlock, LI);
155
25
  }
156
280
  DT.addNewBlock(StartBlock, SplitBlock);
157
280
  DT.addNewBlock(ExitingBlock, StartBlock);
158
280
  RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock));
159
280
  RI.setRegionFor(ExitingBlock, RI.getRegionFor(SplitBlock));
160
280
161
280
  //      \   /                    //
162
280
  //    EnteringBB                 //
163
280
  //        |                      //
164
280
  //    SplitBlock---------\       //
165
280
  //   _____|_____         |       //
166
280
  //  /  EntryBB  \    StartBlock  //
167
280
  //  |  (region) |        |       //
168
280
  //  \_ExitingBB_/   ExitingBlock //
169
280
  //        |                      //
170
280
  //    MergeBlock                 //
171
280
  //        |                      //
172
280
  //      ExitBB                   //
173
280
  //      /    \                   //
174
280
175
280
  // Connect start block to exiting block.
176
280
  Builder.SetInsertPoint(StartBlock);
177
280
  Builder.CreateBr(ExitingBlock);
178
280
  DT.changeImmediateDominator(ExitingBlock, StartBlock);
179
280
180
280
  // Connect exiting block to join block.
181
280
  Builder.SetInsertPoint(ExitingBlock);
182
280
  Builder.CreateBr(MergeBlock);
183
280
  DT.changeImmediateDominator(MergeBlock, SplitBlock);
184
280
185
280
  //      \   /                    //
186
280
  //    EnteringBB                 //
187
280
  //        |                      //
188
280
  //    SplitBlock---------\       //
189
280
  //   _____|_____         |       //
190
280
  //  /  EntryBB  \    StartBlock  //
191
280
  //  |  (region) |        |       //
192
280
  //  \_ExitingBB_/   ExitingBlock //
193
280
  //        |              |       //
194
280
  //    MergeBlock---------/       //
195
280
  //        |                      //
196
280
  //      ExitBB                   //
197
280
  //      /    \                   //
198
280
  //
199
280
200
280
  // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
201
280
  splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI);
202
280
203
280
  //      \   /                    //
204
280
  //    EnteringBB                 //
205
280
  //        |                      //
206
280
  //    SplitBlock---------\       //
207
280
  //        |              |       //
208
280
  //    PreEntryBB         |       //
209
280
  //   _____|_____         |       //
210
280
  //  /  EntryBB  \    StartBlock  //
211
280
  //  |  (region) |        |       //
212
280
  //  \_ExitingBB_/   ExitingBlock //
213
280
  //        |              |       //
214
280
  //    MergeBlock---------/       //
215
280
  //        |                      //
216
280
  //      ExitBB                   //
217
280
  //      /    \                   //
218
280
219
280
  return std::make_pair(StartBlock, ExitingBlock);
220
280
}