Coverage Report

Created: 2019-02-15 18:59

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