Coverage Report

Created: 2018-06-24 14:39

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/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/IRBuilder.h"
24
#include "polly/CodeGen/IslAst.h"
25
#include "polly/CodeGen/IslNodeBuilder.h"
26
#include "polly/CodeGen/PerfMonitor.h"
27
#include "polly/CodeGen/Utils.h"
28
#include "polly/DependenceInfo.h"
29
#include "polly/LinkAllPasses.h"
30
#include "polly/Options.h"
31
#include "polly/ScopDetectionDiagnostic.h"
32
#include "polly/ScopInfo.h"
33
#include "polly/Support/ScopHelper.h"
34
#include "llvm/ADT/Statistic.h"
35
#include "llvm/Analysis/AliasAnalysis.h"
36
#include "llvm/Analysis/BasicAliasAnalysis.h"
37
#include "llvm/Analysis/GlobalsModRef.h"
38
#include "llvm/Analysis/LoopInfo.h"
39
#include "llvm/Analysis/RegionInfo.h"
40
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
41
#include "llvm/IR/BasicBlock.h"
42
#include "llvm/IR/Dominators.h"
43
#include "llvm/IR/Function.h"
44
#include "llvm/IR/Instruction.h"
45
#include "llvm/IR/IntrinsicInst.h"
46
#include "llvm/IR/Intrinsics.h"
47
#include "llvm/IR/Module.h"
48
#include "llvm/IR/PassManager.h"
49
#include "llvm/IR/Verifier.h"
50
#include "llvm/Pass.h"
51
#include "llvm/Support/Casting.h"
52
#include "llvm/Support/CommandLine.h"
53
#include "llvm/Support/Debug.h"
54
#include "llvm/Support/ErrorHandling.h"
55
#include "llvm/Support/raw_ostream.h"
56
#include "isl/ast.h"
57
#include <cassert>
58
#include <utility>
59
60
using namespace llvm;
61
using namespace polly;
62
63
#define DEBUG_TYPE "polly-codegen"
64
65
static cl::opt<bool> Verify("polly-codegen-verify",
66
                            cl::desc("Verify the function generated by Polly"),
67
                            cl::Hidden, cl::init(false), cl::ZeroOrMore,
68
                            cl::cat(PollyCategory));
69
70
bool polly::PerfMonitoring;
71
72
static cl::opt<bool, true>
73
    XPerfMonitoring("polly-codegen-perf-monitoring",
74
                    cl::desc("Add run-time performance monitoring"), cl::Hidden,
75
                    cl::location(polly::PerfMonitoring), cl::init(false),
76
                    cl::ZeroOrMore, cl::cat(PollyCategory));
77
78
STATISTIC(ScopsProcessed, "Number of SCoP processed");
79
STATISTIC(CodegenedScops, "Number of successfully generated SCoPs");
80
STATISTIC(CodegenedAffineLoops,
81
          "Number of original affine loops in SCoPs that have been generated");
82
STATISTIC(CodegenedBoxedLoops,
83
          "Number of original boxed loops in SCoPs that have been generated");
