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 "tm.h" 39 #include "ggc.h" 40 #include "tree.h" 41 #include "rtl.h" 42 #include "basic-block.h" 43 #include "diagnostic.h" 44 #include "tree-flow.h" 45 #include "toplev.h" 46 #include "tree-dump.h" 47 #include "timevar.h" 48 #include "cfgloop.h" 49 #include "tree-chrec.h" 50 #include "tree-data-ref.h" 51 #include "tree-scalar-evolution.h" 52 #include "tree-pass.h" 53 #include "value-prof.h" 54 #include "pointer-set.h" 55 #include "gimple.h" 56 #include "sese.h" 57 #include "predict.h" 58 59 #ifdef HAVE_cloog 60 61 #include "cloog/cloog.h" 62 #include "ppl_c.h" 63 #include "graphite-ppl.h" 64 #include "graphite.h" 65 #include "graphite-poly.h" 66 #include "graphite-scop-detection.h" 67 #include "graphite-clast-to-gimple.h" 68 #include "graphite-sese-to-poly.h" 69 70 /* Print global statistics to FILE. */ 71 72 static void 73 print_global_statistics (FILE* file) 74 { 75 long n_bbs = 0; 76 long n_loops = 0; 77 long n_stmts = 0; 78 long n_conditions = 0; 79 long n_p_bbs = 0; 80 long n_p_loops = 0; 81 long n_p_stmts = 0; 82 long n_p_conditions = 0; 83 84 basic_block bb; 85 86 FOR_ALL_BB (bb) 87 { 88 gimple_stmt_iterator psi; 89 90 n_bbs++; 91 n_p_bbs += bb->count; 92 93 /* Ignore artificial surrounding loop. */ 94 if (bb == bb->loop_father->header 95 && bb->index != 0) 96 { 97 n_loops++; 98 n_p_loops += bb->count; 99 } 100 101 if (VEC_length (edge, bb->succs) > 1) 102 { 103 n_conditions++; 104 n_p_conditions += bb->count; 105 } 106 107 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 108 { 109 n_stmts++; 110 n_p_stmts += bb->count; 111 } 112 } 113 114 fprintf (file, "\nGlobal statistics ("); 115 fprintf (file, "BBS:%ld, ", n_bbs); 116 fprintf (file, "LOOPS:%ld, ", n_loops); 117 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 118 fprintf (file, "STMTS:%ld)\n", n_stmts); 119 fprintf (file, "\nGlobal profiling statistics ("); 120 fprintf (file, "BBS:%ld, ", n_p_bbs); 121 fprintf (file, "LOOPS:%ld, ", n_p_loops); 122 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 123 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 124 } 125 126 /* Print statistics for SCOP to FILE. */ 127 128 static void 129 print_graphite_scop_statistics (FILE* file, scop_p scop) 130 { 131 long n_bbs = 0; 132 long n_loops = 0; 133 long n_stmts = 0; 134 long n_conditions = 0; 135 long n_p_bbs = 0; 136 long n_p_loops = 0; 137 long n_p_stmts = 0; 138 long n_p_conditions = 0; 139 140 basic_block bb; 141 142 FOR_ALL_BB (bb) 143 { 144 gimple_stmt_iterator psi; 145 loop_p loop = bb->loop_father; 146 147 if (!bb_in_sese_p (bb, SCOP_REGION (scop))) 148 continue; 149 150 n_bbs++; 151 n_p_bbs += bb->count; 152 153 if (VEC_length (edge, bb->succs) > 1) 154 { 155 n_conditions++; 156 n_p_conditions += bb->count; 157 } 158 159 for (psi = gsi_start_bb (bb); !gsi_end_p (psi); gsi_next (&psi)) 160 { 161 n_stmts++; 162 n_p_stmts += bb->count; 163 } 164 165 if (loop->header == bb && loop_in_sese_p (loop, SCOP_REGION (scop))) 166 { 167 n_loops++; 168 n_p_loops += bb->count; 169 } 170 } 171 172 fprintf (file, "\nSCoP statistics ("); 173 fprintf (file, "BBS:%ld, ", n_bbs); 174 fprintf (file, "LOOPS:%ld, ", n_loops); 175 fprintf (file, "CONDITIONS:%ld, ", n_conditions); 176 fprintf (file, "STMTS:%ld)\n", n_stmts); 177 fprintf (file, "\nSCoP profiling statistics ("); 178 fprintf (file, "BBS:%ld, ", n_p_bbs); 179 fprintf (file, "LOOPS:%ld, ", n_p_loops); 180 fprintf (file, "CONDITIONS:%ld, ", n_p_conditions); 181 fprintf (file, "STMTS:%ld)\n", n_p_stmts); 182 } 183 184 /* Print statistics for SCOPS to FILE. */ 185 186 static void 187 print_graphite_statistics (FILE* file, VEC (scop_p, heap) *scops) 188 { 189 int i; 190 191 scop_p scop; 192 193 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) 194 print_graphite_scop_statistics (file, scop); 195 } 196 197 /* Initialize graphite: when there are no loops returns false. */ 198 199 static bool 200 graphite_initialize (void) 201 { 202 if (number_of_loops () <= 1 203 /* FIXME: This limit on the number of basic blocks of a function 204 should be removed when the SCOP detection is faster. */ 205 || n_basic_blocks > PARAM_VALUE (PARAM_GRAPHITE_MAX_BBS_PER_FUNCTION)) 206 { 207 if (dump_file && (dump_flags & TDF_DETAILS)) 208 print_global_statistics (dump_file); 209 210 return false; 211 } 212 213 scev_reset (); 214 recompute_all_dominators (); 215 initialize_original_copy_tables (); 216 cloog_initialize (); 217 218 if (dump_file && dump_flags) 219 dump_function_to_file (current_function_decl, dump_file, dump_flags); 220 221 return true; 222 } 223 224 /* Finalize graphite: perform CFG cleanup when NEED_CFG_CLEANUP_P is 225 true. */ 226 227 static void 228 graphite_finalize (bool need_cfg_cleanup_p) 229 { 230 if (need_cfg_cleanup_p) 231 { 232 scev_reset (); 233 cleanup_tree_cfg (); 234 profile_status = PROFILE_ABSENT; 235 release_recorded_exits (); 236 tree_estimate_probability (); 237 } 238 239 cloog_finalize (); 240 free_original_copy_tables (); 241 242 if (dump_file && dump_flags) 243 print_loops (dump_file, 3); 244 } 245 246 /* Perform a set of linear transforms on the loops of the current 247 function. */ 248 249 void 250 graphite_transform_loops (void) 251 { 252 int i; 253 scop_p scop; 254 bool need_cfg_cleanup_p = false; 255 VEC (scop_p, heap) *scops = NULL; 256 htab_t bb_pbb_mapping; 257 258 if (!graphite_initialize ()) 259 return; 260 261 build_scops (&scops); 262 263 if (dump_file && (dump_flags & TDF_DETAILS)) 264 { 265 print_graphite_statistics (dump_file, scops); 266 print_global_statistics (dump_file); 267 } 268 269 bb_pbb_mapping = htab_create (10, bb_pbb_map_hash, eq_bb_pbb_map, free); 270 271 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) 272 build_poly_scop (scop); 273 274 for (i = 0; VEC_iterate (scop_p, scops, i, scop); i++) 275 if (POLY_SCOP_P (scop) 276 && apply_poly_transforms (scop) 277 && gloog (scop, scops, bb_pbb_mapping)) 278 need_cfg_cleanup_p = true; 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