Coverage Report

Created: 2017-03-28 09:59

/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/Utils.h"
25
#include "polly/DependenceInfo.h"
26
#include "polly/LinkAllPasses.h"
27
#include "polly/Options.h"
28
#include "polly/ScopInfo.h"
29
#include "polly/Support/ScopHelper.h"
30
#include "llvm/Analysis/AliasAnalysis.h"
31
#include "llvm/Analysis/BasicAliasAnalysis.h"
32
#include "llvm/Analysis/GlobalsModRef.h"
33
#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
34
#include "llvm/IR/Module.h"
35
#include "llvm/IR/Verifier.h"
36
#include "llvm/Support/Debug.h"
37
38
using namespace polly;
39
using namespace llvm;
40
41
#define DEBUG_TYPE "polly-codegen"
42
43
static cl::opt<bool> Verify("polly-codegen-verify",
44
                            cl::desc("Verify the function generated by Polly"),
45
                            cl::Hidden, cl::init(true), cl::ZeroOrMore,
46
                            cl::cat(PollyCategory));
47
48
namespace {
49
class CodeGeneration : public ScopPass {
50
public:
51
  static char ID;
52
53
283
  CodeGeneration() : ScopPass(ID) {}
54
55
  /// The datalayout used
56
  const DataLayout *DL;
57
58
  /// @name The analysis passes we need to generate code.
59
  ///
60
  ///{
61
  LoopInfo *LI;
62
  IslAstInfo *AI;
63
  DominatorTree *DT;
64
  ScalarEvolution *SE;
65
  RegionInfo *RI;
66
  ///}
67
68
284
  void verifyGeneratedFunction(Scop &S, Function &F) {
69
284
    if (
!verifyFunction(F, &errs()) || 284
!Verify0
)
70
284
      return;
71
284
72
0
    
DEBUG0
({0
73
0
      errs() << "== ISL Codegen created an invalid function ==\n\n== The "
74
0
                "SCoP ==\n";
75
0
      S.print(errs());
76
0
      errs() << "\n== The isl AST ==\n";
77
0
      AI->printScop(errs(), S);
78
0
      errs() << "\n== The invalid function ==\n";
79
0
      F.print(errs());
80
0
    });
81
0
82
0
    llvm_unreachable("Polly generated function could not be verified. Add "
83
0
                     "-polly-codegen-verify=false to disable this assertion.");
84
0
  }
85
86
  // CodeGeneration adds a lot of BBs without updating the RegionInfo
87
  // We make all created BBs belong to the scop's parent region without any
88
  // nested structure to keep the RegionInfo verifier happy.
89
253
  void fixRegionInfo(Function *F, Region *ParentRegion) {
90
4.53k
    for (BasicBlock &BB : *F) {
91
4.53k
      if (RI->getRegionFor(&BB))
92
3.04k
        continue;
93
4.53k
94
1.49k
      RI->setRegionFor(&BB, ParentRegion);
95
1.49k
    }
96
253
  }
97
98
  /// Mark a basic block unreachable.
99
  ///
100
  /// Marks the basic block @p Block unreachable by equipping it with an
101
  /// UnreachableInst.
102
10
  void markBlockUnreachable(BasicBlock &Block, PollyIRBuilder &Builder) {
103
10
    auto *OrigTerminator = Block.getTerminator();
104
10
    Builder.SetInsertPoint(OrigTerminator);
105
10
    Builder.CreateUnreachable();
106
10
    OrigTerminator->eraseFromParent();
107
10
  }
108
109
  /// Generate LLVM-IR for the SCoP @p S.
110
258
  bool runOnScop(Scop &S) override {
111
258
    AI = &getAnalysis<IslAstInfo>();
112
258
113
258
    // Check if we created an isl_ast root node, otherwise exit.
114
258
    isl_ast_node *AstRoot = AI->getAst();
115
258
    if (!AstRoot)
116
0
      return false;
117
258
118
258
    LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
119
258
    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
120
258
    SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
121
258
    DL = &S.getFunction().getParent()->getDataLayout();
122
258
    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
123
258
    Region *R = &S.getRegion();
124
258
    assert(!R->isTopLevelRegion() && "Top level regions are not supported");
125
258
126
258
    ScopAnnotator Annotator;
127
258
    Annotator.buildAliasScopes(S);
128
258
129
258
    simplifyRegion(R, DT, LI, RI);
130
258
    assert(R->isSimple());
131
258
    BasicBlock *EnteringBB = S.getEnteringBlock();
132
258
    assert(EnteringBB);
133
258
    PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
134
258
135
258
    // Only build the run-time condition and parameters _after_ having
136
258
    // introduced the conditional branch. This is important as the conditional
137
258
    // branch will guard the original scop from new induction variables that
138
258
    // the SCEVExpander may introduce while code generating the parameters and
139
258
    // which may introduce scalar dependences that prevent us from correctly
140
258
    // code generating this scop.
141
258
    BasicBlock *StartBlock =
142
258
        executeScopConditionally(S, this, Builder.getTrue());
143
258
    auto *SplitBlock = StartBlock->getSinglePredecessor();
144
258
145
258
    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S,
146
258
                               StartBlock);
147
258
148
258
    // First generate code for the hoisted invariant loads and transitively the
149
258
    // parameters they reference. Afterwards, for the remaining parameters that
150
258
    // might reference the hoisted loads. Finally, build the runtime check
151
258
    // that might reference both hoisted loads as well as parameters.
152
258
    // If the hoisting fails we have to bail and execute the original code.
153
258
    Builder.SetInsertPoint(SplitBlock->getTerminator());
154
258
    if (
!NodeBuilder.preloadInvariantLoads()258
)
{5
155
5
156
5
      // Patch the introduced branch condition to ensure that we always execute
157
5
      // the original SCoP.
158
5
      auto *FalseI1 = Builder.getFalse();
159
5
      auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
160
5
      SplitBBTerm->setOperand(0, FalseI1);
161
5
162
5
      // Since the other branch is hence ignored we mark it as unreachable and
163
5
      // adjust the dominator tree accordingly.
164
5
      auto *ExitingBlock = StartBlock->getUniqueSuccessor();
165
5
      assert(ExitingBlock);
166
5
      auto *MergeBlock = ExitingBlock->getUniqueSuccessor();
167
5
      assert(MergeBlock);
168
5
      markBlockUnreachable(*StartBlock, Builder);
169
5
      markBlockUnreachable(*ExitingBlock, Builder);
170
5
      auto *ExitingBB = S.getExitingBlock();
171
5
      assert(ExitingBB);
172
5
      DT->changeImmediateDominator(MergeBlock, ExitingBB);
173
5
      DT->eraseNode(ExitingBlock);
174
5
175
5
      isl_ast_node_free(AstRoot);
176
253
    } else {
177
253
      NodeBuilder.allocateNewArrays();
178
253
      NodeBuilder.addParameters(S.getContext());
179
253
      Value *RTC = NodeBuilder.createRTC(AI->getRunCondition());
180
253
181
253
      Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
182
253
      Builder.SetInsertPoint(&StartBlock->front());
183
253
184
253
      NodeBuilder.create(AstRoot);
185
253
      NodeBuilder.finalize();
186
253
      fixRegionInfo(EnteringBB->getParent(), R->getParent());
187
253
    }
188
258
189
258
    Function *F = EnteringBB->getParent();
190
258
    verifyGeneratedFunction(S, *F);
191
258
    for (auto *SubF : NodeBuilder.getParallelSubfunctions())
192
26
      verifyGeneratedFunction(S, *SubF);
193
258
194
258
    // Mark the function such that we run additional cleanup passes on this
195
258
    // function (e.g. mem2reg to rediscover phi nodes).
196
258
    F->addFnAttr("polly-optimized");
197
258
198
258
    return true;
199
258
  }
200
201
  /// Register all analyses and transformation required.
202
283
  void getAnalysisUsage(AnalysisUsage &AU) const override {
203
283
    AU.addRequired<DominatorTreeWrapperPass>();
204
283
    AU.addRequired<IslAstInfo>();
205
283
    AU.addRequired<RegionInfoPass>();
206
283
    AU.addRequired<ScalarEvolutionWrapperPass>();
207
283
    AU.addRequired<ScopDetection>();
208
283
    AU.addRequired<ScopInfoRegionPass>();
209
283
    AU.addRequired<LoopInfoWrapperPass>();
210
283
211
283
    AU.addPreserved<DependenceInfo>();
212
283
213
283
    AU.addPreserved<AAResultsWrapperPass>();
214
283
    AU.addPreserved<BasicAAWrapperPass>();
215
283
    AU.addPreserved<LoopInfoWrapperPass>();
216
283
    AU.addPreserved<DominatorTreeWrapperPass>();
217
283
    AU.addPreserved<GlobalsAAWrapperPass>();
218
283
    AU.addPreserved<IslAstInfo>();
219
283
    AU.addPreserved<ScopDetection>();
220
283
    AU.addPreserved<ScalarEvolutionWrapperPass>();
221
283
    AU.addPreserved<SCEVAAWrapperPass>();
222
283
223
283
    // FIXME: We do not yet add regions for the newly generated code to the
224
283
    //        region tree.
225
283
    AU.addPreserved<RegionInfoPass>();
226
283
    AU.addPreserved<ScopInfoRegionPass>();
227
283
  }
228
};
229
} // namespace
230
231
char CodeGeneration::ID = 1;
232
233
0
Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
234
235
39.2k
INITIALIZE_PASS_BEGIN39.2k
(CodeGeneration, "polly-codegen",39.2k
236
39.2k
                      "Polly - Create LLVM-IR from SCoPs", false, false);
237
39.2k
INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
238
39.2k
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);
239
39.2k
INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);
240
39.2k
INITIALIZE_PASS_DEPENDENCY(RegionInfoPass);
241
39.2k
INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass);
242
39.2k
INITIALIZE_PASS_DEPENDENCY(ScopDetection);
243
39.2k
INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
244
                    "Polly - Create LLVM-IR from SCoPs", false, false)