84
85
namespace polly {
86
87
/// Mark a basic block unreachable.
88
///
89
/// Marks the basic block @p Block unreachable by equipping it with an
90
/// UnreachableInst.
91
8
void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
92
8
  auto *OrigTerminator = Block.getTerminator();
93
8
  Builder.SetInsertPoint(OrigTerminator);
94
8
  Builder.CreateUnreachable();
95
8
  OrigTerminator->eraseFromParent();
96
8
}
97
} // namespace polly
98
99
320
static void verifyGeneratedFunction(Scop &S, Function &F, IslAstInfo &AI) {
100
320
  if (!Verify || !verifyFunction(F, &errs()))
101
320
    return;
102
0
103
0
  LLVM_DEBUG({
104
0
    errs() << "== ISL Codegen created an invalid function ==\n\n== The "
105
0
              "SCoP ==\n";
106
0
    errs() << S;
107
0
    errs() << "\n== The isl AST ==\n";
108
0
    AI.print(errs());
109
0
    errs() << "\n== The invalid function ==\n";
110
0
    F.print(errs());
111
0
  });
112
0
113
0
  llvm_unreachable("Polly generated function could not be verified. Add "
114
0
                   "-polly-codegen-verify=false to disable this assertion.");
115
0
}
116
117
// CodeGeneration adds a lot of BBs without updating the RegionInfo
118
// We make all created BBs belong to the scop's parent region without any
119
// nested structure to keep the RegionInfo verifier happy.
120
288
static void fixRegionInfo(Function &F, Region &ParentRegion, RegionInfo &RI) {
121
5.30k
  for (BasicBlock &BB : F) {
122
5.30k
    if (RI.getRegionFor(&BB))
123
3.45k
      continue;
124
1.85k
125
1.85k
    RI.setRegionFor(&BB, &ParentRegion);
126
1.85k
  }
127
288
}
128
129
/// Remove all lifetime markers (llvm.lifetime.start, llvm.lifetime.end) from
130
/// @R.
131
///
132
/// CodeGeneration does not copy lifetime markers into the optimized SCoP,
133
/// which would leave the them only in the original path. This can transform
134
/// code such as
135
///
136
///     llvm.lifetime.start(%p)
137
///     llvm.lifetime.end(%p)
138
///
139
/// into
140
///
141
///     if (RTC) {
142
///       // generated code
143
///     } else {
144
///       // original code
145
///       llvm.lifetime.start(%p)
146
///     }
147
///     llvm.lifetime.end(%p)
148
///
149
/// The current StackColoring algorithm cannot handle if some, but not all,
150
/// paths from the end marker to the entry block cross the start marker. Same
151
/// for start markers that do not always cross the end markers. We avoid any
152
/// issues by removing all lifetime markers, even from the original code.
153
///
154
/// A better solution could be to hoist all llvm.lifetime.start to the split
155
/// node and all llvm.lifetime.end to the merge node, which should be
156
/// conservatively correct.
157
292
static void removeLifetimeMarkers(Region *R) {
158
1.15k
  for (auto *BB : R->blocks()) {
159
1.15k
    auto InstIt = BB->begin();
160
1.15k
    auto InstEnd = BB->end();
161
1.15k
162
5.10k
    while (InstIt != InstEnd) {
163
3.94k
      auto NextIt = InstIt;
164
3.94k
      ++NextIt;
165
3.94k
166
3.94k
      if (auto *IT = dyn_cast<IntrinsicInst>(&*InstIt)) {
167
21
        switch (IT->getIntrinsicID()) {
168
21
        case Intrinsic::lifetime_start:
169
2
        case Intrinsic::lifetime_end:
170
2
          BB->getInstList().erase(InstIt);
171
2
          break;
172
19
        default:
173
19
          break;
174
3.94k
        }
175
3.94k
      }
176
3.94k
177
3.94k
      InstIt = NextIt;
178
3.94k
    }
179
1.15k
  }
180
292
}
181
182
static bool CodeGen(Scop &S, IslAstInfo &AI, LoopInfo &LI, DominatorTree &DT,
183
293
                    ScalarEvolution &SE, RegionInfo &RI) {
184
293
  // Check whether IslAstInfo uses the same isl_ctx. Since -polly-codegen
185
293
  // reports itself to preserve DependenceInfo and IslAstInfo, we might get
186
293
  // those analysis that were computed by a different ScopInfo for a different
187
293
  // Scop structure. When the ScopInfo/Scop object is freed, there is a high
188
293
  // probability that the new ScopInfo/Scop object will be created at the same
189
293
  // heap position with the same address. Comparing whether the Scop or ScopInfo
190
293
  // address is the expected therefore is unreliable.
191
293
  // Instead, we compare the address of the isl_ctx object. Both, DependenceInfo
192
293
  // and IslAstInfo must hold a reference to the isl_ctx object to ensure it is
193
293
  // not freed before the destruction of those analyses which might happen after
194
293
  // the destruction of the Scop/ScopInfo they refer to.  Hence, the isl_ctx
195
293
  // will not be freed and its space not reused as long there is a
196
293
  // DependenceInfo or IslAstInfo around.
197
293
  IslAst &Ast = AI.getIslAst();
198
293
  if (Ast.getSharedIslCtx() != S.getSharedIslCtx()) {
199
1
    LLVM_DEBUG(dbgs() << "Got an IstAst for a different Scop/isl_ctx\n");
200
1
    return false;
201
1
  }
202
292
203
292
  // Check if we created an isl_ast root node, otherwise exit.
204
292
  isl_ast_node *AstRoot = Ast.getAst();
205
292
  if (!AstRoot)
206
0
    return false;
207
292
208
292
  // Collect statistics. Do it before we modify the IR to avoid having it any
209
292
  // influence on the result.
210
292
  auto ScopStats = S.getStatistics();
211
292
  ScopsProcessed++;
212
292
213
292
  auto &DL = S.getFunction().getParent()->getDataLayout();
214
292
  Region *R = &S.getRegion();
215
292
  assert(!R->isTopLevelRegion() && "Top level regions are not supported");
216
292
217
292
  ScopAnnotator Annotator;
218
292
219
292
  simplifyRegion(R, &DT, &LI, &RI);
220
292
  assert(R->isSimple());
221
292
  BasicBlock *EnteringBB = S.getEnteringBlock();
222
292
  assert(EnteringBB);
223
292
  PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
224
292
225
292
  // Only build the run-time condition and parameters _after_ having
226
292
  // introduced the conditional branch. This is important as the conditional
227
292
  // branch will guard the original scop from new induction variables that
228
292
  // the SCEVExpander may introduce while code generating the parameters and
229
292
  // which may introduce scalar dependences that prevent us from correctly
230
292
  // code generating this scop.
231
292
  BBPair StartExitBlocks =
232
292
      std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI));
