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