1 //===- IslAst.cpp - isl code generator interface --------------------------===//
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 isl code generator interface takes a Scop and generates a isl_ast. This
11 // ist_ast can either be returned directly or it can be pretty printed to
12 // stdout.
13 //
14 // A typical isl_ast output looks like this:
15 //
16 // for (c2 = max(0, ceild(n + m, 2); c2 <= min(511, floord(5 * n, 3)); c2++) {
17 //   bb2(c2);
18 // }
19 //
20 //===----------------------------------------------------------------------===//
21 
22 #include "polly/CodeGen/IslAst.h"
23 
24 #include "polly/LinkAllPasses.h"
25 #include "polly/ScopInfo.h"
26 
27 #define DEBUG_TYPE "polly-ast"
28 #include "llvm/Support/CommandLine.h"
29 #include "llvm/Support/Debug.h"
30 
31 #include "isl/union_map.h"
32 #include "isl/list.h"
33 #include "isl/ast.h"
34 #include "isl/ast_build.h"
35 #include "isl/set.h"
36 #include "isl/map.h"
37 #include "isl/aff.h"
38 
39 using namespace llvm;
40 using namespace polly;
41 
42 static cl::opt<bool>
43 UseContext("polly-ast-use-context", cl::desc("Use context"), cl::Hidden,
44            cl::init(false), cl::ZeroOrMore);
45 
46 namespace polly {
47 class IslAst {
48 public:
49   IslAst(Scop *Scop);
50 
51   ~IslAst();
52 
53   /// Print a source code representation of the program.
54   void pprint(llvm::raw_ostream &OS);
55 
56   __isl_give isl_ast_node *getAst();
57 
58 private:
59   Scop *S;
60   isl_ast_node *Root;
61 
62   __isl_give isl_union_map *getSchedule();
63 };
64 } // End namespace polly.
65 
66 
67 static void IslAstUserFree(void *User)
68 {
69   struct IslAstUser *UserStruct = (struct IslAstUser *) User;
70   isl_ast_build_free(UserStruct->Context);
71   isl_pw_multi_aff_free(UserStruct->PMA);
72   free(UserStruct);
73 }
74 
75 static __isl_give isl_ast_node *AtEachDomain(__isl_keep isl_ast_node *Node,
76        __isl_keep isl_ast_build *Context, void *User)
77 {
78   isl_map *Map;
79   struct IslAstUser *UserStruct;
80 
81   UserStruct = (struct IslAstUser *) malloc(sizeof(struct IslAstUser));
82 
83   Map = isl_map_from_union_map(isl_ast_build_get_schedule(Context));
84   UserStruct->PMA = isl_pw_multi_aff_from_map(isl_map_reverse(Map));
85   UserStruct->Context = isl_ast_build_copy(Context);
86 
87   isl_id *Annotation = isl_id_alloc(isl_ast_node_get_ctx(Node), NULL,
88                                     UserStruct);
89   Annotation = isl_id_set_free_user(Annotation, &IslAstUserFree);
90   return isl_ast_node_set_annotation(Node, Annotation);
91 }
92 
93 IslAst::IslAst(Scop *Scop) : S(Scop) {
94   isl_ctx *Ctx = S->getIslCtx();
95   isl_options_set_ast_build_atomic_upper_bound(Ctx, true);
96   isl_ast_build *Context;
97 
98   if (UseContext)
99     Context = isl_ast_build_from_context(S->getContext());
100   else
101     Context = isl_ast_build_from_context(isl_set_universe(S->getParamSpace()));
102 
103   Context = isl_ast_build_set_at_each_domain(Context, AtEachDomain, NULL);
104 
105   isl_union_map *Schedule = getSchedule();
106 
107   Function *F = Scop->getRegion().getEntry()->getParent();
108 
109   DEBUG(dbgs() << ":: isl ast :: " << F->getName()
110                << " :: " << Scop->getRegion().getNameStr() << "\n");;
111   DEBUG(dbgs() << S->getContextStr() << "\n";
112     isl_union_map_dump(Schedule);
113   );
114 
115   Root = isl_ast_build_ast_from_schedule(Context, Schedule);
116 
117   isl_ast_build_free(Context);
118 
119   DEBUG(pprint(dbgs()));
120 }
121 
122 __isl_give isl_union_map *IslAst::getSchedule() {
123   isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace());
124 
125   for (Scop::iterator SI = S->begin(), SE = S->end(); SI != SE; ++SI) {
126     ScopStmt *Stmt = *SI;
127     isl_map *StmtSchedule = Stmt->getScattering();
128 
129     StmtSchedule = isl_map_intersect_domain(StmtSchedule, Stmt->getDomain());
130     Schedule = isl_union_map_union(Schedule,
131                                    isl_union_map_from_map(StmtSchedule));
132   }
133 
134   return Schedule;
135 }
136 
137 IslAst::~IslAst() {
138   isl_ast_node_free(Root);
139 }
140 
141 /// Print a C like representation of the program.
142 void IslAst::pprint(llvm::raw_ostream &OS) {
143   isl_ast_node *Root;
144   isl_ast_print_options *Options = isl_ast_print_options_alloc(S->getIslCtx());
145   isl_printer *P = isl_printer_to_str(S->getIslCtx());
146   P = isl_printer_set_output_format(P, ISL_FORMAT_C);
147   Root = getAst();
148   P = isl_ast_node_print(Root, P, Options);
149   char *result = isl_printer_get_str(P);
150   OS << result << "\n";
151   isl_printer_free(P);
152   isl_ast_node_free(Root);
153   isl_ast_print_options_free(Options);
154 }
155 
156 /// Create the isl_ast from this program.
157 __isl_give isl_ast_node *IslAst::getAst() {
158   return isl_ast_node_copy(Root);
159 }
160 
161 void IslAstInfo::pprint(llvm::raw_ostream &OS) {
162   Ast->pprint(OS);
163 }
164 
165 void IslAstInfo::releaseMemory() {
166   if (Ast) {
167     delete Ast;
168     Ast = 0;
169   }
170 }
171 
172 bool IslAstInfo::runOnScop(Scop &Scop) {
173   if (Ast)
174     delete Ast;
175 
176   S = &Scop;
177 
178   Ast = new IslAst(&Scop);
179 
180   return false;
181 }
182 
183 __isl_give isl_ast_node *IslAstInfo::getAst() {
184   return Ast->getAst();
185 }
186 
187 void IslAstInfo::printScop(raw_ostream &OS) const {
188   Function *F = S->getRegion().getEntry()->getParent();
189 
190   OS << "isl ast for function '" << F->getName() << "':\n";
191 
192   Ast->pprint(OS);
193 }
194 
195 void IslAstInfo::getAnalysisUsage(AnalysisUsage &AU) const {
196   // Get the Common analysis usage of ScopPasses.
197   ScopPass::getAnalysisUsage(AU);
198   AU.addRequired<ScopInfo>();
199 }
200 char IslAstInfo::ID = 0;
201 
202 INITIALIZE_PASS_BEGIN(IslAstInfo, "polly-ast",
203                       "Generate an AST of the SCoP (isl)", false, false)
204 INITIALIZE_PASS_DEPENDENCY(ScopInfo)
205 INITIALIZE_PASS_END(IslAstInfo, "polly-ast",
206                     "Generate an AST from the SCoP (isl)", false, false)
207 
208 Pass *polly::createIslAstInfoPass() {
209   return new IslAstInfo();
210 }
211