Coverage Report

Created: 2017-04-29 12:21

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