Coverage Report

Created: 2017-06-23 12:40

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/CodeGen/CodeGeneration.cpp
Line
Count
Source (jump to first uncovered line)
1
//===------ CodeGeneration.cpp - Code generate the Scops using ISL. ----======//
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
// The CodeGeneration pass takes a Scop created by ScopInfo and translates it
11
// back to LLVM-IR using the ISL code generator.
12
//
13
// The Scop describes the high level memory behavior of a control flow region.
14
// Transformation passes can update the schedule (execution order) of statements
15
// in the Scop. ISL is used to generate an abstract syntax tree that reflects
16
// the updated execution order. This clast is used to create new LLVM-IR that is
17
// computationally equivalent to the original control flow region, but executes
18
// its code in the new execution order defined by the changed schedule.
19
//
20
//===----------------------------------------------------------------------===//
21
22
#include "polly/CodeGen/CodeGeneration.h"
23
#include "polly/CodeGen/IslAst.h"
24
#include "polly/CodeGen/IslNodeBuilder.h"
25
#include "polly/CodeGen/PerfMonitor.h"
26
#include "polly/CodeGen/Utils.h"
27
#include "polly/DependenceInfo.h"
28
#include "polly/LinkAllPasses.h"
29
#include "polly/Options.h"
30
#include "polly/ScopInfo.h"
31
#include "polly/Support/ScopHelper.h"
32
#include "llvm/Analysis/AliasAnalysis.h"
33
#include "llvm/Analysis/BasicAliasAnalysis.h"
34
#include "llvm/Analysis/GlobalsModRef.h"
35
#include "llvm/Analysis/LoopInfo.h"
36
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
37
#include "llvm/IR/Module.h"
38
#include "llvm/IR/PassManager.h"
39
#include "llvm/IR/Verifier.h"
40
#include "llvm/Support/Debug.h"
41
42
using namespace polly;
43
using namespace llvm;
44
45
#define DEBUG_TYPE "polly-codegen"
46
47
static cl::opt<bool> Verify("polly-codegen-verify",
48
                            cl::desc("Verify the function generated by Polly"),
49
                            cl::Hidden, cl::init(false), cl::ZeroOrMore,
50
                            cl::cat(PollyCategory));
51
52
static cl::opt<bool>
53
    PerfMonitoring("polly-codegen-perf-monitoring",
54
                   cl::desc("Add run-time performance monitoring"), cl::Hidden,
55
                   cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
56
57
namespace {
58
59
306
static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
60
306
  if (
!Verify || 306
!verifyFunction(F, &errs())0
)
61
306
    return;
62
306
63
0
  
DEBUG0
({0
64
0
    errs() << "== ISL Codegen created an invalid function ==\n\n== The "
65
0
              "SCoP ==\n";
66
0
    S.print(errs());
67
0
    errs() << "\n== The isl AST ==\n";
68
0
    AI.print(errs());
69
0
    errs() << "\n== The invalid function ==\n";
70
0
    F.print(errs());
71
0
  });
72
0
73
0
  llvm_unreachable("Polly generated function could not be verified. Add "
74
0
                   "-polly-codegen-verify=false to disable this assertion.");
75
0
}
76
77
// CodeGeneration adds a lot of BBs without updating the RegionInfo
78
// We make all created BBs belong to the scop's parent region without any
79
// nested structure to keep the RegionInfo verifier happy.
80
275
static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
81
4.94k
  for (BasicBlock &BB : F) {
82
4.94k
    if (RI.getRegionFor(&BB))
83
3.30k
      continue;
84
4.94k
85
1.63k
    RI.setRegionFor(&BB, &ParentRegion);
86
1.63k
  }
87
275
}
88
89
/// Mark a basic block unreachable.
90
///
91
/// Marks the basic block @p Block unreachable by equipping it with an
92
/// UnreachableInst.
93
10
static void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
94
10
  auto *OrigTerminator = Block.getTerminator();
95
10
  Builder.SetInsertPoint(OrigTerminator);
96
10
  Builder.CreateUnreachable();
97
10
  OrigTerminator->eraseFromParent();
