Coverage Report

Created: 2017-04-29 12:21

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/CodeGen/LoopGenerators.cpp
Line
Count
Source
1
//===------ LoopGenerators.cpp -  IR helper to create loops ---------------===//
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
// This file contains functions to create scalar and parallel loops as LLVM-IR.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "polly/CodeGen/LoopGenerators.h"
15
#include "polly/ScopDetection.h"
16
#include "llvm/Analysis/LoopInfo.h"
17
#include "llvm/IR/DataLayout.h"
18
#include "llvm/IR/Dominators.h"
19
#include "llvm/IR/Module.h"
20
#include "llvm/Support/CommandLine.h"
21
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
22
23
using namespace llvm;
24
using namespace polly;
25
26
static cl::opt<int>
27
    PollyNumThreads("polly-num-threads",
28
                    cl::desc("Number of threads to use (0 = auto)"), cl::Hidden,
29
                    cl::init(0));
30
31
// We generate a loop of either of the following structures:
32
//
33
//              BeforeBB                      BeforeBB
34
//                 |                             |
35
//                 v                             v
36
//              GuardBB                      PreHeaderBB
37
//              /      |                         |   _____
38
//     __  PreHeaderBB  |                        v  \/    |
39
//    /  \    /         |                     HeaderBB  latch
40
// latch  HeaderBB      |                        |\       |
41
//    \  /    \         /                        | \------/
42
//     <       \       /                         |
43
//              \     /                          v
44
//              ExitBB                         ExitBB
45
//
46
// depending on whether or not we know that it is executed at least once. If
47
// not, GuardBB checks if the loop is executed at least once. If this is the
48
// case we branch to PreHeaderBB and subsequently to the HeaderBB, which
49
// contains the loop iv 'polly.indvar', the incremented loop iv
50
// 'polly.indvar_next' as well as the condition to check if we execute another
51
// iteration of the loop. After the loop has finished, we branch to ExitBB.
52
Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
53
                         PollyIRBuilder &Builder, LoopInfo &LI,
54
                         DominatorTree &DT, BasicBlock *&ExitBB,
55
                         ICmpInst::Predicate Predicate,
56
                         ScopAnnotator *Annotator, bool Parallel,
57
239
                         bool UseGuard) {
58
239
  Function *F = Builder.GetInsertBlock()->getParent();
59
239
  LLVMContext &Context = F->getContext();
60
239
61
239
  assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
62
239
  IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
63
239
  assert(LoopIVType && "UB is not integer?");
64
239
65
239
  BasicBlock *BeforeBB = Builder.GetInsertBlock();
66
239
  BasicBlock *GuardBB =
67
151
      UseGuard ? 
BasicBlock::Create(Context, "polly.loop_if", F)88
:
nullptr151
;
68
239
  BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
69
239
  BasicBlock *PreHeaderBB =
70
239
      BasicBlock::Create(Context, "polly.loop_preheader", F);
71
239
72
239
  // Update LoopInfo
73
239
  Loop *OuterLoop = LI.getLoopFor(BeforeBB);
74
239
  Loop *NewLoop = new Loop();
75
239
76
239
  if (OuterLoop)
77
55
    OuterLoop->addChildLoop(NewLoop);
78
239
  else
79
184
    LI.addTopLevelLoop(NewLoop);
80
239
81
239
  if (
OuterLoop239
)
{55
82
55
    if (GuardBB)
83
21
      OuterLoop->addBasicBlockToLoop(GuardBB, LI);
84
55
    OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI);
85
55
  }
86
239
87
239
  NewLoop->addBasicBlockToLoop(HeaderBB, LI);
88
239
89
239
  // Notify the annotator (if present) that we have a new loop, but only
90
239
  // after the header block is set.
91
239
  if (Annotator)
92
213
    Annotator->pushLoop(NewLoop, Parallel);
93
239
94
239
  // ExitBB
95
239
  ExitBB = SplitBlock(BeforeBB, &*Builder.GetInsertPoint(), &DT, &LI);
96
239
  ExitBB->setName("polly.loop_exit");
97
239
98
239
  // BeforeBB
99
239
  if (
GuardBB239
)
{88
100
88
    BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
101
88
    DT.addNewBlock(GuardBB, BeforeBB);
102
88
103
88
    // GuardBB
104
88
    Builder.SetInsertPoint(GuardBB);
105
88
    Value *LoopGuard;
106
88
    LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
107
88
    LoopGuard->setName("polly.loop_guard");
108
88
    Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
109
88
    DT.addNewBlock(PreHeaderBB, GuardBB);
110
151
  } else {
111
151
    BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
112
151
    DT.addNewBlock(PreHeaderBB, BeforeBB);
113
151
  }
