blob: cf762b0136472534bc8d3539ba4ed578285e58f1 [file] [log] [blame]
Tobias Grosser75805372011-04-29 06:27:02 +00001//===------ CodeGeneration.cpp - Code generate the Scops. -----------------===//
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 Cloog.
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. Cloog is used to generate an abstract syntax tree (clast) that
16// reflects the updated execution order. This clast is used to create new
17// LLVM-IR that is computational equivalent to the original control flow region,
18// but executes its code in the new execution order defined by the changed
19// scattering.
20//
21//===----------------------------------------------------------------------===//
22
23#define DEBUG_TYPE "polly-codegen"
24
25#include "polly/LinkAllPasses.h"
26#include "polly/Support/GICHelper.h"
27#include "polly/Support/ScopHelper.h"
28#include "polly/Cloog.h"
29#include "polly/Dependences.h"
30#include "polly/ScopInfo.h"
31#include "polly/TempScopInfo.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Debug.h"
34#include "llvm/Support/IRBuilder.h"
35#include "llvm/Analysis/LoopInfo.h"
36#include "llvm/Analysis/ScalarEvolutionExpander.h"
Tobias Grosser8c4cfc322011-05-14 19:01:49 +000037#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Tobias Grosser75805372011-04-29 06:27:02 +000038#include "llvm/Target/TargetData.h"
39#include "llvm/Module.h"
40#include "llvm/ADT/SetVector.h"
41
42#define CLOOG_INT_GMP 1
43#include "cloog/cloog.h"
44#include "cloog/isl/cloog.h"
45
46#include <vector>
47#include <utility>
48
49using namespace polly;
50using namespace llvm;
51
52struct isl_set;
53
54namespace polly {
55
56static cl::opt<bool>
57Vector("enable-polly-vector",
58 cl::desc("Enable polly vector code generation"), cl::Hidden,
59 cl::value_desc("Vector code generation enabled if true"),
60 cl::init(false));
61
62static cl::opt<bool>
63OpenMP("enable-polly-openmp",
64 cl::desc("Generate OpenMP parallel code"), cl::Hidden,
65 cl::value_desc("OpenMP code generation enabled if true"),
66 cl::init(false));
67
68static cl::opt<bool>
69AtLeastOnce("enable-polly-atLeastOnce",
70 cl::desc("Give polly the hint, that every loop is executed at least"
71 "once"), cl::Hidden,
72 cl::value_desc("OpenMP code generation enabled if true"),
73 cl::init(false));
74
75static cl::opt<bool>
76Aligned("enable-polly-aligned",
77 cl::desc("Assumed aligned memory accesses."), cl::Hidden,
78 cl::value_desc("OpenMP code generation enabled if true"),
79 cl::init(false));
80
Tobias Grosser75805372011-04-29 06:27:02 +000081typedef DenseMap<const Value*, Value*> ValueMapT;
82typedef DenseMap<const char*, Value*> CharMapT;
83typedef std::vector<ValueMapT> VectorValueMapT;
84
85// Create a new loop.
86//
87// @param Builder The builder used to create the loop. It also defines the
88// place where to create the loop.
89// @param UB The upper bound of the loop iv.
90// @param Stride The number by which the loop iv is incremented after every
91// iteration.
92static void createLoop(IRBuilder<> *Builder, Value *LB, Value *UB, APInt Stride,
93 PHINode*& IV, BasicBlock*& AfterBB, Value*& IncrementedIV,
94 DominatorTree *DT) {
95 Function *F = Builder->GetInsertBlock()->getParent();
96 LLVMContext &Context = F->getContext();
97
98 BasicBlock *PreheaderBB = Builder->GetInsertBlock();
99 BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
100 BasicBlock *BodyBB = BasicBlock::Create(Context, "polly.loop_body", F);
101 AfterBB = BasicBlock::Create(Context, "polly.after_loop", F);
102
103 Builder->CreateBr(HeaderBB);
104 DT->addNewBlock(HeaderBB, PreheaderBB);
105
106 Builder->SetInsertPoint(BodyBB);
107
108 Builder->SetInsertPoint(HeaderBB);
109
110 // Use the type of upper and lower bound.
111 assert(LB->getType() == UB->getType()
112 && "Different types for upper and lower bound.");
113
Tobias Grosser55927aa2011-07-18 09:53:32 +0000114 IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
Tobias Grosser75805372011-04-29 06:27:02 +0000115 assert(LoopIVType && "UB is not integer?");
116
117 // IV
118 IV = Builder->CreatePHI(LoopIVType, 2, "polly.loopiv");
119 IV->addIncoming(LB, PreheaderBB);
120
121 // IV increment.
122 Value *StrideValue = ConstantInt::get(LoopIVType,
123 Stride.zext(LoopIVType->getBitWidth()));
124 IncrementedIV = Builder->CreateAdd(IV, StrideValue, "polly.next_loopiv");
125
126 // Exit condition.
127 if (AtLeastOnce) { // At least on iteration.
128 UB = Builder->CreateAdd(UB, Builder->getInt64(1));
129 Value *CMP = Builder->CreateICmpEQ(IV, UB);
130 Builder->CreateCondBr(CMP, AfterBB, BodyBB);
131 } else { // Maybe not executed at all.
132 Value *CMP = Builder->CreateICmpSLE(IV, UB);
133 Builder->CreateCondBr(CMP, BodyBB, AfterBB);
134 }
135 DT->addNewBlock(BodyBB, HeaderBB);
136 DT->addNewBlock(AfterBB, HeaderBB);
137
138 Builder->SetInsertPoint(BodyBB);
139}
140
141class BlockGenerator {
142 IRBuilder<> &Builder;
143 ValueMapT &VMap;
144 VectorValueMapT &ValueMaps;
145 Scop &S;
146 ScopStmt &statement;
147 isl_set *scatteringDomain;
148
149public:
150 BlockGenerator(IRBuilder<> &B, ValueMapT &vmap, VectorValueMapT &vmaps,
151 ScopStmt &Stmt, isl_set *domain)
152 : Builder(B), VMap(vmap), ValueMaps(vmaps), S(*Stmt.getParent()),
153 statement(Stmt), scatteringDomain(domain) {}
154
155 const Region &getRegion() {
156 return S.getRegion();
157 }
158
159 Value* makeVectorOperand(Value *operand, int vectorWidth) {
160 if (operand->getType()->isVectorTy())
161 return operand;
162
163 VectorType *vectorType = VectorType::get(operand->getType(), vectorWidth);
164 Value *vector = UndefValue::get(vectorType);
165 vector = Builder.CreateInsertElement(vector, operand, Builder.getInt32(0));
166
167 std::vector<Constant*> splat;
168
169 for (int i = 0; i < vectorWidth; i++)
170 splat.push_back (Builder.getInt32(0));
171
172 Constant *splatVector = ConstantVector::get(splat);
173
174 return Builder.CreateShuffleVector(vector, vector, splatVector);
175 }
176
Raghesh Aloor490c5982011-08-08 08:34:16 +0000177 Value* getOperand(const Value *oldOperand, ValueMapT &BBMap,
Tobias Grosser75805372011-04-29 06:27:02 +0000178 ValueMapT *VectorMap = 0) {
Raghesh Aloor490c5982011-08-08 08:34:16 +0000179 const Instruction *OpInst = dyn_cast<Instruction>(oldOperand);
Tobias Grosser75805372011-04-29 06:27:02 +0000180
181 if (!OpInst)
Raghesh Aloor490c5982011-08-08 08:34:16 +0000182 return const_cast<Value*>(oldOperand);
Tobias Grosser75805372011-04-29 06:27:02 +0000183
Raghesh Aloor490c5982011-08-08 08:34:16 +0000184 if (VectorMap && VectorMap->count(oldOperand))
185 return (*VectorMap)[oldOperand];
Tobias Grosser75805372011-04-29 06:27:02 +0000186
187 // IVS and Parameters.
Raghesh Aloor490c5982011-08-08 08:34:16 +0000188 if (VMap.count(oldOperand)) {
189 Value *NewOperand = VMap[oldOperand];
Tobias Grosser75805372011-04-29 06:27:02 +0000190
191 // Insert a cast if types are different
Raghesh Aloor490c5982011-08-08 08:34:16 +0000192 if (oldOperand->getType()->getScalarSizeInBits()
Tobias Grosser75805372011-04-29 06:27:02 +0000193 < NewOperand->getType()->getScalarSizeInBits())
194 NewOperand = Builder.CreateTruncOrBitCast(NewOperand,
Raghesh Aloor490c5982011-08-08 08:34:16 +0000195 oldOperand->getType());
Tobias Grosser75805372011-04-29 06:27:02 +0000196
197 return NewOperand;
198 }
199
200 // Instructions calculated in the current BB.
Raghesh Aloor490c5982011-08-08 08:34:16 +0000201 if (BBMap.count(oldOperand)) {
202 return BBMap[oldOperand];
Tobias Grosser75805372011-04-29 06:27:02 +0000203 }
204
205 // Ignore instructions that are referencing ops in the old BB. These
206 // instructions are unused. They where replace by new ones during
207 // createIndependentBlocks().
208 if (getRegion().contains(OpInst->getParent()))
209 return NULL;
210
Raghesh Aloor490c5982011-08-08 08:34:16 +0000211 return const_cast<Value*>(oldOperand);
Tobias Grosser75805372011-04-29 06:27:02 +0000212 }
213
Tobias Grosser55927aa2011-07-18 09:53:32 +0000214 Type *getVectorPtrTy(const Value *V, int vectorWidth) {
215 PointerType *pointerType = dyn_cast<PointerType>(V->getType());
Tobias Grosser75805372011-04-29 06:27:02 +0000216 assert(pointerType && "PointerType expected");
217
Tobias Grosser55927aa2011-07-18 09:53:32 +0000218 Type *scalarType = pointerType->getElementType();
Tobias Grosser75805372011-04-29 06:27:02 +0000219 VectorType *vectorType = VectorType::get(scalarType, vectorWidth);
220
221 return PointerType::getUnqual(vectorType);
222 }
223
224 /// @brief Load a vector from a set of adjacent scalars
225 ///
226 /// In case a set of scalars is known to be next to each other in memory,
227 /// create a vector load that loads those scalars
228 ///
229 /// %vector_ptr= bitcast double* %p to <4 x double>*
230 /// %vec_full = load <4 x double>* %vector_ptr
231 ///
232 Value *generateStrideOneLoad(const LoadInst *load, ValueMapT &BBMap,
233 int size) {
234 const Value *pointer = load->getPointerOperand();
Tobias Grosser55927aa2011-07-18 09:53:32 +0000235 Type *vectorPtrType = getVectorPtrTy(pointer, size);
Tobias Grosser75805372011-04-29 06:27:02 +0000236 Value *newPointer = getOperand(pointer, BBMap);
237 Value *VectorPtr = Builder.CreateBitCast(newPointer, vectorPtrType,
238 "vector_ptr");
239 LoadInst *VecLoad = Builder.CreateLoad(VectorPtr,
240 load->getNameStr()
241 + "_p_vec_full");
242 if (!Aligned)
243 VecLoad->setAlignment(8);
244
245 return VecLoad;
246 }
247
248 /// @brief Load a vector initialized from a single scalar in memory
249 ///
250 /// In case all elements of a vector are initialized to the same
251 /// scalar value, this value is loaded and shuffeled into all elements
252 /// of the vector.
253 ///
254 /// %splat_one = load <1 x double>* %p
255 /// %splat = shufflevector <1 x double> %splat_one, <1 x
256 /// double> %splat_one, <4 x i32> zeroinitializer
257 ///
258 Value *generateStrideZeroLoad(const LoadInst *load, ValueMapT &BBMap,
259 int size) {
260 const Value *pointer = load->getPointerOperand();
Tobias Grosser55927aa2011-07-18 09:53:32 +0000261 Type *vectorPtrType = getVectorPtrTy(pointer, 1);
Tobias Grosser75805372011-04-29 06:27:02 +0000262 Value *newPointer = getOperand(pointer, BBMap);
263 Value *vectorPtr = Builder.CreateBitCast(newPointer, vectorPtrType,
264 load->getNameStr() + "_p_vec_p");
265 LoadInst *scalarLoad= Builder.CreateLoad(vectorPtr,
266 load->getNameStr() + "_p_splat_one");
267
268 if (!Aligned)
269 scalarLoad->setAlignment(8);
270
271 std::vector<Constant*> splat;
272
273 for (int i = 0; i < size; i++)
274 splat.push_back (Builder.getInt32(0));
275
276 Constant *splatVector = ConstantVector::get(splat);
277
278 Value *vectorLoad = Builder.CreateShuffleVector(scalarLoad, scalarLoad,
279 splatVector,
280 load->getNameStr()
281 + "_p_splat");
282 return vectorLoad;
283 }
284
285 /// @Load a vector from scalars distributed in memory
286 ///
287 /// In case some scalars a distributed randomly in memory. Create a vector
288 /// by loading each scalar and by inserting one after the other into the
289 /// vector.
290 ///
291 /// %scalar_1= load double* %p_1
292 /// %vec_1 = insertelement <2 x double> undef, double %scalar_1, i32 0
293 /// %scalar 2 = load double* %p_2
294 /// %vec_2 = insertelement <2 x double> %vec_1, double %scalar_1, i32 1
295 ///
296 Value *generateUnknownStrideLoad(const LoadInst *load,
297 VectorValueMapT &scalarMaps,
298 int size) {
299 const Value *pointer = load->getPointerOperand();
300 VectorType *vectorType = VectorType::get(
301 dyn_cast<PointerType>(pointer->getType())->getElementType(), size);
302
303 Value *vector = UndefValue::get(vectorType);
304
305 for (int i = 0; i < size; i++) {
306 Value *newPointer = getOperand(pointer, scalarMaps[i]);
307 Value *scalarLoad = Builder.CreateLoad(newPointer,
308 load->getNameStr() + "_p_scalar_");
309 vector = Builder.CreateInsertElement(vector, scalarLoad,
310 Builder.getInt32(i),
311 load->getNameStr() + "_p_vec_");
312 }
313
314 return vector;
315 }
316
Raghesh Aloor62b13122011-08-03 17:02:50 +0000317 /// @brief Get the new operand address according to the changed access in
318 /// JSCOP file.
319 Value *getNewAccessOperand(isl_map *newAccessRelation, Value *baseAddr,
Raghesh Aloor490c5982011-08-08 08:34:16 +0000320 const Value *oldOperand, ValueMapT &BBMap) {
Raghesh Aloor62b13122011-08-03 17:02:50 +0000321 unsigned accessIdx = 0;
322 Value *newOperand = Builder.CreateStructGEP(baseAddr,
323 accessIdx, "p_newarrayidx_");
324 return newOperand;
325 }
326
327 /// @brief Generate the operand address
328 Value *generateLocationAccessed(const Instruction *Inst,
329 const Value *pointer, ValueMapT &BBMap ) {
Raghesh Aloor490c5982011-08-08 08:34:16 +0000330 MemoryAccess &access = statement.getAccessFor(Inst);
331 isl_map *newAccessRelation = access.getNewAccessFunction();
Raghesh Aloor62b13122011-08-03 17:02:50 +0000332 if (!newAccessRelation) {
333 Value *newPointer = getOperand(pointer, BBMap);
334 return newPointer;
335 }
336
Raghesh Aloor490c5982011-08-08 08:34:16 +0000337 Value *baseAddr = const_cast<Value*>(access.getBaseAddr());
Raghesh Aloor62b13122011-08-03 17:02:50 +0000338 Value *newPointer = getNewAccessOperand(newAccessRelation, baseAddr,
339 pointer, BBMap);
340 return newPointer;
341 }
342
Tobias Grosser75805372011-04-29 06:27:02 +0000343 Value *generateScalarLoad(const LoadInst *load, ValueMapT &BBMap) {
344 const Value *pointer = load->getPointerOperand();
Raghesh Aloor62b13122011-08-03 17:02:50 +0000345 const Instruction *Inst = dyn_cast<Instruction>(load);
346 Value *newPointer = generateLocationAccessed(Inst, pointer, BBMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000347 Value *scalarLoad = Builder.CreateLoad(newPointer,
348 load->getNameStr() + "_p_scalar_");
349 return scalarLoad;
350 }
351
352 /// @brief Load a value (or several values as a vector) from memory.
353 void generateLoad(const LoadInst *load, ValueMapT &vectorMap,
354 VectorValueMapT &scalarMaps, int vectorWidth) {
355
356 if (scalarMaps.size() == 1) {
357 scalarMaps[0][load] = generateScalarLoad(load, scalarMaps[0]);
358 return;
359 }
360
361 Value *newLoad;
362
363 MemoryAccess &Access = statement.getAccessFor(load);
364
365 assert(scatteringDomain && "No scattering domain available");
366
367 if (Access.isStrideZero(scatteringDomain))
368 newLoad = generateStrideZeroLoad(load, scalarMaps[0], vectorWidth);
369 else if (Access.isStrideOne(scatteringDomain))
370 newLoad = generateStrideOneLoad(load, scalarMaps[0], vectorWidth);
371 else
372 newLoad = generateUnknownStrideLoad(load, scalarMaps, vectorWidth);
373
374 vectorMap[load] = newLoad;
375 }
376
377 void copyInstruction(const Instruction *Inst, ValueMapT &BBMap,
378 ValueMapT &vectorMap, VectorValueMapT &scalarMaps,
379 int vectorDimension, int vectorWidth) {
380 // If this instruction is already in the vectorMap, a vector instruction
381 // was already issued, that calculates the values of all dimensions. No
382 // need to create any more instructions.
383 if (vectorMap.count(Inst))
384 return;
385
386 // Terminator instructions control the control flow. They are explicitally
387 // expressed in the clast and do not need to be copied.
388 if (Inst->isTerminator())
389 return;
390
391 if (const LoadInst *load = dyn_cast<LoadInst>(Inst)) {
392 generateLoad(load, vectorMap, scalarMaps, vectorWidth);
393 return;
394 }
395
396 if (const BinaryOperator *binaryInst = dyn_cast<BinaryOperator>(Inst)) {
397 Value *opZero = Inst->getOperand(0);
398 Value *opOne = Inst->getOperand(1);
399
400 // This is an old instruction that can be ignored.
401 if (!opZero && !opOne)
402 return;
403
404 bool isVectorOp = vectorMap.count(opZero) || vectorMap.count(opOne);
405
406 if (isVectorOp && vectorDimension > 0)
407 return;
408
409 Value *newOpZero, *newOpOne;
410 newOpZero = getOperand(opZero, BBMap, &vectorMap);
411 newOpOne = getOperand(opOne, BBMap, &vectorMap);
412
413
414 std::string name;
415 if (isVectorOp) {
416 newOpZero = makeVectorOperand(newOpZero, vectorWidth);
417 newOpOne = makeVectorOperand(newOpOne, vectorWidth);
418 name = Inst->getNameStr() + "p_vec";
419 } else
420 name = Inst->getNameStr() + "p_sca";
421
422 Value *newInst = Builder.CreateBinOp(binaryInst->getOpcode(), newOpZero,
423 newOpOne, name);
424 if (isVectorOp)
425 vectorMap[Inst] = newInst;
426 else
427 BBMap[Inst] = newInst;
428
429 return;
430 }
431
432 if (const StoreInst *store = dyn_cast<StoreInst>(Inst)) {
433 if (vectorMap.count(store->getValueOperand()) > 0) {
434
435 // We only need to generate one store if we are in vector mode.
436 if (vectorDimension > 0)
437 return;
438
439 MemoryAccess &Access = statement.getAccessFor(store);
440
441 assert(scatteringDomain && "No scattering domain available");
442
443 const Value *pointer = store->getPointerOperand();
444 Value *vector = getOperand(store->getValueOperand(), BBMap, &vectorMap);
445
446 if (Access.isStrideOne(scatteringDomain)) {
Tobias Grosser55927aa2011-07-18 09:53:32 +0000447 Type *vectorPtrType = getVectorPtrTy(pointer, vectorWidth);
Tobias Grosser75805372011-04-29 06:27:02 +0000448 Value *newPointer = getOperand(pointer, BBMap, &vectorMap);
449
450 Value *VectorPtr = Builder.CreateBitCast(newPointer, vectorPtrType,
451 "vector_ptr");
452 StoreInst *Store = Builder.CreateStore(vector, VectorPtr);
453
454 if (!Aligned)
455 Store->setAlignment(8);
456 } else {
457 for (unsigned i = 0; i < scalarMaps.size(); i++) {
458 Value *scalar = Builder.CreateExtractElement(vector,
459 Builder.getInt32(i));
460 Value *newPointer = getOperand(pointer, scalarMaps[i]);
461 Builder.CreateStore(scalar, newPointer);
462 }
463 }
464
465 return;
466 }
467 }
468
469 Instruction *NewInst = Inst->clone();
470
471 // Copy the operands in temporary vector, as an in place update
472 // fails if an instruction is referencing the same operand twice.
473 std::vector<Value*> Operands(NewInst->op_begin(), NewInst->op_end());
474
475 // Replace old operands with the new ones.
476 for (std::vector<Value*>::iterator UI = Operands.begin(),
477 UE = Operands.end(); UI != UE; ++UI) {
478 Value *newOperand = getOperand(*UI, BBMap);
479
480 if (!newOperand) {
481 assert(!isa<StoreInst>(NewInst)
482 && "Store instructions are always needed!");
483 delete NewInst;
484 return;
485 }
486
487 NewInst->replaceUsesOfWith(*UI, newOperand);
488 }
489
490 Builder.Insert(NewInst);
491 BBMap[Inst] = NewInst;
492
493 if (!NewInst->getType()->isVoidTy())
494 NewInst->setName("p_" + Inst->getName());
495 }
496
497 int getVectorSize() {
498 return ValueMaps.size();
499 }
500
501 bool isVectorBlock() {
502 return getVectorSize() > 1;
503 }
504
505 // Insert a copy of a basic block in the newly generated code.
506 //
507 // @param Builder The builder used to insert the code. It also specifies
508 // where to insert the code.
509 // @param BB The basic block to copy
510 // @param VMap A map returning for any old value its new equivalent. This
511 // is used to update the operands of the statements.
512 // For new statements a relation old->new is inserted in this
513 // map.
514 void copyBB(BasicBlock *BB, DominatorTree *DT) {
515 Function *F = Builder.GetInsertBlock()->getParent();
516 LLVMContext &Context = F->getContext();
517 BasicBlock *CopyBB = BasicBlock::Create(Context,
518 "polly.stmt_" + BB->getNameStr(),
519 F);
520 Builder.CreateBr(CopyBB);
521 DT->addNewBlock(CopyBB, Builder.GetInsertBlock());
522 Builder.SetInsertPoint(CopyBB);
523
524 // Create two maps that store the mapping from the original instructions of
525 // the old basic block to their copies in the new basic block. Those maps
526 // are basic block local.
527 //
528 // As vector code generation is supported there is one map for scalar values
529 // and one for vector values.
530 //
531 // In case we just do scalar code generation, the vectorMap is not used and
532 // the scalarMap has just one dimension, which contains the mapping.
533 //
534 // In case vector code generation is done, an instruction may either appear
535 // in the vector map once (as it is calculating >vectorwidth< values at a
536 // time. Or (if the values are calculated using scalar operations), it
537 // appears once in every dimension of the scalarMap.
538 VectorValueMapT scalarBlockMap(getVectorSize());
539 ValueMapT vectorBlockMap;
540
541 for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
542 II != IE; ++II)
543 for (int i = 0; i < getVectorSize(); i++) {
544 if (isVectorBlock())
545 VMap = ValueMaps[i];
546
547 copyInstruction(II, scalarBlockMap[i], vectorBlockMap,
548 scalarBlockMap, i, getVectorSize());
549 }
550 }
551};
552
553/// Class to generate LLVM-IR that calculates the value of a clast_expr.
554class ClastExpCodeGen {
555 IRBuilder<> &Builder;
556 const CharMapT *IVS;
557
Tobias Grosser55927aa2011-07-18 09:53:32 +0000558 Value *codegen(const clast_name *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000559 CharMapT::const_iterator I = IVS->find(e->name);
560
561 if (I != IVS->end())
562 return Builder.CreateSExtOrBitCast(I->second, Ty);
563 else
564 llvm_unreachable("Clast name not found");
565 }
566
Tobias Grosser55927aa2011-07-18 09:53:32 +0000567 Value *codegen(const clast_term *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000568 APInt a = APInt_from_MPZ(e->val);
569
570 Value *ConstOne = ConstantInt::get(Builder.getContext(), a);
571 ConstOne = Builder.CreateSExtOrBitCast(ConstOne, Ty);
572
573 if (e->var) {
574 Value *var = codegen(e->var, Ty);
575 return Builder.CreateMul(ConstOne, var);
576 }
577
578 return ConstOne;
579 }
580
Tobias Grosser55927aa2011-07-18 09:53:32 +0000581 Value *codegen(const clast_binary *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000582 Value *LHS = codegen(e->LHS, Ty);
583
584 APInt RHS_AP = APInt_from_MPZ(e->RHS);
585
586 Value *RHS = ConstantInt::get(Builder.getContext(), RHS_AP);
587 RHS = Builder.CreateSExtOrBitCast(RHS, Ty);
588
589 switch (e->type) {
590 case clast_bin_mod:
591 return Builder.CreateSRem(LHS, RHS);
592 case clast_bin_fdiv:
593 {
594 // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
595 Value *One = ConstantInt::get(Builder.getInt1Ty(), 1);
596 Value *Zero = ConstantInt::get(Builder.getInt1Ty(), 0);
597 One = Builder.CreateZExtOrBitCast(One, Ty);
598 Zero = Builder.CreateZExtOrBitCast(Zero, Ty);
599 Value *Sum1 = Builder.CreateSub(LHS, RHS);
600 Value *Sum2 = Builder.CreateAdd(Sum1, One);
601 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
602 Value *Dividend = Builder.CreateSelect(isNegative, Sum2, LHS);
603 return Builder.CreateSDiv(Dividend, RHS);
604 }
605 case clast_bin_cdiv:
606 {
607 // ceild(n,d) ((n < 0) ? n : (n + d - 1)) / d
608 Value *One = ConstantInt::get(Builder.getInt1Ty(), 1);
609 Value *Zero = ConstantInt::get(Builder.getInt1Ty(), 0);
610 One = Builder.CreateZExtOrBitCast(One, Ty);
611 Zero = Builder.CreateZExtOrBitCast(Zero, Ty);
612 Value *Sum1 = Builder.CreateAdd(LHS, RHS);
613 Value *Sum2 = Builder.CreateSub(Sum1, One);
614 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
615 Value *Dividend = Builder.CreateSelect(isNegative, LHS, Sum2);
616 return Builder.CreateSDiv(Dividend, RHS);
617 }
618 case clast_bin_div:
619 return Builder.CreateSDiv(LHS, RHS);
620 default:
621 llvm_unreachable("Unknown clast binary expression type");
622 };
623 }
624
Tobias Grosser55927aa2011-07-18 09:53:32 +0000625 Value *codegen(const clast_reduction *r, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000626 assert(( r->type == clast_red_min
627 || r->type == clast_red_max
628 || r->type == clast_red_sum)
629 && "Clast reduction type not supported");
630 Value *old = codegen(r->elts[0], Ty);
631
632 for (int i=1; i < r->n; ++i) {
633 Value *exprValue = codegen(r->elts[i], Ty);
634
635 switch (r->type) {
636 case clast_red_min:
637 {
638 Value *cmp = Builder.CreateICmpSLT(old, exprValue);
639 old = Builder.CreateSelect(cmp, old, exprValue);
640 break;
641 }
642 case clast_red_max:
643 {
644 Value *cmp = Builder.CreateICmpSGT(old, exprValue);
645 old = Builder.CreateSelect(cmp, old, exprValue);
646 break;
647 }
648 case clast_red_sum:
649 old = Builder.CreateAdd(old, exprValue);
650 break;
651 default:
652 llvm_unreachable("Clast unknown reduction type");
653 }
654 }
655
656 return old;
657 }
658
659public:
660
661 // A generator for clast expressions.
662 //
663 // @param B The IRBuilder that defines where the code to calculate the
664 // clast expressions should be inserted.
665 // @param IVMAP A Map that translates strings describing the induction
666 // variables to the Values* that represent these variables
667 // on the LLVM side.
668 ClastExpCodeGen(IRBuilder<> &B, CharMapT *IVMap) : Builder(B), IVS(IVMap) {}
669
670 // Generates code to calculate a given clast expression.
671 //
672 // @param e The expression to calculate.
673 // @return The Value that holds the result.
Tobias Grosser55927aa2011-07-18 09:53:32 +0000674 Value *codegen(const clast_expr *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000675 switch(e->type) {
676 case clast_expr_name:
677 return codegen((const clast_name *)e, Ty);
678 case clast_expr_term:
679 return codegen((const clast_term *)e, Ty);
680 case clast_expr_bin:
681 return codegen((const clast_binary *)e, Ty);
682 case clast_expr_red:
683 return codegen((const clast_reduction *)e, Ty);
684 default:
685 llvm_unreachable("Unknown clast expression!");
686 }
687 }
688
689 // @brief Reset the CharMap.
690 //
691 // This function is called to reset the CharMap to new one, while generating
692 // OpenMP code.
693 void setIVS(CharMapT *IVSNew) {
694 IVS = IVSNew;
695 }
696
697};
698
699class ClastStmtCodeGen {
700 // The Scop we code generate.
701 Scop *S;
702 ScalarEvolution &SE;
Tobias Grosser75805372011-04-29 06:27:02 +0000703 DominatorTree *DT;
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000704 ScopDetection *SD;
Tobias Grosser75805372011-04-29 06:27:02 +0000705 Dependences *DP;
706 TargetData *TD;
707
708 // The Builder specifies the current location to code generate at.
709 IRBuilder<> &Builder;
710
711 // Map the Values from the old code to their counterparts in the new code.
712 ValueMapT ValueMap;
713
714 // clastVars maps from the textual representation of a clast variable to its
715 // current *Value. clast variables are scheduling variables, original
716 // induction variables or parameters. They are used either in loop bounds or
717 // to define the statement instance that is executed.
718 //
719 // for (s = 0; s < n + 3; ++i)
720 // for (t = s; t < m; ++j)
721 // Stmt(i = s + 3 * m, j = t);
722 //
723 // {s,t,i,j,n,m} is the set of clast variables in this clast.
724 CharMapT *clastVars;
725
726 // Codegenerator for clast expressions.
727 ClastExpCodeGen ExpGen;
728
729 // Do we currently generate parallel code?
730 bool parallelCodeGeneration;
731
732 std::vector<std::string> parallelLoops;
733
734public:
735
736 const std::vector<std::string> &getParallelLoops() {
737 return parallelLoops;
738 }
739
740 protected:
741 void codegen(const clast_assignment *a) {
742 (*clastVars)[a->LHS] = ExpGen.codegen(a->RHS,
743 TD->getIntPtrType(Builder.getContext()));
744 }
745
746 void codegen(const clast_assignment *a, ScopStmt *Statement,
747 unsigned Dimension, int vectorDim,
748 std::vector<ValueMapT> *VectorVMap = 0) {
749 Value *RHS = ExpGen.codegen(a->RHS,
750 TD->getIntPtrType(Builder.getContext()));
751
752 assert(!a->LHS && "Statement assignments do not have left hand side");
753 const PHINode *PN;
754 PN = Statement->getInductionVariableForDimension(Dimension);
755 const Value *V = PN;
756
Tobias Grosser75805372011-04-29 06:27:02 +0000757 if (VectorVMap)
758 (*VectorVMap)[vectorDim][V] = RHS;
759
760 ValueMap[V] = RHS;
761 }
762
763 void codegenSubstitutions(const clast_stmt *Assignment,
764 ScopStmt *Statement, int vectorDim = 0,
765 std::vector<ValueMapT> *VectorVMap = 0) {
766 int Dimension = 0;
767
768 while (Assignment) {
769 assert(CLAST_STMT_IS_A(Assignment, stmt_ass)
770 && "Substitions are expected to be assignments");
771 codegen((const clast_assignment *)Assignment, Statement, Dimension,
772 vectorDim, VectorVMap);
773 Assignment = Assignment->next;
774 Dimension++;
775 }
776 }
777
778 void codegen(const clast_user_stmt *u, std::vector<Value*> *IVS = NULL,
779 const char *iterator = NULL, isl_set *scatteringDomain = 0) {
780 ScopStmt *Statement = (ScopStmt *)u->statement->usr;
781 BasicBlock *BB = Statement->getBasicBlock();
782
783 if (u->substitutions)
784 codegenSubstitutions(u->substitutions, Statement);
785
786 int vectorDimensions = IVS ? IVS->size() : 1;
787
788 VectorValueMapT VectorValueMap(vectorDimensions);
789
790 if (IVS) {
791 assert (u->substitutions && "Substitutions expected!");
792 int i = 0;
793 for (std::vector<Value*>::iterator II = IVS->begin(), IE = IVS->end();
794 II != IE; ++II) {
795 (*clastVars)[iterator] = *II;
796 codegenSubstitutions(u->substitutions, Statement, i, &VectorValueMap);
797 i++;
798 }
799 }
800
801 BlockGenerator Generator(Builder, ValueMap, VectorValueMap, *Statement,
802 scatteringDomain);
803 Generator.copyBB(BB, DT);
804 }
805
806 void codegen(const clast_block *b) {
807 if (b->body)
808 codegen(b->body);
809 }
810
811 /// @brief Create a classical sequential loop.
812 void codegenForSequential(const clast_for *f, Value *lowerBound = 0,
813 Value *upperBound = 0) {
814 APInt Stride = APInt_from_MPZ(f->stride);
815 PHINode *IV;
816 Value *IncrementedIV;
817 BasicBlock *AfterBB;
818 // The value of lowerbound and upperbound will be supplied, if this
819 // function is called while generating OpenMP code. Otherwise get
820 // the values.
821 assert(((lowerBound && upperBound) || (!lowerBound && !upperBound))
822 && "Either give both bounds or none");
823 if (lowerBound == 0 || upperBound == 0) {
824 lowerBound = ExpGen.codegen(f->LB,
825 TD->getIntPtrType(Builder.getContext()));
826 upperBound = ExpGen.codegen(f->UB,
827 TD->getIntPtrType(Builder.getContext()));
828 }
829 createLoop(&Builder, lowerBound, upperBound, Stride, IV, AfterBB,
830 IncrementedIV, DT);
831
832 // Add loop iv to symbols.
833 (*clastVars)[f->iterator] = IV;
834
835 if (f->body)
836 codegen(f->body);
837
838 // Loop is finished, so remove its iv from the live symbols.
839 clastVars->erase(f->iterator);
840
841 BasicBlock *HeaderBB = *pred_begin(AfterBB);
842 BasicBlock *LastBodyBB = Builder.GetInsertBlock();
843 Builder.CreateBr(HeaderBB);
844 IV->addIncoming(IncrementedIV, LastBodyBB);
845 Builder.SetInsertPoint(AfterBB);
846 }
847
Tobias Grosser75805372011-04-29 06:27:02 +0000848 /// @brief Add a new definition of an openmp subfunction.
849 Function* addOpenMPSubfunction(Module *M) {
850 Function *F = Builder.GetInsertBlock()->getParent();
851 const std::string &Name = F->getNameStr() + ".omp_subfn";
852
Tobias Grosser851b96e2011-07-12 12:42:54 +0000853 std::vector<Type*> Arguments(1, Builder.getInt8PtrTy());
Tobias Grosser75805372011-04-29 06:27:02 +0000854 FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false);
855 Function *FN = Function::Create(FT, Function::InternalLinkage, Name, M);
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000856 // Do not run any polly pass on the new function.
857 SD->markFunctionAsInvalid(FN);
Tobias Grosser75805372011-04-29 06:27:02 +0000858
859 Function::arg_iterator AI = FN->arg_begin();
860 AI->setName("omp.userContext");
861
862 return FN;
863 }
864
865 /// @brief Add values to the OpenMP structure.
866 ///
867 /// Create the subfunction structure and add the values from the list.
868 Value *addValuesToOpenMPStruct(SetVector<Value*> OMPDataVals,
869 Function *SubFunction) {
Tobias Grosser851b96e2011-07-12 12:42:54 +0000870 std::vector<Type*> structMembers;
Tobias Grosser75805372011-04-29 06:27:02 +0000871
872 // Create the structure.
873 for (unsigned i = 0; i < OMPDataVals.size(); i++)
874 structMembers.push_back(OMPDataVals[i]->getType());
875
Tobias Grosser75805372011-04-29 06:27:02 +0000876 StructType *structTy = StructType::get(Builder.getContext(),
877 structMembers);
Tobias Grosser75805372011-04-29 06:27:02 +0000878 // Store the values into the structure.
879 Value *structData = Builder.CreateAlloca(structTy, 0, "omp.userContext");
880 for (unsigned i = 0; i < OMPDataVals.size(); i++) {
881 Value *storeAddr = Builder.CreateStructGEP(structData, i);
882 Builder.CreateStore(OMPDataVals[i], storeAddr);
883 }
884
885 return structData;
886 }
887
888 /// @brief Create OpenMP structure values.
889 ///
890 /// Create a list of values that has to be stored into the subfuncition
891 /// structure.
892 SetVector<Value*> createOpenMPStructValues() {
893 SetVector<Value*> OMPDataVals;
894
895 // Push the clast variables available in the clastVars.
896 for (CharMapT::iterator I = clastVars->begin(), E = clastVars->end();
897 I != E; I++)
898 OMPDataVals.insert(I->second);
899
900 // Push the base addresses of memory references.
901 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
902 ScopStmt *Stmt = *SI;
903 for (SmallVector<MemoryAccess*, 8>::iterator I = Stmt->memacc_begin(),
904 E = Stmt->memacc_end(); I != E; ++I) {
905 Value *BaseAddr = const_cast<Value*>((*I)->getBaseAddr());
906 OMPDataVals.insert((BaseAddr));
907 }
908 }
909
910 return OMPDataVals;
911 }
912
913 /// @brief Extract the values from the subfunction parameter.
914 ///
915 /// Extract the values from the subfunction parameter and update the clast
916 /// variables to point to the new values.
917 void extractValuesFromOpenMPStruct(CharMapT *clastVarsOMP,
918 SetVector<Value*> OMPDataVals,
919 Value *userContext) {
920 // Extract the clast variables.
921 unsigned i = 0;
922 for (CharMapT::iterator I = clastVars->begin(), E = clastVars->end();
923 I != E; I++) {
924 Value *loadAddr = Builder.CreateStructGEP(userContext, i);
925 (*clastVarsOMP)[I->first] = Builder.CreateLoad(loadAddr);
926 i++;
927 }
928
929 // Extract the base addresses of memory references.
930 for (unsigned j = i; j < OMPDataVals.size(); j++) {
931 Value *loadAddr = Builder.CreateStructGEP(userContext, j);
932 Value *baseAddr = OMPDataVals[j];
933 ValueMap[baseAddr] = Builder.CreateLoad(loadAddr);
934 }
935
936 }
937
938 /// @brief Add body to the subfunction.
939 void addOpenMPSubfunctionBody(Function *FN, const clast_for *f,
940 Value *structData,
941 SetVector<Value*> OMPDataVals) {
942 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
943 LLVMContext &Context = FN->getContext();
Tobias Grosser55927aa2011-07-18 09:53:32 +0000944 IntegerType *intPtrTy = TD->getIntPtrType(Context);
Tobias Grosser75805372011-04-29 06:27:02 +0000945
946 // Store the previous basic block.
947 BasicBlock *PrevBB = Builder.GetInsertBlock();
948
949 // Create basic blocks.
950 BasicBlock *HeaderBB = BasicBlock::Create(Context, "omp.setup", FN);
951 BasicBlock *ExitBB = BasicBlock::Create(Context, "omp.exit", FN);
952 BasicBlock *checkNextBB = BasicBlock::Create(Context, "omp.checkNext", FN);
953 BasicBlock *loadIVBoundsBB = BasicBlock::Create(Context, "omp.loadIVBounds",
954 FN);
955
956 DT->addNewBlock(HeaderBB, PrevBB);
957 DT->addNewBlock(ExitBB, HeaderBB);
958 DT->addNewBlock(checkNextBB, HeaderBB);
959 DT->addNewBlock(loadIVBoundsBB, HeaderBB);
960
961 // Fill up basic block HeaderBB.
962 Builder.SetInsertPoint(HeaderBB);
963 Value *lowerBoundPtr = Builder.CreateAlloca(intPtrTy, 0,
964 "omp.lowerBoundPtr");
965 Value *upperBoundPtr = Builder.CreateAlloca(intPtrTy, 0,
966 "omp.upperBoundPtr");
967 Value *userContext = Builder.CreateBitCast(FN->arg_begin(),
968 structData->getType(),
969 "omp.userContext");
970
971 CharMapT clastVarsOMP;
972 extractValuesFromOpenMPStruct(&clastVarsOMP, OMPDataVals, userContext);
973
974 Builder.CreateBr(checkNextBB);
975
976 // Add code to check if another set of iterations will be executed.
977 Builder.SetInsertPoint(checkNextBB);
978 Function *runtimeNextFunction = M->getFunction("GOMP_loop_runtime_next");
979 Value *ret1 = Builder.CreateCall2(runtimeNextFunction,
980 lowerBoundPtr, upperBoundPtr);
981 Value *hasNextSchedule = Builder.CreateTrunc(ret1, Builder.getInt1Ty(),
982 "omp.hasNextScheduleBlock");
983 Builder.CreateCondBr(hasNextSchedule, loadIVBoundsBB, ExitBB);
984
985 // Add code to to load the iv bounds for this set of iterations.
986 Builder.SetInsertPoint(loadIVBoundsBB);
987 Value *lowerBound = Builder.CreateLoad(lowerBoundPtr, "omp.lowerBound");
988 Value *upperBound = Builder.CreateLoad(upperBoundPtr, "omp.upperBound");
989
990 // Subtract one as the upper bound provided by openmp is a < comparison
991 // whereas the codegenForSequential function creates a <= comparison.
992 upperBound = Builder.CreateSub(upperBound, ConstantInt::get(intPtrTy, 1),
993 "omp.upperBoundAdjusted");
994
995 // Use clastVarsOMP during code generation of the OpenMP subfunction.
996 CharMapT *oldClastVars = clastVars;
997 clastVars = &clastVarsOMP;
998 ExpGen.setIVS(&clastVarsOMP);
999
1000 codegenForSequential(f, lowerBound, upperBound);
1001
1002 // Restore the old clastVars.
1003 clastVars = oldClastVars;
1004 ExpGen.setIVS(oldClastVars);
1005
1006 Builder.CreateBr(checkNextBB);
1007
1008 // Add code to terminate this openmp subfunction.
1009 Builder.SetInsertPoint(ExitBB);
1010 Function *endnowaitFunction = M->getFunction("GOMP_loop_end_nowait");
1011 Builder.CreateCall(endnowaitFunction);
1012 Builder.CreateRetVoid();
1013
1014 // Restore the builder back to previous basic block.
1015 Builder.SetInsertPoint(PrevBB);
1016 }
1017
1018 /// @brief Create an OpenMP parallel for loop.
1019 ///
1020 /// This loop reflects a loop as if it would have been created by an OpenMP
1021 /// statement.
1022 void codegenForOpenMP(const clast_for *f) {
1023 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
Tobias Grosser55927aa2011-07-18 09:53:32 +00001024 IntegerType *intPtrTy = TD->getIntPtrType(Builder.getContext());
Tobias Grosser75805372011-04-29 06:27:02 +00001025
1026 Function *SubFunction = addOpenMPSubfunction(M);
1027 SetVector<Value*> OMPDataVals = createOpenMPStructValues();
1028 Value *structData = addValuesToOpenMPStruct(OMPDataVals, SubFunction);
1029
1030 addOpenMPSubfunctionBody(SubFunction, f, structData, OMPDataVals);
1031
1032 // Create call for GOMP_parallel_loop_runtime_start.
1033 Value *subfunctionParam = Builder.CreateBitCast(structData,
1034 Builder.getInt8PtrTy(),
1035 "omp_data");
1036
1037 Value *numberOfThreads = Builder.getInt32(0);
1038 Value *lowerBound = ExpGen.codegen(f->LB, intPtrTy);
1039 Value *upperBound = ExpGen.codegen(f->UB, intPtrTy);
1040
1041 // Add one as the upper bound provided by openmp is a < comparison
1042 // whereas the codegenForSequential function creates a <= comparison.
1043 upperBound = Builder.CreateAdd(upperBound, ConstantInt::get(intPtrTy, 1));
1044 APInt APStride = APInt_from_MPZ(f->stride);
1045 Value *stride = ConstantInt::get(intPtrTy,
1046 APStride.zext(intPtrTy->getBitWidth()));
1047
1048 SmallVector<Value *, 6> Arguments;
1049 Arguments.push_back(SubFunction);
1050 Arguments.push_back(subfunctionParam);
1051 Arguments.push_back(numberOfThreads);
1052 Arguments.push_back(lowerBound);
1053 Arguments.push_back(upperBound);
1054 Arguments.push_back(stride);
1055
1056 Function *parallelStartFunction =
1057 M->getFunction("GOMP_parallel_loop_runtime_start");
Tobias Grosser0679e172011-07-15 22:54:41 +00001058 Builder.CreateCall(parallelStartFunction, Arguments);
Tobias Grosser75805372011-04-29 06:27:02 +00001059
1060 // Create call to the subfunction.
1061 Builder.CreateCall(SubFunction, subfunctionParam);
1062
1063 // Create call for GOMP_parallel_end.
1064 Function *FN = M->getFunction("GOMP_parallel_end");
1065 Builder.CreateCall(FN);
1066 }
1067
1068 bool isInnermostLoop(const clast_for *f) {
1069 const clast_stmt *stmt = f->body;
1070
1071 while (stmt) {
1072 if (!CLAST_STMT_IS_A(stmt, stmt_user))
1073 return false;
1074
1075 stmt = stmt->next;
1076 }
1077
1078 return true;
1079 }
1080
1081 /// @brief Get the number of loop iterations for this loop.
1082 /// @param f The clast for loop to check.
1083 int getNumberOfIterations(const clast_for *f) {
1084 isl_set *loopDomain = isl_set_copy(isl_set_from_cloog_domain(f->domain));
1085 isl_set *tmp = isl_set_copy(loopDomain);
1086
1087 // Calculate a map similar to the identity map, but with the last input
1088 // and output dimension not related.
1089 // [i0, i1, i2, i3] -> [i0, i1, i2, o0]
1090 isl_dim *dim = isl_set_get_dim(loopDomain);
1091 dim = isl_dim_drop_outputs(dim, isl_set_n_dim(loopDomain) - 2, 1);
1092 dim = isl_dim_map_from_set(dim);
1093 isl_map *identity = isl_map_identity(dim);
1094 identity = isl_map_add_dims(identity, isl_dim_in, 1);
1095 identity = isl_map_add_dims(identity, isl_dim_out, 1);
1096
1097 isl_map *map = isl_map_from_domain_and_range(tmp, loopDomain);
1098 map = isl_map_intersect(map, identity);
1099
1100 isl_map *lexmax = isl_map_lexmax(isl_map_copy(map));
1101 isl_map *lexmin = isl_map_lexmin(isl_map_copy(map));
1102 isl_map *sub = isl_map_sum(lexmax, isl_map_neg(lexmin));
1103
1104 isl_set *elements = isl_map_range(sub);
1105
1106 if (!isl_set_is_singleton(elements))
1107 return -1;
1108
1109 isl_point *p = isl_set_sample_point(elements);
1110
1111 isl_int v;
1112 isl_int_init(v);
1113 isl_point_get_coordinate(p, isl_dim_set, isl_set_n_dim(loopDomain) - 1, &v);
1114 int numberIterations = isl_int_get_si(v);
1115 isl_int_clear(v);
1116
1117 return (numberIterations) / isl_int_get_si(f->stride) + 1;
1118 }
1119
1120 /// @brief Create vector instructions for this loop.
1121 void codegenForVector(const clast_for *f) {
1122 DEBUG(dbgs() << "Vectorizing loop '" << f->iterator << "'\n";);
1123 int vectorWidth = getNumberOfIterations(f);
1124
1125 Value *LB = ExpGen.codegen(f->LB,
1126 TD->getIntPtrType(Builder.getContext()));
1127
1128 APInt Stride = APInt_from_MPZ(f->stride);
Tobias Grosser55927aa2011-07-18 09:53:32 +00001129 IntegerType *LoopIVType = dyn_cast<IntegerType>(LB->getType());
Tobias Grosser75805372011-04-29 06:27:02 +00001130 Stride = Stride.zext(LoopIVType->getBitWidth());
1131 Value *StrideValue = ConstantInt::get(LoopIVType, Stride);
1132
1133 std::vector<Value*> IVS(vectorWidth);
1134 IVS[0] = LB;
1135
1136 for (int i = 1; i < vectorWidth; i++)
1137 IVS[i] = Builder.CreateAdd(IVS[i-1], StrideValue, "p_vector_iv");
1138
1139 isl_set *scatteringDomain = isl_set_from_cloog_domain(f->domain);
1140
1141 // Add loop iv to symbols.
1142 (*clastVars)[f->iterator] = LB;
1143
1144 const clast_stmt *stmt = f->body;
1145
1146 while (stmt) {
1147 codegen((const clast_user_stmt *)stmt, &IVS, f->iterator,
1148 scatteringDomain);
1149 stmt = stmt->next;
1150 }
1151
1152 // Loop is finished, so remove its iv from the live symbols.
1153 clastVars->erase(f->iterator);
1154 }
1155
1156 void codegen(const clast_for *f) {
Hongbin Zhengdbdebe22011-05-03 13:46:58 +00001157 if (Vector && isInnermostLoop(f) && DP->isParallelFor(f)
Tobias Grosser75805372011-04-29 06:27:02 +00001158 && (-1 != getNumberOfIterations(f))
1159 && (getNumberOfIterations(f) <= 16)) {
1160 codegenForVector(f);
Hongbin Zhengdbdebe22011-05-03 13:46:58 +00001161 } else if (OpenMP && !parallelCodeGeneration && DP->isParallelFor(f)) {
Tobias Grosser75805372011-04-29 06:27:02 +00001162 parallelCodeGeneration = true;
1163 parallelLoops.push_back(f->iterator);
1164 codegenForOpenMP(f);
1165 parallelCodeGeneration = false;
1166 } else
1167 codegenForSequential(f);
1168 }
1169
1170 Value *codegen(const clast_equation *eq) {
1171 Value *LHS = ExpGen.codegen(eq->LHS,
1172 TD->getIntPtrType(Builder.getContext()));
1173 Value *RHS = ExpGen.codegen(eq->RHS,
1174 TD->getIntPtrType(Builder.getContext()));
1175 CmpInst::Predicate P;
1176
1177 if (eq->sign == 0)
1178 P = ICmpInst::ICMP_EQ;
1179 else if (eq->sign > 0)
1180 P = ICmpInst::ICMP_SGE;
1181 else
1182 P = ICmpInst::ICMP_SLE;
1183
1184 return Builder.CreateICmp(P, LHS, RHS);
1185 }
1186
1187 void codegen(const clast_guard *g) {
1188 Function *F = Builder.GetInsertBlock()->getParent();
1189 LLVMContext &Context = F->getContext();
1190 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
1191 BasicBlock *MergeBB = BasicBlock::Create(Context, "polly.merge", F);
1192 DT->addNewBlock(ThenBB, Builder.GetInsertBlock());
1193 DT->addNewBlock(MergeBB, Builder.GetInsertBlock());
1194
1195 Value *Predicate = codegen(&(g->eq[0]));
1196
1197 for (int i = 1; i < g->n; ++i) {
1198 Value *TmpPredicate = codegen(&(g->eq[i]));
1199 Predicate = Builder.CreateAnd(Predicate, TmpPredicate);
1200 }
1201
1202 Builder.CreateCondBr(Predicate, ThenBB, MergeBB);
1203 Builder.SetInsertPoint(ThenBB);
1204
1205 codegen(g->then);
1206
1207 Builder.CreateBr(MergeBB);
1208 Builder.SetInsertPoint(MergeBB);
1209 }
1210
1211 void codegen(const clast_stmt *stmt) {
1212 if (CLAST_STMT_IS_A(stmt, stmt_root))
1213 assert(false && "No second root statement expected");
1214 else if (CLAST_STMT_IS_A(stmt, stmt_ass))
1215 codegen((const clast_assignment *)stmt);
1216 else if (CLAST_STMT_IS_A(stmt, stmt_user))
1217 codegen((const clast_user_stmt *)stmt);
1218 else if (CLAST_STMT_IS_A(stmt, stmt_block))
1219 codegen((const clast_block *)stmt);
1220 else if (CLAST_STMT_IS_A(stmt, stmt_for))
1221 codegen((const clast_for *)stmt);
1222 else if (CLAST_STMT_IS_A(stmt, stmt_guard))
1223 codegen((const clast_guard *)stmt);
1224
1225 if (stmt->next)
1226 codegen(stmt->next);
1227 }
1228
1229 void addParameters(const CloogNames *names) {
Tobias Grosser97fb5ac2011-06-30 19:39:10 +00001230 SCEVExpander Rewriter(SE, "polly");
Tobias Grosser75805372011-04-29 06:27:02 +00001231
1232 // Create an instruction that specifies the location where the parameters
1233 // are expanded.
1234 CastInst::CreateIntegerCast(ConstantInt::getTrue(Builder.getContext()),
1235 Builder.getInt16Ty(), false, "insertInst",
1236 Builder.GetInsertBlock());
1237
1238 int i = 0;
1239 for (Scop::param_iterator PI = S->param_begin(), PE = S->param_end();
1240 PI != PE; ++PI) {
1241 assert(i < names->nb_parameters && "Not enough parameter names");
1242
1243 const SCEV *Param = *PI;
Tobias Grosser55927aa2011-07-18 09:53:32 +00001244 Type *Ty = Param->getType();
Tobias Grosser75805372011-04-29 06:27:02 +00001245
1246 Instruction *insertLocation = --(Builder.GetInsertBlock()->end());
1247 Value *V = Rewriter.expandCodeFor(Param, Ty, insertLocation);
1248 (*clastVars)[names->parameters[i]] = V;
1249
1250 ++i;
1251 }
1252 }
1253
1254 public:
1255 void codegen(const clast_root *r) {
1256 clastVars = new CharMapT();
1257 addParameters(r->names);
1258 ExpGen.setIVS(clastVars);
1259
1260 parallelCodeGeneration = false;
1261
1262 const clast_stmt *stmt = (const clast_stmt*) r;
1263 if (stmt->next)
1264 codegen(stmt->next);
1265
1266 delete clastVars;
1267 }
1268
1269 ClastStmtCodeGen(Scop *scop, ScalarEvolution &se, DominatorTree *dt,
Hongbin Zheng94c5df12011-05-06 02:38:20 +00001270 ScopDetection *sd, Dependences *dp, TargetData *td,
1271 IRBuilder<> &B) :
1272 S(scop), SE(se), DT(dt), SD(sd), DP(dp), TD(td), Builder(B),
1273 ExpGen(Builder, NULL) {}
Tobias Grosser75805372011-04-29 06:27:02 +00001274
1275};
1276}
1277
1278namespace {
1279class CodeGeneration : public ScopPass {
1280 Region *region;
1281 Scop *S;
1282 DominatorTree *DT;
1283 ScalarEvolution *SE;
1284 ScopDetection *SD;
Tobias Grosser75805372011-04-29 06:27:02 +00001285 TargetData *TD;
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001286 RegionInfo *RI;
Tobias Grosser75805372011-04-29 06:27:02 +00001287
1288 std::vector<std::string> parallelLoops;
1289
1290 public:
1291 static char ID;
1292
1293 CodeGeneration() : ScopPass(ID) {}
1294
Tobias Grosser75805372011-04-29 06:27:02 +00001295 // Adding prototypes required if OpenMP is enabled.
1296 void addOpenMPDefinitions(IRBuilder<> &Builder)
1297 {
1298 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
1299 LLVMContext &Context = Builder.getContext();
Tobias Grosser851b96e2011-07-12 12:42:54 +00001300 IntegerType *intPtrTy = TD->getIntPtrType(Context);
Tobias Grosser75805372011-04-29 06:27:02 +00001301
1302 if (!M->getFunction("GOMP_parallel_end")) {
1303 FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), false);
1304 Function::Create(FT, Function::ExternalLinkage, "GOMP_parallel_end", M);
1305 }
1306
1307 if (!M->getFunction("GOMP_parallel_loop_runtime_start")) {
1308 // Type of first argument.
Tobias Grosser851b96e2011-07-12 12:42:54 +00001309 std::vector<Type*> Arguments(1, Builder.getInt8PtrTy());
Tobias Grosser75805372011-04-29 06:27:02 +00001310 FunctionType *FnArgTy = FunctionType::get(Builder.getVoidTy(), Arguments,
1311 false);
1312 PointerType *FnPtrTy = PointerType::getUnqual(FnArgTy);
1313
Tobias Grosser851b96e2011-07-12 12:42:54 +00001314 std::vector<Type*> args;
Tobias Grosser75805372011-04-29 06:27:02 +00001315 args.push_back(FnPtrTy);
1316 args.push_back(Builder.getInt8PtrTy());
1317 args.push_back(Builder.getInt32Ty());
1318 args.push_back(intPtrTy);
1319 args.push_back(intPtrTy);
1320 args.push_back(intPtrTy);
1321
1322 FunctionType *type = FunctionType::get(Builder.getVoidTy(), args, false);
1323 Function::Create(type, Function::ExternalLinkage,
1324 "GOMP_parallel_loop_runtime_start", M);
1325 }
1326
1327 if (!M->getFunction("GOMP_loop_runtime_next")) {
1328 PointerType *intLongPtrTy = PointerType::getUnqual(intPtrTy);
1329
Tobias Grosser851b96e2011-07-12 12:42:54 +00001330 std::vector<Type*> args;
Tobias Grosser75805372011-04-29 06:27:02 +00001331 args.push_back(intLongPtrTy);
1332 args.push_back(intLongPtrTy);
1333
1334 FunctionType *type = FunctionType::get(Builder.getInt8Ty(), args, false);
1335 Function::Create(type, Function::ExternalLinkage,
1336 "GOMP_loop_runtime_next", M);
1337 }
1338
1339 if (!M->getFunction("GOMP_loop_end_nowait")) {
1340 FunctionType *FT = FunctionType::get(Builder.getVoidTy(),
Tobias Grosser851b96e2011-07-12 12:42:54 +00001341 std::vector<Type*>(), false);
Tobias Grosser75805372011-04-29 06:27:02 +00001342 Function::Create(FT, Function::ExternalLinkage,
1343 "GOMP_loop_end_nowait", M);
1344 }
1345 }
1346
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001347 // Split the entry edge of the region and generate a new basic block on this
1348 // edge. This function also updates ScopInfo and RegionInfo.
1349 //
1350 // @param region The region where the entry edge will be splitted.
1351 BasicBlock *splitEdgeAdvanced(Region *region) {
1352 BasicBlock *newBlock;
1353 BasicBlock *splitBlock;
1354
1355 newBlock = SplitEdge(region->getEnteringBlock(), region->getEntry(), this);
1356
1357 if (DT->dominates(region->getEntry(), newBlock)) {
1358 // Update ScopInfo.
1359 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
1360 if ((*SI)->getBasicBlock() == newBlock) {
1361 (*SI)->setBasicBlock(newBlock);
1362 break;
1363 }
1364
1365 // Update RegionInfo.
1366 splitBlock = region->getEntry();
1367 region->replaceEntry(newBlock);
Tobias Grosser7a16c892011-05-14 19:01:55 +00001368 RI->setRegionFor(newBlock, region);
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001369 } else {
1370 RI->setRegionFor(newBlock, region->getParent());
1371 splitBlock = newBlock;
1372 }
1373
1374 return splitBlock;
1375 }
1376
1377 // Create a split block that branches either to the old code or to a new basic
1378 // block where the new code can be inserted.
1379 //
1380 // @param builder A builder that will be set to point to a basic block, where
1381 // the new code can be generated.
1382 // @return The split basic block.
1383 BasicBlock *addSplitAndStartBlock(IRBuilder<> *builder) {
1384 BasicBlock *splitBlock = splitEdgeAdvanced(region);
1385
1386 splitBlock->setName("polly.enterScop");
1387
1388 Function *function = splitBlock->getParent();
1389 BasicBlock *startBlock = BasicBlock::Create(function->getContext(),
1390 "polly.start", function);
1391 splitBlock->getTerminator()->eraseFromParent();
1392 builder->SetInsertPoint(splitBlock);
1393 builder->CreateCondBr(builder->getTrue(), startBlock, region->getEntry());
1394 DT->addNewBlock(startBlock, splitBlock);
1395
1396 // Start code generation here.
1397 builder->SetInsertPoint(startBlock);
1398 return splitBlock;
1399 }
1400
1401 // Merge the control flow of the newly generated code with the existing code.
1402 //
1403 // @param splitBlock The basic block where the control flow was split between
1404 // old and new version of the Scop.
1405 // @param builder An IRBuilder that points to the last instruction of the
1406 // newly generated code.
1407 void mergeControlFlow(BasicBlock *splitBlock, IRBuilder<> *builder) {
1408 BasicBlock *mergeBlock;
1409 Region *R = region;
1410
1411 if (R->getExit()->getSinglePredecessor())
1412 // No splitEdge required. A block with a single predecessor cannot have
1413 // PHI nodes that would complicate life.
1414 mergeBlock = R->getExit();
1415 else {
1416 mergeBlock = SplitEdge(R->getExitingBlock(), R->getExit(), this);
1417 // SplitEdge will never split R->getExit(), as R->getExit() has more than
1418 // one predecessor. Hence, mergeBlock is always a newly generated block.
1419 mergeBlock->setName("polly.finalMerge");
1420 R->replaceExit(mergeBlock);
1421 }
1422
1423 builder->CreateBr(mergeBlock);
1424
1425 if (DT->dominates(splitBlock, mergeBlock))
1426 DT->changeImmediateDominator(mergeBlock, splitBlock);
1427 }
1428
Tobias Grosser75805372011-04-29 06:27:02 +00001429 bool runOnScop(Scop &scop) {
1430 S = &scop;
1431 region = &S->getRegion();
Tobias Grosser75805372011-04-29 06:27:02 +00001432 DT = &getAnalysis<DominatorTree>();
1433 Dependences *DP = &getAnalysis<Dependences>();
1434 SE = &getAnalysis<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001435 SD = &getAnalysis<ScopDetection>();
1436 TD = &getAnalysis<TargetData>();
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001437 RI = &getAnalysis<RegionInfo>();
Tobias Grosser75805372011-04-29 06:27:02 +00001438
1439 parallelLoops.clear();
1440
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001441 assert(region->isSimple() && "Only simple regions are supported");
Tobias Grosser76d7c522011-05-14 19:01:37 +00001442
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001443 // In the CFG and we generate next to original code of the Scop the
1444 // optimized version. Both the new and the original version of the code
1445 // remain in the CFG. A branch statement decides which version is executed.
1446 // At the moment, we always execute the newly generated version (the old one
1447 // is dead code eliminated by the cleanup passes). Later we may decide to
1448 // execute the new version only under certain conditions. This will be the
1449 // case if we support constructs for which we cannot prove all assumptions
1450 // at compile time.
1451 //
1452 // Before transformation:
1453 //
1454 // bb0
1455 // |
1456 // orig_scop
1457 // |
1458 // bb1
1459 //
1460 // After transformation:
1461 // bb0
1462 // |
1463 // polly.splitBlock
Tobias Grosser2bd3af12011-08-01 22:39:00 +00001464 // / \.
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001465 // | startBlock
1466 // | |
1467 // orig_scop new_scop
1468 // \ /
1469 // \ /
1470 // bb1 (joinBlock)
1471 IRBuilder<> builder(region->getEntry());
Tobias Grosser75805372011-04-29 06:27:02 +00001472
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001473 // The builder will be set to startBlock.
1474 BasicBlock *splitBlock = addSplitAndStartBlock(&builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001475
1476 if (OpenMP)
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001477 addOpenMPDefinitions(builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001478
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001479 ClastStmtCodeGen CodeGen(S, *SE, DT, SD, DP, TD, builder);
Tobias Grosser3fdecae2011-05-14 19:02:39 +00001480 CloogInfo &C = getAnalysis<CloogInfo>();
1481 CodeGen.codegen(C.getClast());
Tobias Grosser75805372011-04-29 06:27:02 +00001482
Tobias Grosser75805372011-04-29 06:27:02 +00001483 parallelLoops.insert(parallelLoops.begin(),
1484 CodeGen.getParallelLoops().begin(),
1485 CodeGen.getParallelLoops().end());
1486
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001487 mergeControlFlow(splitBlock, &builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001488
Tobias Grosserabb6dcd2011-05-14 19:02:34 +00001489 return true;
Tobias Grosser75805372011-04-29 06:27:02 +00001490 }
1491
1492 virtual void printScop(raw_ostream &OS) const {
1493 for (std::vector<std::string>::const_iterator PI = parallelLoops.begin(),
1494 PE = parallelLoops.end(); PI != PE; ++PI)
1495 OS << "Parallel loop with iterator '" << *PI << "' generated\n";
1496 }
1497
1498 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1499 AU.addRequired<CloogInfo>();
1500 AU.addRequired<Dependences>();
1501 AU.addRequired<DominatorTree>();
1502 AU.addRequired<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001503 AU.addRequired<RegionInfo>();
1504 AU.addRequired<ScopDetection>();
1505 AU.addRequired<ScopInfo>();
1506 AU.addRequired<TargetData>();
1507
1508 AU.addPreserved<CloogInfo>();
1509 AU.addPreserved<Dependences>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001510
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001511 // FIXME: We do not create LoopInfo for the newly generated loops.
Tobias Grosser75805372011-04-29 06:27:02 +00001512 AU.addPreserved<LoopInfo>();
1513 AU.addPreserved<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001514 AU.addPreserved<ScopDetection>();
1515 AU.addPreserved<ScalarEvolution>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001516
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001517 // FIXME: We do not yet add regions for the newly generated code to the
1518 // region tree.
Tobias Grosser75805372011-04-29 06:27:02 +00001519 AU.addPreserved<RegionInfo>();
1520 AU.addPreserved<TempScopInfo>();
1521 AU.addPreserved<ScopInfo>();
1522 AU.addPreservedID(IndependentBlocksID);
1523 }
1524};
1525}
1526
1527char CodeGeneration::ID = 1;
1528
1529static RegisterPass<CodeGeneration>
1530Z("polly-codegen", "Polly - Create LLVM-IR from the polyhedral information");
1531
1532Pass* polly::createCodeGenerationPass() {
1533 return new CodeGeneration();
1534}