Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-loop-distribution.c @ 59:5b5b9ea5b220
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 15 Feb 2010 17:22:24 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Loop distribution. |
| 2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc. | |
| 3 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr> | |
| 4 and Sebastian Pop <sebastian.pop@amd.com>. | |
| 5 | |
| 6 This file is part of GCC. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
7 |
| 0 | 8 GCC is free software; you can redistribute it and/or modify it |
| 9 under the terms of the GNU General Public License as published by the | |
| 10 Free Software Foundation; either version 3, or (at your option) any | |
| 11 later version. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
12 |
| 0 | 13 GCC is distributed in the hope that it will be useful, but WITHOUT |
| 14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 16 for more details. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
17 |
| 0 | 18 You should have received a copy of the GNU General Public License |
| 19 along with GCC; see the file COPYING3. If not see | |
| 20 <http://www.gnu.org/licenses/>. */ | |
| 21 | |
| 22 /* This pass performs loop distribution: for example, the loop | |
| 23 | |
| 24 |DO I = 2, N | |
| 25 | A(I) = B(I) + C | |
| 26 | D(I) = A(I-1)*E | |
| 27 |ENDDO | |
| 28 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
29 is transformed to |
| 0 | 30 |
| 31 |DOALL I = 2, N | |
| 32 | A(I) = B(I) + C | |
| 33 |ENDDO | |
| 34 | | |
| 35 |DOALL I = 2, N | |
| 36 | D(I) = A(I-1)*E | |
| 37 |ENDDO | |
| 38 | |
| 39 This pass uses an RDG, Reduced Dependence Graph built on top of the | |
| 40 data dependence relations. The RDG is then topologically sorted to | |
| 41 obtain a map of information producers/consumers based on which it | |
| 42 generates the new loops. */ | |
| 43 | |
| 44 #include "config.h" | |
| 45 #include "system.h" | |
| 46 #include "coretypes.h" | |
| 47 #include "tm.h" | |
| 48 #include "ggc.h" | |
| 49 #include "tree.h" | |
| 50 #include "target.h" | |
| 51 | |
| 52 #include "rtl.h" | |
| 53 #include "basic-block.h" | |
| 54 #include "diagnostic.h" | |
| 55 #include "tree-flow.h" | |
| 56 #include "tree-dump.h" | |
| 57 #include "timevar.h" | |
| 58 #include "cfgloop.h" | |
| 59 #include "expr.h" | |
| 60 #include "optabs.h" | |
| 61 #include "tree-chrec.h" | |
| 62 #include "tree-data-ref.h" | |
| 63 #include "tree-scalar-evolution.h" | |
| 64 #include "tree-pass.h" | |
| 65 #include "lambda.h" | |
| 66 #include "langhooks.h" | |
| 67 #include "tree-vectorizer.h" | |
| 68 | |
| 69 /* If bit I is not set, it means that this node represents an | |
| 70 operation that has already been performed, and that should not be | |
| 71 performed again. This is the subgraph of remaining important | |
| 72 computations that is passed to the DFS algorithm for avoiding to | |
| 73 include several times the same stores in different loops. */ | |
| 74 static bitmap remaining_stmts; | |
| 75 | |
| 76 /* A node of the RDG is marked in this bitmap when it has as a | |
| 77 predecessor a node that writes to memory. */ | |
| 78 static bitmap upstream_mem_writes; | |
| 79 | |
| 80 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of | |
| 81 ORIG_LOOP. */ | |
| 82 | |
| 83 static void | |
| 84 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop) | |
| 85 { | |
| 86 tree new_ssa_name; | |
| 87 gimple_stmt_iterator si_new, si_orig; | |
| 88 edge orig_loop_latch = loop_latch_edge (orig_loop); | |
| 89 edge orig_entry_e = loop_preheader_edge (orig_loop); | |
| 90 edge new_loop_entry_e = loop_preheader_edge (new_loop); | |
| 91 | |
| 92 /* Scan the phis in the headers of the old and new loops | |
| 93 (they are organized in exactly the same order). */ | |
| 94 for (si_new = gsi_start_phis (new_loop->header), | |
| 95 si_orig = gsi_start_phis (orig_loop->header); | |
| 96 !gsi_end_p (si_new) && !gsi_end_p (si_orig); | |
| 97 gsi_next (&si_new), gsi_next (&si_orig)) | |
| 98 { | |
| 99 tree def; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
100 source_location locus; |
| 0 | 101 gimple phi_new = gsi_stmt (si_new); |
| 102 gimple phi_orig = gsi_stmt (si_orig); | |
| 103 | |
| 104 /* Add the first phi argument for the phi in NEW_LOOP (the one | |
| 105 associated with the entry of NEW_LOOP) */ | |
| 106 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
107 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
108 add_phi_arg (phi_new, def, new_loop_entry_e, locus); |
| 0 | 109 |
| 110 /* Add the second phi argument for the phi in NEW_LOOP (the one | |
| 111 associated with the latch of NEW_LOOP) */ | |
| 112 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
113 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch); |
| 0 | 114 |
| 115 if (TREE_CODE (def) == SSA_NAME) | |
| 116 { | |
| 117 new_ssa_name = get_current_def (def); | |
| 118 | |
| 119 if (!new_ssa_name) | |
| 120 /* This only happens if there are no definitions inside the | |
| 121 loop. Use the phi_result in this case. */ | |
| 122 new_ssa_name = PHI_RESULT (phi_new); | |
| 123 } | |
| 124 else | |
| 125 /* Could be an integer. */ | |
| 126 new_ssa_name = def; | |
| 127 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
128 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus); |
| 0 | 129 } |
| 130 } | |
| 131 | |
| 132 /* Return a copy of LOOP placed before LOOP. */ | |
| 133 | |
| 134 static struct loop * | |
| 135 copy_loop_before (struct loop *loop) | |
| 136 { | |
| 137 struct loop *res; | |
| 138 edge preheader = loop_preheader_edge (loop); | |
| 139 | |
| 140 if (!single_exit (loop)) | |
| 141 return NULL; | |
| 142 | |
| 143 initialize_original_copy_tables (); | |
| 144 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader); | |
| 145 free_original_copy_tables (); | |
| 146 | |
| 147 if (!res) | |
| 148 return NULL; | |
| 149 | |
| 150 update_phis_for_loop_copy (loop, res); | |
| 151 rename_variables_in_loop (res); | |
| 152 | |
| 153 return res; | |
| 154 } | |
| 155 | |
| 156 /* Creates an empty basic block after LOOP. */ | |
| 157 | |
| 158 static void | |
| 159 create_bb_after_loop (struct loop *loop) | |
| 160 { | |
| 161 edge exit = single_exit (loop); | |
| 162 | |
| 163 if (!exit) | |
| 164 return; | |
| 165 | |
| 166 split_edge (exit); | |
| 167 } | |
| 168 | |
| 169 /* Generate code for PARTITION from the code in LOOP. The loop is | |
| 170 copied when COPY_P is true. All the statements not flagged in the | |
| 171 PARTITION bitmap are removed from the loop or from its copy. The | |
| 172 statements are indexed in sequence inside a basic block, and the | |
| 173 basic blocks of a loop are taken in dom order. Returns true when | |
| 174 the code gen succeeded. */ | |
| 175 | |
| 176 static bool | |
| 177 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p) | |
| 178 { | |
| 179 unsigned i, x; | |
| 180 gimple_stmt_iterator bsi; | |
| 181 basic_block *bbs; | |
| 182 | |
| 183 if (copy_p) | |
| 184 { | |
| 185 loop = copy_loop_before (loop); | |
| 186 create_preheader (loop, CP_SIMPLE_PREHEADERS); | |
| 187 create_bb_after_loop (loop); | |
| 188 } | |
| 189 | |
| 190 if (loop == NULL) | |
| 191 return false; | |
| 192 | |
| 193 /* Remove stmts not in the PARTITION bitmap. The order in which we | |
| 194 visit the phi nodes and the statements is exactly as in | |
| 195 stmts_from_loop. */ | |
| 196 bbs = get_loop_body_in_dom_order (loop); | |
| 197 | |
| 198 for (x = 0, i = 0; i < loop->num_nodes; i++) | |
| 199 { | |
| 200 basic_block bb = bbs[i]; | |
| 201 | |
| 202 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);) | |
| 203 if (!bitmap_bit_p (partition, x++)) | |
| 204 remove_phi_node (&bsi, true); | |
| 205 else | |
| 206 gsi_next (&bsi); | |
| 207 | |
| 208 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);) | |
| 209 if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL | |
| 210 && !bitmap_bit_p (partition, x++)) | |
| 211 gsi_remove (&bsi, false); | |
| 212 else | |
| 213 gsi_next (&bsi); | |
| 214 | |
| 215 mark_virtual_ops_in_bb (bb); | |
| 216 } | |
| 217 | |
| 218 free (bbs); | |
| 219 return true; | |
| 220 } | |
| 221 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 /* Build the size argument for a memset call. */ |
| 0 | 223 |
| 224 static inline tree | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 build_size_arg_loc (location_t loc, tree nb_iter, tree op, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
226 gimple_seq *stmt_list) |
| 0 | 227 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 gimple_seq stmts; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 tree x; |
| 0 | 230 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
231 x = fold_build2_loc (loc, MULT_EXPR, size_type_node, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 fold_convert_loc (loc, size_type_node, nb_iter), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 fold_convert_loc (loc, size_type_node, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
234 TYPE_SIZE_UNIT (TREE_TYPE (op)))); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
235 x = force_gimple_operand (x, &stmts, true, NULL); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
236 gimple_seq_add_seq (stmt_list, stmts); |
| 0 | 237 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
238 return x; |
| 0 | 239 } |
| 240 | |
| 241 /* Generate a call to memset. Return true when the operation succeeded. */ | |
| 242 | |
| 243 static bool | |
| 244 generate_memset_zero (gimple stmt, tree op0, tree nb_iter, | |
| 245 gimple_stmt_iterator bsi) | |
| 246 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
247 tree addr_base, nb_bytes; |
| 0 | 248 bool res = false; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
249 gimple_seq stmt_list = NULL, stmts; |
| 0 | 250 gimple fn_call; |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
251 tree mem, fn; |
| 0 | 252 gimple_stmt_iterator i; |
| 253 struct data_reference *dr = XCNEW (struct data_reference); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
254 location_t loc = gimple_location (stmt); |
| 0 | 255 |
| 256 DR_STMT (dr) = stmt; | |
| 257 DR_REF (dr) = op0; | |
| 258 if (!dr_analyze_innermost (dr)) | |
| 259 goto end; | |
| 260 | |
| 261 /* Test for a positive stride, iterating over every element. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
262 if (integer_zerop (size_binop (MINUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
263 fold_convert (sizetype, DR_STEP (dr)), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
264 TYPE_SIZE_UNIT (TREE_TYPE (op0))))) |
| 0 | 265 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
266 addr_base = fold_convert_loc (loc, sizetype, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
267 size_binop_loc (loc, PLUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
268 DR_OFFSET (dr), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
269 DR_INIT (dr))); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
270 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
271 TREE_TYPE (DR_BASE_ADDRESS (dr)), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
272 DR_BASE_ADDRESS (dr), addr_base); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
273 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
274 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list); |
| 0 | 275 } |
| 276 | |
| 277 /* Test for a negative stride, iterating over every element. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
278 else if (integer_zerop (size_binop (PLUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
279 TYPE_SIZE_UNIT (TREE_TYPE (op0)), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
280 fold_convert (sizetype, DR_STEP (dr))))) |
| 0 | 281 { |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
282 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list); |
| 0 | 283 |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
284 addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
285 addr_base = fold_convert_loc (loc, sizetype, addr_base); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
286 addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
287 fold_convert_loc (loc, sizetype, nb_bytes)); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
288 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
289 TREE_TYPE (DR_BASE_ADDRESS (dr)), |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
290 DR_BASE_ADDRESS (dr), addr_base); |
| 0 | 291 } |
| 292 else | |
| 293 goto end; | |
| 294 | |
| 295 mem = force_gimple_operand (addr_base, &stmts, true, NULL); | |
| 296 gimple_seq_add_seq (&stmt_list, stmts); | |
| 297 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
298 fn = build_fold_addr_expr (implicit_built_in_decls [BUILT_IN_MEMSET]); |
| 0 | 299 fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes); |
| 300 gimple_seq_add_stmt (&stmt_list, fn_call); | |
| 301 | |
| 302 for (i = gsi_start (stmt_list); !gsi_end_p (i); gsi_next (&i)) | |
| 303 { | |
| 304 gimple s = gsi_stmt (i); | |
| 305 update_stmt_if_modified (s); | |
| 306 } | |
| 307 | |
| 308 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING); | |
| 309 res = true; | |
| 310 | |
| 311 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 312 fprintf (dump_file, "generated memset zero\n"); | |
| 313 | |
| 314 end: | |
| 315 free_data_ref (dr); | |
| 316 return res; | |
| 317 } | |
| 318 | |
| 319 /* Propagate phis in BB b to their uses and remove them. */ | |
| 320 | |
| 321 static void | |
| 322 prop_phis (basic_block b) | |
| 323 { | |
| 324 gimple_stmt_iterator psi; | |
| 325 gimple_seq phis = phi_nodes (b); | |
| 326 | |
| 327 for (psi = gsi_start (phis); !gsi_end_p (psi); ) | |
| 328 { | |
| 329 gimple phi = gsi_stmt (psi); | |
| 330 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0); | |
| 331 | |
| 332 gcc_assert (gimple_phi_num_args (phi) == 1); | |
| 333 | |
| 334 if (!is_gimple_reg (def)) | |
| 335 { | |
| 336 imm_use_iterator iter; | |
| 337 use_operand_p use_p; | |
| 338 gimple stmt; | |
| 339 | |
| 340 FOR_EACH_IMM_USE_STMT (stmt, iter, def) | |
| 341 FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
| 342 SET_USE (use_p, use); | |
| 343 } | |
| 344 else | |
| 345 replace_uses_by (def, use); | |
| 346 | |
| 347 remove_phi_node (&psi, true); | |
| 348 } | |
| 349 } | |
| 350 | |
| 351 /* Tries to generate a builtin function for the instructions of LOOP | |
| 352 pointed to by the bits set in PARTITION. Returns true when the | |
| 353 operation succeeded. */ | |
| 354 | |
| 355 static bool | |
| 356 generate_builtin (struct loop *loop, bitmap partition, bool copy_p) | |
| 357 { | |
| 358 bool res = false; | |
| 359 unsigned i, x = 0; | |
| 360 basic_block *bbs; | |
| 361 gimple write = NULL; | |
| 362 tree op0, op1; | |
| 363 gimple_stmt_iterator bsi; | |
| 364 tree nb_iter = number_of_exit_cond_executions (loop); | |
| 365 | |
| 366 if (!nb_iter || nb_iter == chrec_dont_know) | |
| 367 return false; | |
| 368 | |
| 369 bbs = get_loop_body_in_dom_order (loop); | |
| 370 | |
| 371 for (i = 0; i < loop->num_nodes; i++) | |
| 372 { | |
| 373 basic_block bb = bbs[i]; | |
| 374 | |
| 375 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
| 376 x++; | |
| 377 | |
| 378 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) | |
| 379 { | |
| 380 gimple stmt = gsi_stmt (bsi); | |
| 381 | |
| 382 if (bitmap_bit_p (partition, x++) | |
| 383 && is_gimple_assign (stmt) | |
| 384 && !is_gimple_reg (gimple_assign_lhs (stmt))) | |
| 385 { | |
| 386 /* Don't generate the builtins when there are more than | |
| 387 one memory write. */ | |
| 388 if (write != NULL) | |
| 389 goto end; | |
| 390 | |
| 391 write = stmt; | |
| 392 } | |
| 393 } | |
| 394 } | |
| 395 | |
| 396 if (!write) | |
| 397 goto end; | |
| 398 | |
| 399 op0 = gimple_assign_lhs (write); | |
| 400 op1 = gimple_assign_rhs1 (write); | |
| 401 | |
| 402 if (!(TREE_CODE (op0) == ARRAY_REF | |
| 403 || TREE_CODE (op0) == INDIRECT_REF)) | |
| 404 goto end; | |
| 405 | |
| 406 /* The new statements will be placed before LOOP. */ | |
| 407 bsi = gsi_last_bb (loop_preheader_edge (loop)->src); | |
| 408 | |
| 409 if (gimple_assign_rhs_code (write) == INTEGER_CST | |
| 410 && (integer_zerop (op1) || real_zerop (op1))) | |
| 411 res = generate_memset_zero (write, op0, nb_iter, bsi); | |
| 412 | |
| 413 /* If this is the last partition for which we generate code, we have | |
| 414 to destroy the loop. */ | |
| 415 if (res && !copy_p) | |
| 416 { | |
| 417 unsigned nbbs = loop->num_nodes; | |
| 418 basic_block src = loop_preheader_edge (loop)->src; | |
| 419 basic_block dest = single_exit (loop)->dest; | |
| 420 prop_phis (dest); | |
| 421 make_edge (src, dest, EDGE_FALLTHRU); | |
| 422 cancel_loop_tree (loop); | |
| 423 | |
| 424 for (i = 0; i < nbbs; i++) | |
| 425 delete_basic_block (bbs[i]); | |
| 426 | |
| 427 set_immediate_dominator (CDI_DOMINATORS, dest, | |
| 428 recompute_dominator (CDI_DOMINATORS, dest)); | |
| 429 } | |
| 430 | |
| 431 end: | |
| 432 free (bbs); | |
| 433 return res; | |
| 434 } | |
| 435 | |
| 436 /* Generates code for PARTITION. For simple loops, this function can | |
| 437 generate a built-in. */ | |
| 438 | |
| 439 static bool | |
| 440 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p) | |
| 441 { | |
| 442 if (generate_builtin (loop, partition, copy_p)) | |
| 443 return true; | |
| 444 | |
| 445 return generate_loops_for_partition (loop, partition, copy_p); | |
| 446 } | |
| 447 | |
| 448 | |
| 449 /* Returns true if the node V of RDG cannot be recomputed. */ | |
| 450 | |
| 451 static bool | |
| 452 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v) | |
| 453 { | |
| 454 if (RDG_MEM_WRITE_STMT (rdg, v)) | |
| 455 return true; | |
| 456 | |
| 457 return false; | |
| 458 } | |
| 459 | |
| 460 /* Returns true when the vertex V has already been generated in the | |
| 461 current partition (V is in PROCESSED), or when V belongs to another | |
| 462 partition and cannot be recomputed (V is not in REMAINING_STMTS). */ | |
| 463 | |
| 464 static inline bool | |
| 465 already_processed_vertex_p (bitmap processed, int v) | |
| 466 { | |
| 467 return (bitmap_bit_p (processed, v) | |
| 468 || !bitmap_bit_p (remaining_stmts, v)); | |
| 469 } | |
| 470 | |
| 471 /* Returns NULL when there is no anti-dependence among the successors | |
| 472 of vertex V, otherwise returns the edge with the anti-dep. */ | |
| 473 | |
| 474 static struct graph_edge * | |
| 475 has_anti_dependence (struct vertex *v) | |
| 476 { | |
| 477 struct graph_edge *e; | |
| 478 | |
| 479 if (v->succ) | |
| 480 for (e = v->succ; e; e = e->succ_next) | |
| 481 if (RDGE_TYPE (e) == anti_dd) | |
| 482 return e; | |
| 483 | |
| 484 return NULL; | |
| 485 } | |
| 486 | |
| 487 /* Returns true when V has an anti-dependence edge among its successors. */ | |
| 488 | |
| 489 static bool | |
| 490 predecessor_has_mem_write (struct graph *rdg, struct vertex *v) | |
| 491 { | |
| 492 struct graph_edge *e; | |
| 493 | |
| 494 if (v->pred) | |
| 495 for (e = v->pred; e; e = e->pred_next) | |
| 496 if (bitmap_bit_p (upstream_mem_writes, e->src) | |
| 497 /* Don't consider flow channels: a write to memory followed | |
| 498 by a read from memory. These channels allow the split of | |
| 499 the RDG in different partitions. */ | |
| 500 && !RDG_MEM_WRITE_STMT (rdg, e->src)) | |
| 501 return true; | |
| 502 | |
| 503 return false; | |
| 504 } | |
| 505 | |
| 506 /* Initializes the upstream_mem_writes bitmap following the | |
| 507 information from RDG. */ | |
| 508 | |
| 509 static void | |
| 510 mark_nodes_having_upstream_mem_writes (struct graph *rdg) | |
| 511 { | |
| 512 int v, x; | |
| 513 bitmap seen = BITMAP_ALLOC (NULL); | |
| 514 | |
| 515 for (v = rdg->n_vertices - 1; v >= 0; v--) | |
| 516 if (!bitmap_bit_p (seen, v)) | |
| 517 { | |
| 518 unsigned i; | |
| 519 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3); | |
| 520 | |
| 521 graphds_dfs (rdg, &v, 1, &nodes, false, NULL); | |
| 522 | |
| 523 for (i = 0; VEC_iterate (int, nodes, i, x); i++) | |
| 524 { | |
| 525 if (bitmap_bit_p (seen, x)) | |
| 526 continue; | |
| 527 | |
| 528 bitmap_set_bit (seen, x); | |
| 529 | |
| 530 if (RDG_MEM_WRITE_STMT (rdg, x) | |
| 531 || predecessor_has_mem_write (rdg, &(rdg->vertices[x])) | |
| 532 /* In anti dependences the read should occur before | |
| 533 the write, this is why both the read and the write | |
| 534 should be placed in the same partition. */ | |
| 535 || has_anti_dependence (&(rdg->vertices[x]))) | |
| 536 { | |
| 537 bitmap_set_bit (upstream_mem_writes, x); | |
| 538 } | |
| 539 } | |
| 540 | |
| 541 VEC_free (int, heap, nodes); | |
| 542 } | |
| 543 } | |
| 544 | |
| 545 /* Returns true when vertex u has a memory write node as a predecessor | |
| 546 in RDG. */ | |
| 547 | |
| 548 static bool | |
| 549 has_upstream_mem_writes (int u) | |
| 550 { | |
| 551 return bitmap_bit_p (upstream_mem_writes, u); | |
| 552 } | |
| 553 | |
| 554 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap, | |
| 555 bitmap, bool *); | |
| 556 | |
| 557 /* Flag all the uses of U. */ | |
| 558 | |
| 559 static void | |
| 560 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops, | |
| 561 bitmap processed, bool *part_has_writes) | |
| 562 { | |
| 563 struct graph_edge *e; | |
| 564 | |
| 565 for (e = rdg->vertices[u].succ; e; e = e->succ_next) | |
| 566 if (!bitmap_bit_p (processed, e->dest)) | |
| 567 { | |
| 568 rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops, | |
| 569 processed, part_has_writes); | |
| 570 rdg_flag_all_uses (rdg, e->dest, partition, loops, processed, | |
| 571 part_has_writes); | |
| 572 } | |
| 573 } | |
| 574 | |
| 575 /* Flag the uses of U stopping following the information from | |
| 576 upstream_mem_writes. */ | |
| 577 | |
| 578 static void | |
| 579 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops, | |
| 580 bitmap processed, bool *part_has_writes) | |
| 581 { | |
| 582 use_operand_p use_p; | |
| 583 struct vertex *x = &(rdg->vertices[u]); | |
| 584 gimple stmt = RDGV_STMT (x); | |
| 585 struct graph_edge *anti_dep = has_anti_dependence (x); | |
| 586 | |
| 587 /* Keep in the same partition the destination of an antidependence, | |
| 588 because this is a store to the exact same location. Putting this | |
| 589 in another partition is bad for cache locality. */ | |
| 590 if (anti_dep) | |
| 591 { | |
| 592 int v = anti_dep->dest; | |
| 593 | |
| 594 if (!already_processed_vertex_p (processed, v)) | |
| 595 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, | |
| 596 processed, part_has_writes); | |
| 597 } | |
| 598 | |
| 599 if (gimple_code (stmt) != GIMPLE_PHI) | |
| 600 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
601 if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P) |
| 0 | 602 { |
| 603 tree use = USE_FROM_PTR (use_p); | |
| 604 | |
| 605 if (TREE_CODE (use) == SSA_NAME) | |
| 606 { | |
| 607 gimple def_stmt = SSA_NAME_DEF_STMT (use); | |
| 608 int v = rdg_vertex_for_stmt (rdg, def_stmt); | |
| 609 | |
| 610 if (v >= 0 | |
| 611 && !already_processed_vertex_p (processed, v)) | |
| 612 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, | |
| 613 processed, part_has_writes); | |
| 614 } | |
| 615 } | |
| 616 } | |
| 617 | |
| 618 if (is_gimple_assign (stmt) && has_upstream_mem_writes (u)) | |
| 619 { | |
| 620 tree op0 = gimple_assign_lhs (stmt); | |
| 621 | |
| 622 /* Scalar channels don't have enough space for transmitting data | |
| 623 between tasks, unless we add more storage by privatizing. */ | |
| 624 if (is_gimple_reg (op0)) | |
| 625 { | |
| 626 use_operand_p use_p; | |
| 627 imm_use_iterator iter; | |
| 628 | |
| 629 FOR_EACH_IMM_USE_FAST (use_p, iter, op0) | |
| 630 { | |
| 631 int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p)); | |
| 632 | |
| 633 if (!already_processed_vertex_p (processed, v)) | |
| 634 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, | |
| 635 processed, part_has_writes); | |
| 636 } | |
| 637 } | |
| 638 } | |
| 639 } | |
| 640 | |
| 641 /* Flag V from RDG as part of PARTITION, and also flag its loop number | |
| 642 in LOOPS. */ | |
| 643 | |
| 644 static void | |
| 645 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops, | |
| 646 bool *part_has_writes) | |
| 647 { | |
| 648 struct loop *loop; | |
| 649 | |
| 650 if (bitmap_bit_p (partition, v)) | |
| 651 return; | |
| 652 | |
| 653 loop = loop_containing_stmt (RDG_STMT (rdg, v)); | |
| 654 bitmap_set_bit (loops, loop->num); | |
| 655 bitmap_set_bit (partition, v); | |
| 656 | |
| 657 if (rdg_cannot_recompute_vertex_p (rdg, v)) | |
| 658 { | |
| 659 *part_has_writes = true; | |
| 660 bitmap_clear_bit (remaining_stmts, v); | |
| 661 } | |
| 662 } | |
| 663 | |
| 664 /* Flag in the bitmap PARTITION the vertex V and all its predecessors. | |
| 665 Also flag their loop number in LOOPS. */ | |
| 666 | |
| 667 static void | |
| 668 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition, | |
| 669 bitmap loops, bitmap processed, | |
| 670 bool *part_has_writes) | |
| 671 { | |
| 672 unsigned i; | |
| 673 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3); | |
| 674 int x; | |
| 675 | |
| 676 bitmap_set_bit (processed, v); | |
| 677 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes); | |
| 678 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts); | |
| 679 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes); | |
| 680 | |
| 681 for (i = 0; VEC_iterate (int, nodes, i, x); i++) | |
| 682 if (!already_processed_vertex_p (processed, x)) | |
| 683 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed, | |
| 684 part_has_writes); | |
| 685 | |
| 686 VEC_free (int, heap, nodes); | |
| 687 } | |
| 688 | |
| 689 /* Initialize CONDS with all the condition statements from the basic | |
| 690 blocks of LOOP. */ | |
| 691 | |
| 692 static void | |
| 693 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds) | |
| 694 { | |
| 695 unsigned i; | |
| 696 edge e; | |
| 697 VEC (edge, heap) *exits = get_loop_exit_edges (loop); | |
| 698 | |
| 699 for (i = 0; VEC_iterate (edge, exits, i, e); i++) | |
| 700 { | |
| 701 gimple cond = last_stmt (e->src); | |
| 702 | |
| 703 if (cond) | |
| 704 VEC_safe_push (gimple, heap, *conds, cond); | |
| 705 } | |
| 706 | |
| 707 VEC_free (edge, heap, exits); | |
| 708 } | |
| 709 | |
| 710 /* Add to PARTITION all the exit condition statements for LOOPS | |
| 711 together with all their dependent statements determined from | |
| 712 RDG. */ | |
| 713 | |
| 714 static void | |
| 715 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition, | |
| 716 bitmap processed, bool *part_has_writes) | |
| 717 { | |
| 718 unsigned i; | |
| 719 bitmap_iterator bi; | |
| 720 VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3); | |
| 721 | |
| 722 EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi) | |
| 723 collect_condition_stmts (get_loop (i), &conds); | |
| 724 | |
| 725 while (!VEC_empty (gimple, conds)) | |
| 726 { | |
| 727 gimple cond = VEC_pop (gimple, conds); | |
| 728 int v = rdg_vertex_for_stmt (rdg, cond); | |
| 729 bitmap new_loops = BITMAP_ALLOC (NULL); | |
| 730 | |
| 731 if (!already_processed_vertex_p (processed, v)) | |
| 732 rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed, | |
| 733 part_has_writes); | |
| 734 | |
| 735 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi) | |
| 736 if (!bitmap_bit_p (loops, i)) | |
| 737 { | |
| 738 bitmap_set_bit (loops, i); | |
| 739 collect_condition_stmts (get_loop (i), &conds); | |
| 740 } | |
| 741 | |
| 742 BITMAP_FREE (new_loops); | |
| 743 } | |
| 744 } | |
| 745 | |
| 746 /* Flag all the nodes of RDG containing memory accesses that could | |
| 747 potentially belong to arrays already accessed in the current | |
| 748 PARTITION. */ | |
| 749 | |
| 750 static void | |
| 751 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition, | |
| 752 bitmap loops, bitmap processed, | |
| 753 VEC (int, heap) **other_stores) | |
| 754 { | |
| 755 bool foo; | |
| 756 unsigned i, n; | |
| 757 int j, k, kk; | |
| 758 bitmap_iterator ii; | |
| 759 struct graph_edge *e; | |
| 760 | |
| 761 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii) | |
| 762 if (RDG_MEM_WRITE_STMT (rdg, i) | |
| 763 || RDG_MEM_READS_STMT (rdg, i)) | |
| 764 { | |
| 765 for (j = 0; j < rdg->n_vertices; j++) | |
| 766 if (!bitmap_bit_p (processed, j) | |
| 767 && (RDG_MEM_WRITE_STMT (rdg, j) | |
| 768 || RDG_MEM_READS_STMT (rdg, j)) | |
| 769 && rdg_has_similar_memory_accesses (rdg, i, j)) | |
| 770 { | |
| 771 /* Flag first the node J itself, and all the nodes that | |
| 772 are needed to compute J. */ | |
| 773 rdg_flag_vertex_and_dependent (rdg, j, partition, loops, | |
| 774 processed, &foo); | |
| 775 | |
| 776 /* When J is a read, we want to coalesce in the same | |
| 777 PARTITION all the nodes that are using J: this is | |
| 778 needed for better cache locality. */ | |
| 779 rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo); | |
| 780 | |
| 781 /* Remove from OTHER_STORES the vertex that we flagged. */ | |
| 782 if (RDG_MEM_WRITE_STMT (rdg, j)) | |
| 783 for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++) | |
| 784 if (kk == j) | |
| 785 { | |
| 786 VEC_unordered_remove (int, *other_stores, k); | |
| 787 break; | |
| 788 } | |
| 789 } | |
| 790 | |
| 791 /* If the node I has two uses, then keep these together in the | |
| 792 same PARTITION. */ | |
| 793 for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++); | |
| 794 | |
| 795 if (n > 1) | |
| 796 rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo); | |
| 797 } | |
| 798 } | |
| 799 | |
| 800 /* Returns a bitmap in which all the statements needed for computing | |
| 801 the strongly connected component C of the RDG are flagged, also | |
| 802 including the loop exit conditions. */ | |
| 803 | |
| 804 static bitmap | |
| 805 build_rdg_partition_for_component (struct graph *rdg, rdgc c, | |
| 806 bool *part_has_writes, | |
| 807 VEC (int, heap) **other_stores) | |
| 808 { | |
| 809 int i, v; | |
| 810 bitmap partition = BITMAP_ALLOC (NULL); | |
| 811 bitmap loops = BITMAP_ALLOC (NULL); | |
| 812 bitmap processed = BITMAP_ALLOC (NULL); | |
| 813 | |
| 814 for (i = 0; VEC_iterate (int, c->vertices, i, v); i++) | |
| 815 if (!already_processed_vertex_p (processed, v)) | |
| 816 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed, | |
| 817 part_has_writes); | |
| 818 | |
| 819 /* Also iterate on the array of stores not in the starting vertices, | |
| 820 and determine those vertices that have some memory affinity with | |
| 821 the current nodes in the component: these are stores to the same | |
| 822 arrays, i.e. we're taking care of cache locality. */ | |
| 823 rdg_flag_similar_memory_accesses (rdg, partition, loops, processed, | |
| 824 other_stores); | |
| 825 | |
| 826 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes); | |
| 827 | |
| 828 BITMAP_FREE (processed); | |
| 829 BITMAP_FREE (loops); | |
| 830 return partition; | |
| 831 } | |
| 832 | |
| 833 /* Free memory for COMPONENTS. */ | |
| 834 | |
| 835 static void | |
| 836 free_rdg_components (VEC (rdgc, heap) *components) | |
| 837 { | |
| 838 int i; | |
| 839 rdgc x; | |
| 840 | |
| 841 for (i = 0; VEC_iterate (rdgc, components, i, x); i++) | |
| 842 { | |
| 843 VEC_free (int, heap, x->vertices); | |
| 844 free (x); | |
| 845 } | |
| 846 } | |
| 847 | |
| 848 /* Build the COMPONENTS vector with the strongly connected components | |
| 849 of RDG in which the STARTING_VERTICES occur. */ | |
| 850 | |
| 851 static void | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
852 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices, |
| 0 | 853 VEC (rdgc, heap) **components) |
| 854 { | |
| 855 int i, v; | |
| 856 bitmap saved_components = BITMAP_ALLOC (NULL); | |
| 857 int n_components = graphds_scc (rdg, NULL); | |
| 858 VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components); | |
| 859 | |
| 860 for (i = 0; i < n_components; i++) | |
| 861 all_components[i] = VEC_alloc (int, heap, 3); | |
| 862 | |
| 863 for (i = 0; i < rdg->n_vertices; i++) | |
| 864 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i); | |
| 865 | |
| 866 for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++) | |
| 867 { | |
| 868 int c = rdg->vertices[v].component; | |
| 869 | |
| 870 if (!bitmap_bit_p (saved_components, c)) | |
| 871 { | |
| 872 rdgc x = XCNEW (struct rdg_component); | |
| 873 x->num = c; | |
| 874 x->vertices = all_components[c]; | |
| 875 | |
| 876 VEC_safe_push (rdgc, heap, *components, x); | |
| 877 bitmap_set_bit (saved_components, c); | |
| 878 } | |
| 879 } | |
| 880 | |
| 881 for (i = 0; i < n_components; i++) | |
| 882 if (!bitmap_bit_p (saved_components, i)) | |
| 883 VEC_free (int, heap, all_components[i]); | |
| 884 | |
| 885 free (all_components); | |
| 886 BITMAP_FREE (saved_components); | |
| 887 } | |
| 888 | |
| 889 /* Aggregate several components into a useful partition that is | |
| 890 registered in the PARTITIONS vector. Partitions will be | |
| 891 distributed in different loops. */ | |
| 892 | |
| 893 static void | |
| 894 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components, | |
| 895 VEC (int, heap) **other_stores, | |
| 896 VEC (bitmap, heap) **partitions, bitmap processed) | |
| 897 { | |
| 898 int i; | |
| 899 rdgc x; | |
| 900 bitmap partition = BITMAP_ALLOC (NULL); | |
| 901 | |
| 902 for (i = 0; VEC_iterate (rdgc, components, i, x); i++) | |
| 903 { | |
| 904 bitmap np; | |
| 905 bool part_has_writes = false; | |
| 906 int v = VEC_index (int, x->vertices, 0); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
907 |
| 0 | 908 if (bitmap_bit_p (processed, v)) |
| 909 continue; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
910 |
| 0 | 911 np = build_rdg_partition_for_component (rdg, x, &part_has_writes, |
| 912 other_stores); | |
| 913 bitmap_ior_into (partition, np); | |
| 914 bitmap_ior_into (processed, np); | |
| 915 BITMAP_FREE (np); | |
| 916 | |
| 917 if (part_has_writes) | |
| 918 { | |
| 919 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 920 { | |
| 921 fprintf (dump_file, "ldist useful partition:\n"); | |
| 922 dump_bitmap (dump_file, partition); | |
| 923 } | |
| 924 | |
| 925 VEC_safe_push (bitmap, heap, *partitions, partition); | |
| 926 partition = BITMAP_ALLOC (NULL); | |
| 927 } | |
| 928 } | |
| 929 | |
| 930 /* Add the nodes from the RDG that were not marked as processed, and | |
| 931 that are used outside the current loop. These are scalar | |
| 932 computations that are not yet part of previous partitions. */ | |
| 933 for (i = 0; i < rdg->n_vertices; i++) | |
| 934 if (!bitmap_bit_p (processed, i) | |
| 935 && rdg_defs_used_in_other_loops_p (rdg, i)) | |
| 936 VEC_safe_push (int, heap, *other_stores, i); | |
| 937 | |
| 938 /* If there are still statements left in the OTHER_STORES array, | |
| 939 create other components and partitions with these stores and | |
| 940 their dependences. */ | |
| 941 if (VEC_length (int, *other_stores) > 0) | |
| 942 { | |
| 943 VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3); | |
| 944 VEC (int, heap) *foo = VEC_alloc (int, heap, 3); | |
| 945 | |
| 946 rdg_build_components (rdg, *other_stores, &comps); | |
| 947 rdg_build_partitions (rdg, comps, &foo, partitions, processed); | |
| 948 | |
| 949 VEC_free (int, heap, foo); | |
| 950 free_rdg_components (comps); | |
| 951 } | |
| 952 | |
| 953 /* If there is something left in the last partition, save it. */ | |
| 954 if (bitmap_count_bits (partition) > 0) | |
| 955 VEC_safe_push (bitmap, heap, *partitions, partition); | |
| 956 else | |
| 957 BITMAP_FREE (partition); | |
| 958 } | |
| 959 | |
| 960 /* Dump to FILE the PARTITIONS. */ | |
| 961 | |
| 962 static void | |
| 963 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions) | |
| 964 { | |
| 965 int i; | |
| 966 bitmap partition; | |
| 967 | |
| 968 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++) | |
| 969 debug_bitmap_file (file, partition); | |
| 970 } | |
| 971 | |
| 972 /* Debug PARTITIONS. */ | |
| 973 extern void debug_rdg_partitions (VEC (bitmap, heap) *); | |
| 974 | |
| 975 void | |
| 976 debug_rdg_partitions (VEC (bitmap, heap) *partitions) | |
| 977 { | |
| 978 dump_rdg_partitions (stderr, partitions); | |
| 979 } | |
| 980 | |
| 981 /* Returns the number of read and write operations in the RDG. */ | |
| 982 | |
| 983 static int | |
| 984 number_of_rw_in_rdg (struct graph *rdg) | |
| 985 { | |
| 986 int i, res = 0; | |
| 987 | |
| 988 for (i = 0; i < rdg->n_vertices; i++) | |
| 989 { | |
| 990 if (RDG_MEM_WRITE_STMT (rdg, i)) | |
| 991 ++res; | |
| 992 | |
| 993 if (RDG_MEM_READS_STMT (rdg, i)) | |
| 994 ++res; | |
| 995 } | |
| 996 | |
| 997 return res; | |
| 998 } | |
| 999 | |
| 1000 /* Returns the number of read and write operations in a PARTITION of | |
| 1001 the RDG. */ | |
| 1002 | |
| 1003 static int | |
| 1004 number_of_rw_in_partition (struct graph *rdg, bitmap partition) | |
| 1005 { | |
| 1006 int res = 0; | |
| 1007 unsigned i; | |
| 1008 bitmap_iterator ii; | |
| 1009 | |
| 1010 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii) | |
| 1011 { | |
| 1012 if (RDG_MEM_WRITE_STMT (rdg, i)) | |
| 1013 ++res; | |
| 1014 | |
| 1015 if (RDG_MEM_READS_STMT (rdg, i)) | |
| 1016 ++res; | |
| 1017 } | |
| 1018 | |
| 1019 return res; | |
| 1020 } | |
| 1021 | |
| 1022 /* Returns true when one of the PARTITIONS contains all the read or | |
| 1023 write operations of RDG. */ | |
| 1024 | |
| 1025 static bool | |
| 1026 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions) | |
| 1027 { | |
| 1028 int i; | |
| 1029 bitmap partition; | |
| 1030 int nrw = number_of_rw_in_rdg (rdg); | |
| 1031 | |
| 1032 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++) | |
| 1033 if (nrw == number_of_rw_in_partition (rdg, partition)) | |
| 1034 return true; | |
| 1035 | |
| 1036 return false; | |
| 1037 } | |
| 1038 | |
| 1039 /* Generate code from STARTING_VERTICES in RDG. Returns the number of | |
| 1040 distributed loops. */ | |
| 1041 | |
| 1042 static int | |
| 1043 ldist_gen (struct loop *loop, struct graph *rdg, | |
| 1044 VEC (int, heap) *starting_vertices) | |
| 1045 { | |
| 1046 int i, nbp; | |
| 1047 VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3); | |
| 1048 VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3); | |
| 1049 VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3); | |
| 1050 bitmap partition, processed = BITMAP_ALLOC (NULL); | |
| 1051 | |
| 1052 remaining_stmts = BITMAP_ALLOC (NULL); | |
| 1053 upstream_mem_writes = BITMAP_ALLOC (NULL); | |
| 1054 | |
| 1055 for (i = 0; i < rdg->n_vertices; i++) | |
| 1056 { | |
| 1057 bitmap_set_bit (remaining_stmts, i); | |
| 1058 | |
| 1059 /* Save in OTHER_STORES all the memory writes that are not in | |
| 1060 STARTING_VERTICES. */ | |
| 1061 if (RDG_MEM_WRITE_STMT (rdg, i)) | |
| 1062 { | |
| 1063 int v; | |
| 1064 unsigned j; | |
| 1065 bool found = false; | |
| 1066 | |
| 1067 for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++) | |
| 1068 if (i == v) | |
| 1069 { | |
| 1070 found = true; | |
| 1071 break; | |
| 1072 } | |
| 1073 | |
| 1074 if (!found) | |
| 1075 VEC_safe_push (int, heap, other_stores, i); | |
| 1076 } | |
| 1077 } | |
| 1078 | |
| 1079 mark_nodes_having_upstream_mem_writes (rdg); | |
| 1080 rdg_build_components (rdg, starting_vertices, &components); | |
| 1081 rdg_build_partitions (rdg, components, &other_stores, &partitions, | |
| 1082 processed); | |
| 1083 BITMAP_FREE (processed); | |
| 1084 nbp = VEC_length (bitmap, partitions); | |
| 1085 | |
| 1086 if (nbp <= 1 | |
| 1087 || partition_contains_all_rw (rdg, partitions)) | |
| 1088 goto ldist_done; | |
| 1089 | |
| 1090 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1091 dump_rdg_partitions (dump_file, partitions); | |
| 1092 | |
| 1093 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++) | |
| 1094 if (!generate_code_for_partition (loop, partition, i < nbp - 1)) | |
| 1095 goto ldist_done; | |
| 1096 | |
| 1097 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa); | |
| 1098 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa); | |
| 1099 | |
| 1100 ldist_done: | |
| 1101 | |
| 1102 BITMAP_FREE (remaining_stmts); | |
| 1103 BITMAP_FREE (upstream_mem_writes); | |
| 1104 | |
| 1105 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++) | |
| 1106 BITMAP_FREE (partition); | |
| 1107 | |
| 1108 VEC_free (int, heap, other_stores); | |
| 1109 VEC_free (bitmap, heap, partitions); | |
| 1110 free_rdg_components (components); | |
| 1111 return nbp; | |
| 1112 } | |
| 1113 | |
| 1114 /* Distributes the code from LOOP in such a way that producer | |
| 1115 statements are placed before consumer statements. When STMTS is | |
| 1116 NULL, performs the maximal distribution, if STMTS is not NULL, | |
| 1117 tries to separate only these statements from the LOOP's body. | |
| 1118 Returns the number of distributed loops. */ | |
| 1119 | |
| 1120 static int | |
| 1121 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts) | |
| 1122 { | |
| 1123 bool res = false; | |
| 1124 struct graph *rdg; | |
| 1125 gimple s; | |
| 1126 unsigned i; | |
| 1127 VEC (int, heap) *vertices; | |
| 1128 | |
| 1129 if (loop->num_nodes > 2) | |
| 1130 { | |
| 1131 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1132 fprintf (dump_file, | |
| 1133 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n", | |
| 1134 loop->num); | |
| 1135 | |
| 1136 return res; | |
| 1137 } | |
| 1138 | |
| 1139 rdg = build_rdg (loop); | |
| 1140 | |
| 1141 if (!rdg) | |
| 1142 { | |
| 1143 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1144 fprintf (dump_file, | |
| 1145 "FIXME: Loop %d not distributed: failed to build the RDG.\n", | |
| 1146 loop->num); | |
| 1147 | |
| 1148 return res; | |
| 1149 } | |
| 1150 | |
| 1151 vertices = VEC_alloc (int, heap, 3); | |
| 1152 | |
| 1153 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1154 dump_rdg (dump_file, rdg); | |
| 1155 | |
| 1156 for (i = 0; VEC_iterate (gimple, stmts, i, s); i++) | |
| 1157 { | |
| 1158 int v = rdg_vertex_for_stmt (rdg, s); | |
| 1159 | |
| 1160 if (v >= 0) | |
| 1161 { | |
| 1162 VEC_safe_push (int, heap, vertices, v); | |
| 1163 | |
| 1164 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1165 fprintf (dump_file, | |
| 1166 "ldist asked to generate code for vertex %d\n", v); | |
| 1167 } | |
| 1168 } | |
| 1169 | |
| 1170 res = ldist_gen (loop, rdg, vertices); | |
| 1171 VEC_free (int, heap, vertices); | |
| 1172 free_rdg (rdg); | |
| 1173 | |
| 1174 return res; | |
| 1175 } | |
| 1176 | |
| 1177 /* Distribute all loops in the current function. */ | |
| 1178 | |
| 1179 static unsigned int | |
| 1180 tree_loop_distribution (void) | |
| 1181 { | |
| 1182 struct loop *loop; | |
| 1183 loop_iterator li; | |
| 1184 int nb_generated_loops = 0; | |
| 1185 | |
| 1186 FOR_EACH_LOOP (li, loop, 0) | |
| 1187 { | |
| 1188 VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3); | |
| 1189 | |
| 1190 /* With the following working list, we're asking distribute_loop | |
| 1191 to separate the stores of the loop: when dependences allow, | |
| 1192 it will end on having one store per loop. */ | |
| 1193 stores_from_loop (loop, &work_list); | |
| 1194 | |
| 1195 /* A simple heuristic for cache locality is to not split stores | |
| 1196 to the same array. Without this call, an unrolled loop would | |
| 1197 be split into as many loops as unroll factor, each loop | |
| 1198 storing in the same array. */ | |
| 1199 remove_similar_memory_refs (&work_list); | |
| 1200 | |
| 1201 nb_generated_loops = distribute_loop (loop, work_list); | |
| 1202 | |
| 1203 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 1204 { | |
| 1205 if (nb_generated_loops > 1) | |
| 1206 fprintf (dump_file, "Loop %d distributed: split to %d loops.\n", | |
| 1207 loop->num, nb_generated_loops); | |
| 1208 else | |
| 1209 fprintf (dump_file, "Loop %d is the same.\n", loop->num); | |
| 1210 } | |
| 1211 | |
| 1212 verify_loop_structure (); | |
| 1213 | |
| 1214 VEC_free (gimple, heap, work_list); | |
| 1215 } | |
| 1216 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1217 return 0; |
| 0 | 1218 } |
| 1219 | |
| 1220 static bool | |
| 1221 gate_tree_loop_distribution (void) | |
| 1222 { | |
| 1223 return flag_tree_loop_distribution != 0; | |
| 1224 } | |
| 1225 | |
| 1226 struct gimple_opt_pass pass_loop_distribution = | |
| 1227 { | |
| 1228 { | |
| 1229 GIMPLE_PASS, | |
| 1230 "ldist", /* name */ | |
| 1231 gate_tree_loop_distribution, /* gate */ | |
| 1232 tree_loop_distribution, /* execute */ | |
| 1233 NULL, /* sub */ | |
| 1234 NULL, /* next */ | |
| 1235 0, /* static_pass_number */ | |
| 1236 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */ | |
| 1237 PROP_cfg | PROP_ssa, /* properties_required */ | |
| 1238 0, /* properties_provided */ | |
| 1239 0, /* properties_destroyed */ | |
| 1240 0, /* todo_flags_start */ | |
| 1241 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */ | |
| 1242 } | |
| 1243 }; |