Coverage Report

Created: 2019-02-21 13:17

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