Coverage Report

Created: 2017-10-03 07:32

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