114
239
115
239
  // PreHeaderBB
116
239
  Builder.SetInsertPoint(PreHeaderBB);
117
239
  Builder.CreateBr(HeaderBB);
118
239
119
239
  // HeaderBB
120
239
  DT.addNewBlock(HeaderBB, PreHeaderBB);
121
239
  Builder.SetInsertPoint(HeaderBB);
122
239
  PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
123
239
  IV->addIncoming(LB, PreHeaderBB);
124
239
  Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
125
239
  Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
126
239
  Value *LoopCondition;
127
239
  UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub");
128
239
  LoopCondition = Builder.CreateICmp(Predicate, IV, UB);
129
239
  LoopCondition->setName("polly.loop_cond");
130
239
131
239
  // Create the loop latch and annotate it as such.
132
239
  BranchInst *B = Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
133
239
  if (Annotator)
134
213
    Annotator->annotateLoopLatch(B, NewLoop, Parallel);
135
239
136
239
  IV->addIncoming(IncrementedIV, HeaderBB);
137
239
  if (GuardBB)
138
88
    DT.changeImmediateDominator(ExitBB, GuardBB);
139
239
  else
140
151
    DT.changeImmediateDominator(ExitBB, HeaderBB);
141
239
142
239
  // The loop body should be added here.
143
239
  Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
144
239
  return IV;
145
239
}
146
147
Value *ParallelLoopGenerator::createParallelLoop(
148
    Value *LB, Value *UB, Value *Stride, SetVector<Value *> &UsedValues,
149
26
    ValueMapT &Map, BasicBlock::iterator *LoopBody) {
150
26
  Function *SubFn;
151
26
152
26
  AllocaInst *Struct = storeValuesIntoStruct(UsedValues);
153
26
  BasicBlock::iterator BeforeLoop = Builder.GetInsertPoint();
154
26
  Value *IV = createSubFn(Stride, Struct, UsedValues, Map, &SubFn);
155
26
  *LoopBody = Builder.GetInsertPoint();
156
26
  Builder.SetInsertPoint(&*BeforeLoop);
157
26
158
26
  Value *SubFnParam = Builder.CreateBitCast(Struct, Builder.getInt8PtrTy(),
159
26
                                            "polly.par.userContext");
160
26
161
26
  // Add one as the upper bound provided by openmp is a < comparison
162
26
  // whereas the codegenForSequential function creates a <= comparison.
163
26
  UB = Builder.CreateAdd(UB, ConstantInt::get(LongType, 1));
164
26
165
26
  // Tell the runtime we start a parallel loop
166
26
  createCallSpawnThreads(SubFn, SubFnParam, LB, UB, Stride);
167
26
  Builder.CreateCall(SubFn, SubFnParam);
168
26
  createCallJoinThreads();
169
26
170
26
  return IV;
171
26
}
172
173
void ParallelLoopGenerator::createCallSpawnThreads(Value *SubFn,
174
                                                   Value *SubFnParam, Value *LB,
175
26
                                                   Value *UB, Value *Stride) {
176
26
  const std::string Name = "GOMP_parallel_loop_runtime_start";
177
26
178
26
  Function *F = M->getFunction(Name);
179
26
180
26
  // If F is not available, declare it.
181
26
  if (
!F26
)
{24
182
24
    GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
183
24
184
24
    Type *Params[] = {PointerType::getUnqual(FunctionType::get(
185
24
                          Builder.getVoidTy(), Builder.getInt8PtrTy(), false)),
186
24
                      Builder.getInt8PtrTy(),
187
24
                      Builder.getInt32Ty(),
188
24
                      LongType,
189
24
                      LongType,
190
24
                      LongType};
191
24
192
24
    FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), Params, false);
193
24
    F = Function::Create(Ty, Linkage, Name, M);
194
24
  }
195
26
196
26
  Value *NumberOfThreads = Builder.getInt32(PollyNumThreads);
197
26
  Value *Args[] = {SubFn, SubFnParam, NumberOfThreads, LB, UB, Stride};
198
26
199
26
  Builder.CreateCall(F, Args);
