Coverage Report

Created: 2017-08-21 19:50

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