blob: 84289ed37baaafe973351c5115a53b00dfc95856 [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
Tobias Grosser0a91f322012-05-29 09:11:46 +000023#include "polly/CodeGen/Cloog.h"
Sebastian Pope1f65542012-05-07 16:35:11 +000024#ifdef CLOOG_FOUND
25
26#define DEBUG_TYPE "polly-codegen"
Tobias Grosser75805372011-04-29 06:27:02 +000027#include "polly/Dependences.h"
Tobias Grosserbda1f8f2012-02-01 14:23:29 +000028#include "polly/LinkAllPasses.h"
Tobias Grosser75805372011-04-29 06:27:02 +000029#include "polly/ScopInfo.h"
30#include "polly/TempScopInfo.h"
Hongbin Zheng8a846612012-04-25 13:18:28 +000031#include "polly/CodeGen/CodeGeneration.h"
32#include "polly/CodeGen/BlockGenerators.h"
33#include "polly/CodeGen/LoopGenerators.h"
Tobias Grosser6217e182012-08-03 12:50:07 +000034#include "polly/CodeGen/PTXGenerator.h"
Tobias Grosser3a275d22012-05-29 09:11:54 +000035#include "polly/CodeGen/Utils.h"
Hongbin Zheng3b11a162012-04-25 13:16:49 +000036#include "polly/Support/GICHelper.h"
Tobias Grosserbda1f8f2012-02-01 14:23:29 +000037
38#include "llvm/Module.h"
39#include "llvm/ADT/SetVector.h"
Tobias Grosser900893d2012-03-29 13:10:26 +000040#include "llvm/ADT/PostOrderIterator.h"
Tobias Grosserbda1f8f2012-02-01 14:23:29 +000041#include "llvm/Analysis/LoopInfo.h"
42#include "llvm/Analysis/ScalarEvolutionExpander.h"
Tobias Grosser75805372011-04-29 06:27:02 +000043#include "llvm/Support/CommandLine.h"
44#include "llvm/Support/Debug.h"
Micah Villmow7a3d8202012-10-08 17:26:19 +000045#include "llvm/DataLayout.h"
Tobias Grosserbda1f8f2012-02-01 14:23:29 +000046#include "llvm/Transforms/Utils/BasicBlockUtils.h"
Tobias Grosser75805372011-04-29 06:27:02 +000047
48#define CLOOG_INT_GMP 1
49#include "cloog/cloog.h"
50#include "cloog/isl/cloog.h"
51
Raghesh Aloora71989c2011-12-28 02:48:26 +000052#include "isl/aff.h"
53
Tobias Grosser75805372011-04-29 06:27:02 +000054#include <vector>
55#include <utility>
56
57using namespace polly;
58using namespace llvm;
59
60struct isl_set;
61
62namespace polly {
Tobias Grosser75805372011-04-29 06:27:02 +000063static cl::opt<bool>
64OpenMP("enable-polly-openmp",
65 cl::desc("Generate OpenMP parallel code"), cl::Hidden,
66 cl::value_desc("OpenMP code generation enabled if true"),
Tobias Grosser0acfcdb2012-03-16 17:17:16 +000067 cl::init(false), cl::ZeroOrMore);
Tobias Grosser75805372011-04-29 06:27:02 +000068
Tobias Grosser6217e182012-08-03 12:50:07 +000069#ifdef GPU_CODEGEN
70static cl::opt<bool>
71GPGPU("enable-polly-gpgpu",
72 cl::desc("Generate GPU parallel code"), cl::Hidden,
73 cl::value_desc("GPGPU code generation enabled if true"),
74 cl::init(false), cl::ZeroOrMore);
75
76static cl::opt<std::string>
77GPUTriple("polly-gpgpu-triple",
78 cl::desc("Target triple for GPU code generation"),
79 cl::Hidden, cl::init(""));
80#endif /* GPU_CODEGEN */
81
Tobias Grosser75805372011-04-29 06:27:02 +000082typedef DenseMap<const char*, Value*> CharMapT;
Tobias Grosser70e8cdb2012-01-24 16:42:21 +000083
Tobias Grosser75805372011-04-29 06:27:02 +000084/// Class to generate LLVM-IR that calculates the value of a clast_expr.
85class ClastExpCodeGen {
86 IRBuilder<> &Builder;
Tobias Grosser5e8ffa82012-03-23 12:20:36 +000087 const CharMapT &IVS;
Tobias Grosser75805372011-04-29 06:27:02 +000088
Tobias Grosserbb137e32012-01-24 16:42:28 +000089 Value *codegen(const clast_name *e, Type *Ty);
90 Value *codegen(const clast_term *e, Type *Ty);
91 Value *codegen(const clast_binary *e, Type *Ty);
92 Value *codegen(const clast_reduction *r, Type *Ty);
Tobias Grosser75805372011-04-29 06:27:02 +000093public:
94
95 // A generator for clast expressions.
96 //
97 // @param B The IRBuilder that defines where the code to calculate the
98 // clast expressions should be inserted.
99 // @param IVMAP A Map that translates strings describing the induction
100 // variables to the Values* that represent these variables
101 // on the LLVM side.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000102 ClastExpCodeGen(IRBuilder<> &B, CharMapT &IVMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000103
104 // Generates code to calculate a given clast expression.
105 //
106 // @param e The expression to calculate.
107 // @return The Value that holds the result.
Tobias Grosserbb137e32012-01-24 16:42:28 +0000108 Value *codegen(const clast_expr *e, Type *Ty);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000109};
110
111Value *ClastExpCodeGen::codegen(const clast_name *e, Type *Ty) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000112 CharMapT::const_iterator I = IVS.find(e->name);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000113
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000114 assert(I != IVS.end() && "Clast name not found");
Tobias Grosserbb137e32012-01-24 16:42:28 +0000115
116 return Builder.CreateSExtOrBitCast(I->second, Ty);
117}
118
119Value *ClastExpCodeGen::codegen(const clast_term *e, Type *Ty) {
120 APInt a = APInt_from_MPZ(e->val);
121
122 Value *ConstOne = ConstantInt::get(Builder.getContext(), a);
123 ConstOne = Builder.CreateSExtOrBitCast(ConstOne, Ty);
124
125 if (!e->var)
126 return ConstOne;
127
128 Value *var = codegen(e->var, Ty);
129 return Builder.CreateMul(ConstOne, var);
130}
131
132Value *ClastExpCodeGen::codegen(const clast_binary *e, Type *Ty) {
133 Value *LHS = codegen(e->LHS, Ty);
134
135 APInt RHS_AP = APInt_from_MPZ(e->RHS);
136
137 Value *RHS = ConstantInt::get(Builder.getContext(), RHS_AP);
138 RHS = Builder.CreateSExtOrBitCast(RHS, Ty);
139
140 switch (e->type) {
141 case clast_bin_mod:
142 return Builder.CreateSRem(LHS, RHS);
143 case clast_bin_fdiv:
144 {
Tobias Grosser9a44b972012-02-16 14:13:19 +0000145 // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
Tobias Grosser906eafe2012-02-16 09:56:10 +0000146 Value *One = ConstantInt::get(Ty, 1);
147 Value *Zero = ConstantInt::get(Ty, 0);
Tobias Grosser9a44b972012-02-16 14:13:19 +0000148 Value *Sum1 = Builder.CreateSub(LHS, RHS);
149 Value *Sum2 = Builder.CreateAdd(Sum1, One);
150 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
151 Value *Dividend = Builder.CreateSelect(isNegative, Sum2, LHS);
152 return Builder.CreateSDiv(Dividend, RHS);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000153 }
154 case clast_bin_cdiv:
155 {
Tobias Grosser9a44b972012-02-16 14:13:19 +0000156 // ceild(n,d) ((n < 0) ? n : (n + d - 1)) / d
157 Value *One = ConstantInt::get(Ty, 1);
Tobias Grosser906eafe2012-02-16 09:56:10 +0000158 Value *Zero = ConstantInt::get(Ty, 0);
Tobias Grosser9a44b972012-02-16 14:13:19 +0000159 Value *Sum1 = Builder.CreateAdd(LHS, RHS);
160 Value *Sum2 = Builder.CreateSub(Sum1, One);
161 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
162 Value *Dividend = Builder.CreateSelect(isNegative, LHS, Sum2);
163 return Builder.CreateSDiv(Dividend, RHS);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000164 }
165 case clast_bin_div:
166 return Builder.CreateSDiv(LHS, RHS);
167 };
168
169 llvm_unreachable("Unknown clast binary expression type");
170}
171
172Value *ClastExpCodeGen::codegen(const clast_reduction *r, Type *Ty) {
173 assert(( r->type == clast_red_min
174 || r->type == clast_red_max
175 || r->type == clast_red_sum)
176 && "Clast reduction type not supported");
177 Value *old = codegen(r->elts[0], Ty);
178
179 for (int i=1; i < r->n; ++i) {
180 Value *exprValue = codegen(r->elts[i], Ty);
181
182 switch (r->type) {
183 case clast_red_min:
184 {
185 Value *cmp = Builder.CreateICmpSLT(old, exprValue);
186 old = Builder.CreateSelect(cmp, old, exprValue);
187 break;
188 }
189 case clast_red_max:
190 {
191 Value *cmp = Builder.CreateICmpSGT(old, exprValue);
192 old = Builder.CreateSelect(cmp, old, exprValue);
193 break;
194 }
195 case clast_red_sum:
196 old = Builder.CreateAdd(old, exprValue);
197 break;
Tobias Grosserbb137e32012-01-24 16:42:28 +0000198 }
Tobias Grosser75805372011-04-29 06:27:02 +0000199 }
200
Tobias Grosserbb137e32012-01-24 16:42:28 +0000201 return old;
202}
203
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000204ClastExpCodeGen::ClastExpCodeGen(IRBuilder<> &B, CharMapT &IVMap)
Tobias Grosserbb137e32012-01-24 16:42:28 +0000205 : Builder(B), IVS(IVMap) {}
206
207Value *ClastExpCodeGen::codegen(const clast_expr *e, Type *Ty) {
208 switch(e->type) {
209 case clast_expr_name:
210 return codegen((const clast_name *)e, Ty);
211 case clast_expr_term:
212 return codegen((const clast_term *)e, Ty);
213 case clast_expr_bin:
214 return codegen((const clast_binary *)e, Ty);
215 case clast_expr_red:
216 return codegen((const clast_reduction *)e, Ty);
217 }
218
219 llvm_unreachable("Unknown clast expression!");
220}
221
Tobias Grosser75805372011-04-29 06:27:02 +0000222class ClastStmtCodeGen {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000223public:
224 const std::vector<std::string> &getParallelLoops();
225
226private:
Tobias Grosser75805372011-04-29 06:27:02 +0000227 // The Scop we code generate.
228 Scop *S;
Tobias Grosser0ac92142012-02-14 14:02:27 +0000229 Pass *P;
Tobias Grosser75805372011-04-29 06:27:02 +0000230
231 // The Builder specifies the current location to code generate at.
232 IRBuilder<> &Builder;
233
234 // Map the Values from the old code to their counterparts in the new code.
235 ValueMapT ValueMap;
236
237 // clastVars maps from the textual representation of a clast variable to its
238 // current *Value. clast variables are scheduling variables, original
239 // induction variables or parameters. They are used either in loop bounds or
240 // to define the statement instance that is executed.
241 //
242 // for (s = 0; s < n + 3; ++i)
243 // for (t = s; t < m; ++j)
244 // Stmt(i = s + 3 * m, j = t);
245 //
246 // {s,t,i,j,n,m} is the set of clast variables in this clast.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000247 CharMapT ClastVars;
Tobias Grosser75805372011-04-29 06:27:02 +0000248
249 // Codegenerator for clast expressions.
250 ClastExpCodeGen ExpGen;
251
252 // Do we currently generate parallel code?
253 bool parallelCodeGeneration;
254
255 std::vector<std::string> parallelLoops;
256
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000257 void codegen(const clast_assignment *a);
Tobias Grosser75805372011-04-29 06:27:02 +0000258
259 void codegen(const clast_assignment *a, ScopStmt *Statement,
260 unsigned Dimension, int vectorDim,
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000261 std::vector<ValueMapT> *VectorVMap = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000262
263 void codegenSubstitutions(const clast_stmt *Assignment,
264 ScopStmt *Statement, int vectorDim = 0,
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000265 std::vector<ValueMapT> *VectorVMap = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000266
267 void codegen(const clast_user_stmt *u, std::vector<Value*> *IVS = NULL,
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000268 const char *iterator = NULL, isl_set *scatteringDomain = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000269
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000270 void codegen(const clast_block *b);
Tobias Grosser75805372011-04-29 06:27:02 +0000271
272 /// @brief Create a classical sequential loop.
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000273 void codegenForSequential(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000274
275 /// @brief Create OpenMP structure values.
276 ///
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000277 /// Create a list of values that has to be stored into the OpenMP subfuncition
Tobias Grosser75805372011-04-29 06:27:02 +0000278 /// structure.
Tobias Grosser177982c2012-11-01 05:34:48 +0000279 SetVector<Value*> getOMPValues(const clast_stmt *Body);
Tobias Grosser75805372011-04-29 06:27:02 +0000280
Tobias Grossera17f6662012-11-01 05:34:35 +0000281 /// @brief Update ClastVars and ValueMap according to a value map.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000282 ///
Tobias Grossera17f6662012-11-01 05:34:35 +0000283 /// @param VMap A map from old to new values.
284 void updateWithValueMap(OMPGenerator::ValueToValueMapTy &VMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000285
286 /// @brief Create an OpenMP parallel for loop.
287 ///
288 /// This loop reflects a loop as if it would have been created by an OpenMP
289 /// statement.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000290 void codegenForOpenMP(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000291
Tobias Grosser6217e182012-08-03 12:50:07 +0000292#ifdef GPU_CODEGEN
293 /// @brief Create GPGPU device memory access values.
294 ///
295 /// Create a list of values that will be set to be parameters of the GPGPU
296 /// subfunction. These parameters represent device memory base addresses
297 /// and the size in bytes.
298 SetVector<Value*> getGPUValues(unsigned &OutputBytes);
299
300 /// @brief Create a GPU parallel for loop.
301 ///
302 /// This loop reflects a loop as if it would have been created by a GPU
303 /// statement.
304 void codegenForGPGPU(const clast_for *F);
305
306 /// @brief Get innermost for loop.
307 const clast_stmt *getScheduleInfo(const clast_for *F,
308 std::vector<int> &NumIters,
309 unsigned &LoopDepth,
310 unsigned &NonPLoopDepth);
311#endif /* GPU_CODEGEN */
312
Tobias Grossere192b232012-05-22 08:46:07 +0000313 /// @brief Check if a loop is parallel
314 ///
315 /// Detect if a clast_for loop can be executed in parallel.
316 ///
Tobias Grosserc1b6cec2012-11-19 12:26:25 +0000317 /// @param For The clast for loop to check.
Tobias Grossere192b232012-05-22 08:46:07 +0000318 ///
319 /// @return bool Returns true if the incoming clast_for statement can
320 /// execute in parallel.
321 bool isParallelFor(const clast_for *For);
322
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000323 bool isInnermostLoop(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000324
325 /// @brief Get the number of loop iterations for this loop.
326 /// @param f The clast for loop to check.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000327 int getNumberOfIterations(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000328
329 /// @brief Create vector instructions for this loop.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000330 void codegenForVector(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000331
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000332 void codegen(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000333
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000334 Value *codegen(const clast_equation *eq);
Tobias Grosser75805372011-04-29 06:27:02 +0000335
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000336 void codegen(const clast_guard *g);
Tobias Grosser75805372011-04-29 06:27:02 +0000337
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000338 void codegen(const clast_stmt *stmt);
Tobias Grosser75805372011-04-29 06:27:02 +0000339
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000340 void addParameters(const CloogNames *names);
Tobias Grosser75805372011-04-29 06:27:02 +0000341
Tobias Grossere9ffea22012-03-15 09:34:48 +0000342 IntegerType *getIntPtrTy();
343
Tobias Grosser75805372011-04-29 06:27:02 +0000344 public:
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000345 void codegen(const clast_root *r);
Tobias Grosser75805372011-04-29 06:27:02 +0000346
Tobias Grosserd596b372012-03-15 09:34:52 +0000347 ClastStmtCodeGen(Scop *scop, IRBuilder<> &B, Pass *P);
Tobias Grosser75805372011-04-29 06:27:02 +0000348};
349}
350
Tobias Grossere9ffea22012-03-15 09:34:48 +0000351IntegerType *ClastStmtCodeGen::getIntPtrTy() {
Tobias Grosser5d01691d2012-11-01 16:45:18 +0000352 return P->getAnalysis<DataLayout>().getIntPtrType(Builder.getContext());
Tobias Grossere9ffea22012-03-15 09:34:48 +0000353}
354
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000355const std::vector<std::string> &ClastStmtCodeGen::getParallelLoops() {
356 return parallelLoops;
357}
358
359void ClastStmtCodeGen::codegen(const clast_assignment *a) {
Tobias Grossere9ffea22012-03-15 09:34:48 +0000360 Value *V= ExpGen.codegen(a->RHS, getIntPtrTy());
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000361 ClastVars[a->LHS] = V;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000362}
363
Tobias Grosserf00bd962012-04-02 12:26:13 +0000364void ClastStmtCodeGen::codegen(const clast_assignment *A, ScopStmt *Stmt,
365 unsigned Dim, int VectorDim,
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000366 std::vector<ValueMapT> *VectorVMap) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000367 const PHINode *PN;
Tobias Grosserf00bd962012-04-02 12:26:13 +0000368 Value *RHS;
369
370 assert(!A->LHS && "Statement assignments do not have left hand side");
371
Tobias Grosserf00bd962012-04-02 12:26:13 +0000372 PN = Stmt->getInductionVariableForDimension(Dim);
Tobias Grosser0905a232012-04-03 12:24:32 +0000373 RHS = ExpGen.codegen(A->RHS, Builder.getInt64Ty());
374 RHS = Builder.CreateTruncOrBitCast(RHS, PN->getType());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000375
376 if (VectorVMap)
Tobias Grosserf00bd962012-04-02 12:26:13 +0000377 (*VectorVMap)[VectorDim][PN] = RHS;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000378
Tobias Grosserf00bd962012-04-02 12:26:13 +0000379 ValueMap[PN] = RHS;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000380}
381
382void ClastStmtCodeGen::codegenSubstitutions(const clast_stmt *Assignment,
383 ScopStmt *Statement, int vectorDim,
384 std::vector<ValueMapT> *VectorVMap) {
385 int Dimension = 0;
386
387 while (Assignment) {
388 assert(CLAST_STMT_IS_A(Assignment, stmt_ass)
389 && "Substitions are expected to be assignments");
390 codegen((const clast_assignment *)Assignment, Statement, Dimension,
391 vectorDim, VectorVMap);
392 Assignment = Assignment->next;
393 Dimension++;
394 }
395}
396
397void ClastStmtCodeGen::codegen(const clast_user_stmt *u,
398 std::vector<Value*> *IVS , const char *iterator,
Tobias Grosser14bcbd52012-03-02 11:26:52 +0000399 isl_set *Domain) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000400 ScopStmt *Statement = (ScopStmt *)u->statement->usr;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000401
402 if (u->substitutions)
403 codegenSubstitutions(u->substitutions, Statement);
404
Tobias Grosser80998e72012-03-02 11:27:28 +0000405 int VectorDimensions = IVS ? IVS->size() : 1;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000406
Tobias Grosser80998e72012-03-02 11:27:28 +0000407 if (VectorDimensions == 1) {
Tobias Grosser55d52082012-03-02 15:20:39 +0000408 BlockGenerator::generate(Builder, *Statement, ValueMap, P);
Tobias Grosser80998e72012-03-02 11:27:28 +0000409 return;
410 }
411
412 VectorValueMapT VectorMap(VectorDimensions);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000413
414 if (IVS) {
415 assert (u->substitutions && "Substitutions expected!");
416 int i = 0;
417 for (std::vector<Value*>::iterator II = IVS->begin(), IE = IVS->end();
418 II != IE; ++II) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000419 ClastVars[iterator] = *II;
Tobias Grosser14bcbd52012-03-02 11:26:52 +0000420 codegenSubstitutions(u->substitutions, Statement, i, &VectorMap);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000421 i++;
422 }
423 }
424
Tobias Grosser55d52082012-03-02 15:20:39 +0000425 VectorBlockGenerator::generate(Builder, *Statement, VectorMap, Domain, P);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000426}
427
428void ClastStmtCodeGen::codegen(const clast_block *b) {
429 if (b->body)
430 codegen(b->body);
431}
432
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000433void ClastStmtCodeGen::codegenForSequential(const clast_for *f) {
434 Value *LowerBound, *UpperBound, *IV, *Stride;
Tobias Grosser0ac92142012-02-14 14:02:27 +0000435 BasicBlock *AfterBB;
Tobias Grossere9ffea22012-03-15 09:34:48 +0000436 Type *IntPtrTy = getIntPtrTy();
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000437
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000438 LowerBound = ExpGen.codegen(f->LB, IntPtrTy);
439 UpperBound = ExpGen.codegen(f->UB, IntPtrTy);
440 Stride = Builder.getInt(APInt_from_MPZ(f->stride));
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000441
Tobias Grosserc967d8e2012-10-16 07:29:13 +0000442 IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
443 CmpInst::ICMP_SLE);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000444
445 // Add loop iv to symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000446 ClastVars[f->iterator] = IV;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000447
448 if (f->body)
449 codegen(f->body);
450
451 // Loop is finished, so remove its iv from the live symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000452 ClastVars.erase(f->iterator);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000453 Builder.SetInsertPoint(AfterBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000454}
455
Tobias Grosser177982c2012-11-01 05:34:48 +0000456// Helper class to determine all scalar parameters used in the basic blocks of a
457// clast. Scalar parameters are scalar variables defined outside of the SCoP.
458class ParameterVisitor : public ClastVisitor {
459 std::set<Value *> Values;
460public:
461 ParameterVisitor() : ClastVisitor(), Values() { }
462
463 void visitUser(const clast_user_stmt *Stmt) {
464 const ScopStmt *S = static_cast<const ScopStmt *>(Stmt->statement->usr);
465 const BasicBlock *BB = S->getBasicBlock();
466
467 // Check all the operands of instructions in the basic block.
468 for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); BI != BE;
469 ++BI) {
470 const Instruction &Inst = *BI;
471 for (Instruction::const_op_iterator II = Inst.op_begin(),
472 IE = Inst.op_end(); II != IE; ++II) {
473 Value *SrcVal = *II;
474
475 if (Instruction *OpInst = dyn_cast<Instruction>(SrcVal))
476 if (S->getParent()->getRegion().contains(OpInst))
477 continue;
478
479 if (isa<Instruction>(SrcVal) || isa<Argument>(SrcVal))
480 Values.insert(SrcVal);
481 }
482 }
483 }
484
485 // Iterator to iterate over the values found.
486 typedef std::set<Value *>::const_iterator const_iterator;
487 inline const_iterator begin() const { return Values.begin(); }
488 inline const_iterator end() const { return Values.end(); }
489};
490
491SetVector<Value*> ClastStmtCodeGen::getOMPValues(const clast_stmt *Body) {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000492 SetVector<Value*> Values;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000493
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000494 // The clast variables
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000495 for (CharMapT::iterator I = ClastVars.begin(), E = ClastVars.end();
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000496 I != E; I++)
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000497 Values.insert(I->second);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000498
Tobias Grosser177982c2012-11-01 05:34:48 +0000499 // Find the temporaries that are referenced in the clast statements'
500 // basic blocks but are not defined by these blocks (e.g., references
501 // to function arguments or temporaries defined before the start of
502 // the SCoP).
503 ParameterVisitor Params;
504 Params.visit(Body);
505
506 for (ParameterVisitor::const_iterator PI = Params.begin(), PE = Params.end();
507 PI != PE; ++PI) {
508 Value *V = *PI;
509 Values.insert(V);
510 DEBUG(dbgs() << "Adding temporary for OMP copy-in: " << *V << "\n");
511 }
512
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000513 return Values;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000514}
515
Tobias Grossera17f6662012-11-01 05:34:35 +0000516void ClastStmtCodeGen::updateWithValueMap(
517 OMPGenerator::ValueToValueMapTy &VMap) {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000518 std::set<Value*> Inserted;
519
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000520 for (CharMapT::iterator I = ClastVars.begin(), E = ClastVars.end();
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000521 I != E; I++) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000522 ClastVars[I->first] = VMap[I->second];
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000523 Inserted.insert(I->second);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000524 }
525
Tobias Grossera17f6662012-11-01 05:34:35 +0000526 for (OMPGenerator::ValueToValueMapTy::iterator I = VMap.begin(),
527 E = VMap.end(); I != E; ++I) {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000528 if (Inserted.count(I->first))
529 continue;
530
531 ValueMap[I->first] = I->second;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000532 }
533}
534
Tobias Grosser900893d2012-03-29 13:10:26 +0000535static void clearDomtree(Function *F, DominatorTree &DT) {
536 DomTreeNode *N = DT.getNode(&F->getEntryBlock());
537 std::vector<BasicBlock*> Nodes;
538 for (po_iterator<DomTreeNode*> I = po_begin(N), E = po_end(N); I != E; ++I)
539 Nodes.push_back(I->getBlock());
540
541 for (std::vector<BasicBlock*>::iterator I = Nodes.begin(), E = Nodes.end();
542 I != E; ++I)
543 DT.eraseNode(*I);
544}
545
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000546void ClastStmtCodeGen::codegenForOpenMP(const clast_for *For) {
Tobias Grosserebf30082012-03-23 12:20:32 +0000547 Value *Stride, *LB, *UB, *IV;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000548 BasicBlock::iterator LoopBody;
549 IntegerType *IntPtrTy = getIntPtrTy();
550 SetVector<Value*> Values;
551 OMPGenerator::ValueToValueMapTy VMap;
552 OMPGenerator OMPGen(Builder, P);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000553
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000554 Stride = Builder.getInt(APInt_from_MPZ(For->stride));
555 Stride = Builder.CreateSExtOrBitCast(Stride, IntPtrTy);
Tobias Grosserebf30082012-03-23 12:20:32 +0000556 LB = ExpGen.codegen(For->LB, IntPtrTy);
557 UB = ExpGen.codegen(For->UB, IntPtrTy);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000558
Tobias Grosser177982c2012-11-01 05:34:48 +0000559 Values = getOMPValues(For->body);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000560
Tobias Grosserebf30082012-03-23 12:20:32 +0000561 IV = OMPGen.createParallelLoop(LB, UB, Stride, Values, VMap, &LoopBody);
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000562 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
563 Builder.SetInsertPoint(LoopBody);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000564
Tobias Grossera17f6662012-11-01 05:34:35 +0000565 // Save the current values.
566 const ValueMapT ValueMapCopy = ValueMap;
567 const CharMapT ClastVarsCopy = ClastVars;
568
569 updateWithValueMap(VMap);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000570 ClastVars[For->iterator] = IV;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000571
572 if (For->body)
573 codegen(For->body);
574
Tobias Grossera17f6662012-11-01 05:34:35 +0000575 // Restore the original values.
576 ValueMap = ValueMapCopy;
577 ClastVars = ClastVarsCopy;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000578
Tobias Grosser900893d2012-03-29 13:10:26 +0000579 clearDomtree((*LoopBody).getParent()->getParent(),
580 P->getAnalysis<DominatorTree>());
581
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000582 Builder.SetInsertPoint(AfterLoop);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000583}
584
Tobias Grosser6217e182012-08-03 12:50:07 +0000585#ifdef GPU_CODEGEN
586static unsigned getArraySizeInBytes(const ArrayType *AT) {
587 unsigned Bytes = AT->getNumElements();
588 if (const ArrayType *T = dyn_cast<ArrayType>(AT->getElementType()))
589 Bytes *= getArraySizeInBytes(T);
590 else
591 Bytes *= AT->getElementType()->getPrimitiveSizeInBits() / 8;
592
593 return Bytes;
594}
595
596SetVector<Value*> ClastStmtCodeGen::getGPUValues(unsigned &OutputBytes) {
597 SetVector<Value*> Values;
598 OutputBytes = 0;
599
600 // Record the memory reference base addresses.
601 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
602 ScopStmt *Stmt = *SI;
603 for (SmallVector<MemoryAccess*, 8>::iterator I = Stmt->memacc_begin(),
604 E = Stmt->memacc_end(); I != E; ++I) {
605 Value *BaseAddr = const_cast<Value*>((*I)->getBaseAddr());
606 Values.insert((BaseAddr));
607
608 // FIXME: we assume that there is one and only one array to be written
609 // in a SCoP.
610 int NumWrites = 0;
611 if ((*I)->isWrite()) {
612 ++NumWrites;
613 assert(NumWrites <= 1 &&
614 "We support at most one array to be written in a SCoP.");
615 if (const PointerType * PT =
616 dyn_cast<PointerType>(BaseAddr->getType())) {
617 Type *T = PT->getArrayElementType();
618 const ArrayType *ATy = dyn_cast<ArrayType>(T);
619 OutputBytes = getArraySizeInBytes(ATy);
620 }
621 }
622 }
623 }
624
625 return Values;
626}
627
628const clast_stmt *ClastStmtCodeGen::getScheduleInfo(const clast_for *F,
629 std::vector<int> &NumIters,
630 unsigned &LoopDepth,
631 unsigned &NonPLoopDepth) {
632 clast_stmt *Stmt = (clast_stmt *)F;
633 const clast_for *Result;
634 bool NonParaFlag = false;
635 LoopDepth = 0;
636 NonPLoopDepth = 0;
637
638 while (Stmt) {
639 if (CLAST_STMT_IS_A(Stmt, stmt_for)) {
640 const clast_for *T = (clast_for *) Stmt;
641 if (isParallelFor(T)) {
642 if (!NonParaFlag) {
643 NumIters.push_back(getNumberOfIterations(T));
644 Result = T;
645 }
646 } else
647 NonParaFlag = true;
648
649 Stmt = T->body;
650 LoopDepth++;
651 continue;
652 }
653 Stmt = Stmt->next;
654 }
655
656 assert(NumIters.size() == 4 &&
657 "The loops should be tiled into 4-depth parallel loops and an "
658 "innermost non-parallel one (if exist).");
659 NonPLoopDepth = LoopDepth - NumIters.size();
660 assert(NonPLoopDepth <= 1
661 && "We support only one innermost non-parallel loop currently.");
662 return (const clast_stmt *)Result->body;
663}
664
665void ClastStmtCodeGen::codegenForGPGPU(const clast_for *F) {
666 BasicBlock::iterator LoopBody;
667 SetVector<Value *> Values;
668 SetVector<Value *> IVS;
669 std::vector<int> NumIterations;
670 PTXGenerator::ValueToValueMapTy VMap;
671
672 assert(!GPUTriple.empty()
673 && "Target triple should be set properly for GPGPU code generation.");
674 PTXGenerator PTXGen(Builder, P, GPUTriple);
675
676 // Get original IVS and ScopStmt
677 unsigned TiledLoopDepth, NonPLoopDepth;
678 const clast_stmt *InnerStmt = getScheduleInfo(F, NumIterations,
679 TiledLoopDepth, NonPLoopDepth);
680 const clast_stmt *TmpStmt;
681 const clast_user_stmt *U;
682 const clast_for *InnerFor;
683 if (CLAST_STMT_IS_A(InnerStmt, stmt_for)) {
684 InnerFor = (const clast_for *)InnerStmt;
685 TmpStmt = InnerFor->body;
686 } else
687 TmpStmt = InnerStmt;
688 U = (const clast_user_stmt *) TmpStmt;
689 ScopStmt *Statement = (ScopStmt *) U->statement->usr;
690 for (unsigned i = 0; i < Statement->getNumIterators() - NonPLoopDepth; i++) {
691 const Value* IV = Statement->getInductionVariableForDimension(i);
692 IVS.insert(const_cast<Value *>(IV));
693 }
694
695 unsigned OutBytes;
696 Values = getGPUValues(OutBytes);
697 PTXGen.setOutputBytes(OutBytes);
698 PTXGen.startGeneration(Values, IVS, VMap, &LoopBody);
699
700 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
701 Builder.SetInsertPoint(LoopBody);
702
703 BasicBlock *AfterBB = 0;
704 if (NonPLoopDepth) {
705 Value *LowerBound, *UpperBound, *IV, *Stride;
706 Type *IntPtrTy = getIntPtrTy();
707 LowerBound = ExpGen.codegen(InnerFor->LB, IntPtrTy);
708 UpperBound = ExpGen.codegen(InnerFor->UB, IntPtrTy);
709 Stride = Builder.getInt(APInt_from_MPZ(InnerFor->stride));
Tobias Grosser6f3d0632012-11-30 00:39:49 +0000710 IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
711 CmpInst::ICMP_SLE);
Tobias Grosser6217e182012-08-03 12:50:07 +0000712 const Value *OldIV_ = Statement->getInductionVariableForDimension(2);
713 Value *OldIV = const_cast<Value *>(OldIV_);
714 VMap.insert(std::make_pair<Value*, Value*>(OldIV, IV));
715 }
716
Tobias Grossera17f6662012-11-01 05:34:35 +0000717 // Preserve the current values.
718 const ValueMapT ValueMapCopy = ValueMap;
719 const CharMapT ClastVarsCopy = ClastVars;
720 updateWithVMap(VMap);
721
Tobias Grosser6217e182012-08-03 12:50:07 +0000722 BlockGenerator::generate(Builder, *Statement, ValueMap, P);
Tobias Grossera17f6662012-11-01 05:34:35 +0000723
724 // Restore the original values.
725 ValueMap = ValueMapCopy;
726 ClastVars = ClastVarsCopy;
Tobias Grosser6217e182012-08-03 12:50:07 +0000727
728 if (AfterBB)
729 Builder.SetInsertPoint(AfterBB->begin());
730
731 // FIXME: The replacement of the host base address with the parameter of ptx
732 // subfunction should have been done by updateWithValueMap. We use the
733 // following codes to avoid affecting other parts of Polly. This should be
734 // fixed later.
735 Function *FN = Builder.GetInsertBlock()->getParent();
736 for (unsigned j = 0; j < Values.size(); j++) {
737 Value *baseAddr = Values[j];
738 for (Function::iterator B = FN->begin(); B != FN->end(); ++B) {
739 for (BasicBlock::iterator I = B->begin(); I != B->end(); ++I)
740 I->replaceUsesOfWith(baseAddr, ValueMap[baseAddr]);
741 }
742 }
743 Builder.SetInsertPoint(AfterLoop);
744 PTXGen.setLaunchingParameters(NumIterations[0], NumIterations[1],
745 NumIterations[2], NumIterations[3]);
746 PTXGen.finishGeneration(FN);
747}
748#endif
749
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000750bool ClastStmtCodeGen::isInnermostLoop(const clast_for *f) {
751 const clast_stmt *stmt = f->body;
752
753 while (stmt) {
754 if (!CLAST_STMT_IS_A(stmt, stmt_user))
755 return false;
756
757 stmt = stmt->next;
758 }
759
760 return true;
761}
762
763int ClastStmtCodeGen::getNumberOfIterations(const clast_for *f) {
764 isl_set *loopDomain = isl_set_copy(isl_set_from_cloog_domain(f->domain));
765 isl_set *tmp = isl_set_copy(loopDomain);
766
767 // Calculate a map similar to the identity map, but with the last input
768 // and output dimension not related.
769 // [i0, i1, i2, i3] -> [i0, i1, i2, o0]
770 isl_space *Space = isl_set_get_space(loopDomain);
771 Space = isl_space_drop_outputs(Space,
772 isl_set_dim(loopDomain, isl_dim_set) - 2, 1);
773 Space = isl_space_map_from_set(Space);
774 isl_map *identity = isl_map_identity(Space);
775 identity = isl_map_add_dims(identity, isl_dim_in, 1);
776 identity = isl_map_add_dims(identity, isl_dim_out, 1);
777
778 isl_map *map = isl_map_from_domain_and_range(tmp, loopDomain);
779 map = isl_map_intersect(map, identity);
780
781 isl_map *lexmax = isl_map_lexmax(isl_map_copy(map));
782 isl_map *lexmin = isl_map_lexmin(map);
783 isl_map *sub = isl_map_sum(lexmax, isl_map_neg(lexmin));
784
785 isl_set *elements = isl_map_range(sub);
786
787 if (!isl_set_is_singleton(elements)) {
788 isl_set_free(elements);
789 return -1;
790 }
791
792 isl_point *p = isl_set_sample_point(elements);
793
794 isl_int v;
795 isl_int_init(v);
796 isl_point_get_coordinate(p, isl_dim_set, isl_set_n_dim(loopDomain) - 1, &v);
797 int numberIterations = isl_int_get_si(v);
798 isl_int_clear(v);
799 isl_point_free(p);
800
801 return (numberIterations) / isl_int_get_si(f->stride) + 1;
802}
803
Tobias Grosser2da263e2012-03-15 09:34:55 +0000804void ClastStmtCodeGen::codegenForVector(const clast_for *F) {
805 DEBUG(dbgs() << "Vectorizing loop '" << F->iterator << "'\n";);
806 int VectorWidth = getNumberOfIterations(F);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000807
Tobias Grosser2da263e2012-03-15 09:34:55 +0000808 Value *LB = ExpGen.codegen(F->LB, getIntPtrTy());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000809
Tobias Grosser2da263e2012-03-15 09:34:55 +0000810 APInt Stride = APInt_from_MPZ(F->stride);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000811 IntegerType *LoopIVType = dyn_cast<IntegerType>(LB->getType());
812 Stride = Stride.zext(LoopIVType->getBitWidth());
813 Value *StrideValue = ConstantInt::get(LoopIVType, Stride);
814
Tobias Grosser2da263e2012-03-15 09:34:55 +0000815 std::vector<Value*> IVS(VectorWidth);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000816 IVS[0] = LB;
817
Tobias Grosser2da263e2012-03-15 09:34:55 +0000818 for (int i = 1; i < VectorWidth; i++)
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000819 IVS[i] = Builder.CreateAdd(IVS[i-1], StrideValue, "p_vector_iv");
820
Tobias Grosser00d898d2012-03-15 09:34:58 +0000821 isl_set *Domain = isl_set_from_cloog_domain(F->domain);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000822
823 // Add loop iv to symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000824 ClastVars[F->iterator] = LB;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000825
Tobias Grosser2da263e2012-03-15 09:34:55 +0000826 const clast_stmt *Stmt = F->body;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000827
Tobias Grosser2da263e2012-03-15 09:34:55 +0000828 while (Stmt) {
Tobias Grosser00d898d2012-03-15 09:34:58 +0000829 codegen((const clast_user_stmt *)Stmt, &IVS, F->iterator,
830 isl_set_copy(Domain));
Tobias Grosser2da263e2012-03-15 09:34:55 +0000831 Stmt = Stmt->next;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000832 }
833
834 // Loop is finished, so remove its iv from the live symbols.
Tobias Grosser00d898d2012-03-15 09:34:58 +0000835 isl_set_free(Domain);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000836 ClastVars.erase(F->iterator);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000837}
838
Tobias Grossere192b232012-05-22 08:46:07 +0000839
840bool ClastStmtCodeGen::isParallelFor(const clast_for *f) {
841 isl_set *Domain = isl_set_from_cloog_domain(f->domain);
842 assert(Domain && "Cannot access domain of loop");
843
844 Dependences &D = P->getAnalysis<Dependences>();
845
846 return D.isParallelDimension(isl_set_copy(Domain), isl_set_n_dim(Domain));
847}
848
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000849void ClastStmtCodeGen::codegen(const clast_for *f) {
Hongbin Zheng68794212012-05-06 10:22:19 +0000850 bool Vector = PollyVectorizerChoice != VECTORIZER_NONE;
Tobias Grossere192b232012-05-22 08:46:07 +0000851 if ((Vector || OpenMP) && isParallelFor(f)) {
Tobias Grosserce3f5372012-03-02 11:26:42 +0000852 if (Vector && isInnermostLoop(f) && (-1 != getNumberOfIterations(f))
853 && (getNumberOfIterations(f) <= 16)) {
854 codegenForVector(f);
855 return;
856 }
857
858 if (OpenMP && !parallelCodeGeneration) {
859 parallelCodeGeneration = true;
860 parallelLoops.push_back(f->iterator);
861 codegenForOpenMP(f);
862 parallelCodeGeneration = false;
863 return;
864 }
865 }
866
Tobias Grosser6217e182012-08-03 12:50:07 +0000867#ifdef GPU_CODEGEN
868 if (GPGPU && isParallelFor(f)) {
869 if (!parallelCodeGeneration) {
870 parallelCodeGeneration = true;
871 parallelLoops.push_back(f->iterator);
872 codegenForGPGPU(f);
873 parallelCodeGeneration = false;
874 return;
875 }
876 }
877#endif
878
Tobias Grosserce3f5372012-03-02 11:26:42 +0000879 codegenForSequential(f);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000880}
881
882Value *ClastStmtCodeGen::codegen(const clast_equation *eq) {
Tobias Grossere9ffea22012-03-15 09:34:48 +0000883 Value *LHS = ExpGen.codegen(eq->LHS, getIntPtrTy());
884 Value *RHS = ExpGen.codegen(eq->RHS, getIntPtrTy());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000885 CmpInst::Predicate P;
886
887 if (eq->sign == 0)
888 P = ICmpInst::ICMP_EQ;
889 else if (eq->sign > 0)
890 P = ICmpInst::ICMP_SGE;
891 else
892 P = ICmpInst::ICMP_SLE;
893
894 return Builder.CreateICmp(P, LHS, RHS);
895}
896
897void ClastStmtCodeGen::codegen(const clast_guard *g) {
898 Function *F = Builder.GetInsertBlock()->getParent();
899 LLVMContext &Context = F->getContext();
Tobias Grosser0ac92142012-02-14 14:02:27 +0000900
901 BasicBlock *CondBB = SplitBlock(Builder.GetInsertBlock(),
902 Builder.GetInsertPoint(), P);
903 CondBB->setName("polly.cond");
904 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), P);
905 MergeBB->setName("polly.merge");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000906 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000907
Tobias Grosserd596b372012-03-15 09:34:52 +0000908 DominatorTree &DT = P->getAnalysis<DominatorTree>();
909 DT.addNewBlock(ThenBB, CondBB);
910 DT.changeImmediateDominator(MergeBB, CondBB);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000911
912 CondBB->getTerminator()->eraseFromParent();
913
914 Builder.SetInsertPoint(CondBB);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000915
916 Value *Predicate = codegen(&(g->eq[0]));
917
918 for (int i = 1; i < g->n; ++i) {
919 Value *TmpPredicate = codegen(&(g->eq[i]));
920 Predicate = Builder.CreateAnd(Predicate, TmpPredicate);
921 }
922
923 Builder.CreateCondBr(Predicate, ThenBB, MergeBB);
924 Builder.SetInsertPoint(ThenBB);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000925 Builder.CreateBr(MergeBB);
926 Builder.SetInsertPoint(ThenBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000927
928 codegen(g->then);
Tobias Grosser62a3c962012-02-16 09:56:21 +0000929
930 Builder.SetInsertPoint(MergeBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000931}
932
933void ClastStmtCodeGen::codegen(const clast_stmt *stmt) {
934 if (CLAST_STMT_IS_A(stmt, stmt_root))
935 assert(false && "No second root statement expected");
936 else if (CLAST_STMT_IS_A(stmt, stmt_ass))
937 codegen((const clast_assignment *)stmt);
938 else if (CLAST_STMT_IS_A(stmt, stmt_user))
939 codegen((const clast_user_stmt *)stmt);
940 else if (CLAST_STMT_IS_A(stmt, stmt_block))
941 codegen((const clast_block *)stmt);
942 else if (CLAST_STMT_IS_A(stmt, stmt_for))
943 codegen((const clast_for *)stmt);
944 else if (CLAST_STMT_IS_A(stmt, stmt_guard))
945 codegen((const clast_guard *)stmt);
946
947 if (stmt->next)
948 codegen(stmt->next);
949}
950
951void ClastStmtCodeGen::addParameters(const CloogNames *names) {
Tobias Grosserd596b372012-03-15 09:34:52 +0000952 SCEVExpander Rewriter(P->getAnalysis<ScalarEvolution>(), "polly");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000953
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000954 int i = 0;
955 for (Scop::param_iterator PI = S->param_begin(), PE = S->param_end();
956 PI != PE; ++PI) {
957 assert(i < names->nb_parameters && "Not enough parameter names");
958
959 const SCEV *Param = *PI;
960 Type *Ty = Param->getType();
961
962 Instruction *insertLocation = --(Builder.GetInsertBlock()->end());
963 Value *V = Rewriter.expandCodeFor(Param, Ty, insertLocation);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000964 ClastVars[names->parameters[i]] = V;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000965
966 ++i;
967 }
968}
969
970void ClastStmtCodeGen::codegen(const clast_root *r) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000971 addParameters(r->names);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000972
973 parallelCodeGeneration = false;
974
975 const clast_stmt *stmt = (const clast_stmt*) r;
976 if (stmt->next)
977 codegen(stmt->next);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000978}
979
Tobias Grosserd596b372012-03-15 09:34:52 +0000980ClastStmtCodeGen::ClastStmtCodeGen(Scop *scop, IRBuilder<> &B, Pass *P) :
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000981 S(scop), P(P), Builder(B), ExpGen(Builder, ClastVars) {}
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000982
Tobias Grosser75805372011-04-29 06:27:02 +0000983namespace {
984class CodeGeneration : public ScopPass {
Tobias Grosser3a275d22012-05-29 09:11:54 +0000985 std::vector<std::string> ParallelLoops;
Tobias Grosser75805372011-04-29 06:27:02 +0000986
987 public:
988 static char ID;
989
990 CodeGeneration() : ScopPass(ID) {}
991
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000992
Tobias Grosser3a275d22012-05-29 09:11:54 +0000993 bool runOnScop(Scop &S) {
994 ParallelLoops.clear();
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000995
Tobias Grosser3a275d22012-05-29 09:11:54 +0000996 assert(S.getRegion().isSimple() && "Only simple regions are supported");
Tobias Grossercb47dfe2012-02-15 09:58:50 +0000997
Tobias Grosser3a275d22012-05-29 09:11:54 +0000998 BasicBlock *StartBlock = executeScopConditionally(S, this);
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000999
Tobias Grosser3a275d22012-05-29 09:11:54 +00001000 IRBuilder<> Builder(StartBlock->begin());
Tobias Grosser8c4cfc322011-05-14 19:01:49 +00001001
Tobias Grosser3a275d22012-05-29 09:11:54 +00001002 ClastStmtCodeGen CodeGen(&S, Builder, this);
Tobias Grosser3fdecae2011-05-14 19:02:39 +00001003 CloogInfo &C = getAnalysis<CloogInfo>();
1004 CodeGen.codegen(C.getClast());
Tobias Grosser75805372011-04-29 06:27:02 +00001005
Tobias Grosser3a275d22012-05-29 09:11:54 +00001006 ParallelLoops.insert(ParallelLoops.begin(),
Tobias Grosser75805372011-04-29 06:27:02 +00001007 CodeGen.getParallelLoops().begin(),
1008 CodeGen.getParallelLoops().end());
Tobias Grosserabb6dcd2011-05-14 19:02:34 +00001009 return true;
Tobias Grosser75805372011-04-29 06:27:02 +00001010 }
1011
1012 virtual void printScop(raw_ostream &OS) const {
Tobias Grosser3a275d22012-05-29 09:11:54 +00001013 for (std::vector<std::string>::const_iterator PI = ParallelLoops.begin(),
1014 PE = ParallelLoops.end(); PI != PE; ++PI)
Tobias Grosser75805372011-04-29 06:27:02 +00001015 OS << "Parallel loop with iterator '" << *PI << "' generated\n";
1016 }
1017
1018 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1019 AU.addRequired<CloogInfo>();
1020 AU.addRequired<Dependences>();
1021 AU.addRequired<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001022 AU.addRequired<RegionInfo>();
Tobias Grosser73600b82011-10-08 00:30:40 +00001023 AU.addRequired<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001024 AU.addRequired<ScopDetection>();
1025 AU.addRequired<ScopInfo>();
Micah Villmow7a3d8202012-10-08 17:26:19 +00001026 AU.addRequired<DataLayout>();
Tobias Grosser75805372011-04-29 06:27:02 +00001027
1028 AU.addPreserved<CloogInfo>();
1029 AU.addPreserved<Dependences>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001030
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001031 // FIXME: We do not create LoopInfo for the newly generated loops.
Tobias Grosser75805372011-04-29 06:27:02 +00001032 AU.addPreserved<LoopInfo>();
1033 AU.addPreserved<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001034 AU.addPreserved<ScopDetection>();
1035 AU.addPreserved<ScalarEvolution>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001036
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001037 // FIXME: We do not yet add regions for the newly generated code to the
1038 // region tree.
Tobias Grosser75805372011-04-29 06:27:02 +00001039 AU.addPreserved<RegionInfo>();
1040 AU.addPreserved<TempScopInfo>();
1041 AU.addPreserved<ScopInfo>();
1042 AU.addPreservedID(IndependentBlocksID);
1043 }
1044};
1045}
1046
1047char CodeGeneration::ID = 1;
1048
Tobias Grosser73600b82011-10-08 00:30:40 +00001049INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
Tobias Grosser3c2efba2012-03-06 07:38:57 +00001050 "Polly - Create LLVM-IR from SCoPs", false, false)
Tobias Grosser73600b82011-10-08 00:30:40 +00001051INITIALIZE_PASS_DEPENDENCY(CloogInfo)
1052INITIALIZE_PASS_DEPENDENCY(Dependences)
1053INITIALIZE_PASS_DEPENDENCY(DominatorTree)
1054INITIALIZE_PASS_DEPENDENCY(RegionInfo)
1055INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1056INITIALIZE_PASS_DEPENDENCY(ScopDetection)
Tobias Grosser660b58d2012-10-08 08:56:52 +00001057INITIALIZE_PASS_DEPENDENCY(DataLayout)
Tobias Grosser73600b82011-10-08 00:30:40 +00001058INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
Tobias Grosser3c2efba2012-03-06 07:38:57 +00001059 "Polly - Create LLVM-IR from SCoPs", false, false)
Tobias Grosser75805372011-04-29 06:27:02 +00001060
Tobias Grosser7ffe4e82011-11-17 12:56:10 +00001061Pass *polly::createCodeGenerationPass() {
Tobias Grosser75805372011-04-29 06:27:02 +00001062 return new CodeGeneration();
1063}
Sebastian Pope1f65542012-05-07 16:35:11 +00001064
1065#endif // CLOOG_FOUND