98
10
}
99
100
/// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from
101
/// @R.
102
///
103
/// CodeGeneration does not copy lifetime markers into the optimized SCoP,
104
/// which would leave the them only in the original path. This can transform
105
/// code such as
106
///
107
///     llvm.lifetime.start(%p)
108
///     llvm.lifetime.end(%p)
109
///
110
/// into
111
///
112
///     if (RTC) {
113
///       // generated code
114
///     } else {
115
///       // original code
116
///       llvm.lifetime.start(%p)
117
///     }
118
///     llvm.lifetime.end(%p)
119
///
120
/// The current StackColoring algorithm cannot handle if some, but not all,
121
/// paths from the end marker to the entry block cross the start marker. Same
122
/// for start markers that do not always cross the end markers. We avoid any
123
/// issues by removing all lifetime markers, even from the original code.
124
///
125
/// A better solution could be to hoist all llvm.lifetime.start to the split
126
/// node and all llvm.lifetime.end to the merge node, which should be
127
/// conservatively correct.
128
280
static void removeLifetimeMarkers(Region *R) {
129
1.09k
  for (auto *BB : R->blocks()) {
130
1.09k
    auto InstIt = BB->begin();
131
1.09k
    auto InstEnd = BB->end();
132
1.09k
133
4.84k
    while (
InstIt != InstEnd4.84k
)
{3.75k
134
3.75k
      auto NextIt = InstIt;
135
3.75k
      ++NextIt;
136
3.75k
137
3.75k
      if (auto *
IT3.75k
= dyn_cast<IntrinsicInst>(&*InstIt))
{20
138
20
        switch (IT->getIntrinsicID()) {
139
2
        case llvm::Intrinsic::lifetime_start:
140
2
        case llvm::Intrinsic::lifetime_end:
141
2
          BB->getInstList().erase(InstIt);
142
2
          break;
143
18
        default:
144
18
          break;
145
20
        }
146
20
      }
147
3.75k
148
3.75k
      InstIt = NextIt;
149
3.75k
    }
150
1.09k
  }
151
280
}
152
153
static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
154
280
                    ScalarEvolution &SE, RegionInfo &RI) {
155
280
  // Check if we created an isl_ast root node, otherwise exit.
156
280
  isl_ast_node *AstRoot = AI.getAst();
157
280
  if (!AstRoot)
158
0
    return false;
159
280
160
280
  auto &DL = S.getFunction().getParent()->getDataLayout();
161
280
  Region *R = &S.getRegion();
162
280
  assert(!R->isTopLevelRegion() && "Top level regions are not supported");
163
280
164
280
  ScopAnnotator Annotator;
165
280
166
280
  simplifyRegion(R, &DT, &LI, &RI);
167
280
  assert(R->isSimple());
168
280
  BasicBlock *EnteringBB = S.getEnteringBlock();
169
280
  assert(EnteringBB);
170
280
  PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
171
280
172
280
  // Only build the run-time condition and parameters _after_ having
173
280
  // introduced the conditional branch. This is important as the conditional
174
280
  // branch will guard the original scop from new induction variables that
175
280
  // the SCEVExpander may introduce while code generating the parameters and
176
280
  // which may introduce scalar dependences that prevent us from correctly
177
280
  // code generating this scop.
178
280
  BasicBlock *StartBlock =
179
280
      executeScopConditionally(S, Builder.getTrue(), DT, RI, LI);
180
280
  removeLifetimeMarkers(R);
181
280
  auto *SplitBlock = StartBlock->getSinglePredecessor();
182
280
183
280
  IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
184
280
185
280
  // All arrays must have their base pointers known before
186
280
  // ScopAnnotator::buildAliasScopes.
187
280
  NodeBuilder.allocateNewArrays();
188
280
  Annotator.buildAliasScopes(S);
189
280
190
280
  if (
PerfMonitoring280
)
{5
191
5
    PerfMonitor P(S, EnteringBB->getParent()->getParent());
192
5
    P.initialize();
193
5
    P.insertRegionStart(SplitBlock->getTerminator());
194
5
195
5
    BasicBlock *MergeBlock = SplitBlock->getTerminator()
196
5
                                 ->getSuccessor(0)
197
5
                                 ->getUniqueSuccessor()
198
5
                                 ->getUniqueSuccessor();
199
5
    P.insertRegionEnd(MergeBlock->getTerminator());
200
5
  }
201
280
202
280
  // First generate code for the hoisted invariant loads and transitively the
203
280
  // parameters they reference. Afterwards, for the remaining parameters that
204
280
  // might reference the hoisted loads. Finally, build the runtime check
205
280
  // that might reference both hoisted loads as well as parameters.
206
280
  // If the hoisting fails we have to bail and execute the original code.
207
280
  Builder.SetInsertPoint(SplitBlock->getTerminator());
208
280
  if (
!NodeBuilder.preloadInvariantLoads()280
)
{5
209
5
210
5
    // Patch the introduced branch condition to ensure that we always execute
211
5
    // the original SCoP.
212
5
    auto *FalseI1 = Builder.getFalse();
213
5
    auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
214
5
    SplitBBTerm->setOperand(0, FalseI1);
215
5
216
5
    // Since the other branch is hence ignored we mark it as unreachable and
217
5
    // adjust the dominator tree accordingly.
218
5
    auto *ExitingBlock = StartBlock->getUniqueSuccessor();
219
5
    assert(ExitingBlock);
220
5
    auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
221
5
    assert(MergeBlock);
222
5
    markBlockUnreachable(*StartBlock, Builder);
223
5
    markBlockUnreachable(*ExitingBlock, Builder);
224
5
    auto *ExitingBB = S.getExitingBlock();
225
5
    assert(ExitingBB);
226
5
    DT.changeImmediateDominator(MergeBlock, ExitingBB);
227
5
    DT.eraseNode(ExitingBlock);
228
5
229
5
    isl_ast_node_free(AstRoot);
230
275
  } else {
231
275
    NodeBuilder.addParameters(S.getContext());
232
275
    Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
233
275
234
275
    Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
235
275
    Builder.SetInsertPoint(&StartBlock->front());
236
275
237
275
    NodeBuilder.create(AstRoot);
238
275
    NodeBuilder.finalize();
239
275
    fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
240
275
  }
241
280
242
280
  Function *F = EnteringBB->getParent();
243
280
  verifyGeneratedFunction(S, *F, AI);
244
280
  for (auto *SubF : NodeBuilder.getParallelSubfunctions())
245
26
    verifyGeneratedFunction(S, *SubF, AI);
246
280
247
280
  // Mark the function such that we run additional cleanup passes on this
248
280
  // function (e.g. mem2reg to rediscover phi nodes).
249
280
  F->addFnAttr("polly-optimized");
250
280
  return true;
251
280
}
252
253
class CodeGeneration : public ScopPass {
254
public:
255
  static char ID;
256
257
301
  CodeGeneration() : ScopPass(ID) {}
258
259
  /// The data layout used.
260
  const DataLayout *DL;
261
262
  /// @name The analysis passes we need to generate code.
263
  ///
264
  ///{
265
  LoopInfo *LI;
266
  IslAstInfo *AI;
267
  DominatorTree *DT;
268
  ScalarEvolution *SE;
269
  RegionInfo *RI;
270
  ///}
271
272
  /// Generate LLVM-IR for the SCoP @p S.
273
280
  bool runOnScop(Scop &S) override {
274
280
    AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
275
280
    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
276
280
    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
277
280
    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
278
280
    DL = &S.getFunction().getParent()->getDataLayout();
279
280
    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
280
280
    return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
281
280
  }
282
283
  /// Register all analyses and transformation required.
284
301
  void getAnalysisUsage(AnalysisUsage &AU) const override {
285
301
    AU.addRequired<DominatorTreeWrapperPass>();
286
301
    AU.addRequired<IslAstInfoWrapperPass>();
287
301
    AU.addRequired<RegionInfoPass>();
288
301
    AU.addRequired<ScalarEvolutionWrapperPass>();
289
301
    AU.addRequired<ScopDetectionWrapperPass>();
290
301
    AU.addRequired<ScopInfoRegionPass>();
291
301
    AU.addRequired<LoopInfoWrapperPass>();
292
301
293
301
    AU.addPreserved<DependenceInfo>();
294
301
295
301
    AU.addPreserved<AAResultsWrapperPass>();
296
301
    AU.addPreserved<BasicAAWrapperPass>();
297
301
    AU.addPreserved<LoopInfoWrapperPass>();
298
301
    AU.addPreserved<DominatorTreeWrapperPass>();
299
301
    AU.addPreserved<GlobalsAAWrapperPass>();
300
301
    AU.addPreserved<IslAstInfoWrapperPass>();
301
301
    AU.addPreserved<ScopDetectionWrapperPass>();
302
301
    AU.addPreserved<ScalarEvolutionWrapperPass>();
303
301
    AU.addPreserved<SCEVAAWrapperPass>();
304
301
305
301
    // FIXME: We do not yet add regions for the newly generated code to the
306
301
    //        region tree.
307
301
    AU.addPreserved<RegionInfoPass>();
308
301
    AU.addPreserved<ScopInfoRegionPass>();
309
301
  }
310
};
311
} // namespace
312
313
PreservedAnalyses
314
polly::CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
315
0
                               ScopStandardAnalysisResults &AR, SPMUpdater &U) {
316
0
  auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
317
0
  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI))
318
0
    return PreservedAnalyses::none();
319
0
320
0
  return PreservedAnalyses::all();
321
0
}
322
323
char CodeGeneration::ID = 1;
324
325
0
Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
326
327
41.0k
INITIALIZE_PASS_BEGIN41.0k
(CodeGeneration, "polly-codegen",41.0k
328
41.0k
                      "Polly - Create LLVM-IR from SCoPs", false, false);
329
41.0k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
330
41.0k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
331
41.0k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
332
41.0k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
333
41.0k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
334
41.0k
INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
335
41.0k
INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
336
                    "Polly - Create LLVM-IR from SCoPs", false, false)