233
292
  BasicBlock *StartBlock = std::get<0>(StartExitBlocks);
234
292
  BasicBlock *ExitBlock = std::get<1>(StartExitBlocks);
235
292
236
292
  removeLifetimeMarkers(R);
237
292
  auto *SplitBlock = StartBlock->getSinglePredecessor();
238
292
239
292
  IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock);
240
292
241
292
  // All arrays must have their base pointers known before
242
292
  // ScopAnnotator::buildAliasScopes.
243
292
  NodeBuilder.allocateNewArrays(StartExitBlocks);
244
292
  Annotator.buildAliasScopes(S);
245
292
246
292
  if (PerfMonitoring) {
247
5
    PerfMonitor P(S, EnteringBB->getParent()->getParent());
248
5
    P.initialize();
249
5
    P.insertRegionStart(SplitBlock->getTerminator());
250
5
251
5
    BasicBlock *MergeBlock = ExitBlock->getUniqueSuccessor();
252
5
    P.insertRegionEnd(MergeBlock->getTerminator());
253
5
  }
254
292
255
292
  // First generate code for the hoisted invariant loads and transitively the
256
292
  // parameters they reference. Afterwards, for the remaining parameters that
257
292
  // might reference the hoisted loads. Finally, build the runtime check
258
292
  // that might reference both hoisted loads as well as parameters.
259
292
  // If the hoisting fails we have to bail and execute the original code.
260
292
  Builder.SetInsertPoint(SplitBlock->getTerminator());
261
292
  if (!NodeBuilder.preloadInvariantLoads()) {
262
4
    // Patch the introduced branch condition to ensure that we always execute
263
4
    // the original SCoP.
264
4
    auto *FalseI1 = Builder.getFalse();
265
4
    auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
266
4
    SplitBBTerm->setOperand(0, FalseI1);
267
4
268
4
    // Since the other branch is hence ignored we mark it as unreachable and
269
4
    // adjust the dominator tree accordingly.
270
4
    auto *ExitingBlock = StartBlock->getUniqueSuccessor();
271
4
    assert(ExitingBlock);
272
4
    auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
273
4
    assert(MergeBlock);
274
4
    markBlockUnreachable(*StartBlock, Builder);
275
4
    markBlockUnreachable(*ExitingBlock, Builder);
276
4
    auto *ExitingBB = S.getExitingBlock();
277
4
    assert(ExitingBB);
278
4
    DT.changeImmediateDominator(MergeBlock, ExitingBB);
279
4
    DT.eraseNode(ExitingBlock);
280
4
281
4
    isl_ast_node_free(AstRoot);
282
288
  } else {
283
288
    NodeBuilder.addParameters(S.getContext().release());
284
288
    Value *RTC = NodeBuilder.createRTC(AI.getRunCondition());
285
288
286
288
    Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
287
288
288
288
    // Explicitly set the insert point to the end of the block to avoid that a
289
288
    // split at the builder's current
290
288
    // insert position would move the malloc calls to the wrong BasicBlock.
291
288
    // Ideally we would just split the block during allocation of the new
292
288
    // arrays, but this would break the assumption that there are no blocks
293
288
    // between polly.start and polly.exiting (at this point).
294
288
    Builder.SetInsertPoint(StartBlock->getTerminator());
295
288
296
288
    NodeBuilder.create(AstRoot);
297
288
    NodeBuilder.finalize();
298
288
    fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI);