200
26
}
201
202
Value *ParallelLoopGenerator::createCallGetWorkItem(Value *LBPtr,
203
26
                                                    Value *UBPtr) {
204
26
  const std::string Name = "GOMP_loop_runtime_next";
205
26
206
26
  Function *F = M->getFunction(Name);
207
26
208
26
  // If F is not available, declare it.
209
26
  if (
!F26
)
{24
210
24
    GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
211
24
    Type *Params[] = {LongType->getPointerTo(), LongType->getPointerTo()};
212
24
    FunctionType *Ty = FunctionType::get(Builder.getInt8Ty(), Params, false);
213
24
    F = Function::Create(Ty, Linkage, Name, M);
214
24
  }
215
26
216
26
  Value *Args[] = {LBPtr, UBPtr};
217
26
  Value *Return = Builder.CreateCall(F, Args);
218
26
  Return = Builder.CreateICmpNE(
219
26
      Return, Builder.CreateZExt(Builder.getFalse(), Return->getType()));
220
26
  return Return;
221
26
}
222
223
26
void ParallelLoopGenerator::createCallJoinThreads() {
224
26
  const std::string Name = "GOMP_parallel_end";
225
26
226
26
  Function *F = M->getFunction(Name);
227
26
228
26
  // If F is not available, declare it.
229
26
  if (
!F26
)
{24
230
24
    GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
231
24
232
24
    FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
233
24
    F = Function::Create(Ty, Linkage, Name, M);
234
24
  }
235
26
236
26
  Builder.CreateCall(F, {});
237
26
}
238
239
26
void ParallelLoopGenerator::createCallCleanupThread() {
240
26
  const std::string Name = "GOMP_loop_end_nowait";
241
26
242
26
  Function *F = M->getFunction(Name);
243
26
244
26
  // If F is not available, declare it.
245
26
  if (
!F26
)
{24
246
24
    GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
247
24
248
24
    FunctionType *Ty = FunctionType::get(Builder.getVoidTy(), false);
249
24
    F = Function::Create(Ty, Linkage, Name, M);
250
24
  }
251
26
252
26
  Builder.CreateCall(F, {});
253
26
}
254
255
26
Function *ParallelLoopGenerator::createSubFnDefinition() {
256
26
  Function *F = Builder.GetInsertBlock()->getParent();
257
26
  std::vector<Type *> Arguments(1, Builder.getInt8PtrTy());
258
26
  FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false);
259
26
  Function *SubFn = Function::Create(FT, Function::InternalLinkage,
260
26
                                     F->getName() + "_polly_subfn", M);
261
26
262
26
  // Certain backends (e.g., NVPTX) do not support '.'s in function names.
263
26
  // Hence, we ensure that all '.'s are replaced by '_'s.
264
26
  std::string FunctionName = SubFn->getName();
265
26
  std::replace(FunctionName.begin(), FunctionName.end(), '.', '_');
266
26
  SubFn->setName(FunctionName);
267
26
268
26
  // Do not run any polly pass on the new function.
269
26
  SubFn->addFnAttr(PollySkipFnAttr);
270
26
271
26
  Function::arg_iterator AI = SubFn->arg_begin();
272
26
  AI->setName("polly.par.userContext");
273
26
274
26
  return SubFn;
