blob: c9c2742f6bb5098ae2fbe4b43a4c640b391b5962 [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 Aloor129e8672011-08-15 02:33:39 +0000317 /// @brief Get the memory access offset to be added to the base address
318 std::vector <Value*> getMemoryAccessIndex(isl_map *accessRelation,
319 Value *baseAddr) {
320 isl_int offsetMPZ;
321 isl_int_init(offsetMPZ);
322
323 assert((isl_map_dim(accessRelation, isl_dim_out) == 1)
324 && "Only single dimensional access functions supported");
325
326 if (isl_map_plain_is_fixed(accessRelation, isl_dim_out,
327 0, &offsetMPZ) == -1)
328 errs() << "Only fixed value access functions supported\n";
329
330 // Convert the offset from MPZ to Value*.
331 APInt offset = APInt_from_MPZ(offsetMPZ);
332 Value *offsetValue = ConstantInt::get(Builder.getContext(), offset);
333 PointerType *baseAddrType = dyn_cast<PointerType>(baseAddr->getType());
334 Type *arrayType = baseAddrType->getElementType();
335 Type *arrayElementType = dyn_cast<ArrayType>(arrayType)->getElementType();
336 offsetValue = Builder.CreateSExtOrBitCast(offsetValue, arrayElementType);
337
338 std::vector<Value*> indexArray;
339 Value *nullValue = Constant::getNullValue(arrayElementType);
340 indexArray.push_back(nullValue);
341 indexArray.push_back(offsetValue);
342
343 isl_int_clear(offsetMPZ);
344 return indexArray;
345 }
346
Raghesh Aloor62b13122011-08-03 17:02:50 +0000347 /// @brief Get the new operand address according to the changed access in
348 /// JSCOP file.
349 Value *getNewAccessOperand(isl_map *newAccessRelation, Value *baseAddr,
Raghesh Aloor490c5982011-08-08 08:34:16 +0000350 const Value *oldOperand, ValueMapT &BBMap) {
Raghesh Aloor129e8672011-08-15 02:33:39 +0000351 std::vector<Value*> indexArray = getMemoryAccessIndex(newAccessRelation,
352 baseAddr);
353 Value *newOperand = Builder.CreateGEP(baseAddr, indexArray,
354 "p_newarrayidx_");
Raghesh Aloor62b13122011-08-03 17:02:50 +0000355 return newOperand;
356 }
357
358 /// @brief Generate the operand address
359 Value *generateLocationAccessed(const Instruction *Inst,
360 const Value *pointer, ValueMapT &BBMap ) {
Raghesh Aloor490c5982011-08-08 08:34:16 +0000361 MemoryAccess &access = statement.getAccessFor(Inst);
Raghesh Aloor129e8672011-08-15 02:33:39 +0000362 isl_map *currentAccessRelation = access.getAccessFunction();
Raghesh Aloor490c5982011-08-08 08:34:16 +0000363 isl_map *newAccessRelation = access.getNewAccessFunction();
Raghesh Aloor129e8672011-08-15 02:33:39 +0000364
365 assert(isl_map_has_equal_dim(currentAccessRelation, newAccessRelation)
366 && "Current and new access function dimensions differ");
367
Raghesh Aloor62b13122011-08-03 17:02:50 +0000368 if (!newAccessRelation) {
369 Value *newPointer = getOperand(pointer, BBMap);
370 return newPointer;
371 }
Raghesh Aloore75e9862011-08-11 08:44:56 +0000372
Raghesh Aloor490c5982011-08-08 08:34:16 +0000373 Value *baseAddr = const_cast<Value*>(access.getBaseAddr());
Raghesh Aloor62b13122011-08-03 17:02:50 +0000374 Value *newPointer = getNewAccessOperand(newAccessRelation, baseAddr,
375 pointer, BBMap);
376 return newPointer;
377 }
378
Tobias Grosser75805372011-04-29 06:27:02 +0000379 Value *generateScalarLoad(const LoadInst *load, ValueMapT &BBMap) {
380 const Value *pointer = load->getPointerOperand();
Raghesh Aloor62b13122011-08-03 17:02:50 +0000381 const Instruction *Inst = dyn_cast<Instruction>(load);
382 Value *newPointer = generateLocationAccessed(Inst, pointer, BBMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000383 Value *scalarLoad = Builder.CreateLoad(newPointer,
384 load->getNameStr() + "_p_scalar_");
385 return scalarLoad;
386 }
387
388 /// @brief Load a value (or several values as a vector) from memory.
389 void generateLoad(const LoadInst *load, ValueMapT &vectorMap,
390 VectorValueMapT &scalarMaps, int vectorWidth) {
391
392 if (scalarMaps.size() == 1) {
393 scalarMaps[0][load] = generateScalarLoad(load, scalarMaps[0]);
394 return;
395 }
396
397 Value *newLoad;
398
399 MemoryAccess &Access = statement.getAccessFor(load);
400
401 assert(scatteringDomain && "No scattering domain available");
402
403 if (Access.isStrideZero(scatteringDomain))
404 newLoad = generateStrideZeroLoad(load, scalarMaps[0], vectorWidth);
405 else if (Access.isStrideOne(scatteringDomain))
406 newLoad = generateStrideOneLoad(load, scalarMaps[0], vectorWidth);
407 else
408 newLoad = generateUnknownStrideLoad(load, scalarMaps, vectorWidth);
409
410 vectorMap[load] = newLoad;
411 }
412
413 void copyInstruction(const Instruction *Inst, ValueMapT &BBMap,
414 ValueMapT &vectorMap, VectorValueMapT &scalarMaps,
415 int vectorDimension, int vectorWidth) {
416 // If this instruction is already in the vectorMap, a vector instruction
417 // was already issued, that calculates the values of all dimensions. No
418 // need to create any more instructions.
419 if (vectorMap.count(Inst))
420 return;
421
422 // Terminator instructions control the control flow. They are explicitally
423 // expressed in the clast and do not need to be copied.
424 if (Inst->isTerminator())
425 return;
426
427 if (const LoadInst *load = dyn_cast<LoadInst>(Inst)) {
428 generateLoad(load, vectorMap, scalarMaps, vectorWidth);
429 return;
430 }
431
432 if (const BinaryOperator *binaryInst = dyn_cast<BinaryOperator>(Inst)) {
433 Value *opZero = Inst->getOperand(0);
434 Value *opOne = Inst->getOperand(1);
435
436 // This is an old instruction that can be ignored.
437 if (!opZero && !opOne)
438 return;
439
440 bool isVectorOp = vectorMap.count(opZero) || vectorMap.count(opOne);
441
442 if (isVectorOp && vectorDimension > 0)
443 return;
444
445 Value *newOpZero, *newOpOne;
446 newOpZero = getOperand(opZero, BBMap, &vectorMap);
447 newOpOne = getOperand(opOne, BBMap, &vectorMap);
448
449
450 std::string name;
451 if (isVectorOp) {
452 newOpZero = makeVectorOperand(newOpZero, vectorWidth);
453 newOpOne = makeVectorOperand(newOpOne, vectorWidth);
454 name = Inst->getNameStr() + "p_vec";
455 } else
456 name = Inst->getNameStr() + "p_sca";
457
458 Value *newInst = Builder.CreateBinOp(binaryInst->getOpcode(), newOpZero,
459 newOpOne, name);
460 if (isVectorOp)
461 vectorMap[Inst] = newInst;
462 else
463 BBMap[Inst] = newInst;
464
465 return;
466 }
467
468 if (const StoreInst *store = dyn_cast<StoreInst>(Inst)) {
469 if (vectorMap.count(store->getValueOperand()) > 0) {
470
471 // We only need to generate one store if we are in vector mode.
472 if (vectorDimension > 0)
473 return;
474
475 MemoryAccess &Access = statement.getAccessFor(store);
476
477 assert(scatteringDomain && "No scattering domain available");
478
479 const Value *pointer = store->getPointerOperand();
480 Value *vector = getOperand(store->getValueOperand(), BBMap, &vectorMap);
481
482 if (Access.isStrideOne(scatteringDomain)) {
Tobias Grosser55927aa2011-07-18 09:53:32 +0000483 Type *vectorPtrType = getVectorPtrTy(pointer, vectorWidth);
Tobias Grosser75805372011-04-29 06:27:02 +0000484 Value *newPointer = getOperand(pointer, BBMap, &vectorMap);
485
486 Value *VectorPtr = Builder.CreateBitCast(newPointer, vectorPtrType,
487 "vector_ptr");
488 StoreInst *Store = Builder.CreateStore(vector, VectorPtr);
489
490 if (!Aligned)
491 Store->setAlignment(8);
492 } else {
493 for (unsigned i = 0; i < scalarMaps.size(); i++) {
494 Value *scalar = Builder.CreateExtractElement(vector,
495 Builder.getInt32(i));
496 Value *newPointer = getOperand(pointer, scalarMaps[i]);
497 Builder.CreateStore(scalar, newPointer);
498 }
499 }
500
501 return;
502 }
503 }
504
505 Instruction *NewInst = Inst->clone();
506
507 // Copy the operands in temporary vector, as an in place update
508 // fails if an instruction is referencing the same operand twice.
509 std::vector<Value*> Operands(NewInst->op_begin(), NewInst->op_end());
510
511 // Replace old operands with the new ones.
512 for (std::vector<Value*>::iterator UI = Operands.begin(),
513 UE = Operands.end(); UI != UE; ++UI) {
514 Value *newOperand = getOperand(*UI, BBMap);
515
516 if (!newOperand) {
517 assert(!isa<StoreInst>(NewInst)
518 && "Store instructions are always needed!");
519 delete NewInst;
520 return;
521 }
522
523 NewInst->replaceUsesOfWith(*UI, newOperand);
524 }
525
526 Builder.Insert(NewInst);
527 BBMap[Inst] = NewInst;
528
529 if (!NewInst->getType()->isVoidTy())
530 NewInst->setName("p_" + Inst->getName());
531 }
532
533 int getVectorSize() {
534 return ValueMaps.size();
535 }
536
537 bool isVectorBlock() {
538 return getVectorSize() > 1;
539 }
540
541 // Insert a copy of a basic block in the newly generated code.
542 //
543 // @param Builder The builder used to insert the code. It also specifies
544 // where to insert the code.
545 // @param BB The basic block to copy
546 // @param VMap A map returning for any old value its new equivalent. This
547 // is used to update the operands of the statements.
548 // For new statements a relation old->new is inserted in this
549 // map.
550 void copyBB(BasicBlock *BB, DominatorTree *DT) {
551 Function *F = Builder.GetInsertBlock()->getParent();
552 LLVMContext &Context = F->getContext();
553 BasicBlock *CopyBB = BasicBlock::Create(Context,
554 "polly.stmt_" + BB->getNameStr(),
555 F);
556 Builder.CreateBr(CopyBB);
557 DT->addNewBlock(CopyBB, Builder.GetInsertBlock());
558 Builder.SetInsertPoint(CopyBB);
559
560 // Create two maps that store the mapping from the original instructions of
561 // the old basic block to their copies in the new basic block. Those maps
562 // are basic block local.
563 //
564 // As vector code generation is supported there is one map for scalar values
565 // and one for vector values.
566 //
567 // In case we just do scalar code generation, the vectorMap is not used and
568 // the scalarMap has just one dimension, which contains the mapping.
569 //
570 // In case vector code generation is done, an instruction may either appear
571 // in the vector map once (as it is calculating >vectorwidth< values at a
572 // time. Or (if the values are calculated using scalar operations), it
573 // appears once in every dimension of the scalarMap.
574 VectorValueMapT scalarBlockMap(getVectorSize());
575 ValueMapT vectorBlockMap;
576
577 for (BasicBlock::const_iterator II = BB->begin(), IE = BB->end();
578 II != IE; ++II)
579 for (int i = 0; i < getVectorSize(); i++) {
580 if (isVectorBlock())
581 VMap = ValueMaps[i];
582
583 copyInstruction(II, scalarBlockMap[i], vectorBlockMap,
584 scalarBlockMap, i, getVectorSize());
585 }
586 }
587};
588
589/// Class to generate LLVM-IR that calculates the value of a clast_expr.
590class ClastExpCodeGen {
591 IRBuilder<> &Builder;
592 const CharMapT *IVS;
593
Tobias Grosser55927aa2011-07-18 09:53:32 +0000594 Value *codegen(const clast_name *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000595 CharMapT::const_iterator I = IVS->find(e->name);
596
597 if (I != IVS->end())
598 return Builder.CreateSExtOrBitCast(I->second, Ty);
599 else
600 llvm_unreachable("Clast name not found");
601 }
602
Tobias Grosser55927aa2011-07-18 09:53:32 +0000603 Value *codegen(const clast_term *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000604 APInt a = APInt_from_MPZ(e->val);
605
606 Value *ConstOne = ConstantInt::get(Builder.getContext(), a);
607 ConstOne = Builder.CreateSExtOrBitCast(ConstOne, Ty);
608
609 if (e->var) {
610 Value *var = codegen(e->var, Ty);
611 return Builder.CreateMul(ConstOne, var);
612 }
613
614 return ConstOne;
615 }
616
Tobias Grosser55927aa2011-07-18 09:53:32 +0000617 Value *codegen(const clast_binary *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000618 Value *LHS = codegen(e->LHS, Ty);
619
620 APInt RHS_AP = APInt_from_MPZ(e->RHS);
621
622 Value *RHS = ConstantInt::get(Builder.getContext(), RHS_AP);
623 RHS = Builder.CreateSExtOrBitCast(RHS, Ty);
624
625 switch (e->type) {
626 case clast_bin_mod:
627 return Builder.CreateSRem(LHS, RHS);
628 case clast_bin_fdiv:
629 {
630 // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
631 Value *One = ConstantInt::get(Builder.getInt1Ty(), 1);
632 Value *Zero = ConstantInt::get(Builder.getInt1Ty(), 0);
633 One = Builder.CreateZExtOrBitCast(One, Ty);
634 Zero = Builder.CreateZExtOrBitCast(Zero, Ty);
635 Value *Sum1 = Builder.CreateSub(LHS, RHS);
636 Value *Sum2 = Builder.CreateAdd(Sum1, One);
637 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
638 Value *Dividend = Builder.CreateSelect(isNegative, Sum2, LHS);
639 return Builder.CreateSDiv(Dividend, RHS);
640 }
641 case clast_bin_cdiv:
642 {
643 // ceild(n,d) ((n < 0) ? n : (n + d - 1)) / d
644 Value *One = ConstantInt::get(Builder.getInt1Ty(), 1);
645 Value *Zero = ConstantInt::get(Builder.getInt1Ty(), 0);
646 One = Builder.CreateZExtOrBitCast(One, Ty);
647 Zero = Builder.CreateZExtOrBitCast(Zero, Ty);
648 Value *Sum1 = Builder.CreateAdd(LHS, RHS);
649 Value *Sum2 = Builder.CreateSub(Sum1, One);
650 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
651 Value *Dividend = Builder.CreateSelect(isNegative, LHS, Sum2);
652 return Builder.CreateSDiv(Dividend, RHS);
653 }
654 case clast_bin_div:
655 return Builder.CreateSDiv(LHS, RHS);
656 default:
657 llvm_unreachable("Unknown clast binary expression type");
658 };
659 }
660
Tobias Grosser55927aa2011-07-18 09:53:32 +0000661 Value *codegen(const clast_reduction *r, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000662 assert(( r->type == clast_red_min
663 || r->type == clast_red_max
664 || r->type == clast_red_sum)
665 && "Clast reduction type not supported");
666 Value *old = codegen(r->elts[0], Ty);
667
668 for (int i=1; i < r->n; ++i) {
669 Value *exprValue = codegen(r->elts[i], Ty);
670
671 switch (r->type) {
672 case clast_red_min:
673 {
674 Value *cmp = Builder.CreateICmpSLT(old, exprValue);
675 old = Builder.CreateSelect(cmp, old, exprValue);
676 break;
677 }
678 case clast_red_max:
679 {
680 Value *cmp = Builder.CreateICmpSGT(old, exprValue);
681 old = Builder.CreateSelect(cmp, old, exprValue);
682 break;
683 }
684 case clast_red_sum:
685 old = Builder.CreateAdd(old, exprValue);
686 break;
687 default:
688 llvm_unreachable("Clast unknown reduction type");
689 }
690 }
691
692 return old;
693 }
694
695public:
696
697 // A generator for clast expressions.
698 //
699 // @param B The IRBuilder that defines where the code to calculate the
700 // clast expressions should be inserted.
701 // @param IVMAP A Map that translates strings describing the induction
702 // variables to the Values* that represent these variables
703 // on the LLVM side.
704 ClastExpCodeGen(IRBuilder<> &B, CharMapT *IVMap) : Builder(B), IVS(IVMap) {}
705
706 // Generates code to calculate a given clast expression.
707 //
708 // @param e The expression to calculate.
709 // @return The Value that holds the result.
Tobias Grosser55927aa2011-07-18 09:53:32 +0000710 Value *codegen(const clast_expr *e, Type *Ty) {
Tobias Grosser75805372011-04-29 06:27:02 +0000711 switch(e->type) {
712 case clast_expr_name:
713 return codegen((const clast_name *)e, Ty);
714 case clast_expr_term:
715 return codegen((const clast_term *)e, Ty);
716 case clast_expr_bin:
717 return codegen((const clast_binary *)e, Ty);
718 case clast_expr_red:
719 return codegen((const clast_reduction *)e, Ty);
720 default:
721 llvm_unreachable("Unknown clast expression!");
722 }
723 }
724
725 // @brief Reset the CharMap.
726 //
727 // This function is called to reset the CharMap to new one, while generating
728 // OpenMP code.
729 void setIVS(CharMapT *IVSNew) {
730 IVS = IVSNew;
731 }
732
733};
734
735class ClastStmtCodeGen {
736 // The Scop we code generate.
737 Scop *S;
738 ScalarEvolution &SE;
Tobias Grosser75805372011-04-29 06:27:02 +0000739 DominatorTree *DT;
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000740 ScopDetection *SD;
Tobias Grosser75805372011-04-29 06:27:02 +0000741 Dependences *DP;
742 TargetData *TD;
743
744 // The Builder specifies the current location to code generate at.
745 IRBuilder<> &Builder;
746
747 // Map the Values from the old code to their counterparts in the new code.
748 ValueMapT ValueMap;
749
750 // clastVars maps from the textual representation of a clast variable to its
751 // current *Value. clast variables are scheduling variables, original
752 // induction variables or parameters. They are used either in loop bounds or
753 // to define the statement instance that is executed.
754 //
755 // for (s = 0; s < n + 3; ++i)
756 // for (t = s; t < m; ++j)
757 // Stmt(i = s + 3 * m, j = t);
758 //
759 // {s,t,i,j,n,m} is the set of clast variables in this clast.
760 CharMapT *clastVars;
761
762 // Codegenerator for clast expressions.
763 ClastExpCodeGen ExpGen;
764
765 // Do we currently generate parallel code?
766 bool parallelCodeGeneration;
767
768 std::vector<std::string> parallelLoops;
769
770public:
771
772 const std::vector<std::string> &getParallelLoops() {
773 return parallelLoops;
774 }
775
776 protected:
777 void codegen(const clast_assignment *a) {
778 (*clastVars)[a->LHS] = ExpGen.codegen(a->RHS,
779 TD->getIntPtrType(Builder.getContext()));
780 }
781
782 void codegen(const clast_assignment *a, ScopStmt *Statement,
783 unsigned Dimension, int vectorDim,
784 std::vector<ValueMapT> *VectorVMap = 0) {
785 Value *RHS = ExpGen.codegen(a->RHS,
786 TD->getIntPtrType(Builder.getContext()));
787
788 assert(!a->LHS && "Statement assignments do not have left hand side");
789 const PHINode *PN;
790 PN = Statement->getInductionVariableForDimension(Dimension);
791 const Value *V = PN;
792
Tobias Grosser75805372011-04-29 06:27:02 +0000793 if (VectorVMap)
794 (*VectorVMap)[vectorDim][V] = RHS;
795
796 ValueMap[V] = RHS;
797 }
798
799 void codegenSubstitutions(const clast_stmt *Assignment,
800 ScopStmt *Statement, int vectorDim = 0,
801 std::vector<ValueMapT> *VectorVMap = 0) {
802 int Dimension = 0;
803
804 while (Assignment) {
805 assert(CLAST_STMT_IS_A(Assignment, stmt_ass)
806 && "Substitions are expected to be assignments");
807 codegen((const clast_assignment *)Assignment, Statement, Dimension,
808 vectorDim, VectorVMap);
809 Assignment = Assignment->next;
810 Dimension++;
811 }
812 }
813
814 void codegen(const clast_user_stmt *u, std::vector<Value*> *IVS = NULL,
815 const char *iterator = NULL, isl_set *scatteringDomain = 0) {
816 ScopStmt *Statement = (ScopStmt *)u->statement->usr;
817 BasicBlock *BB = Statement->getBasicBlock();
818
819 if (u->substitutions)
820 codegenSubstitutions(u->substitutions, Statement);
821
822 int vectorDimensions = IVS ? IVS->size() : 1;
823
824 VectorValueMapT VectorValueMap(vectorDimensions);
825
826 if (IVS) {
827 assert (u->substitutions && "Substitutions expected!");
828 int i = 0;
829 for (std::vector<Value*>::iterator II = IVS->begin(), IE = IVS->end();
830 II != IE; ++II) {
831 (*clastVars)[iterator] = *II;
832 codegenSubstitutions(u->substitutions, Statement, i, &VectorValueMap);
833 i++;
834 }
835 }
836
837 BlockGenerator Generator(Builder, ValueMap, VectorValueMap, *Statement,
838 scatteringDomain);
839 Generator.copyBB(BB, DT);
840 }
841
842 void codegen(const clast_block *b) {
843 if (b->body)
844 codegen(b->body);
845 }
846
847 /// @brief Create a classical sequential loop.
848 void codegenForSequential(const clast_for *f, Value *lowerBound = 0,
849 Value *upperBound = 0) {
850 APInt Stride = APInt_from_MPZ(f->stride);
851 PHINode *IV;
852 Value *IncrementedIV;
853 BasicBlock *AfterBB;
854 // The value of lowerbound and upperbound will be supplied, if this
855 // function is called while generating OpenMP code. Otherwise get
856 // the values.
857 assert(((lowerBound && upperBound) || (!lowerBound && !upperBound))
858 && "Either give both bounds or none");
859 if (lowerBound == 0 || upperBound == 0) {
860 lowerBound = ExpGen.codegen(f->LB,
861 TD->getIntPtrType(Builder.getContext()));
862 upperBound = ExpGen.codegen(f->UB,
863 TD->getIntPtrType(Builder.getContext()));
864 }
865 createLoop(&Builder, lowerBound, upperBound, Stride, IV, AfterBB,
866 IncrementedIV, DT);
867
868 // Add loop iv to symbols.
869 (*clastVars)[f->iterator] = IV;
870
871 if (f->body)
872 codegen(f->body);
873
874 // Loop is finished, so remove its iv from the live symbols.
875 clastVars->erase(f->iterator);
876
877 BasicBlock *HeaderBB = *pred_begin(AfterBB);
878 BasicBlock *LastBodyBB = Builder.GetInsertBlock();
879 Builder.CreateBr(HeaderBB);
880 IV->addIncoming(IncrementedIV, LastBodyBB);
881 Builder.SetInsertPoint(AfterBB);
882 }
883
Tobias Grosser75805372011-04-29 06:27:02 +0000884 /// @brief Add a new definition of an openmp subfunction.
885 Function* addOpenMPSubfunction(Module *M) {
886 Function *F = Builder.GetInsertBlock()->getParent();
887 const std::string &Name = F->getNameStr() + ".omp_subfn";
888
Tobias Grosser851b96e2011-07-12 12:42:54 +0000889 std::vector<Type*> Arguments(1, Builder.getInt8PtrTy());
Tobias Grosser75805372011-04-29 06:27:02 +0000890 FunctionType *FT = FunctionType::get(Builder.getVoidTy(), Arguments, false);
891 Function *FN = Function::Create(FT, Function::InternalLinkage, Name, M);
Hongbin Zheng94c5df12011-05-06 02:38:20 +0000892 // Do not run any polly pass on the new function.
893 SD->markFunctionAsInvalid(FN);
Tobias Grosser75805372011-04-29 06:27:02 +0000894
895 Function::arg_iterator AI = FN->arg_begin();
896 AI->setName("omp.userContext");
897
898 return FN;
899 }
900
901 /// @brief Add values to the OpenMP structure.
902 ///
903 /// Create the subfunction structure and add the values from the list.
904 Value *addValuesToOpenMPStruct(SetVector<Value*> OMPDataVals,
905 Function *SubFunction) {
Tobias Grosser851b96e2011-07-12 12:42:54 +0000906 std::vector<Type*> structMembers;
Tobias Grosser75805372011-04-29 06:27:02 +0000907
908 // Create the structure.
909 for (unsigned i = 0; i < OMPDataVals.size(); i++)
910 structMembers.push_back(OMPDataVals[i]->getType());
911
Tobias Grosser75805372011-04-29 06:27:02 +0000912 StructType *structTy = StructType::get(Builder.getContext(),
913 structMembers);
Tobias Grosser75805372011-04-29 06:27:02 +0000914 // Store the values into the structure.
915 Value *structData = Builder.CreateAlloca(structTy, 0, "omp.userContext");
916 for (unsigned i = 0; i < OMPDataVals.size(); i++) {
917 Value *storeAddr = Builder.CreateStructGEP(structData, i);
918 Builder.CreateStore(OMPDataVals[i], storeAddr);
919 }
920
921 return structData;
922 }
923
924 /// @brief Create OpenMP structure values.
925 ///
926 /// Create a list of values that has to be stored into the subfuncition
927 /// structure.
928 SetVector<Value*> createOpenMPStructValues() {
929 SetVector<Value*> OMPDataVals;
930
931 // Push the clast variables available in the clastVars.
932 for (CharMapT::iterator I = clastVars->begin(), E = clastVars->end();
933 I != E; I++)
934 OMPDataVals.insert(I->second);
935
936 // Push the base addresses of memory references.
937 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
938 ScopStmt *Stmt = *SI;
939 for (SmallVector<MemoryAccess*, 8>::iterator I = Stmt->memacc_begin(),
940 E = Stmt->memacc_end(); I != E; ++I) {
941 Value *BaseAddr = const_cast<Value*>((*I)->getBaseAddr());
942 OMPDataVals.insert((BaseAddr));
943 }
944 }
945
946 return OMPDataVals;
947 }
948
949 /// @brief Extract the values from the subfunction parameter.
950 ///
951 /// Extract the values from the subfunction parameter and update the clast
952 /// variables to point to the new values.
953 void extractValuesFromOpenMPStruct(CharMapT *clastVarsOMP,
954 SetVector<Value*> OMPDataVals,
955 Value *userContext) {
956 // Extract the clast variables.
957 unsigned i = 0;
958 for (CharMapT::iterator I = clastVars->begin(), E = clastVars->end();
959 I != E; I++) {
960 Value *loadAddr = Builder.CreateStructGEP(userContext, i);
961 (*clastVarsOMP)[I->first] = Builder.CreateLoad(loadAddr);
962 i++;
963 }
964
965 // Extract the base addresses of memory references.
966 for (unsigned j = i; j < OMPDataVals.size(); j++) {
967 Value *loadAddr = Builder.CreateStructGEP(userContext, j);
968 Value *baseAddr = OMPDataVals[j];
969 ValueMap[baseAddr] = Builder.CreateLoad(loadAddr);
970 }
971
972 }
973
974 /// @brief Add body to the subfunction.
975 void addOpenMPSubfunctionBody(Function *FN, const clast_for *f,
976 Value *structData,
977 SetVector<Value*> OMPDataVals) {
978 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
979 LLVMContext &Context = FN->getContext();
Tobias Grosser55927aa2011-07-18 09:53:32 +0000980 IntegerType *intPtrTy = TD->getIntPtrType(Context);
Tobias Grosser75805372011-04-29 06:27:02 +0000981
982 // Store the previous basic block.
983 BasicBlock *PrevBB = Builder.GetInsertBlock();
984
985 // Create basic blocks.
986 BasicBlock *HeaderBB = BasicBlock::Create(Context, "omp.setup", FN);
987 BasicBlock *ExitBB = BasicBlock::Create(Context, "omp.exit", FN);
988 BasicBlock *checkNextBB = BasicBlock::Create(Context, "omp.checkNext", FN);
989 BasicBlock *loadIVBoundsBB = BasicBlock::Create(Context, "omp.loadIVBounds",
990 FN);
991
992 DT->addNewBlock(HeaderBB, PrevBB);
993 DT->addNewBlock(ExitBB, HeaderBB);
994 DT->addNewBlock(checkNextBB, HeaderBB);
995 DT->addNewBlock(loadIVBoundsBB, HeaderBB);
996
997 // Fill up basic block HeaderBB.
998 Builder.SetInsertPoint(HeaderBB);
999 Value *lowerBoundPtr = Builder.CreateAlloca(intPtrTy, 0,
1000 "omp.lowerBoundPtr");
1001 Value *upperBoundPtr = Builder.CreateAlloca(intPtrTy, 0,
1002 "omp.upperBoundPtr");
1003 Value *userContext = Builder.CreateBitCast(FN->arg_begin(),
1004 structData->getType(),
1005 "omp.userContext");
1006
1007 CharMapT clastVarsOMP;
1008 extractValuesFromOpenMPStruct(&clastVarsOMP, OMPDataVals, userContext);
1009
1010 Builder.CreateBr(checkNextBB);
1011
1012 // Add code to check if another set of iterations will be executed.
1013 Builder.SetInsertPoint(checkNextBB);
1014 Function *runtimeNextFunction = M->getFunction("GOMP_loop_runtime_next");
1015 Value *ret1 = Builder.CreateCall2(runtimeNextFunction,
1016 lowerBoundPtr, upperBoundPtr);
1017 Value *hasNextSchedule = Builder.CreateTrunc(ret1, Builder.getInt1Ty(),
1018 "omp.hasNextScheduleBlock");
1019 Builder.CreateCondBr(hasNextSchedule, loadIVBoundsBB, ExitBB);
1020
1021 // Add code to to load the iv bounds for this set of iterations.
1022 Builder.SetInsertPoint(loadIVBoundsBB);
1023 Value *lowerBound = Builder.CreateLoad(lowerBoundPtr, "omp.lowerBound");
1024 Value *upperBound = Builder.CreateLoad(upperBoundPtr, "omp.upperBound");
1025
1026 // Subtract one as the upper bound provided by openmp is a < comparison
1027 // whereas the codegenForSequential function creates a <= comparison.
1028 upperBound = Builder.CreateSub(upperBound, ConstantInt::get(intPtrTy, 1),
1029 "omp.upperBoundAdjusted");
1030
1031 // Use clastVarsOMP during code generation of the OpenMP subfunction.
1032 CharMapT *oldClastVars = clastVars;
1033 clastVars = &clastVarsOMP;
1034 ExpGen.setIVS(&clastVarsOMP);
1035
1036 codegenForSequential(f, lowerBound, upperBound);
1037
1038 // Restore the old clastVars.
1039 clastVars = oldClastVars;
1040 ExpGen.setIVS(oldClastVars);
1041
1042 Builder.CreateBr(checkNextBB);
1043
1044 // Add code to terminate this openmp subfunction.
1045 Builder.SetInsertPoint(ExitBB);
1046 Function *endnowaitFunction = M->getFunction("GOMP_loop_end_nowait");
1047 Builder.CreateCall(endnowaitFunction);
1048 Builder.CreateRetVoid();
1049
1050 // Restore the builder back to previous basic block.
1051 Builder.SetInsertPoint(PrevBB);
1052 }
1053
1054 /// @brief Create an OpenMP parallel for loop.
1055 ///
1056 /// This loop reflects a loop as if it would have been created by an OpenMP
1057 /// statement.
1058 void codegenForOpenMP(const clast_for *f) {
1059 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
Tobias Grosser55927aa2011-07-18 09:53:32 +00001060 IntegerType *intPtrTy = TD->getIntPtrType(Builder.getContext());
Tobias Grosser75805372011-04-29 06:27:02 +00001061
1062 Function *SubFunction = addOpenMPSubfunction(M);
1063 SetVector<Value*> OMPDataVals = createOpenMPStructValues();
1064 Value *structData = addValuesToOpenMPStruct(OMPDataVals, SubFunction);
1065
1066 addOpenMPSubfunctionBody(SubFunction, f, structData, OMPDataVals);
1067
1068 // Create call for GOMP_parallel_loop_runtime_start.
1069 Value *subfunctionParam = Builder.CreateBitCast(structData,
1070 Builder.getInt8PtrTy(),
1071 "omp_data");
1072
1073 Value *numberOfThreads = Builder.getInt32(0);
1074 Value *lowerBound = ExpGen.codegen(f->LB, intPtrTy);
1075 Value *upperBound = ExpGen.codegen(f->UB, intPtrTy);
1076
1077 // Add one as the upper bound provided by openmp is a < comparison
1078 // whereas the codegenForSequential function creates a <= comparison.
1079 upperBound = Builder.CreateAdd(upperBound, ConstantInt::get(intPtrTy, 1));
1080 APInt APStride = APInt_from_MPZ(f->stride);
1081 Value *stride = ConstantInt::get(intPtrTy,
1082 APStride.zext(intPtrTy->getBitWidth()));
1083
1084 SmallVector<Value *, 6> Arguments;
1085 Arguments.push_back(SubFunction);
1086 Arguments.push_back(subfunctionParam);
1087 Arguments.push_back(numberOfThreads);
1088 Arguments.push_back(lowerBound);
1089 Arguments.push_back(upperBound);
1090 Arguments.push_back(stride);
1091
1092 Function *parallelStartFunction =
1093 M->getFunction("GOMP_parallel_loop_runtime_start");
Tobias Grosser0679e172011-07-15 22:54:41 +00001094 Builder.CreateCall(parallelStartFunction, Arguments);
Tobias Grosser75805372011-04-29 06:27:02 +00001095
1096 // Create call to the subfunction.
1097 Builder.CreateCall(SubFunction, subfunctionParam);
1098
1099 // Create call for GOMP_parallel_end.
1100 Function *FN = M->getFunction("GOMP_parallel_end");
1101 Builder.CreateCall(FN);
1102 }
1103
1104 bool isInnermostLoop(const clast_for *f) {
1105 const clast_stmt *stmt = f->body;
1106
1107 while (stmt) {
1108 if (!CLAST_STMT_IS_A(stmt, stmt_user))
1109 return false;
1110
1111 stmt = stmt->next;
1112 }
1113
1114 return true;
1115 }
1116
1117 /// @brief Get the number of loop iterations for this loop.
1118 /// @param f The clast for loop to check.
1119 int getNumberOfIterations(const clast_for *f) {
1120 isl_set *loopDomain = isl_set_copy(isl_set_from_cloog_domain(f->domain));
1121 isl_set *tmp = isl_set_copy(loopDomain);
1122
1123 // Calculate a map similar to the identity map, but with the last input
1124 // and output dimension not related.
1125 // [i0, i1, i2, i3] -> [i0, i1, i2, o0]
1126 isl_dim *dim = isl_set_get_dim(loopDomain);
1127 dim = isl_dim_drop_outputs(dim, isl_set_n_dim(loopDomain) - 2, 1);
1128 dim = isl_dim_map_from_set(dim);
1129 isl_map *identity = isl_map_identity(dim);
1130 identity = isl_map_add_dims(identity, isl_dim_in, 1);
1131 identity = isl_map_add_dims(identity, isl_dim_out, 1);
1132
1133 isl_map *map = isl_map_from_domain_and_range(tmp, loopDomain);
1134 map = isl_map_intersect(map, identity);
1135
1136 isl_map *lexmax = isl_map_lexmax(isl_map_copy(map));
Tobias Grosserb76f38532011-08-20 11:11:25 +00001137 isl_map *lexmin = isl_map_lexmin(map);
Tobias Grosser75805372011-04-29 06:27:02 +00001138 isl_map *sub = isl_map_sum(lexmax, isl_map_neg(lexmin));
1139
1140 isl_set *elements = isl_map_range(sub);
1141
Tobias Grosserc532f122011-08-25 08:40:59 +00001142 if (!isl_set_is_singleton(elements)) {
1143 isl_set_free(elements);
Tobias Grosser75805372011-04-29 06:27:02 +00001144 return -1;
Tobias Grosserc532f122011-08-25 08:40:59 +00001145 }
Tobias Grosser75805372011-04-29 06:27:02 +00001146
1147 isl_point *p = isl_set_sample_point(elements);
1148
1149 isl_int v;
1150 isl_int_init(v);
1151 isl_point_get_coordinate(p, isl_dim_set, isl_set_n_dim(loopDomain) - 1, &v);
1152 int numberIterations = isl_int_get_si(v);
1153 isl_int_clear(v);
Tobias Grosserb76f38532011-08-20 11:11:25 +00001154 isl_point_free(p);
Tobias Grosser75805372011-04-29 06:27:02 +00001155
1156 return (numberIterations) / isl_int_get_si(f->stride) + 1;
1157 }
1158
1159 /// @brief Create vector instructions for this loop.
1160 void codegenForVector(const clast_for *f) {
1161 DEBUG(dbgs() << "Vectorizing loop '" << f->iterator << "'\n";);
1162 int vectorWidth = getNumberOfIterations(f);
1163
1164 Value *LB = ExpGen.codegen(f->LB,
1165 TD->getIntPtrType(Builder.getContext()));
1166
1167 APInt Stride = APInt_from_MPZ(f->stride);
Tobias Grosser55927aa2011-07-18 09:53:32 +00001168 IntegerType *LoopIVType = dyn_cast<IntegerType>(LB->getType());
Tobias Grosser75805372011-04-29 06:27:02 +00001169 Stride = Stride.zext(LoopIVType->getBitWidth());
1170 Value *StrideValue = ConstantInt::get(LoopIVType, Stride);
1171
1172 std::vector<Value*> IVS(vectorWidth);
1173 IVS[0] = LB;
1174
1175 for (int i = 1; i < vectorWidth; i++)
1176 IVS[i] = Builder.CreateAdd(IVS[i-1], StrideValue, "p_vector_iv");
1177
1178 isl_set *scatteringDomain = isl_set_from_cloog_domain(f->domain);
1179
1180 // Add loop iv to symbols.
1181 (*clastVars)[f->iterator] = LB;
1182
1183 const clast_stmt *stmt = f->body;
1184
1185 while (stmt) {
1186 codegen((const clast_user_stmt *)stmt, &IVS, f->iterator,
1187 scatteringDomain);
1188 stmt = stmt->next;
1189 }
1190
1191 // Loop is finished, so remove its iv from the live symbols.
1192 clastVars->erase(f->iterator);
1193 }
1194
1195 void codegen(const clast_for *f) {
Hongbin Zhengdbdebe22011-05-03 13:46:58 +00001196 if (Vector && isInnermostLoop(f) && DP->isParallelFor(f)
Tobias Grosser75805372011-04-29 06:27:02 +00001197 && (-1 != getNumberOfIterations(f))
1198 && (getNumberOfIterations(f) <= 16)) {
1199 codegenForVector(f);
Hongbin Zhengdbdebe22011-05-03 13:46:58 +00001200 } else if (OpenMP && !parallelCodeGeneration && DP->isParallelFor(f)) {
Tobias Grosser75805372011-04-29 06:27:02 +00001201 parallelCodeGeneration = true;
1202 parallelLoops.push_back(f->iterator);
1203 codegenForOpenMP(f);
1204 parallelCodeGeneration = false;
1205 } else
1206 codegenForSequential(f);
1207 }
1208
1209 Value *codegen(const clast_equation *eq) {
1210 Value *LHS = ExpGen.codegen(eq->LHS,
1211 TD->getIntPtrType(Builder.getContext()));
1212 Value *RHS = ExpGen.codegen(eq->RHS,
1213 TD->getIntPtrType(Builder.getContext()));
1214 CmpInst::Predicate P;
1215
1216 if (eq->sign == 0)
1217 P = ICmpInst::ICMP_EQ;
1218 else if (eq->sign > 0)
1219 P = ICmpInst::ICMP_SGE;
1220 else
1221 P = ICmpInst::ICMP_SLE;
1222
1223 return Builder.CreateICmp(P, LHS, RHS);
1224 }
1225
1226 void codegen(const clast_guard *g) {
1227 Function *F = Builder.GetInsertBlock()->getParent();
1228 LLVMContext &Context = F->getContext();
1229 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
1230 BasicBlock *MergeBB = BasicBlock::Create(Context, "polly.merge", F);
1231 DT->addNewBlock(ThenBB, Builder.GetInsertBlock());
1232 DT->addNewBlock(MergeBB, Builder.GetInsertBlock());
1233
1234 Value *Predicate = codegen(&(g->eq[0]));
1235
1236 for (int i = 1; i < g->n; ++i) {
1237 Value *TmpPredicate = codegen(&(g->eq[i]));
1238 Predicate = Builder.CreateAnd(Predicate, TmpPredicate);
1239 }
1240
1241 Builder.CreateCondBr(Predicate, ThenBB, MergeBB);
1242 Builder.SetInsertPoint(ThenBB);
1243
1244 codegen(g->then);
1245
1246 Builder.CreateBr(MergeBB);
1247 Builder.SetInsertPoint(MergeBB);
1248 }
1249
1250 void codegen(const clast_stmt *stmt) {
1251 if (CLAST_STMT_IS_A(stmt, stmt_root))
1252 assert(false && "No second root statement expected");
1253 else if (CLAST_STMT_IS_A(stmt, stmt_ass))
1254 codegen((const clast_assignment *)stmt);
1255 else if (CLAST_STMT_IS_A(stmt, stmt_user))
1256 codegen((const clast_user_stmt *)stmt);
1257 else if (CLAST_STMT_IS_A(stmt, stmt_block))
1258 codegen((const clast_block *)stmt);
1259 else if (CLAST_STMT_IS_A(stmt, stmt_for))
1260 codegen((const clast_for *)stmt);
1261 else if (CLAST_STMT_IS_A(stmt, stmt_guard))
1262 codegen((const clast_guard *)stmt);
1263
1264 if (stmt->next)
1265 codegen(stmt->next);
1266 }
1267
1268 void addParameters(const CloogNames *names) {
Tobias Grosser97fb5ac2011-06-30 19:39:10 +00001269 SCEVExpander Rewriter(SE, "polly");
Tobias Grosser75805372011-04-29 06:27:02 +00001270
1271 // Create an instruction that specifies the location where the parameters
1272 // are expanded.
1273 CastInst::CreateIntegerCast(ConstantInt::getTrue(Builder.getContext()),
1274 Builder.getInt16Ty(), false, "insertInst",
1275 Builder.GetInsertBlock());
1276
1277 int i = 0;
1278 for (Scop::param_iterator PI = S->param_begin(), PE = S->param_end();
1279 PI != PE; ++PI) {
1280 assert(i < names->nb_parameters && "Not enough parameter names");
1281
1282 const SCEV *Param = *PI;
Tobias Grosser55927aa2011-07-18 09:53:32 +00001283 Type *Ty = Param->getType();
Tobias Grosser75805372011-04-29 06:27:02 +00001284
1285 Instruction *insertLocation = --(Builder.GetInsertBlock()->end());
1286 Value *V = Rewriter.expandCodeFor(Param, Ty, insertLocation);
1287 (*clastVars)[names->parameters[i]] = V;
1288
1289 ++i;
1290 }
1291 }
1292
1293 public:
1294 void codegen(const clast_root *r) {
1295 clastVars = new CharMapT();
1296 addParameters(r->names);
1297 ExpGen.setIVS(clastVars);
1298
1299 parallelCodeGeneration = false;
1300
1301 const clast_stmt *stmt = (const clast_stmt*) r;
1302 if (stmt->next)
1303 codegen(stmt->next);
1304
1305 delete clastVars;
1306 }
1307
1308 ClastStmtCodeGen(Scop *scop, ScalarEvolution &se, DominatorTree *dt,
Hongbin Zheng94c5df12011-05-06 02:38:20 +00001309 ScopDetection *sd, Dependences *dp, TargetData *td,
1310 IRBuilder<> &B) :
1311 S(scop), SE(se), DT(dt), SD(sd), DP(dp), TD(td), Builder(B),
1312 ExpGen(Builder, NULL) {}
Tobias Grosser75805372011-04-29 06:27:02 +00001313
1314};
1315}
1316
1317namespace {
1318class CodeGeneration : public ScopPass {
1319 Region *region;
1320 Scop *S;
1321 DominatorTree *DT;
1322 ScalarEvolution *SE;
1323 ScopDetection *SD;
Tobias Grosser75805372011-04-29 06:27:02 +00001324 TargetData *TD;
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001325 RegionInfo *RI;
Tobias Grosser75805372011-04-29 06:27:02 +00001326
1327 std::vector<std::string> parallelLoops;
1328
1329 public:
1330 static char ID;
1331
1332 CodeGeneration() : ScopPass(ID) {}
1333
Tobias Grosser75805372011-04-29 06:27:02 +00001334 // Adding prototypes required if OpenMP is enabled.
1335 void addOpenMPDefinitions(IRBuilder<> &Builder)
1336 {
1337 Module *M = Builder.GetInsertBlock()->getParent()->getParent();
1338 LLVMContext &Context = Builder.getContext();
Tobias Grosser851b96e2011-07-12 12:42:54 +00001339 IntegerType *intPtrTy = TD->getIntPtrType(Context);
Tobias Grosser75805372011-04-29 06:27:02 +00001340
1341 if (!M->getFunction("GOMP_parallel_end")) {
1342 FunctionType *FT = FunctionType::get(Type::getVoidTy(Context), false);
1343 Function::Create(FT, Function::ExternalLinkage, "GOMP_parallel_end", M);
1344 }
1345
1346 if (!M->getFunction("GOMP_parallel_loop_runtime_start")) {
1347 // Type of first argument.
Tobias Grosser851b96e2011-07-12 12:42:54 +00001348 std::vector<Type*> Arguments(1, Builder.getInt8PtrTy());
Tobias Grosser75805372011-04-29 06:27:02 +00001349 FunctionType *FnArgTy = FunctionType::get(Builder.getVoidTy(), Arguments,
1350 false);
1351 PointerType *FnPtrTy = PointerType::getUnqual(FnArgTy);
1352
Tobias Grosser851b96e2011-07-12 12:42:54 +00001353 std::vector<Type*> args;
Tobias Grosser75805372011-04-29 06:27:02 +00001354 args.push_back(FnPtrTy);
1355 args.push_back(Builder.getInt8PtrTy());
1356 args.push_back(Builder.getInt32Ty());
1357 args.push_back(intPtrTy);
1358 args.push_back(intPtrTy);
1359 args.push_back(intPtrTy);
1360
1361 FunctionType *type = FunctionType::get(Builder.getVoidTy(), args, false);
1362 Function::Create(type, Function::ExternalLinkage,
1363 "GOMP_parallel_loop_runtime_start", M);
1364 }
1365
1366 if (!M->getFunction("GOMP_loop_runtime_next")) {
1367 PointerType *intLongPtrTy = PointerType::getUnqual(intPtrTy);
1368
Tobias Grosser851b96e2011-07-12 12:42:54 +00001369 std::vector<Type*> args;
Tobias Grosser75805372011-04-29 06:27:02 +00001370 args.push_back(intLongPtrTy);
1371 args.push_back(intLongPtrTy);
1372
1373 FunctionType *type = FunctionType::get(Builder.getInt8Ty(), args, false);
1374 Function::Create(type, Function::ExternalLinkage,
1375 "GOMP_loop_runtime_next", M);
1376 }
1377
1378 if (!M->getFunction("GOMP_loop_end_nowait")) {
1379 FunctionType *FT = FunctionType::get(Builder.getVoidTy(),
Tobias Grosser851b96e2011-07-12 12:42:54 +00001380 std::vector<Type*>(), false);
Tobias Grosser75805372011-04-29 06:27:02 +00001381 Function::Create(FT, Function::ExternalLinkage,
1382 "GOMP_loop_end_nowait", M);
1383 }
1384 }
1385
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001386 // Split the entry edge of the region and generate a new basic block on this
1387 // edge. This function also updates ScopInfo and RegionInfo.
1388 //
1389 // @param region The region where the entry edge will be splitted.
1390 BasicBlock *splitEdgeAdvanced(Region *region) {
1391 BasicBlock *newBlock;
1392 BasicBlock *splitBlock;
1393
1394 newBlock = SplitEdge(region->getEnteringBlock(), region->getEntry(), this);
1395
1396 if (DT->dominates(region->getEntry(), newBlock)) {
1397 // Update ScopInfo.
1398 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI)
1399 if ((*SI)->getBasicBlock() == newBlock) {
1400 (*SI)->setBasicBlock(newBlock);
1401 break;
1402 }
1403
1404 // Update RegionInfo.
1405 splitBlock = region->getEntry();
1406 region->replaceEntry(newBlock);
Tobias Grosser7a16c892011-05-14 19:01:55 +00001407 RI->setRegionFor(newBlock, region);
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001408 } else {
1409 RI->setRegionFor(newBlock, region->getParent());
1410 splitBlock = newBlock;
1411 }
1412
1413 return splitBlock;
1414 }
1415
1416 // Create a split block that branches either to the old code or to a new basic
1417 // block where the new code can be inserted.
1418 //
1419 // @param builder A builder that will be set to point to a basic block, where
1420 // the new code can be generated.
1421 // @return The split basic block.
1422 BasicBlock *addSplitAndStartBlock(IRBuilder<> *builder) {
1423 BasicBlock *splitBlock = splitEdgeAdvanced(region);
1424
1425 splitBlock->setName("polly.enterScop");
1426
1427 Function *function = splitBlock->getParent();
1428 BasicBlock *startBlock = BasicBlock::Create(function->getContext(),
1429 "polly.start", function);
1430 splitBlock->getTerminator()->eraseFromParent();
1431 builder->SetInsertPoint(splitBlock);
1432 builder->CreateCondBr(builder->getTrue(), startBlock, region->getEntry());
1433 DT->addNewBlock(startBlock, splitBlock);
1434
1435 // Start code generation here.
1436 builder->SetInsertPoint(startBlock);
1437 return splitBlock;
1438 }
1439
1440 // Merge the control flow of the newly generated code with the existing code.
1441 //
1442 // @param splitBlock The basic block where the control flow was split between
1443 // old and new version of the Scop.
1444 // @param builder An IRBuilder that points to the last instruction of the
1445 // newly generated code.
1446 void mergeControlFlow(BasicBlock *splitBlock, IRBuilder<> *builder) {
1447 BasicBlock *mergeBlock;
1448 Region *R = region;
1449
1450 if (R->getExit()->getSinglePredecessor())
1451 // No splitEdge required. A block with a single predecessor cannot have
1452 // PHI nodes that would complicate life.
1453 mergeBlock = R->getExit();
1454 else {
1455 mergeBlock = SplitEdge(R->getExitingBlock(), R->getExit(), this);
1456 // SplitEdge will never split R->getExit(), as R->getExit() has more than
1457 // one predecessor. Hence, mergeBlock is always a newly generated block.
1458 mergeBlock->setName("polly.finalMerge");
1459 R->replaceExit(mergeBlock);
1460 }
1461
1462 builder->CreateBr(mergeBlock);
1463
1464 if (DT->dominates(splitBlock, mergeBlock))
1465 DT->changeImmediateDominator(mergeBlock, splitBlock);
1466 }
1467
Tobias Grosser75805372011-04-29 06:27:02 +00001468 bool runOnScop(Scop &scop) {
1469 S = &scop;
1470 region = &S->getRegion();
Tobias Grosser75805372011-04-29 06:27:02 +00001471 DT = &getAnalysis<DominatorTree>();
1472 Dependences *DP = &getAnalysis<Dependences>();
1473 SE = &getAnalysis<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001474 SD = &getAnalysis<ScopDetection>();
1475 TD = &getAnalysis<TargetData>();
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001476 RI = &getAnalysis<RegionInfo>();
Tobias Grosser75805372011-04-29 06:27:02 +00001477
1478 parallelLoops.clear();
1479
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001480 assert(region->isSimple() && "Only simple regions are supported");
Tobias Grosser76d7c522011-05-14 19:01:37 +00001481
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001482 // In the CFG and we generate next to original code of the Scop the
1483 // optimized version. Both the new and the original version of the code
1484 // remain in the CFG. A branch statement decides which version is executed.
1485 // At the moment, we always execute the newly generated version (the old one
1486 // is dead code eliminated by the cleanup passes). Later we may decide to
1487 // execute the new version only under certain conditions. This will be the
1488 // case if we support constructs for which we cannot prove all assumptions
1489 // at compile time.
1490 //
1491 // Before transformation:
1492 //
1493 // bb0
1494 // |
1495 // orig_scop
1496 // |
1497 // bb1
1498 //
1499 // After transformation:
1500 // bb0
1501 // |
1502 // polly.splitBlock
Tobias Grosser2bd3af12011-08-01 22:39:00 +00001503 // / \.
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001504 // | startBlock
1505 // | |
1506 // orig_scop new_scop
1507 // \ /
1508 // \ /
1509 // bb1 (joinBlock)
1510 IRBuilder<> builder(region->getEntry());
Tobias Grosser75805372011-04-29 06:27:02 +00001511
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001512 // The builder will be set to startBlock.
1513 BasicBlock *splitBlock = addSplitAndStartBlock(&builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001514
1515 if (OpenMP)
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001516 addOpenMPDefinitions(builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001517
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001518 ClastStmtCodeGen CodeGen(S, *SE, DT, SD, DP, TD, builder);
Tobias Grosser3fdecae2011-05-14 19:02:39 +00001519 CloogInfo &C = getAnalysis<CloogInfo>();
1520 CodeGen.codegen(C.getClast());
Tobias Grosser75805372011-04-29 06:27:02 +00001521
Tobias Grosser75805372011-04-29 06:27:02 +00001522 parallelLoops.insert(parallelLoops.begin(),
1523 CodeGen.getParallelLoops().begin(),
1524 CodeGen.getParallelLoops().end());
1525
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001526 mergeControlFlow(splitBlock, &builder);
Tobias Grosser75805372011-04-29 06:27:02 +00001527
Tobias Grosserabb6dcd2011-05-14 19:02:34 +00001528 return true;
Tobias Grosser75805372011-04-29 06:27:02 +00001529 }
1530
1531 virtual void printScop(raw_ostream &OS) const {
1532 for (std::vector<std::string>::const_iterator PI = parallelLoops.begin(),
1533 PE = parallelLoops.end(); PI != PE; ++PI)
1534 OS << "Parallel loop with iterator '" << *PI << "' generated\n";
1535 }
1536
1537 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1538 AU.addRequired<CloogInfo>();
1539 AU.addRequired<Dependences>();
1540 AU.addRequired<DominatorTree>();
1541 AU.addRequired<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001542 AU.addRequired<RegionInfo>();
1543 AU.addRequired<ScopDetection>();
1544 AU.addRequired<ScopInfo>();
1545 AU.addRequired<TargetData>();
1546
1547 AU.addPreserved<CloogInfo>();
1548 AU.addPreserved<Dependences>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001549
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001550 // FIXME: We do not create LoopInfo for the newly generated loops.
Tobias Grosser75805372011-04-29 06:27:02 +00001551 AU.addPreserved<LoopInfo>();
1552 AU.addPreserved<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001553 AU.addPreserved<ScopDetection>();
1554 AU.addPreserved<ScalarEvolution>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001555
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001556 // FIXME: We do not yet add regions for the newly generated code to the
1557 // region tree.
Tobias Grosser75805372011-04-29 06:27:02 +00001558 AU.addPreserved<RegionInfo>();
1559 AU.addPreserved<TempScopInfo>();
1560 AU.addPreserved<ScopInfo>();
1561 AU.addPreservedID(IndependentBlocksID);
1562 }
1563};
1564}
1565
1566char CodeGeneration::ID = 1;
1567
1568static RegisterPass<CodeGeneration>
1569Z("polly-codegen", "Polly - Create LLVM-IR from the polyhedral information");
1570
1571Pass* polly::createCodeGenerationPass() {
1572 return new CodeGeneration();
1573}