Coverage Report

Created: 2019-07-24 05:18

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