blob: e3e5621693e1a1023396e835c8e1cbce5bd3a12f [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
Chandler Carruth535d52c2013-01-02 11:47:44 +000038#include "llvm/IR/Module.h"
Tobias Grosserbda1f8f2012-02-01 14:23:29 +000039#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"
Chandler Carruth535d52c2013-01-02 11:47:44 +000045#include "llvm/IR/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>
Tobias Grosserc14582f2013-02-05 18:01:29 +000064OpenMP("enable-polly-openmp", cl::desc("Generate OpenMP parallel code"),
65 cl::Hidden, cl::value_desc("OpenMP code generation enabled if true"),
Tobias Grosser0acfcdb2012-03-16 17:17:16 +000066 cl::init(false), cl::ZeroOrMore);
Tobias Grosser75805372011-04-29 06:27:02 +000067
Tobias Grosser6217e182012-08-03 12:50:07 +000068#ifdef GPU_CODEGEN
69static cl::opt<bool>
Tobias Grosserc14582f2013-02-05 18:01:29 +000070GPGPU("enable-polly-gpgpu", cl::desc("Generate GPU parallel code"), cl::Hidden,
71 cl::value_desc("GPGPU code generation enabled if true"), cl::init(false),
72 cl::ZeroOrMore);
Tobias Grosser6217e182012-08-03 12:50:07 +000073
Tobias Grosserc14582f2013-02-05 18:01:29 +000074static cl::opt<std::string> GPUTriple(
75 "polly-gpgpu-triple", cl::desc("Target triple for GPU code generation"),
76 cl::Hidden, cl::init(""));
Tobias Grosser6217e182012-08-03 12:50:07 +000077#endif /* GPU_CODEGEN */
78
Tobias Grosserc14582f2013-02-05 18:01:29 +000079typedef DenseMap<const char *, Value *> CharMapT;
Tobias Grosser70e8cdb2012-01-24 16:42:21 +000080
Tobias Grosser75805372011-04-29 06:27:02 +000081/// Class to generate LLVM-IR that calculates the value of a clast_expr.
82class ClastExpCodeGen {
83 IRBuilder<> &Builder;
Tobias Grosser5e8ffa82012-03-23 12:20:36 +000084 const CharMapT &IVS;
Tobias Grosser75805372011-04-29 06:27:02 +000085
Tobias Grosserbb137e32012-01-24 16:42:28 +000086 Value *codegen(const clast_name *e, Type *Ty);
87 Value *codegen(const clast_term *e, Type *Ty);
88 Value *codegen(const clast_binary *e, Type *Ty);
89 Value *codegen(const clast_reduction *r, Type *Ty);
Tobias Grosser75805372011-04-29 06:27:02 +000090public:
91
92 // A generator for clast expressions.
93 //
94 // @param B The IRBuilder that defines where the code to calculate the
95 // clast expressions should be inserted.
96 // @param IVMAP A Map that translates strings describing the induction
97 // variables to the Values* that represent these variables
98 // on the LLVM side.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +000099 ClastExpCodeGen(IRBuilder<> &B, CharMapT &IVMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000100
101 // Generates code to calculate a given clast expression.
102 //
103 // @param e The expression to calculate.
104 // @return The Value that holds the result.
Tobias Grosserbb137e32012-01-24 16:42:28 +0000105 Value *codegen(const clast_expr *e, Type *Ty);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000106};
107
108Value *ClastExpCodeGen::codegen(const clast_name *e, Type *Ty) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000109 CharMapT::const_iterator I = IVS.find(e->name);
Tobias Grosserbb137e32012-01-24 16:42:28 +0000110
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000111 assert(I != IVS.end() && "Clast name not found");
Tobias Grosserbb137e32012-01-24 16:42:28 +0000112
113 return Builder.CreateSExtOrBitCast(I->second, Ty);
114}
115
116Value *ClastExpCodeGen::codegen(const clast_term *e, Type *Ty) {
117 APInt a = APInt_from_MPZ(e->val);
118
119 Value *ConstOne = ConstantInt::get(Builder.getContext(), a);
120 ConstOne = Builder.CreateSExtOrBitCast(ConstOne, Ty);
121
122 if (!e->var)
123 return ConstOne;
124
125 Value *var = codegen(e->var, Ty);
126 return Builder.CreateMul(ConstOne, var);
127}
128
129Value *ClastExpCodeGen::codegen(const clast_binary *e, Type *Ty) {
130 Value *LHS = codegen(e->LHS, Ty);
131
132 APInt RHS_AP = APInt_from_MPZ(e->RHS);
133
134 Value *RHS = ConstantInt::get(Builder.getContext(), RHS_AP);
135 RHS = Builder.CreateSExtOrBitCast(RHS, Ty);
136
137 switch (e->type) {
138 case clast_bin_mod:
139 return Builder.CreateSRem(LHS, RHS);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000140 case clast_bin_fdiv: {
141 // floord(n,d) ((n < 0) ? (n - d + 1) : n) / d
142 Value *One = ConstantInt::get(Ty, 1);
143 Value *Zero = ConstantInt::get(Ty, 0);
144 Value *Sum1 = Builder.CreateSub(LHS, RHS);
145 Value *Sum2 = Builder.CreateAdd(Sum1, One);
146 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
147 Value *Dividend = Builder.CreateSelect(isNegative, Sum2, LHS);
148 return Builder.CreateSDiv(Dividend, RHS);
149 }
150 case clast_bin_cdiv: {
151 // ceild(n,d) ((n < 0) ? n : (n + d - 1)) / d
152 Value *One = ConstantInt::get(Ty, 1);
153 Value *Zero = ConstantInt::get(Ty, 0);
154 Value *Sum1 = Builder.CreateAdd(LHS, RHS);
155 Value *Sum2 = Builder.CreateSub(Sum1, One);
156 Value *isNegative = Builder.CreateICmpSLT(LHS, Zero);
157 Value *Dividend = Builder.CreateSelect(isNegative, LHS, Sum2);
158 return Builder.CreateSDiv(Dividend, RHS);
159 }
Tobias Grosserbb137e32012-01-24 16:42:28 +0000160 case clast_bin_div:
161 return Builder.CreateSDiv(LHS, RHS);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000162 }
Tobias Grosserbb137e32012-01-24 16:42:28 +0000163
164 llvm_unreachable("Unknown clast binary expression type");
165}
166
167Value *ClastExpCodeGen::codegen(const clast_reduction *r, Type *Ty) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000168 assert((r->type == clast_red_min || r->type == clast_red_max ||
169 r->type == clast_red_sum) && "Clast reduction type not supported");
Tobias Grosserbb137e32012-01-24 16:42:28 +0000170 Value *old = codegen(r->elts[0], Ty);
171
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000172 for (int i = 1; i < r->n; ++i) {
Tobias Grosserbb137e32012-01-24 16:42:28 +0000173 Value *exprValue = codegen(r->elts[i], Ty);
174
175 switch (r->type) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000176 case clast_red_min: {
177 Value *cmp = Builder.CreateICmpSLT(old, exprValue);
178 old = Builder.CreateSelect(cmp, old, exprValue);
179 break;
180 }
181 case clast_red_max: {
182 Value *cmp = Builder.CreateICmpSGT(old, exprValue);
183 old = Builder.CreateSelect(cmp, old, exprValue);
184 break;
185 }
Tobias Grosserbb137e32012-01-24 16:42:28 +0000186 case clast_red_sum:
187 old = Builder.CreateAdd(old, exprValue);
188 break;
Tobias Grosserbb137e32012-01-24 16:42:28 +0000189 }
Tobias Grosser75805372011-04-29 06:27:02 +0000190 }
191
Tobias Grosserbb137e32012-01-24 16:42:28 +0000192 return old;
193}
194
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000195ClastExpCodeGen::ClastExpCodeGen(IRBuilder<> &B, CharMapT &IVMap)
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000196 : Builder(B), IVS(IVMap) {}
Tobias Grosserbb137e32012-01-24 16:42:28 +0000197
198Value *ClastExpCodeGen::codegen(const clast_expr *e, Type *Ty) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000199 switch (e->type) {
Tobias Grosserbb137e32012-01-24 16:42:28 +0000200 case clast_expr_name:
201 return codegen((const clast_name *)e, Ty);
202 case clast_expr_term:
203 return codegen((const clast_term *)e, Ty);
204 case clast_expr_bin:
205 return codegen((const clast_binary *)e, Ty);
206 case clast_expr_red:
207 return codegen((const clast_reduction *)e, Ty);
208 }
209
210 llvm_unreachable("Unknown clast expression!");
211}
212
Tobias Grosser75805372011-04-29 06:27:02 +0000213class ClastStmtCodeGen {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000214public:
215 const std::vector<std::string> &getParallelLoops();
216
217private:
Tobias Grosser75805372011-04-29 06:27:02 +0000218 // The Scop we code generate.
219 Scop *S;
Tobias Grosser0ac92142012-02-14 14:02:27 +0000220 Pass *P;
Tobias Grosser75805372011-04-29 06:27:02 +0000221
222 // The Builder specifies the current location to code generate at.
223 IRBuilder<> &Builder;
224
225 // Map the Values from the old code to their counterparts in the new code.
226 ValueMapT ValueMap;
227
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000228 // Map the loops from the old code to expressions function of the induction
229 // variables in the new code. For example, when the code generator produces
230 // this AST:
231 //
232 // for (int c1 = 0; c1 <= 1023; c1 += 1)
233 // for (int c2 = 0; c2 <= 1023; c2 += 1)
234 // Stmt(c2 + 3, c1);
235 //
236 // LoopToScev is a map associating:
237 // "outer loop in the old loop nest" -> SCEV("c2 + 3"),
238 // "inner loop in the old loop nest" -> SCEV("c1").
239 LoopToScevMapT LoopToScev;
240
Tobias Grosser75805372011-04-29 06:27:02 +0000241 // clastVars maps from the textual representation of a clast variable to its
242 // current *Value. clast variables are scheduling variables, original
243 // induction variables or parameters. They are used either in loop bounds or
244 // to define the statement instance that is executed.
245 //
246 // for (s = 0; s < n + 3; ++i)
247 // for (t = s; t < m; ++j)
248 // Stmt(i = s + 3 * m, j = t);
249 //
250 // {s,t,i,j,n,m} is the set of clast variables in this clast.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000251 CharMapT ClastVars;
Tobias Grosser75805372011-04-29 06:27:02 +0000252
253 // Codegenerator for clast expressions.
254 ClastExpCodeGen ExpGen;
255
256 // Do we currently generate parallel code?
257 bool parallelCodeGeneration;
258
259 std::vector<std::string> parallelLoops;
260
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000261 void codegen(const clast_assignment *a);
Tobias Grosser75805372011-04-29 06:27:02 +0000262
263 void codegen(const clast_assignment *a, ScopStmt *Statement,
264 unsigned Dimension, int vectorDim,
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000265 std::vector<ValueMapT> *VectorVMap = 0,
266 std::vector<LoopToScevMapT> *VLTS = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000267
Tobias Grosserc14582f2013-02-05 18:01:29 +0000268 void codegenSubstitutions(const clast_stmt *Assignment, ScopStmt *Statement,
269 int vectorDim = 0,
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000270 std::vector<ValueMapT> *VectorVMap = 0,
271 std::vector<LoopToScevMapT> *VLTS = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000272
Tobias Grosserc14582f2013-02-05 18:01:29 +0000273 void codegen(const clast_user_stmt *u, std::vector<Value *> *IVS = NULL,
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000274 const char *iterator = NULL, isl_set *scatteringDomain = 0);
Tobias Grosser75805372011-04-29 06:27:02 +0000275
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000276 void codegen(const clast_block *b);
Tobias Grosser75805372011-04-29 06:27:02 +0000277
278 /// @brief Create a classical sequential loop.
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000279 void codegenForSequential(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000280
281 /// @brief Create OpenMP structure values.
282 ///
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000283 /// Create a list of values that has to be stored into the OpenMP subfuncition
Tobias Grosser75805372011-04-29 06:27:02 +0000284 /// structure.
Tobias Grosserc14582f2013-02-05 18:01:29 +0000285 SetVector<Value *> getOMPValues(const clast_stmt *Body);
Tobias Grosser75805372011-04-29 06:27:02 +0000286
Tobias Grossera17f6662012-11-01 05:34:35 +0000287 /// @brief Update ClastVars and ValueMap according to a value map.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000288 ///
Tobias Grossera17f6662012-11-01 05:34:35 +0000289 /// @param VMap A map from old to new values.
290 void updateWithValueMap(OMPGenerator::ValueToValueMapTy &VMap);
Tobias Grosser75805372011-04-29 06:27:02 +0000291
292 /// @brief Create an OpenMP parallel for loop.
293 ///
294 /// This loop reflects a loop as if it would have been created by an OpenMP
295 /// statement.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000296 void codegenForOpenMP(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000297
Tobias Grosser6217e182012-08-03 12:50:07 +0000298#ifdef GPU_CODEGEN
299 /// @brief Create GPGPU device memory access values.
300 ///
301 /// Create a list of values that will be set to be parameters of the GPGPU
302 /// subfunction. These parameters represent device memory base addresses
303 /// and the size in bytes.
Tobias Grosserc14582f2013-02-05 18:01:29 +0000304 SetVector<Value *> getGPUValues(unsigned &OutputBytes);
Tobias Grosser6217e182012-08-03 12:50:07 +0000305
306 /// @brief Create a GPU parallel for loop.
307 ///
308 /// This loop reflects a loop as if it would have been created by a GPU
309 /// statement.
310 void codegenForGPGPU(const clast_for *F);
311
312 /// @brief Get innermost for loop.
Tobias Grosserc14582f2013-02-05 18:01:29 +0000313 const clast_stmt *
314 getScheduleInfo(const clast_for *F, std::vector<int> &NumIters,
315 unsigned &LoopDepth, unsigned &NonPLoopDepth);
Tobias Grosser6217e182012-08-03 12:50:07 +0000316#endif /* GPU_CODEGEN */
317
Tobias Grossere192b232012-05-22 08:46:07 +0000318 /// @brief Check if a loop is parallel
319 ///
320 /// Detect if a clast_for loop can be executed in parallel.
321 ///
Tobias Grosserc1b6cec2012-11-19 12:26:25 +0000322 /// @param For The clast for loop to check.
Tobias Grossere192b232012-05-22 08:46:07 +0000323 ///
324 /// @return bool Returns true if the incoming clast_for statement can
325 /// execute in parallel.
326 bool isParallelFor(const clast_for *For);
327
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000328 bool isInnermostLoop(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000329
330 /// @brief Get the number of loop iterations for this loop.
331 /// @param f The clast for loop to check.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000332 int getNumberOfIterations(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000333
334 /// @brief Create vector instructions for this loop.
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000335 void codegenForVector(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000336
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000337 void codegen(const clast_for *f);
Tobias Grosser75805372011-04-29 06:27:02 +0000338
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000339 Value *codegen(const clast_equation *eq);
Tobias Grosser75805372011-04-29 06:27:02 +0000340
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000341 void codegen(const clast_guard *g);
Tobias Grosser75805372011-04-29 06:27:02 +0000342
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000343 void codegen(const clast_stmt *stmt);
Tobias Grosser75805372011-04-29 06:27:02 +0000344
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000345 void addParameters(const CloogNames *names);
Tobias Grosser75805372011-04-29 06:27:02 +0000346
Tobias Grossere9ffea22012-03-15 09:34:48 +0000347 IntegerType *getIntPtrTy();
348
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000349public:
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000350 void codegen(const clast_root *r);
Tobias Grosser75805372011-04-29 06:27:02 +0000351
Tobias Grosserd596b372012-03-15 09:34:52 +0000352 ClastStmtCodeGen(Scop *scop, IRBuilder<> &B, Pass *P);
Tobias Grosser75805372011-04-29 06:27:02 +0000353};
354}
355
Tobias Grossere9ffea22012-03-15 09:34:48 +0000356IntegerType *ClastStmtCodeGen::getIntPtrTy() {
Tobias Grosser5d01691d2012-11-01 16:45:18 +0000357 return P->getAnalysis<DataLayout>().getIntPtrType(Builder.getContext());
Tobias Grossere9ffea22012-03-15 09:34:48 +0000358}
359
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000360const std::vector<std::string> &ClastStmtCodeGen::getParallelLoops() {
361 return parallelLoops;
362}
363
364void ClastStmtCodeGen::codegen(const clast_assignment *a) {
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000365 Value *V = ExpGen.codegen(a->RHS, getIntPtrTy());
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000366 ClastVars[a->LHS] = V;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000367}
368
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000369void ClastStmtCodeGen::codegen(
370 const clast_assignment *A, ScopStmt *Stmt, unsigned Dim, int VectorDim,
371 std::vector<ValueMapT> *VectorVMap, std::vector<LoopToScevMapT> *VLTS) {
Tobias Grosserf00bd962012-04-02 12:26:13 +0000372 Value *RHS;
373
374 assert(!A->LHS && "Statement assignments do not have left hand side");
375
Tobias Grosser0905a232012-04-03 12:24:32 +0000376 RHS = ExpGen.codegen(A->RHS, Builder.getInt64Ty());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000377
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000378 const llvm::SCEV *URHS = S->getSE()->getUnknown(RHS);
379 if (VLTS)
380 (*VLTS)[VectorDim][Stmt->getLoopForDimension(Dim)] = URHS;
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000381 LoopToScev[Stmt->getLoopForDimension(Dim)] = URHS;
Sebastian Pope039bb12013-03-18 19:09:49 +0000382
383 const PHINode *PN = Stmt->getInductionVariableForDimension(Dim);
384 if (PN) {
385 RHS = Builder.CreateTruncOrBitCast(RHS, PN->getType());
386
387 if (VectorVMap)
388 (*VectorVMap)[VectorDim][PN] = RHS;
389
390 ValueMap[PN] = RHS;
391 }
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000392}
393
Tobias Grosserc14582f2013-02-05 18:01:29 +0000394void ClastStmtCodeGen::codegenSubstitutions(
395 const clast_stmt *Assignment, ScopStmt *Statement, int vectorDim,
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000396 std::vector<ValueMapT> *VectorVMap, std::vector<LoopToScevMapT> *VLTS) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000397 int Dimension = 0;
398
399 while (Assignment) {
Tobias Grosserae2d83e2012-12-29 23:57:18 +0000400 assert(CLAST_STMT_IS_A(Assignment, stmt_ass) &&
401 "Substitions are expected to be assignments");
Tobias Grosserc14582f2013-02-05 18:01:29 +0000402 codegen((const clast_assignment *)Assignment, Statement, Dimension,
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000403 vectorDim, VectorVMap, VLTS);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000404 Assignment = Assignment->next;
405 Dimension++;
406 }
407}
408
Sebastian Popa00a0292012-12-18 07:46:06 +0000409// Takes the cloog specific domain and translates it into a map Statement ->
410// PartialSchedule, where the PartialSchedule contains all the dimensions that
411// have been code generated up to this point.
Tobias Grosserc14582f2013-02-05 18:01:29 +0000412static __isl_give isl_map *
413extractPartialSchedule(ScopStmt *Statement, isl_set *Domain) {
Sebastian Popa00a0292012-12-18 07:46:06 +0000414 isl_map *Schedule = Statement->getScattering();
415 int ScheduledDimensions = isl_set_dim(Domain, isl_dim_set);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000416 int UnscheduledDimensions =
417 isl_map_dim(Schedule, isl_dim_out) - ScheduledDimensions;
Sebastian Popa00a0292012-12-18 07:46:06 +0000418
419 return isl_map_project_out(Schedule, isl_dim_out, ScheduledDimensions,
420 UnscheduledDimensions);
421}
422
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000423void ClastStmtCodeGen::codegen(const clast_user_stmt *u,
Tobias Grosserc14582f2013-02-05 18:01:29 +0000424 std::vector<Value *> *IVS, const char *iterator,
Tobias Grosser14bcbd52012-03-02 11:26:52 +0000425 isl_set *Domain) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000426 ScopStmt *Statement = (ScopStmt *)u->statement->usr;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000427
428 if (u->substitutions)
429 codegenSubstitutions(u->substitutions, Statement);
430
Tobias Grosser80998e72012-03-02 11:27:28 +0000431 int VectorDimensions = IVS ? IVS->size() : 1;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000432
Tobias Grosser80998e72012-03-02 11:27:28 +0000433 if (VectorDimensions == 1) {
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000434 BlockGenerator::generate(Builder, *Statement, ValueMap, LoopToScev, P);
Tobias Grosser80998e72012-03-02 11:27:28 +0000435 return;
436 }
437
438 VectorValueMapT VectorMap(VectorDimensions);
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000439 std::vector<LoopToScevMapT> VLTS(VectorDimensions);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000440
441 if (IVS) {
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000442 assert(u->substitutions && "Substitutions expected!");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000443 int i = 0;
Tobias Grosserc14582f2013-02-05 18:01:29 +0000444 for (std::vector<Value *>::iterator II = IVS->begin(), IE = IVS->end();
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000445 II != IE; ++II) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000446 ClastVars[iterator] = *II;
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000447 codegenSubstitutions(u->substitutions, Statement, i, &VectorMap, &VLTS);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000448 i++;
449 }
450 }
451
Sebastian Popa00a0292012-12-18 07:46:06 +0000452 isl_map *Schedule = extractPartialSchedule(Statement, Domain);
Sebastian Pop9d10fff2013-02-15 20:55:59 +0000453 VectorBlockGenerator::generate(Builder, *Statement, VectorMap, VLTS, Schedule,
454 P);
Sebastian Popa00a0292012-12-18 07:46:06 +0000455 isl_map_free(Schedule);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000456}
457
458void ClastStmtCodeGen::codegen(const clast_block *b) {
459 if (b->body)
460 codegen(b->body);
461}
462
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000463void ClastStmtCodeGen::codegenForSequential(const clast_for *f) {
464 Value *LowerBound, *UpperBound, *IV, *Stride;
Tobias Grosser0ac92142012-02-14 14:02:27 +0000465 BasicBlock *AfterBB;
Tobias Grossere9ffea22012-03-15 09:34:48 +0000466 Type *IntPtrTy = getIntPtrTy();
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000467
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000468 LowerBound = ExpGen.codegen(f->LB, IntPtrTy);
469 UpperBound = ExpGen.codegen(f->UB, IntPtrTy);
470 Stride = Builder.getInt(APInt_from_MPZ(f->stride));
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000471
Tobias Grosserc967d8e2012-10-16 07:29:13 +0000472 IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
473 CmpInst::ICMP_SLE);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000474
475 // Add loop iv to symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000476 ClastVars[f->iterator] = IV;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000477
478 if (f->body)
479 codegen(f->body);
480
481 // Loop is finished, so remove its iv from the live symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000482 ClastVars.erase(f->iterator);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000483 Builder.SetInsertPoint(AfterBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000484}
485
Tobias Grosser177982c2012-11-01 05:34:48 +0000486// Helper class to determine all scalar parameters used in the basic blocks of a
487// clast. Scalar parameters are scalar variables defined outside of the SCoP.
488class ParameterVisitor : public ClastVisitor {
489 std::set<Value *> Values;
490public:
Tobias Grosserc14582f2013-02-05 18:01:29 +0000491 ParameterVisitor() : ClastVisitor(), Values() {}
Tobias Grosser177982c2012-11-01 05:34:48 +0000492
493 void visitUser(const clast_user_stmt *Stmt) {
494 const ScopStmt *S = static_cast<const ScopStmt *>(Stmt->statement->usr);
495 const BasicBlock *BB = S->getBasicBlock();
496
497 // Check all the operands of instructions in the basic block.
498 for (BasicBlock::const_iterator BI = BB->begin(), BE = BB->end(); BI != BE;
499 ++BI) {
500 const Instruction &Inst = *BI;
501 for (Instruction::const_op_iterator II = Inst.op_begin(),
Tobias Grosserc14582f2013-02-05 18:01:29 +0000502 IE = Inst.op_end();
503 II != IE; ++II) {
Tobias Grosser177982c2012-11-01 05:34:48 +0000504 Value *SrcVal = *II;
505
506 if (Instruction *OpInst = dyn_cast<Instruction>(SrcVal))
507 if (S->getParent()->getRegion().contains(OpInst))
508 continue;
509
510 if (isa<Instruction>(SrcVal) || isa<Argument>(SrcVal))
511 Values.insert(SrcVal);
512 }
513 }
514 }
515
516 // Iterator to iterate over the values found.
517 typedef std::set<Value *>::const_iterator const_iterator;
518 inline const_iterator begin() const { return Values.begin(); }
Tobias Grosserc14582f2013-02-05 18:01:29 +0000519 inline const_iterator end() const { return Values.end(); }
Tobias Grosser177982c2012-11-01 05:34:48 +0000520};
521
Tobias Grosserc14582f2013-02-05 18:01:29 +0000522SetVector<Value *> ClastStmtCodeGen::getOMPValues(const clast_stmt *Body) {
523 SetVector<Value *> Values;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000524
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000525 // The clast variables
Tobias Grosserc14582f2013-02-05 18:01:29 +0000526 for (CharMapT::iterator I = ClastVars.begin(), E = ClastVars.end(); I != E;
527 I++)
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000528 Values.insert(I->second);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000529
Tobias Grosser177982c2012-11-01 05:34:48 +0000530 // Find the temporaries that are referenced in the clast statements'
531 // basic blocks but are not defined by these blocks (e.g., references
532 // to function arguments or temporaries defined before the start of
533 // the SCoP).
534 ParameterVisitor Params;
535 Params.visit(Body);
536
537 for (ParameterVisitor::const_iterator PI = Params.begin(), PE = Params.end();
538 PI != PE; ++PI) {
539 Value *V = *PI;
540 Values.insert(V);
541 DEBUG(dbgs() << "Adding temporary for OMP copy-in: " << *V << "\n");
542 }
543
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000544 return Values;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000545}
546
Tobias Grossera17f6662012-11-01 05:34:35 +0000547void ClastStmtCodeGen::updateWithValueMap(
Tobias Grosserc14582f2013-02-05 18:01:29 +0000548 OMPGenerator::ValueToValueMapTy &VMap) {
549 std::set<Value *> Inserted;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000550
Tobias Grosserc14582f2013-02-05 18:01:29 +0000551 for (CharMapT::iterator I = ClastVars.begin(), E = ClastVars.end(); I != E;
552 I++) {
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000553 ClastVars[I->first] = VMap[I->second];
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000554 Inserted.insert(I->second);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000555 }
556
Tobias Grossera17f6662012-11-01 05:34:35 +0000557 for (OMPGenerator::ValueToValueMapTy::iterator I = VMap.begin(),
Tobias Grosserc14582f2013-02-05 18:01:29 +0000558 E = VMap.end();
559 I != E; ++I) {
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000560 if (Inserted.count(I->first))
561 continue;
562
563 ValueMap[I->first] = I->second;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000564 }
565}
566
Tobias Grosser900893d2012-03-29 13:10:26 +0000567static void clearDomtree(Function *F, DominatorTree &DT) {
568 DomTreeNode *N = DT.getNode(&F->getEntryBlock());
Tobias Grosserc14582f2013-02-05 18:01:29 +0000569 std::vector<BasicBlock *> Nodes;
570 for (po_iterator<DomTreeNode *> I = po_begin(N), E = po_end(N); I != E; ++I)
Tobias Grosser900893d2012-03-29 13:10:26 +0000571 Nodes.push_back(I->getBlock());
572
Tobias Grosserc14582f2013-02-05 18:01:29 +0000573 for (std::vector<BasicBlock *>::iterator I = Nodes.begin(), E = Nodes.end();
Tobias Grosser900893d2012-03-29 13:10:26 +0000574 I != E; ++I)
575 DT.eraseNode(*I);
576}
577
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000578void ClastStmtCodeGen::codegenForOpenMP(const clast_for *For) {
Tobias Grosserebf30082012-03-23 12:20:32 +0000579 Value *Stride, *LB, *UB, *IV;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000580 BasicBlock::iterator LoopBody;
581 IntegerType *IntPtrTy = getIntPtrTy();
Tobias Grosserc14582f2013-02-05 18:01:29 +0000582 SetVector<Value *> Values;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000583 OMPGenerator::ValueToValueMapTy VMap;
584 OMPGenerator OMPGen(Builder, P);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000585
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000586 Stride = Builder.getInt(APInt_from_MPZ(For->stride));
587 Stride = Builder.CreateSExtOrBitCast(Stride, IntPtrTy);
Tobias Grosserebf30082012-03-23 12:20:32 +0000588 LB = ExpGen.codegen(For->LB, IntPtrTy);
589 UB = ExpGen.codegen(For->UB, IntPtrTy);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000590
Tobias Grosser177982c2012-11-01 05:34:48 +0000591 Values = getOMPValues(For->body);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000592
Tobias Grosserebf30082012-03-23 12:20:32 +0000593 IV = OMPGen.createParallelLoop(LB, UB, Stride, Values, VMap, &LoopBody);
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000594 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
595 Builder.SetInsertPoint(LoopBody);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000596
Tobias Grossera17f6662012-11-01 05:34:35 +0000597 // Save the current values.
598 const ValueMapT ValueMapCopy = ValueMap;
599 const CharMapT ClastVarsCopy = ClastVars;
600
601 updateWithValueMap(VMap);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000602 ClastVars[For->iterator] = IV;
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000603
604 if (For->body)
605 codegen(For->body);
606
Tobias Grossera17f6662012-11-01 05:34:35 +0000607 // Restore the original values.
608 ValueMap = ValueMapCopy;
609 ClastVars = ClastVarsCopy;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000610
Tobias Grosser900893d2012-03-29 13:10:26 +0000611 clearDomtree((*LoopBody).getParent()->getParent(),
612 P->getAnalysis<DominatorTree>());
613
Tobias Grosserf74a4cd2012-03-23 10:35:18 +0000614 Builder.SetInsertPoint(AfterLoop);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000615}
616
Tobias Grosser6217e182012-08-03 12:50:07 +0000617#ifdef GPU_CODEGEN
618static unsigned getArraySizeInBytes(const ArrayType *AT) {
619 unsigned Bytes = AT->getNumElements();
620 if (const ArrayType *T = dyn_cast<ArrayType>(AT->getElementType()))
621 Bytes *= getArraySizeInBytes(T);
622 else
623 Bytes *= AT->getElementType()->getPrimitiveSizeInBits() / 8;
624
625 return Bytes;
626}
627
Tobias Grosserc14582f2013-02-05 18:01:29 +0000628SetVector<Value *> ClastStmtCodeGen::getGPUValues(unsigned &OutputBytes) {
629 SetVector<Value *> Values;
Tobias Grosser6217e182012-08-03 12:50:07 +0000630 OutputBytes = 0;
631
632 // Record the memory reference base addresses.
633 for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
634 ScopStmt *Stmt = *SI;
Tobias Grosserc14582f2013-02-05 18:01:29 +0000635 for (SmallVector<MemoryAccess *, 8>::iterator I = Stmt->memacc_begin(),
636 E = Stmt->memacc_end();
637 I != E; ++I) {
638 Value *BaseAddr = const_cast<Value *>((*I)->getBaseAddr());
Tobias Grosser6217e182012-08-03 12:50:07 +0000639 Values.insert((BaseAddr));
640
641 // FIXME: we assume that there is one and only one array to be written
642 // in a SCoP.
643 int NumWrites = 0;
644 if ((*I)->isWrite()) {
645 ++NumWrites;
646 assert(NumWrites <= 1 &&
647 "We support at most one array to be written in a SCoP.");
Tobias Grosserc14582f2013-02-05 18:01:29 +0000648 if (const PointerType *PT =
649 dyn_cast<PointerType>(BaseAddr->getType())) {
Tobias Grosser6217e182012-08-03 12:50:07 +0000650 Type *T = PT->getArrayElementType();
651 const ArrayType *ATy = dyn_cast<ArrayType>(T);
652 OutputBytes = getArraySizeInBytes(ATy);
653 }
654 }
655 }
656 }
657
658 return Values;
659}
660
Tobias Grosserc14582f2013-02-05 18:01:29 +0000661const clast_stmt *ClastStmtCodeGen::getScheduleInfo(
662 const clast_for *F, std::vector<int> &NumIters, unsigned &LoopDepth,
663 unsigned &NonPLoopDepth) {
Tobias Grosser6217e182012-08-03 12:50:07 +0000664 clast_stmt *Stmt = (clast_stmt *)F;
665 const clast_for *Result;
666 bool NonParaFlag = false;
667 LoopDepth = 0;
668 NonPLoopDepth = 0;
669
670 while (Stmt) {
671 if (CLAST_STMT_IS_A(Stmt, stmt_for)) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000672 const clast_for *T = (clast_for *)Stmt;
Tobias Grosser6217e182012-08-03 12:50:07 +0000673 if (isParallelFor(T)) {
674 if (!NonParaFlag) {
675 NumIters.push_back(getNumberOfIterations(T));
676 Result = T;
677 }
678 } else
679 NonParaFlag = true;
680
681 Stmt = T->body;
682 LoopDepth++;
683 continue;
684 }
685 Stmt = Stmt->next;
686 }
687
688 assert(NumIters.size() == 4 &&
689 "The loops should be tiled into 4-depth parallel loops and an "
690 "innermost non-parallel one (if exist).");
691 NonPLoopDepth = LoopDepth - NumIters.size();
Tobias Grosserc14582f2013-02-05 18:01:29 +0000692 assert(NonPLoopDepth <= 1 &&
693 "We support only one innermost non-parallel loop currently.");
Tobias Grosser6217e182012-08-03 12:50:07 +0000694 return (const clast_stmt *)Result->body;
695}
696
697void ClastStmtCodeGen::codegenForGPGPU(const clast_for *F) {
698 BasicBlock::iterator LoopBody;
699 SetVector<Value *> Values;
700 SetVector<Value *> IVS;
701 std::vector<int> NumIterations;
702 PTXGenerator::ValueToValueMapTy VMap;
703
Tobias Grosserae2d83e2012-12-29 23:57:18 +0000704 assert(!GPUTriple.empty() &&
705 "Target triple should be set properly for GPGPU code generation.");
Tobias Grosser6217e182012-08-03 12:50:07 +0000706 PTXGenerator PTXGen(Builder, P, GPUTriple);
707
708 // Get original IVS and ScopStmt
709 unsigned TiledLoopDepth, NonPLoopDepth;
Tobias Grosserc14582f2013-02-05 18:01:29 +0000710 const clast_stmt *InnerStmt =
711 getScheduleInfo(F, NumIterations, TiledLoopDepth, NonPLoopDepth);
Tobias Grosser6217e182012-08-03 12:50:07 +0000712 const clast_stmt *TmpStmt;
713 const clast_user_stmt *U;
714 const clast_for *InnerFor;
715 if (CLAST_STMT_IS_A(InnerStmt, stmt_for)) {
716 InnerFor = (const clast_for *)InnerStmt;
717 TmpStmt = InnerFor->body;
718 } else
719 TmpStmt = InnerStmt;
Tobias Grosserc14582f2013-02-05 18:01:29 +0000720 U = (const clast_user_stmt *)TmpStmt;
721 ScopStmt *Statement = (ScopStmt *)U->statement->usr;
Tobias Grosser6217e182012-08-03 12:50:07 +0000722 for (unsigned i = 0; i < Statement->getNumIterators() - NonPLoopDepth; i++) {
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000723 const Value *IV = Statement->getInductionVariableForDimension(i);
Tobias Grosser6217e182012-08-03 12:50:07 +0000724 IVS.insert(const_cast<Value *>(IV));
725 }
726
727 unsigned OutBytes;
728 Values = getGPUValues(OutBytes);
729 PTXGen.setOutputBytes(OutBytes);
730 PTXGen.startGeneration(Values, IVS, VMap, &LoopBody);
731
732 BasicBlock::iterator AfterLoop = Builder.GetInsertPoint();
733 Builder.SetInsertPoint(LoopBody);
734
735 BasicBlock *AfterBB = 0;
736 if (NonPLoopDepth) {
737 Value *LowerBound, *UpperBound, *IV, *Stride;
738 Type *IntPtrTy = getIntPtrTy();
739 LowerBound = ExpGen.codegen(InnerFor->LB, IntPtrTy);
740 UpperBound = ExpGen.codegen(InnerFor->UB, IntPtrTy);
741 Stride = Builder.getInt(APInt_from_MPZ(InnerFor->stride));
Tobias Grosser6f3d0632012-11-30 00:39:49 +0000742 IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, AfterBB,
743 CmpInst::ICMP_SLE);
Tobias Grosser6217e182012-08-03 12:50:07 +0000744 const Value *OldIV_ = Statement->getInductionVariableForDimension(2);
745 Value *OldIV = const_cast<Value *>(OldIV_);
Tobias Grosserc14582f2013-02-05 18:01:29 +0000746 VMap.insert(std::make_pair<Value *, Value *>(OldIV, IV));
Tobias Grosser6217e182012-08-03 12:50:07 +0000747 }
748
Tobias Grosser46c6abb2012-11-30 01:05:05 +0000749 updateWithValueMap(VMap);
Tobias Grossera17f6662012-11-01 05:34:35 +0000750
Tobias Grosser6217e182012-08-03 12:50:07 +0000751 BlockGenerator::generate(Builder, *Statement, ValueMap, P);
Tobias Grossera17f6662012-11-01 05:34:35 +0000752
Tobias Grosser6217e182012-08-03 12:50:07 +0000753 if (AfterBB)
754 Builder.SetInsertPoint(AfterBB->begin());
755
756 // FIXME: The replacement of the host base address with the parameter of ptx
757 // subfunction should have been done by updateWithValueMap. We use the
758 // following codes to avoid affecting other parts of Polly. This should be
759 // fixed later.
760 Function *FN = Builder.GetInsertBlock()->getParent();
761 for (unsigned j = 0; j < Values.size(); j++) {
762 Value *baseAddr = Values[j];
763 for (Function::iterator B = FN->begin(); B != FN->end(); ++B) {
764 for (BasicBlock::iterator I = B->begin(); I != B->end(); ++I)
765 I->replaceUsesOfWith(baseAddr, ValueMap[baseAddr]);
766 }
767 }
768 Builder.SetInsertPoint(AfterLoop);
769 PTXGen.setLaunchingParameters(NumIterations[0], NumIterations[1],
770 NumIterations[2], NumIterations[3]);
771 PTXGen.finishGeneration(FN);
772}
773#endif
774
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000775bool ClastStmtCodeGen::isInnermostLoop(const clast_for *f) {
776 const clast_stmt *stmt = f->body;
777
778 while (stmt) {
779 if (!CLAST_STMT_IS_A(stmt, stmt_user))
780 return false;
781
782 stmt = stmt->next;
783 }
784
785 return true;
786}
787
Sebastian Pop04c4ce32012-12-18 07:46:13 +0000788int ClastStmtCodeGen::getNumberOfIterations(const clast_for *For) {
789 isl_set *LoopDomain = isl_set_copy(isl_set_from_cloog_domain(For->domain));
Sebastian Pop2aa5c242012-12-18 08:56:51 +0000790 int NumberOfIterations = polly::getNumberOfIterations(LoopDomain);
791 if (NumberOfIterations == -1)
792 return -1;
793 return NumberOfIterations / isl_int_get_si(For->stride) + 1;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000794}
795
Tobias Grosser2da263e2012-03-15 09:34:55 +0000796void ClastStmtCodeGen::codegenForVector(const clast_for *F) {
797 DEBUG(dbgs() << "Vectorizing loop '" << F->iterator << "'\n";);
798 int VectorWidth = getNumberOfIterations(F);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000799
Tobias Grosser2da263e2012-03-15 09:34:55 +0000800 Value *LB = ExpGen.codegen(F->LB, getIntPtrTy());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000801
Tobias Grosser2da263e2012-03-15 09:34:55 +0000802 APInt Stride = APInt_from_MPZ(F->stride);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000803 IntegerType *LoopIVType = dyn_cast<IntegerType>(LB->getType());
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000804 Stride = Stride.zext(LoopIVType->getBitWidth());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000805 Value *StrideValue = ConstantInt::get(LoopIVType, Stride);
806
Tobias Grosserc14582f2013-02-05 18:01:29 +0000807 std::vector<Value *> IVS(VectorWidth);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000808 IVS[0] = LB;
809
Tobias Grosser2da263e2012-03-15 09:34:55 +0000810 for (int i = 1; i < VectorWidth; i++)
Tobias Grosserc14582f2013-02-05 18:01:29 +0000811 IVS[i] = Builder.CreateAdd(IVS[i - 1], StrideValue, "p_vector_iv");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000812
Tobias Grosser00d898d2012-03-15 09:34:58 +0000813 isl_set *Domain = isl_set_from_cloog_domain(F->domain);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000814
815 // Add loop iv to symbols.
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000816 ClastVars[F->iterator] = LB;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000817
Tobias Grosser2da263e2012-03-15 09:34:55 +0000818 const clast_stmt *Stmt = F->body;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000819
Tobias Grosser2da263e2012-03-15 09:34:55 +0000820 while (Stmt) {
Tobias Grosser00d898d2012-03-15 09:34:58 +0000821 codegen((const clast_user_stmt *)Stmt, &IVS, F->iterator,
822 isl_set_copy(Domain));
Tobias Grosser2da263e2012-03-15 09:34:55 +0000823 Stmt = Stmt->next;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000824 }
825
826 // Loop is finished, so remove its iv from the live symbols.
Tobias Grosser00d898d2012-03-15 09:34:58 +0000827 isl_set_free(Domain);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000828 ClastVars.erase(F->iterator);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000829}
830
Tobias Grossere192b232012-05-22 08:46:07 +0000831bool ClastStmtCodeGen::isParallelFor(const clast_for *f) {
832 isl_set *Domain = isl_set_from_cloog_domain(f->domain);
833 assert(Domain && "Cannot access domain of loop");
834
835 Dependences &D = P->getAnalysis<Dependences>();
836
837 return D.isParallelDimension(isl_set_copy(Domain), isl_set_n_dim(Domain));
838}
839
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000840void ClastStmtCodeGen::codegen(const clast_for *f) {
Hongbin Zheng68794212012-05-06 10:22:19 +0000841 bool Vector = PollyVectorizerChoice != VECTORIZER_NONE;
Tobias Grossere192b232012-05-22 08:46:07 +0000842 if ((Vector || OpenMP) && isParallelFor(f)) {
Tobias Grosserae2d83e2012-12-29 23:57:18 +0000843 if (Vector && isInnermostLoop(f) && (-1 != getNumberOfIterations(f)) &&
844 (getNumberOfIterations(f) <= 16)) {
Tobias Grosserce3f5372012-03-02 11:26:42 +0000845 codegenForVector(f);
846 return;
847 }
848
849 if (OpenMP && !parallelCodeGeneration) {
850 parallelCodeGeneration = true;
851 parallelLoops.push_back(f->iterator);
852 codegenForOpenMP(f);
853 parallelCodeGeneration = false;
854 return;
855 }
856 }
857
Tobias Grosser6217e182012-08-03 12:50:07 +0000858#ifdef GPU_CODEGEN
859 if (GPGPU && isParallelFor(f)) {
860 if (!parallelCodeGeneration) {
861 parallelCodeGeneration = true;
862 parallelLoops.push_back(f->iterator);
863 codegenForGPGPU(f);
864 parallelCodeGeneration = false;
865 return;
866 }
867 }
868#endif
869
Tobias Grosserce3f5372012-03-02 11:26:42 +0000870 codegenForSequential(f);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000871}
872
873Value *ClastStmtCodeGen::codegen(const clast_equation *eq) {
Tobias Grossere9ffea22012-03-15 09:34:48 +0000874 Value *LHS = ExpGen.codegen(eq->LHS, getIntPtrTy());
875 Value *RHS = ExpGen.codegen(eq->RHS, getIntPtrTy());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000876 CmpInst::Predicate P;
877
878 if (eq->sign == 0)
879 P = ICmpInst::ICMP_EQ;
880 else if (eq->sign > 0)
881 P = ICmpInst::ICMP_SGE;
882 else
883 P = ICmpInst::ICMP_SLE;
884
885 return Builder.CreateICmp(P, LHS, RHS);
886}
887
888void ClastStmtCodeGen::codegen(const clast_guard *g) {
889 Function *F = Builder.GetInsertBlock()->getParent();
890 LLVMContext &Context = F->getContext();
Tobias Grosser0ac92142012-02-14 14:02:27 +0000891
Tobias Grosserc14582f2013-02-05 18:01:29 +0000892 BasicBlock *CondBB =
893 SplitBlock(Builder.GetInsertBlock(), Builder.GetInsertPoint(), P);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000894 CondBB->setName("polly.cond");
895 BasicBlock *MergeBB = SplitBlock(CondBB, CondBB->begin(), P);
896 MergeBB->setName("polly.merge");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000897 BasicBlock *ThenBB = BasicBlock::Create(Context, "polly.then", F);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000898
Tobias Grosserd596b372012-03-15 09:34:52 +0000899 DominatorTree &DT = P->getAnalysis<DominatorTree>();
900 DT.addNewBlock(ThenBB, CondBB);
901 DT.changeImmediateDominator(MergeBB, CondBB);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000902
903 CondBB->getTerminator()->eraseFromParent();
904
905 Builder.SetInsertPoint(CondBB);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000906
907 Value *Predicate = codegen(&(g->eq[0]));
908
909 for (int i = 1; i < g->n; ++i) {
910 Value *TmpPredicate = codegen(&(g->eq[i]));
911 Predicate = Builder.CreateAnd(Predicate, TmpPredicate);
912 }
913
914 Builder.CreateCondBr(Predicate, ThenBB, MergeBB);
915 Builder.SetInsertPoint(ThenBB);
Tobias Grosser0ac92142012-02-14 14:02:27 +0000916 Builder.CreateBr(MergeBB);
917 Builder.SetInsertPoint(ThenBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000918
919 codegen(g->then);
Tobias Grosser62a3c962012-02-16 09:56:21 +0000920
921 Builder.SetInsertPoint(MergeBB->begin());
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000922}
923
924void ClastStmtCodeGen::codegen(const clast_stmt *stmt) {
Tobias Grosserc14582f2013-02-05 18:01:29 +0000925 if (CLAST_STMT_IS_A(stmt, stmt_root))
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000926 assert(false && "No second root statement expected");
927 else if (CLAST_STMT_IS_A(stmt, stmt_ass))
928 codegen((const clast_assignment *)stmt);
929 else if (CLAST_STMT_IS_A(stmt, stmt_user))
930 codegen((const clast_user_stmt *)stmt);
931 else if (CLAST_STMT_IS_A(stmt, stmt_block))
932 codegen((const clast_block *)stmt);
933 else if (CLAST_STMT_IS_A(stmt, stmt_for))
934 codegen((const clast_for *)stmt);
935 else if (CLAST_STMT_IS_A(stmt, stmt_guard))
936 codegen((const clast_guard *)stmt);
937
938 if (stmt->next)
939 codegen(stmt->next);
940}
941
942void ClastStmtCodeGen::addParameters(const CloogNames *names) {
Tobias Grosserd596b372012-03-15 09:34:52 +0000943 SCEVExpander Rewriter(P->getAnalysis<ScalarEvolution>(), "polly");
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000944
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000945 int i = 0;
946 for (Scop::param_iterator PI = S->param_begin(), PE = S->param_end();
947 PI != PE; ++PI) {
948 assert(i < names->nb_parameters && "Not enough parameter names");
949
950 const SCEV *Param = *PI;
951 Type *Ty = Param->getType();
952
953 Instruction *insertLocation = --(Builder.GetInsertBlock()->end());
954 Value *V = Rewriter.expandCodeFor(Param, Ty, insertLocation);
Tobias Grosser5e8ffa82012-03-23 12:20:36 +0000955 ClastVars[names->parameters[i]] = V;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000956
957 ++i;
958 }
959}
960
961void ClastStmtCodeGen::codegen(const clast_root *r) {
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000962 addParameters(r->names);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000963
964 parallelCodeGeneration = false;
965
Tobias Grosserc14582f2013-02-05 18:01:29 +0000966 const clast_stmt *stmt = (const clast_stmt *)r;
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000967 if (stmt->next)
968 codegen(stmt->next);
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000969}
970
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000971ClastStmtCodeGen::ClastStmtCodeGen(Scop *scop, IRBuilder<> &B, Pass *P)
Tobias Grosser4d96c8d2013-03-23 01:05:07 +0000972 : S(scop), P(P), Builder(B), ExpGen(Builder, ClastVars) {}
Tobias Grosser9bc5eb082012-01-24 16:42:32 +0000973
Tobias Grosser75805372011-04-29 06:27:02 +0000974namespace {
975class CodeGeneration : public ScopPass {
Tobias Grosser3a275d22012-05-29 09:11:54 +0000976 std::vector<std::string> ParallelLoops;
Tobias Grosser75805372011-04-29 06:27:02 +0000977
Tobias Grosser1bb59b02012-12-29 23:47:38 +0000978public:
Tobias Grosser75805372011-04-29 06:27:02 +0000979 static char ID;
980
981 CodeGeneration() : ScopPass(ID) {}
982
Tobias Grosser3a275d22012-05-29 09:11:54 +0000983 bool runOnScop(Scop &S) {
984 ParallelLoops.clear();
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000985
Tobias Grosser3a275d22012-05-29 09:11:54 +0000986 assert(S.getRegion().isSimple() && "Only simple regions are supported");
Tobias Grossercb47dfe2012-02-15 09:58:50 +0000987
Tobias Grosser3a275d22012-05-29 09:11:54 +0000988 BasicBlock *StartBlock = executeScopConditionally(S, this);
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000989
Tobias Grosser3a275d22012-05-29 09:11:54 +0000990 IRBuilder<> Builder(StartBlock->begin());
Tobias Grosser8c4cfc322011-05-14 19:01:49 +0000991
Tobias Grosser3a275d22012-05-29 09:11:54 +0000992 ClastStmtCodeGen CodeGen(&S, Builder, this);
Tobias Grosser3fdecae2011-05-14 19:02:39 +0000993 CloogInfo &C = getAnalysis<CloogInfo>();
994 CodeGen.codegen(C.getClast());
Tobias Grosser75805372011-04-29 06:27:02 +0000995
Tobias Grosser3a275d22012-05-29 09:11:54 +0000996 ParallelLoops.insert(ParallelLoops.begin(),
Tobias Grosser75805372011-04-29 06:27:02 +0000997 CodeGen.getParallelLoops().begin(),
998 CodeGen.getParallelLoops().end());
Tobias Grosserabb6dcd2011-05-14 19:02:34 +0000999 return true;
Tobias Grosser75805372011-04-29 06:27:02 +00001000 }
1001
1002 virtual void printScop(raw_ostream &OS) const {
Tobias Grosser3a275d22012-05-29 09:11:54 +00001003 for (std::vector<std::string>::const_iterator PI = ParallelLoops.begin(),
Tobias Grosserc14582f2013-02-05 18:01:29 +00001004 PE = ParallelLoops.end();
1005 PI != PE; ++PI)
Tobias Grosser75805372011-04-29 06:27:02 +00001006 OS << "Parallel loop with iterator '" << *PI << "' generated\n";
1007 }
1008
1009 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1010 AU.addRequired<CloogInfo>();
1011 AU.addRequired<Dependences>();
1012 AU.addRequired<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001013 AU.addRequired<RegionInfo>();
Tobias Grosser73600b82011-10-08 00:30:40 +00001014 AU.addRequired<ScalarEvolution>();
Tobias Grosser75805372011-04-29 06:27:02 +00001015 AU.addRequired<ScopDetection>();
1016 AU.addRequired<ScopInfo>();
Micah Villmow7a3d8202012-10-08 17:26:19 +00001017 AU.addRequired<DataLayout>();
Tobias Grosserecfe21b2013-03-20 18:03:18 +00001018 AU.addRequired<LoopInfo>();
Tobias Grosser75805372011-04-29 06:27:02 +00001019
1020 AU.addPreserved<CloogInfo>();
1021 AU.addPreserved<Dependences>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001022
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001023 // FIXME: We do not create LoopInfo for the newly generated loops.
Tobias Grosser75805372011-04-29 06:27:02 +00001024 AU.addPreserved<LoopInfo>();
1025 AU.addPreserved<DominatorTree>();
Tobias Grosser75805372011-04-29 06:27:02 +00001026 AU.addPreserved<ScopDetection>();
1027 AU.addPreserved<ScalarEvolution>();
Tobias Grosser5d6eb862011-05-14 19:02:45 +00001028
Tobias Grosser4e3f9a42011-05-23 15:23:36 +00001029 // FIXME: We do not yet add regions for the newly generated code to the
1030 // region tree.
Tobias Grosser75805372011-04-29 06:27:02 +00001031 AU.addPreserved<RegionInfo>();
1032 AU.addPreserved<TempScopInfo>();
1033 AU.addPreserved<ScopInfo>();
1034 AU.addPreservedID(IndependentBlocksID);
1035 }
1036};
1037}
1038
1039char CodeGeneration::ID = 1;
1040
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00001041Pass *polly::createCodeGenerationPass() { return new CodeGeneration(); }
Sebastian Pope1f65542012-05-07 16:35:11 +00001042
Tobias Grosser7242ad92013-02-22 08:07:06 +00001043INITIALIZE_PASS_BEGIN(CodeGeneration, "polly-codegen",
1044 "Polly - Create LLVM-IR from SCoPs", false, false);
1045INITIALIZE_PASS_DEPENDENCY(CloogInfo);
1046INITIALIZE_PASS_DEPENDENCY(Dependences);
1047INITIALIZE_PASS_DEPENDENCY(DominatorTree);
1048INITIALIZE_PASS_DEPENDENCY(RegionInfo);
1049INITIALIZE_PASS_DEPENDENCY(ScalarEvolution);
1050INITIALIZE_PASS_DEPENDENCY(ScopDetection);
1051INITIALIZE_PASS_DEPENDENCY(DataLayout);
1052INITIALIZE_PASS_END(CodeGeneration, "polly-codegen",
Tobias Grosser4d96c8d2013-03-23 01:05:07 +00001053 "Polly - Create LLVM-IR from SCoPs", false, false)
Tobias Grosser7242ad92013-02-22 08:07:06 +00001054
Sebastian Pope1f65542012-05-07 16:35:11 +00001055#endif // CLOOG_FOUND