1*e4b17023SJohn Marino /* Gimple Represented as Polyhedra.
2*e4b17023SJohn Marino Copyright (C) 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
3*e4b17023SJohn Marino Contributed by Sebastian Pop <sebastian.pop@inria.fr>.
4*e4b17023SJohn Marino
5*e4b17023SJohn Marino This file is part of GCC.
6*e4b17023SJohn Marino
7*e4b17023SJohn Marino GCC is free software; you can redistribute it and/or modify
8*e4b17023SJohn Marino it under the terms of the GNU General Public License as published by
9*e4b17023SJohn Marino the Free Software Foundation; either version 3, or (at your option)
10*e4b17023SJohn Marino any later version.
11*e4b17023SJohn Marino
12*e4b17023SJohn Marino GCC is distributed in the hope that it will be useful,
13*e4b17023SJohn Marino but WITHOUT ANY WARRANTY; without even the implied warranty of
14*e4b17023SJohn Marino MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15*e4b17023SJohn Marino GNU General Public License for more details.
16*e4b17023SJohn Marino
17*e4b17023SJohn Marino You should have received a copy of the GNU General Public License
18*e4b17023SJohn Marino along with GCC; see the file COPYING3. If not see
19*e4b17023SJohn Marino <http://www.gnu.org/licenses/>. */
20*e4b17023SJohn Marino
21*e4b17023SJohn Marino /* This pass converts GIMPLE to GRAPHITE, performs some loop
22*e4b17023SJohn Marino transformations and then converts the resulting representation back
23*e4b17023SJohn Marino to GIMPLE.
24*e4b17023SJohn Marino
25*e4b17023SJohn Marino An early description of this pass can be found in the GCC Summit'06
26*e4b17023SJohn Marino paper "GRAPHITE: Polyhedral Analyses and Optimizations for GCC".
27*e4b17023SJohn Marino The wiki page http://gcc.gnu.org/wiki/Graphite contains pointers to
28*e4b17023SJohn Marino the related work.
29*e4b17023SJohn Marino
30*e4b17023SJohn Marino One important document to read is CLooG's internal manual:
31*e4b17023SJohn Marino http://repo.or.cz/w/cloog-ppl.git?a=blob_plain;f=doc/cloog.texi;hb=HEAD
32*e4b17023SJohn Marino that describes the data structure of loops used in this file, and
33*e4b17023SJohn Marino the functions that are used for transforming the code. */
34*e4b17023SJohn Marino
35*e4b17023SJohn Marino #include "config.h"
36*e4b17023SJohn Marino #include "system.h"
37*e4b17023SJohn Marino #include "coretypes.h"
38*e4b17023SJohn Marino #include "diagnostic-core.h"
39*e4b17023SJohn Marino #include "tree-flow.h"
40*e4b17023SJohn Marino #include "tree-dump.h"
41*e4b17023SJohn Marino #include "cfgloop.h"
42*e4b17023SJohn Marino #include "tree-chrec.h"
43*e4b17023SJohn Marino #include "tree-data-ref.h"
44*e4b17023SJohn Marino #include "tree-scalar-evolution.h"
45*e4b17023SJohn Marino #include "sese.h"
46*e4b17023SJohn Marino #include "dbgcnt.h"
47*e4b17023SJohn Marino
48*e4b17023SJohn Marino #ifdef HAVE_cloog
49*e4b17023SJohn Marino
50*e4b17023SJohn Marino #include "ppl_c.h"
51*e4b17023SJohn Marino #include "graphite-ppl.h"
52*e4b17023SJohn Marino #include "graphite-poly.h"
53*e4b17023SJohn Marino #include "graphite-scop-detection.h"
54*e4b17023SJohn Marino #include "graphite-clast-to-gimple.h"
55*e4b17023SJohn Marino #include "graphite-sese-to-poly.h"
56*e4b17023SJohn Marino
57*e4b17023SJohn Marino CloogState *cloog_state;
58*e4b17023SJohn Marino
59*e4b17023SJohn Marino /* Print global statistics to FILE. */
60*e4b17023SJohn Marino
61*e4b17023SJohn Marino static void
print_global_statistics(FILE * file)62*e4b17023SJohn Marino print_global_statistics (FILE* file)
63*e4b17023SJohn Marino {
64*e4b17023SJohn Marino long n_bbs = 0;
65*e4b17023SJohn Marino long n_loops = 0;
66*e4b17023SJohn Marino long n_stmts = 0;
67*e4b17023SJohn Marino long n_conditions = 0;
68*e4b17023SJohn Marino long n_p_bbs = 0;
69*e4b17023SJohn Marino long n_p_loops = 0;
70*e4b17023SJohn Marino long n_p_stmts = 0;
71*e4b17023SJohn Marino long n_p_conditions = 0;
72*e4b17023SJohn Marino
73*e4b17023SJohn Marino basic_block bb;
74*e4b17023SJohn Marino
75*e4b17023SJohn Marino FOR_ALL_BB (bb)
76*e4b17023SJohn Marino {
77*e4b17023SJohn Marino gimple_stmt_iterator psi;
78*e4b17023SJohn Marino
79*e4b17023SJohn Marino n_bbs++;
80*e4b17023SJohn Marino n_p_bbs += bb->count;
81*e4b17023SJohn Marino
82*e4b17023SJohn Marino /* Ignore artificial surrounding loop. */
83*e4b17023SJohn Marino if (bb == bb->loop_father->header
84*e4b17023SJohn Marino && bb->index != 0)
85*e4b17023SJohn Marino {
86*e4b17023SJohn Marino n_loops++;
87*e4b17023SJohn Marino n_p_loops += bb->count;
88*e4b17023SJohn Marino }
89*e4b17023SJohn Marino
90*e4b17023SJohn Marino if (VEC_length (edge, bb->succs) > 1)
91*e4b17023SJohn Marino {
92*e4b17023SJohn Marino n_conditions++;
93*e4b17023SJohn Marino n_p_conditions += bb->count;
94*e4b17023SJohn Marino }
95*e4b17023SJohn Marino
96*e4b17023SJohn Marino for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
97*e4b17023SJohn Marino {
98*e4b17023SJohn Marino n_stmts++;
99*e4b17023SJohn Marino n_p_stmts += bb->count;
100*e4b17023SJohn Marino }
101*e4b17023SJohn Marino }
102*e4b17023SJohn Marino
103*e4b17023SJohn Marino fprintf (file, "\nGlobal statistics (");
104*e4b17023SJohn Marino fprintf (file, "BBS:%ld, ", n_bbs);
105*e4b17023SJohn Marino fprintf (file, "LOOPS:%ld, ", n_loops);
106*e4b17023SJohn Marino fprintf (file, "CONDITIONS:%ld, ", n_conditions);
107*e4b17023SJohn Marino fprintf (file, "STMTS:%ld)\n", n_stmts);
108*e4b17023SJohn Marino fprintf (file, "\nGlobal profiling statistics (");
109*e4b17023SJohn Marino fprintf (file, "BBS:%ld, ", n_p_bbs);
110*e4b17023SJohn Marino fprintf (file, "LOOPS:%ld, ", n_p_loops);
111*e4b17023SJohn Marino fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
112*e4b17023SJohn Marino fprintf (file, "STMTS:%ld)\n", n_p_stmts);
113*e4b17023SJohn Marino }
114*e4b17023SJohn Marino
115*e4b17023SJohn Marino /* Print statistics for SCOP to FILE. */
116*e4b17023SJohn Marino
117*e4b17023SJohn Marino static void
print_graphite_scop_statistics(FILE * file,scop_p scop)118*e4b17023SJohn Marino print_graphite_scop_statistics (FILE* file, scop_p scop)
119*e4b17023SJohn Marino {
120*e4b17023SJohn Marino long n_bbs = 0;
121*e4b17023SJohn Marino long n_loops = 0;
122*e4b17023SJohn Marino long n_stmts = 0;
123*e4b17023SJohn Marino long n_conditions = 0;
124*e4b17023SJohn Marino long n_p_bbs = 0;
125*e4b17023SJohn Marino long n_p_loops = 0;
126*e4b17023SJohn Marino long n_p_stmts = 0;
127*e4b17023SJohn Marino long n_p_conditions = 0;
128*e4b17023SJohn Marino
129*e4b17023SJohn Marino basic_block bb;
130*e4b17023SJohn Marino
131*e4b17023SJohn Marino FOR_ALL_BB (bb)
132*e4b17023SJohn Marino {
133*e4b17023SJohn Marino gimple_stmt_iterator psi;
134*e4b17023SJohn Marino loop_p loop = bb->loop_father;
135*e4b17023SJohn Marino
136*e4b17023SJohn Marino if (!bb_in_sese_p (bb, SCOP_REGION (scop)))
137*e4b17023SJohn Marino continue;
138*e4b17023SJohn Marino
139*e4b17023SJohn Marino n_bbs++;
140*e4b17023SJohn Marino n_p_bbs += bb->count;
141*e4b17023SJohn Marino
142*e4b17023SJohn Marino if (VEC_length (edge, bb->succs) > 1)
143*e4b17023SJohn Marino {
144*e4b17023SJohn Marino n_conditions++;
145*e4b17023SJohn Marino n_p_conditions += bb->count;
146*e4b17023SJohn Marino }
147*e4b17023SJohn Marino
148*e4b17023SJohn Marino for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi))
149*e4b17023SJohn Marino {
150*e4b17023SJohn Marino n_stmts++;
151*e4b17023SJohn Marino n_p_stmts += bb->count;
152*e4b17023SJohn Marino }
153*e4b17023SJohn Marino
154*e4b17023SJohn Marino if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop)))
155*e4b17023SJohn Marino {
156*e4b17023SJohn Marino n_loops++;
157*e4b17023SJohn Marino n_p_loops += bb->count;
158*e4b17023SJohn Marino }
159*e4b17023SJohn Marino }
160*e4b17023SJohn Marino
161*e4b17023SJohn Marino fprintf (file, "\nSCoP statistics (");
162*e4b17023SJohn Marino fprintf (file, "BBS:%ld, ", n_bbs);
163*e4b17023SJohn Marino fprintf (file, "LOOPS:%ld, ", n_loops);
164*e4b17023SJohn Marino fprintf (file, "CONDITIONS:%ld, ", n_conditions);
165*e4b17023SJohn Marino fprintf (file, "STMTS:%ld)\n", n_stmts);
166*e4b17023SJohn Marino fprintf (file, "\nSCoP profiling statistics (");
167*e4b17023SJohn Marino fprintf (file, "BBS:%ld, ", n_p_bbs);
168*e4b17023SJohn Marino fprintf (file, "LOOPS:%ld, ", n_p_loops);
169*e4b17023SJohn Marino fprintf (file, "CONDITIONS:%ld, ", n_p_conditions);
170*e4b17023SJohn Marino fprintf (file, "STMTS:%ld)\n", n_p_stmts);
171*e4b17023SJohn Marino }
172*e4b17023SJohn Marino
173*e4b17023SJohn Marino /* Print statistics for SCOPS to FILE. */
174*e4b17023SJohn Marino
175*e4b17023SJohn Marino static void
print_graphite_statistics(FILE * file,VEC (scop_p,heap)* scops)176*e4b17023SJohn Marino print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops)
177*e4b17023SJohn Marino {
178*e4b17023SJohn Marino int i;
179*e4b17023SJohn Marino
180*e4b17023SJohn Marino scop_p scop;
181*e4b17023SJohn Marino
182*e4b17023SJohn Marino FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
183*e4b17023SJohn Marino print_graphite_scop_statistics (file, scop);
184*e4b17023SJohn Marino }
185*e4b17023SJohn Marino
186*e4b17023SJohn Marino /* Initialize graphite: when there are no loops returns false. */
187*e4b17023SJohn Marino
188*e4b17023SJohn Marino static bool
graphite_initialize(void)189*e4b17023SJohn Marino graphite_initialize (void)
190*e4b17023SJohn Marino {
191*e4b17023SJohn Marino int ppl_initialized;
192*e4b17023SJohn Marino
193*e4b17023SJohn Marino if (number_of_loops () <= 1
194*e4b17023SJohn Marino /* FIXME: This limit on the number of basic blocks of a function
195*e4b17023SJohn Marino should be removed when the SCOP detection is faster. */
196*e4b17023SJohn Marino || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION))
197*e4b17023SJohn Marino {
198*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
199*e4b17023SJohn Marino print_global_statistics (dump_file);
200*e4b17023SJohn Marino
201*e4b17023SJohn Marino return false;
202*e4b17023SJohn Marino }
203*e4b17023SJohn Marino
204*e4b17023SJohn Marino scev_reset ();
205*e4b17023SJohn Marino recompute_all_dominators ();
206*e4b17023SJohn Marino initialize_original_copy_tables ();
207*e4b17023SJohn Marino
208*e4b17023SJohn Marino ppl_initialized = ppl_initialize ();
209*e4b17023SJohn Marino gcc_assert (ppl_initialized == 0);
210*e4b17023SJohn Marino
211*e4b17023SJohn Marino cloog_state = cloog_state_malloc ();
212*e4b17023SJohn Marino cloog_initialize ();
213*e4b17023SJohn Marino
214*e4b17023SJohn Marino if (dump_file && dump_flags)
215*e4b17023SJohn Marino dump_function_to_file (current_function_decl, dump_file, dump_flags);
216*e4b17023SJohn Marino
217*e4b17023SJohn Marino return true;
218*e4b17023SJohn Marino }
219*e4b17023SJohn Marino
220*e4b17023SJohn Marino /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is
221*e4b17023SJohn Marino true. */
222*e4b17023SJohn Marino
223*e4b17023SJohn Marino static void
graphite_finalize(bool need_cfg_cleanup_p)224*e4b17023SJohn Marino graphite_finalize (bool need_cfg_cleanup_p)
225*e4b17023SJohn Marino {
226*e4b17023SJohn Marino if (need_cfg_cleanup_p)
227*e4b17023SJohn Marino {
228*e4b17023SJohn Marino scev_reset ();
229*e4b17023SJohn Marino cleanup_tree_cfg ();
230*e4b17023SJohn Marino profile_status = PROFILE_ABSENT;
231*e4b17023SJohn Marino release_recorded_exits ();
232*e4b17023SJohn Marino tree_estimate_probability ();
233*e4b17023SJohn Marino }
234*e4b17023SJohn Marino
235*e4b17023SJohn Marino cloog_state_free (cloog_state);
236*e4b17023SJohn Marino cloog_finalize ();
237*e4b17023SJohn Marino ppl_finalize ();
238*e4b17023SJohn Marino free_original_copy_tables ();
239*e4b17023SJohn Marino
240*e4b17023SJohn Marino if (dump_file && dump_flags)
241*e4b17023SJohn Marino print_loops (dump_file, 3);
242*e4b17023SJohn Marino }
243*e4b17023SJohn Marino
244*e4b17023SJohn Marino /* Perform a set of linear transforms on the loops of the current
245*e4b17023SJohn Marino function. */
246*e4b17023SJohn Marino
247*e4b17023SJohn Marino void
graphite_transform_loops(void)248*e4b17023SJohn Marino graphite_transform_loops (void)
249*e4b17023SJohn Marino {
250*e4b17023SJohn Marino int i;
251*e4b17023SJohn Marino scop_p scop;
252*e4b17023SJohn Marino bool need_cfg_cleanup_p = false;
253*e4b17023SJohn Marino VEC (scop_p, heap) *scops = NULL;
254*e4b17023SJohn Marino htab_t bb_pbb_mapping;
255*e4b17023SJohn Marino
256*e4b17023SJohn Marino if (!graphite_initialize ())
257*e4b17023SJohn Marino return;
258*e4b17023SJohn Marino
259*e4b17023SJohn Marino build_scops (&scops);
260*e4b17023SJohn Marino
261*e4b17023SJohn Marino if (dump_file && (dump_flags & TDF_DETAILS))
262*e4b17023SJohn Marino {
263*e4b17023SJohn Marino print_graphite_statistics (dump_file, scops);
264*e4b17023SJohn Marino print_global_statistics (dump_file);
265*e4b17023SJohn Marino }
266*e4b17023SJohn Marino
267*e4b17023SJohn Marino bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free);
268*e4b17023SJohn Marino
269*e4b17023SJohn Marino FOR_EACH_VEC_ELT (scop_p, scops, i, scop)
270*e4b17023SJohn Marino if (dbg_cnt (graphite_scop))
271*e4b17023SJohn Marino {
272*e4b17023SJohn Marino build_poly_scop (scop);
273*e4b17023SJohn Marino
274*e4b17023SJohn Marino if (POLY_SCOP_P (scop)
275*e4b17023SJohn Marino && apply_poly_transforms (scop)
276*e4b17023SJohn Marino && gloog (scop, bb_pbb_mapping))
277*e4b17023SJohn Marino need_cfg_cleanup_p = true;
278*e4b17023SJohn Marino }
279*e4b17023SJohn Marino
280*e4b17023SJohn Marino htab_delete (bb_pbb_mapping);
281*e4b17023SJohn Marino free_scops (scops);
282*e4b17023SJohn Marino graphite_finalize (need_cfg_cleanup_p);
283*e4b17023SJohn Marino }
284*e4b17023SJohn Marino
285*e4b17023SJohn Marino #else /* If Cloog is not available: #ifndef HAVE_cloog. */
286*e4b17023SJohn Marino
287*e4b17023SJohn Marino void
graphite_transform_loops(void)288*e4b17023SJohn Marino graphite_transform_loops (void)
289*e4b17023SJohn Marino {
290*e4b17023SJohn Marino sorry ("Graphite loop optimizations cannot be used");
291*e4b17023SJohn Marino }
292*e4b17023SJohn Marino
293*e4b17023SJohn Marino #endif
294