275
26
}
276
277
AllocaInst *
278
26
ParallelLoopGenerator::storeValuesIntoStruct(SetVector<Value *> &Values) {
279
26
  SmallVector<Type *, 8> Members;
280
26
281
26
  for (Value *V : Values)
282
58
    Members.push_back(V->getType());
283
26
284
26
  const DataLayout &DL = Builder.GetInsertBlock()->getModule()->getDataLayout();
285
26
286
26
  // We do not want to allocate the alloca inside any loop, thus we allocate it
287
26
  // in the entry block of the function and use annotations to denote the actual
288
26
  // live span (similar to clang).
289
26
  BasicBlock &EntryBB = Builder.GetInsertBlock()->getParent()->getEntryBlock();
290
26
  Instruction *IP = &*EntryBB.getFirstInsertionPt();
291
26
  StructType *Ty = StructType::get(Builder.getContext(), Members);
292
26
  AllocaInst *Struct = new AllocaInst(Ty, DL.getAllocaAddrSpace(), nullptr,
293
26
                                      "polly.par.userContext", IP);
294
26
295
84
  for (unsigned i = 0; 
i < Values.size()84
;
i++58
)
{58
296
58
    Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
297
58
    Address->setName("polly.subfn.storeaddr." + Values[i]->getName());
298
58
    Builder.CreateStore(Values[i], Address);
299
58
  }
300
26
301
26
  return Struct;
302
26
}
303
304
void ParallelLoopGenerator::extractValuesFromStruct(
305
26
    SetVector<Value *> OldValues, Type *Ty, Value *Struct, ValueMapT &Map) {
306
84
  for (unsigned i = 0; 
i < OldValues.size()84
;
i++58
)
{58
307
58
    Value *Address = Builder.CreateStructGEP(Ty, Struct, i);
308
58
    Value *NewValue = Builder.CreateLoad(Address);
309
58
    NewValue->setName("polly.subfunc.arg." + OldValues[i]->getName());
310
58
    Map[OldValues[i]] = NewValue;
311
58
  }
312
26
}
313
314
Value *ParallelLoopGenerator::createSubFn(Value *Stride, AllocaInst *StructData,
315
                                          SetVector<Value *> Data,
316
26
                                          ValueMapT &Map, Function **SubFnPtr) {
317
26
  BasicBlock *PrevBB, *HeaderBB, *ExitBB, *CheckNextBB, *PreHeaderBB, *AfterBB;
318
26
  Value *LBPtr, *UBPtr, *UserContext, *Ret1, *HasNextSchedule, *LB, *UB, *IV;
319
26
  Function *SubFn = createSubFnDefinition();
320
26
  LLVMContext &Context = SubFn->getContext();
321
26
322
26
  // Store the previous basic block.
323
26
  PrevBB = Builder.GetInsertBlock();
324
26
325
26
  // Create basic blocks.
326
26
  HeaderBB = BasicBlock::Create(Context, "polly.par.setup", SubFn);
327
26
  ExitBB = BasicBlock::Create(Context, "polly.par.exit", SubFn);
328
26
  CheckNextBB = BasicBlock::Create(Context, "polly.par.checkNext", SubFn);
329
26
  PreHeaderBB = BasicBlock::Create(Context, "polly.par.loadIVBounds", SubFn);
330
26
331
26
  DT.addNewBlock(HeaderBB, PrevBB);
332
26
  DT.addNewBlock(ExitBB, HeaderBB);
333
26
  DT.addNewBlock(CheckNextBB, HeaderBB);
334
26
  DT.addNewBlock(PreHeaderBB, HeaderBB);
335
26
336
26
  // Fill up basic block HeaderBB.
337
26
  Builder.SetInsertPoint(HeaderBB);
338
26
  LBPtr = Builder.CreateAlloca(LongType, nullptr, "polly.par.LBPtr");
339
26
  UBPtr = Builder.CreateAlloca(LongType, nullptr, "polly.par.UBPtr");
340
26
  UserContext = Builder.CreateBitCast(
341
26
      &*SubFn->arg_begin(), StructData->getType(), "polly.par.userContext");
342
26
343
26
  extractValuesFromStruct(Data, StructData->getAllocatedType(), UserContext,
344
26
                          Map);
345
26
  Builder.CreateBr(CheckNextBB);
346
26
347
26
  // Add code to check if another set of iterations will be executed.
348
26
  Builder.SetInsertPoint(CheckNextBB);
349
26
  Ret1 = createCallGetWorkItem(LBPtr, UBPtr);
350
26
  HasNextSchedule = Builder.CreateTrunc(Ret1, Builder.getInt1Ty(),
351
26
                                        "polly.par.hasNextScheduleBlock");
352
26
  Builder.CreateCondBr(HasNextSchedule, PreHeaderBB, ExitBB);
353
26
354
26
  // Add code to load the iv bounds for this set of iterations.
355
26
  Builder.SetInsertPoint(PreHeaderBB);
356
26
  LB = Builder.CreateLoad(LBPtr, "polly.par.LB");
357
26
  UB = Builder.CreateLoad(UBPtr, "polly.par.UB");
358
26
359
26
  // Subtract one as the upper bound provided by openmp is a < comparison
360
26
  // whereas the codegenForSequential function creates a <= comparison.
361
26
  UB = Builder.CreateSub(UB, ConstantInt::get(LongType, 1),
362
26
                         "polly.par.UBAdjusted");
363
26
364
26
  Builder.CreateBr(CheckNextBB);
365
26
  Builder.SetInsertPoint(&*--Builder.GetInsertPoint());
366
26
  IV = createLoop(LB, UB, Stride, Builder, LI, DT, AfterBB, ICmpInst::ICMP_SLE,
367
26
                  nullptr, true, /* UseGuard */ false);
368
26
369
26
  BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
370
26
371
26
  // Add code to terminate this subfunction.
372
26
  Builder.SetInsertPoint(ExitBB);
373
26
  createCallCleanupThread();
374
26
  Builder.CreateRetVoid();
375
26
376
26
  Builder.SetInsertPoint(&*LoopBody);
377
26
  *SubFnPtr = SubFn;
378
26
379
26
  return IV;
380
26
}