299
288
300
288
    CodegenedScops++;
301
288
    CodegenedAffineLoops += ScopStats.NumAffineLoops;
302
288
    CodegenedBoxedLoops += ScopStats.NumBoxedLoops;
303
288
  }
304
292
305
292
  Function *F = EnteringBB->getParent();
306
292
  verifyGeneratedFunction(S, *F, AI);
307
292
  for (auto *SubF : NodeBuilder.getParallelSubfunctions())
308
28
    verifyGeneratedFunction(S, *SubF, AI);
309
292
310
292
  // Mark the function such that we run additional cleanup passes on this
311
292
  // function (e.g. mem2reg to rediscover phi nodes).
312
292
  F->addFnAttr("polly-optimized");
313
292
  return true;
314
292
}
315
316
namespace {
317
318
class CodeGeneration : public ScopPass {
319
public:
320
  static char ID;
321
322
  /// The data layout used.
323
  const DataLayout *DL;
324
325
  /// @name The analysis passes we need to generate code.
326
  ///
327
  ///{
328
  LoopInfo *LI;
329
  IslAstInfo *AI;
330
  DominatorTree *DT;
331
  ScalarEvolution *SE;
332
  RegionInfo *RI;
333
  ///}
334
335
314
  CodeGeneration() : ScopPass(ID) {}
336
337
  /// Generate LLVM-IR for the SCoP @p S.
338
293
  bool runOnScop(Scop &S) override {
339
293
    // Skip SCoPs in case they're already code-generated by PPCGCodeGeneration.
340
293
    if (S.isToBeSkipped())
341
0
      return false;
342
293
343
293
    AI = &getAnalysis<IslAstInfoWrapperPass>().getAI();
344
293
    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
345
293
    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
346
293
    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
347
293
    DL = &S.getFunction().getParent()->getDataLayout();
348
293
    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
349
293
    return CodeGen(S, *AI, *LI, *DT, *SE, *RI);
350
293
  }
351
352
  /// Register all analyses and transformation required.
353
314
  void getAnalysisUsage(AnalysisUsage &AU) const override {
354
314
    ScopPass::getAnalysisUsage(AU);
355
314
356
314
    AU.addRequired<DominatorTreeWrapperPass>();
357
314
    AU.addRequired<IslAstInfoWrapperPass>();
358
314
    AU.addRequired<RegionInfoPass>();
359
314
    AU.addRequired<ScalarEvolutionWrapperPass>();
360
314
    AU.addRequired<ScopDetectionWrapperPass>();
361
314
    AU.addRequired<ScopInfoRegionPass>();
362
314
    AU.addRequired<LoopInfoWrapperPass>();
363
314
364
314
    AU.addPreserved<DependenceInfo>();
365
314
    AU.addPreserved<IslAstInfoWrapperPass>();
366
314
367
314
    // FIXME: We do not yet add regions for the newly generated code to the
368
314
    //        region tree.
369
314
  }
370
};
371
} // namespace
372
373
PreservedAnalyses CodeGenerationPass::run(Scop &S, ScopAnalysisManager &SAM,
374
                                          ScopStandardAnalysisResults &AR,
375
0
                                          SPMUpdater &U) {
376
0
  auto &AI = SAM.getResult<IslAstAnalysis>(S, AR);
377
0
  if (CodeGen(S, AI, AR.LI, AR.DT, AR.SE, AR.RI)) {
378
0
    U.invalidateScop(S);
379
0
    return PreservedAnalyses::none();
380
0
  }
381
0
382
0
  return PreservedAnalyses::all();
383
0
}
384
385
char CodeGeneration::ID = 1;
386
387
0
Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
388
389
43.8k
INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
390
43.8k
                      "Polly - Create LLVM-IR from SCoPs", false, false);
391
43.8k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
392
43.8k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
393
43.8k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
394
43.8k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
395
43.8k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
396
43.8k
INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass);
397
43.8k
INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
398
                    "Polly - Create LLVM-IR from SCoPs", false, false)