|
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.
|
|
|
7
|
|
|
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.
|
|
|
12
|
|
|
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.
|
|
|
17
|
|
|
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
|
|
|
29 is transformed to
|
|
|
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 /* TODOs we need to run after the pass. */
|
|
|
81 static unsigned int todo;
|
|
|
82
|
|
|
83 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
|
|
|
84 ORIG_LOOP. */
|
|
|
85
|
|
|
86 static void
|
|
|
87 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
|
|
|
88 {
|
|
|
89 tree new_ssa_name;
|
|
|
90 gimple_stmt_iterator si_new, si_orig;
|
|
|
91 edge orig_loop_latch = loop_latch_edge (orig_loop);
|
|
|
92 edge orig_entry_e = loop_preheader_edge (orig_loop);
|
|
|
93 edge new_loop_entry_e = loop_preheader_edge (new_loop);
|
|
|
94
|
|
|
95 /* Scan the phis in the headers of the old and new loops
|
|
|
96 (they are organized in exactly the same order). */
|
|
|
97 for (si_new = gsi_start_phis (new_loop->header),
|
|
|
98 si_orig = gsi_start_phis (orig_loop->header);
|
|
|
99 !gsi_end_p (si_new) && !gsi_end_p (si_orig);
|
|
|
100 gsi_next (&si_new), gsi_next (&si_orig))
|
|
|
101 {
|
|
|
102 tree def;
|
|
|
103 gimple phi_new = gsi_stmt (si_new);
|
|
|
104 gimple phi_orig = gsi_stmt (si_orig);
|
|
|
105
|
|
|
106 /* Add the first phi argument for the phi in NEW_LOOP (the one
|
|
|
107 associated with the entry of NEW_LOOP) */
|
|
|
108 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
|
|
|
109 add_phi_arg (phi_new, def, new_loop_entry_e);
|
|
|
110
|
|
|
111 /* Add the second phi argument for the phi in NEW_LOOP (the one
|
|
|
112 associated with the latch of NEW_LOOP) */
|
|
|
113 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
|
|
|
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
|
|
|
128 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
|
|
|
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
|
|
|
222 /* Build size argument. */
|
|
|
223
|
|
|
224 static inline tree
|
|
|
225 build_size_arg (tree nb_iter, tree op, gimple_seq* stmt_list)
|
|
|
226 {
|
|
|
227 tree nb_bytes;
|
|
|
228 gimple_seq stmts = NULL;
|
|
|
229
|
|
|
230 nb_bytes = fold_build2 (MULT_EXPR, TREE_TYPE (nb_iter),
|
|
|
231 nb_iter, TYPE_SIZE_UNIT (TREE_TYPE (op)));
|
|
|
232 nb_bytes = force_gimple_operand (nb_bytes, &stmts, true, NULL);
|
|
|
233 gimple_seq_add_seq (stmt_list, stmts);
|
|
|
234
|
|
|
235 return nb_bytes;
|
|
|
236 }
|
|
|
237
|
|
|
238 /* Generate a call to memset. Return true when the operation succeeded. */
|
|
|
239
|
|
|
240 static bool
|
|
|
241 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
|
|
|
242 gimple_stmt_iterator bsi)
|
|
|
243 {
|
|
|
244 tree t, addr_base;
|
|
|
245 tree nb_bytes = NULL;
|
|
|
246 bool res = false;
|
|
|
247 gimple_seq stmts = NULL, stmt_list = NULL;
|
|
|
248 gimple fn_call;
|
|
|
249 tree mem, fndecl, fntype, fn;
|
|
|
250 gimple_stmt_iterator i;
|
|
|
251 ssa_op_iter iter;
|
|
|
252 struct data_reference *dr = XCNEW (struct data_reference);
|
|
|
253
|
|
|
254 DR_STMT (dr) = stmt;
|
|
|
255 DR_REF (dr) = op0;
|
|
|
256 if (!dr_analyze_innermost (dr))
|
|
|
257 goto end;
|
|
|
258
|
|
|
259 /* Test for a positive stride, iterating over every element. */
|
|
|
260 if (integer_zerop (fold_build2 (MINUS_EXPR, integer_type_node, DR_STEP (dr),
|
|
|
261 TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
|
|
|
262 {
|
|
|
263 tree offset = fold_convert (sizetype,
|
|
|
264 size_binop (PLUS_EXPR,
|
|
|
265 DR_OFFSET (dr),
|
|
|
266 DR_INIT (dr)));
|
|
|
267 addr_base = fold_build2 (POINTER_PLUS_EXPR,
|
|
|
268 TREE_TYPE (DR_BASE_ADDRESS (dr)),
|
|
|
269 DR_BASE_ADDRESS (dr), offset);
|
|
|
270 }
|
|
|
271
|
|
|
272 /* Test for a negative stride, iterating over every element. */
|
|
|
273 else if (integer_zerop (fold_build2 (PLUS_EXPR, integer_type_node,
|
|
|
274 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
|
|
|
275 DR_STEP (dr))))
|
|
|
276 {
|
|
|
277 nb_bytes = build_size_arg (nb_iter, op0, &stmt_list);
|
|
|
278 addr_base = size_binop (PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
|
|
|
279 addr_base = fold_build2 (MINUS_EXPR, sizetype, addr_base, nb_bytes);
|
|
|
280 addr_base = force_gimple_operand (addr_base, &stmts, true, NULL);
|
|
|
281 gimple_seq_add_seq (&stmt_list, stmts);
|
|
|
282
|
|
|
283 addr_base = fold_build2 (POINTER_PLUS_EXPR,
|
|
|
284 TREE_TYPE (DR_BASE_ADDRESS (dr)),
|
|
|
285 DR_BASE_ADDRESS (dr), addr_base);
|
|
|
286 }
|
|
|
287 else
|
|
|
288 goto end;
|
|
|
289
|
|
|
290 mem = force_gimple_operand (addr_base, &stmts, true, NULL);
|
|
|
291 gimple_seq_add_seq (&stmt_list, stmts);
|
|
|
292
|
|
|
293 fndecl = implicit_built_in_decls [BUILT_IN_MEMSET];
|
|
|
294 fntype = TREE_TYPE (fndecl);
|
|
|
295 fn = build1 (ADDR_EXPR, build_pointer_type (fntype), fndecl);
|
|
|
296
|
|
|
297 if (!nb_bytes)
|
|
|
298 nb_bytes = build_size_arg (nb_iter, op0, &stmt_list);
|
|
|
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 FOR_EACH_SSA_TREE_OPERAND (t, s, iter, SSA_OP_VIRTUAL_DEFS)
|
|
|
308 {
|
|
|
309 if (TREE_CODE (t) == SSA_NAME)
|
|
|
310 t = SSA_NAME_VAR (t);
|
|
|
311 mark_sym_for_renaming (t);
|
|
|
312 }
|
|
|
313 }
|
|
|
314
|
|
|
315 /* Mark also the uses of the VDEFS of STMT to be renamed. */
|
|
|
316 FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_VIRTUAL_DEFS)
|
|
|
317 {
|
|
|
318 if (TREE_CODE (t) == SSA_NAME)
|
|
|
319 {
|
|
|
320 gimple s;
|
|
|
321 imm_use_iterator imm_iter;
|
|
|
322
|
|
|
323 FOR_EACH_IMM_USE_STMT (s, imm_iter, t)
|
|
|
324 update_stmt (s);
|
|
|
325
|
|
|
326 t = SSA_NAME_VAR (t);
|
|
|
327 }
|
|
|
328 mark_sym_for_renaming (t);
|
|
|
329 }
|
|
|
330
|
|
|
331 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
|
|
|
332 res = true;
|
|
|
333
|
|
|
334 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
335 fprintf (dump_file, "generated memset zero\n");
|
|
|
336
|
|
|
337 todo |= TODO_rebuild_alias;
|
|
|
338
|
|
|
339 end:
|
|
|
340 free_data_ref (dr);
|
|
|
341 return res;
|
|
|
342 }
|
|
|
343
|
|
|
344 /* Propagate phis in BB b to their uses and remove them. */
|
|
|
345
|
|
|
346 static void
|
|
|
347 prop_phis (basic_block b)
|
|
|
348 {
|
|
|
349 gimple_stmt_iterator psi;
|
|
|
350 gimple_seq phis = phi_nodes (b);
|
|
|
351
|
|
|
352 for (psi = gsi_start (phis); !gsi_end_p (psi); )
|
|
|
353 {
|
|
|
354 gimple phi = gsi_stmt (psi);
|
|
|
355 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
|
|
|
356
|
|
|
357 gcc_assert (gimple_phi_num_args (phi) == 1);
|
|
|
358
|
|
|
359 if (!is_gimple_reg (def))
|
|
|
360 {
|
|
|
361 imm_use_iterator iter;
|
|
|
362 use_operand_p use_p;
|
|
|
363 gimple stmt;
|
|
|
364
|
|
|
365 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
|
|
|
366 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
|
|
|
367 SET_USE (use_p, use);
|
|
|
368 }
|
|
|
369 else
|
|
|
370 replace_uses_by (def, use);
|
|
|
371
|
|
|
372 remove_phi_node (&psi, true);
|
|
|
373 }
|
|
|
374 }
|
|
|
375
|
|
|
376 /* Tries to generate a builtin function for the instructions of LOOP
|
|
|
377 pointed to by the bits set in PARTITION. Returns true when the
|
|
|
378 operation succeeded. */
|
|
|
379
|
|
|
380 static bool
|
|
|
381 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
|
|
|
382 {
|
|
|
383 bool res = false;
|
|
|
384 unsigned i, x = 0;
|
|
|
385 basic_block *bbs;
|
|
|
386 gimple write = NULL;
|
|
|
387 tree op0, op1;
|
|
|
388 gimple_stmt_iterator bsi;
|
|
|
389 tree nb_iter = number_of_exit_cond_executions (loop);
|
|
|
390
|
|
|
391 if (!nb_iter || nb_iter == chrec_dont_know)
|
|
|
392 return false;
|
|
|
393
|
|
|
394 bbs = get_loop_body_in_dom_order (loop);
|
|
|
395
|
|
|
396 for (i = 0; i < loop->num_nodes; i++)
|
|
|
397 {
|
|
|
398 basic_block bb = bbs[i];
|
|
|
399
|
|
|
400 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
|
|
401 x++;
|
|
|
402
|
|
|
403 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
|
|
|
404 {
|
|
|
405 gimple stmt = gsi_stmt (bsi);
|
|
|
406
|
|
|
407 if (bitmap_bit_p (partition, x++)
|
|
|
408 && is_gimple_assign (stmt)
|
|
|
409 && !is_gimple_reg (gimple_assign_lhs (stmt)))
|
|
|
410 {
|
|
|
411 /* Don't generate the builtins when there are more than
|
|
|
412 one memory write. */
|
|
|
413 if (write != NULL)
|
|
|
414 goto end;
|
|
|
415
|
|
|
416 write = stmt;
|
|
|
417 }
|
|
|
418 }
|
|
|
419 }
|
|
|
420
|
|
|
421 if (!write)
|
|
|
422 goto end;
|
|
|
423
|
|
|
424 op0 = gimple_assign_lhs (write);
|
|
|
425 op1 = gimple_assign_rhs1 (write);
|
|
|
426
|
|
|
427 if (!(TREE_CODE (op0) == ARRAY_REF
|
|
|
428 || TREE_CODE (op0) == INDIRECT_REF))
|
|
|
429 goto end;
|
|
|
430
|
|
|
431 /* The new statements will be placed before LOOP. */
|
|
|
432 bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
|
|
|
433
|
|
|
434 if (gimple_assign_rhs_code (write) == INTEGER_CST
|
|
|
435 && (integer_zerop (op1) || real_zerop (op1)))
|
|
|
436 res = generate_memset_zero (write, op0, nb_iter, bsi);
|
|
|
437
|
|
|
438 /* If this is the last partition for which we generate code, we have
|
|
|
439 to destroy the loop. */
|
|
|
440 if (res && !copy_p)
|
|
|
441 {
|
|
|
442 unsigned nbbs = loop->num_nodes;
|
|
|
443 basic_block src = loop_preheader_edge (loop)->src;
|
|
|
444 basic_block dest = single_exit (loop)->dest;
|
|
|
445 prop_phis (dest);
|
|
|
446 make_edge (src, dest, EDGE_FALLTHRU);
|
|
|
447 cancel_loop_tree (loop);
|
|
|
448
|
|
|
449 for (i = 0; i < nbbs; i++)
|
|
|
450 delete_basic_block (bbs[i]);
|
|
|
451
|
|
|
452 set_immediate_dominator (CDI_DOMINATORS, dest,
|
|
|
453 recompute_dominator (CDI_DOMINATORS, dest));
|
|
|
454 }
|
|
|
455
|
|
|
456 end:
|
|
|
457 free (bbs);
|
|
|
458 return res;
|
|
|
459 }
|
|
|
460
|
|
|
461 /* Generates code for PARTITION. For simple loops, this function can
|
|
|
462 generate a built-in. */
|
|
|
463
|
|
|
464 static bool
|
|
|
465 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
|
|
|
466 {
|
|
|
467 if (generate_builtin (loop, partition, copy_p))
|
|
|
468 return true;
|
|
|
469
|
|
|
470 return generate_loops_for_partition (loop, partition, copy_p);
|
|
|
471 }
|
|
|
472
|
|
|
473
|
|
|
474 /* Returns true if the node V of RDG cannot be recomputed. */
|
|
|
475
|
|
|
476 static bool
|
|
|
477 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
|
|
|
478 {
|
|
|
479 if (RDG_MEM_WRITE_STMT (rdg, v))
|
|
|
480 return true;
|
|
|
481
|
|
|
482 return false;
|
|
|
483 }
|
|
|
484
|
|
|
485 /* Returns true when the vertex V has already been generated in the
|
|
|
486 current partition (V is in PROCESSED), or when V belongs to another
|
|
|
487 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
|
|
|
488
|
|
|
489 static inline bool
|
|
|
490 already_processed_vertex_p (bitmap processed, int v)
|
|
|
491 {
|
|
|
492 return (bitmap_bit_p (processed, v)
|
|
|
493 || !bitmap_bit_p (remaining_stmts, v));
|
|
|
494 }
|
|
|
495
|
|
|
496 /* Returns NULL when there is no anti-dependence among the successors
|
|
|
497 of vertex V, otherwise returns the edge with the anti-dep. */
|
|
|
498
|
|
|
499 static struct graph_edge *
|
|
|
500 has_anti_dependence (struct vertex *v)
|
|
|
501 {
|
|
|
502 struct graph_edge *e;
|
|
|
503
|
|
|
504 if (v->succ)
|
|
|
505 for (e = v->succ; e; e = e->succ_next)
|
|
|
506 if (RDGE_TYPE (e) == anti_dd)
|
|
|
507 return e;
|
|
|
508
|
|
|
509 return NULL;
|
|
|
510 }
|
|
|
511
|
|
|
512 /* Returns true when V has an anti-dependence edge among its successors. */
|
|
|
513
|
|
|
514 static bool
|
|
|
515 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
|
|
|
516 {
|
|
|
517 struct graph_edge *e;
|
|
|
518
|
|
|
519 if (v->pred)
|
|
|
520 for (e = v->pred; e; e = e->pred_next)
|
|
|
521 if (bitmap_bit_p (upstream_mem_writes, e->src)
|
|
|
522 /* Don't consider flow channels: a write to memory followed
|
|
|
523 by a read from memory. These channels allow the split of
|
|
|
524 the RDG in different partitions. */
|
|
|
525 && !RDG_MEM_WRITE_STMT (rdg, e->src))
|
|
|
526 return true;
|
|
|
527
|
|
|
528 return false;
|
|
|
529 }
|
|
|
530
|
|
|
531 /* Initializes the upstream_mem_writes bitmap following the
|
|
|
532 information from RDG. */
|
|
|
533
|
|
|
534 static void
|
|
|
535 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
|
|
|
536 {
|
|
|
537 int v, x;
|
|
|
538 bitmap seen = BITMAP_ALLOC (NULL);
|
|
|
539
|
|
|
540 for (v = rdg->n_vertices - 1; v >= 0; v--)
|
|
|
541 if (!bitmap_bit_p (seen, v))
|
|
|
542 {
|
|
|
543 unsigned i;
|
|
|
544 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
|
|
|
545 bool has_upstream_mem_write_p = false;
|
|
|
546
|
|
|
547 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
|
|
|
548
|
|
|
549 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
|
|
|
550 {
|
|
|
551 if (bitmap_bit_p (seen, x))
|
|
|
552 continue;
|
|
|
553
|
|
|
554 bitmap_set_bit (seen, x);
|
|
|
555
|
|
|
556 if (RDG_MEM_WRITE_STMT (rdg, x)
|
|
|
557 || predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
|
|
|
558 /* In anti dependences the read should occur before
|
|
|
559 the write, this is why both the read and the write
|
|
|
560 should be placed in the same partition. */
|
|
|
561 || has_anti_dependence (&(rdg->vertices[x])))
|
|
|
562 {
|
|
|
563 has_upstream_mem_write_p = true;
|
|
|
564 bitmap_set_bit (upstream_mem_writes, x);
|
|
|
565 }
|
|
|
566 }
|
|
|
567
|
|
|
568 VEC_free (int, heap, nodes);
|
|
|
569 }
|
|
|
570 }
|
|
|
571
|
|
|
572 /* Returns true when vertex u has a memory write node as a predecessor
|
|
|
573 in RDG. */
|
|
|
574
|
|
|
575 static bool
|
|
|
576 has_upstream_mem_writes (int u)
|
|
|
577 {
|
|
|
578 return bitmap_bit_p (upstream_mem_writes, u);
|
|
|
579 }
|
|
|
580
|
|
|
581 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
|
|
|
582 bitmap, bool *);
|
|
|
583
|
|
|
584 /* Flag all the uses of U. */
|
|
|
585
|
|
|
586 static void
|
|
|
587 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
|
|
|
588 bitmap processed, bool *part_has_writes)
|
|
|
589 {
|
|
|
590 struct graph_edge *e;
|
|
|
591
|
|
|
592 for (e = rdg->vertices[u].succ; e; e = e->succ_next)
|
|
|
593 if (!bitmap_bit_p (processed, e->dest))
|
|
|
594 {
|
|
|
595 rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
|
|
|
596 processed, part_has_writes);
|
|
|
597 rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
|
|
|
598 part_has_writes);
|
|
|
599 }
|
|
|
600 }
|
|
|
601
|
|
|
602 /* Flag the uses of U stopping following the information from
|
|
|
603 upstream_mem_writes. */
|
|
|
604
|
|
|
605 static void
|
|
|
606 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
|
|
|
607 bitmap processed, bool *part_has_writes)
|
|
|
608 {
|
|
|
609 ssa_op_iter iter;
|
|
|
610 use_operand_p use_p;
|
|
|
611 struct vertex *x = &(rdg->vertices[u]);
|
|
|
612 gimple stmt = RDGV_STMT (x);
|
|
|
613 struct graph_edge *anti_dep = has_anti_dependence (x);
|
|
|
614
|
|
|
615 /* Keep in the same partition the destination of an antidependence,
|
|
|
616 because this is a store to the exact same location. Putting this
|
|
|
617 in another partition is bad for cache locality. */
|
|
|
618 if (anti_dep)
|
|
|
619 {
|
|
|
620 int v = anti_dep->dest;
|
|
|
621
|
|
|
622 if (!already_processed_vertex_p (processed, v))
|
|
|
623 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
|
|
|
624 processed, part_has_writes);
|
|
|
625 }
|
|
|
626
|
|
|
627 if (gimple_code (stmt) != GIMPLE_PHI)
|
|
|
628 {
|
|
|
629 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
|
|
|
630 {
|
|
|
631 tree use = USE_FROM_PTR (use_p);
|
|
|
632
|
|
|
633 if (TREE_CODE (use) == SSA_NAME)
|
|
|
634 {
|
|
|
635 gimple def_stmt = SSA_NAME_DEF_STMT (use);
|
|
|
636 int v = rdg_vertex_for_stmt (rdg, def_stmt);
|
|
|
637
|
|
|
638 if (v >= 0
|
|
|
639 && !already_processed_vertex_p (processed, v))
|
|
|
640 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
|
|
|
641 processed, part_has_writes);
|
|
|
642 }
|
|
|
643 }
|
|
|
644 }
|
|
|
645
|
|
|
646 if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
|
|
|
647 {
|
|
|
648 tree op0 = gimple_assign_lhs (stmt);
|
|
|
649
|
|
|
650 /* Scalar channels don't have enough space for transmitting data
|
|
|
651 between tasks, unless we add more storage by privatizing. */
|
|
|
652 if (is_gimple_reg (op0))
|
|
|
653 {
|
|
|
654 use_operand_p use_p;
|
|
|
655 imm_use_iterator iter;
|
|
|
656
|
|
|
657 FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
|
|
|
658 {
|
|
|
659 int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
|
|
|
660
|
|
|
661 if (!already_processed_vertex_p (processed, v))
|
|
|
662 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
|
|
|
663 processed, part_has_writes);
|
|
|
664 }
|
|
|
665 }
|
|
|
666 }
|
|
|
667 }
|
|
|
668
|
|
|
669 /* Flag V from RDG as part of PARTITION, and also flag its loop number
|
|
|
670 in LOOPS. */
|
|
|
671
|
|
|
672 static void
|
|
|
673 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
|
|
|
674 bool *part_has_writes)
|
|
|
675 {
|
|
|
676 struct loop *loop;
|
|
|
677
|
|
|
678 if (bitmap_bit_p (partition, v))
|
|
|
679 return;
|
|
|
680
|
|
|
681 loop = loop_containing_stmt (RDG_STMT (rdg, v));
|
|
|
682 bitmap_set_bit (loops, loop->num);
|
|
|
683 bitmap_set_bit (partition, v);
|
|
|
684
|
|
|
685 if (rdg_cannot_recompute_vertex_p (rdg, v))
|
|
|
686 {
|
|
|
687 *part_has_writes = true;
|
|
|
688 bitmap_clear_bit (remaining_stmts, v);
|
|
|
689 }
|
|
|
690 }
|
|
|
691
|
|
|
692 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
|
|
|
693 Also flag their loop number in LOOPS. */
|
|
|
694
|
|
|
695 static void
|
|
|
696 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
|
|
|
697 bitmap loops, bitmap processed,
|
|
|
698 bool *part_has_writes)
|
|
|
699 {
|
|
|
700 unsigned i;
|
|
|
701 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
|
|
|
702 int x;
|
|
|
703
|
|
|
704 bitmap_set_bit (processed, v);
|
|
|
705 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
|
|
|
706 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
|
|
|
707 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
|
|
|
708
|
|
|
709 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
|
|
|
710 if (!already_processed_vertex_p (processed, x))
|
|
|
711 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
|
|
|
712 part_has_writes);
|
|
|
713
|
|
|
714 VEC_free (int, heap, nodes);
|
|
|
715 }
|
|
|
716
|
|
|
717 /* Initialize CONDS with all the condition statements from the basic
|
|
|
718 blocks of LOOP. */
|
|
|
719
|
|
|
720 static void
|
|
|
721 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
|
|
|
722 {
|
|
|
723 unsigned i;
|
|
|
724 edge e;
|
|
|
725 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
|
|
|
726
|
|
|
727 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
|
|
|
728 {
|
|
|
729 gimple cond = last_stmt (e->src);
|
|
|
730
|
|
|
731 if (cond)
|
|
|
732 VEC_safe_push (gimple, heap, *conds, cond);
|
|
|
733 }
|
|
|
734
|
|
|
735 VEC_free (edge, heap, exits);
|
|
|
736 }
|
|
|
737
|
|
|
738 /* Add to PARTITION all the exit condition statements for LOOPS
|
|
|
739 together with all their dependent statements determined from
|
|
|
740 RDG. */
|
|
|
741
|
|
|
742 static void
|
|
|
743 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
|
|
|
744 bitmap processed, bool *part_has_writes)
|
|
|
745 {
|
|
|
746 unsigned i;
|
|
|
747 bitmap_iterator bi;
|
|
|
748 VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
|
|
|
749
|
|
|
750 EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
|
|
|
751 collect_condition_stmts (get_loop (i), &conds);
|
|
|
752
|
|
|
753 while (!VEC_empty (gimple, conds))
|
|
|
754 {
|
|
|
755 gimple cond = VEC_pop (gimple, conds);
|
|
|
756 int v = rdg_vertex_for_stmt (rdg, cond);
|
|
|
757 bitmap new_loops = BITMAP_ALLOC (NULL);
|
|
|
758
|
|
|
759 if (!already_processed_vertex_p (processed, v))
|
|
|
760 rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
|
|
|
761 part_has_writes);
|
|
|
762
|
|
|
763 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
|
|
|
764 if (!bitmap_bit_p (loops, i))
|
|
|
765 {
|
|
|
766 bitmap_set_bit (loops, i);
|
|
|
767 collect_condition_stmts (get_loop (i), &conds);
|
|
|
768 }
|
|
|
769
|
|
|
770 BITMAP_FREE (new_loops);
|
|
|
771 }
|
|
|
772 }
|
|
|
773
|
|
|
774 /* Flag all the nodes of RDG containing memory accesses that could
|
|
|
775 potentially belong to arrays already accessed in the current
|
|
|
776 PARTITION. */
|
|
|
777
|
|
|
778 static void
|
|
|
779 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
|
|
|
780 bitmap loops, bitmap processed,
|
|
|
781 VEC (int, heap) **other_stores)
|
|
|
782 {
|
|
|
783 bool foo;
|
|
|
784 unsigned i, n;
|
|
|
785 int j, k, kk;
|
|
|
786 bitmap_iterator ii;
|
|
|
787 struct graph_edge *e;
|
|
|
788
|
|
|
789 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
|
|
|
790 if (RDG_MEM_WRITE_STMT (rdg, i)
|
|
|
791 || RDG_MEM_READS_STMT (rdg, i))
|
|
|
792 {
|
|
|
793 for (j = 0; j < rdg->n_vertices; j++)
|
|
|
794 if (!bitmap_bit_p (processed, j)
|
|
|
795 && (RDG_MEM_WRITE_STMT (rdg, j)
|
|
|
796 || RDG_MEM_READS_STMT (rdg, j))
|
|
|
797 && rdg_has_similar_memory_accesses (rdg, i, j))
|
|
|
798 {
|
|
|
799 /* Flag first the node J itself, and all the nodes that
|
|
|
800 are needed to compute J. */
|
|
|
801 rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
|
|
|
802 processed, &foo);
|
|
|
803
|
|
|
804 /* When J is a read, we want to coalesce in the same
|
|
|
805 PARTITION all the nodes that are using J: this is
|
|
|
806 needed for better cache locality. */
|
|
|
807 rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
|
|
|
808
|
|
|
809 /* Remove from OTHER_STORES the vertex that we flagged. */
|
|
|
810 if (RDG_MEM_WRITE_STMT (rdg, j))
|
|
|
811 for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++)
|
|
|
812 if (kk == j)
|
|
|
813 {
|
|
|
814 VEC_unordered_remove (int, *other_stores, k);
|
|
|
815 break;
|
|
|
816 }
|
|
|
817 }
|
|
|
818
|
|
|
819 /* If the node I has two uses, then keep these together in the
|
|
|
820 same PARTITION. */
|
|
|
821 for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
|
|
|
822
|
|
|
823 if (n > 1)
|
|
|
824 rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
|
|
|
825 }
|
|
|
826 }
|
|
|
827
|
|
|
828 /* Returns a bitmap in which all the statements needed for computing
|
|
|
829 the strongly connected component C of the RDG are flagged, also
|
|
|
830 including the loop exit conditions. */
|
|
|
831
|
|
|
832 static bitmap
|
|
|
833 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
|
|
|
834 bool *part_has_writes,
|
|
|
835 VEC (int, heap) **other_stores)
|
|
|
836 {
|
|
|
837 int i, v;
|
|
|
838 bitmap partition = BITMAP_ALLOC (NULL);
|
|
|
839 bitmap loops = BITMAP_ALLOC (NULL);
|
|
|
840 bitmap processed = BITMAP_ALLOC (NULL);
|
|
|
841
|
|
|
842 for (i = 0; VEC_iterate (int, c->vertices, i, v); i++)
|
|
|
843 if (!already_processed_vertex_p (processed, v))
|
|
|
844 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
|
|
|
845 part_has_writes);
|
|
|
846
|
|
|
847 /* Also iterate on the array of stores not in the starting vertices,
|
|
|
848 and determine those vertices that have some memory affinity with
|
|
|
849 the current nodes in the component: these are stores to the same
|
|
|
850 arrays, i.e. we're taking care of cache locality. */
|
|
|
851 rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
|
|
|
852 other_stores);
|
|
|
853
|
|
|
854 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
|
|
|
855
|
|
|
856 BITMAP_FREE (processed);
|
|
|
857 BITMAP_FREE (loops);
|
|
|
858 return partition;
|
|
|
859 }
|
|
|
860
|
|
|
861 /* Free memory for COMPONENTS. */
|
|
|
862
|
|
|
863 static void
|
|
|
864 free_rdg_components (VEC (rdgc, heap) *components)
|
|
|
865 {
|
|
|
866 int i;
|
|
|
867 rdgc x;
|
|
|
868
|
|
|
869 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
|
|
|
870 {
|
|
|
871 VEC_free (int, heap, x->vertices);
|
|
|
872 free (x);
|
|
|
873 }
|
|
|
874 }
|
|
|
875
|
|
|
876 /* Build the COMPONENTS vector with the strongly connected components
|
|
|
877 of RDG in which the STARTING_VERTICES occur. */
|
|
|
878
|
|
|
879 static void
|
|
|
880 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
|
|
|
881 VEC (rdgc, heap) **components)
|
|
|
882 {
|
|
|
883 int i, v;
|
|
|
884 bitmap saved_components = BITMAP_ALLOC (NULL);
|
|
|
885 int n_components = graphds_scc (rdg, NULL);
|
|
|
886 VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
|
|
|
887
|
|
|
888 for (i = 0; i < n_components; i++)
|
|
|
889 all_components[i] = VEC_alloc (int, heap, 3);
|
|
|
890
|
|
|
891 for (i = 0; i < rdg->n_vertices; i++)
|
|
|
892 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
|
|
|
893
|
|
|
894 for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++)
|
|
|
895 {
|
|
|
896 int c = rdg->vertices[v].component;
|
|
|
897
|
|
|
898 if (!bitmap_bit_p (saved_components, c))
|
|
|
899 {
|
|
|
900 rdgc x = XCNEW (struct rdg_component);
|
|
|
901 x->num = c;
|
|
|
902 x->vertices = all_components[c];
|
|
|
903
|
|
|
904 VEC_safe_push (rdgc, heap, *components, x);
|
|
|
905 bitmap_set_bit (saved_components, c);
|
|
|
906 }
|
|
|
907 }
|
|
|
908
|
|
|
909 for (i = 0; i < n_components; i++)
|
|
|
910 if (!bitmap_bit_p (saved_components, i))
|
|
|
911 VEC_free (int, heap, all_components[i]);
|
|
|
912
|
|
|
913 free (all_components);
|
|
|
914 BITMAP_FREE (saved_components);
|
|
|
915 }
|
|
|
916
|
|
|
917 /* Aggregate several components into a useful partition that is
|
|
|
918 registered in the PARTITIONS vector. Partitions will be
|
|
|
919 distributed in different loops. */
|
|
|
920
|
|
|
921 static void
|
|
|
922 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
|
|
|
923 VEC (int, heap) **other_stores,
|
|
|
924 VEC (bitmap, heap) **partitions, bitmap processed)
|
|
|
925 {
|
|
|
926 int i;
|
|
|
927 rdgc x;
|
|
|
928 bitmap partition = BITMAP_ALLOC (NULL);
|
|
|
929
|
|
|
930 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
|
|
|
931 {
|
|
|
932 bitmap np;
|
|
|
933 bool part_has_writes = false;
|
|
|
934 int v = VEC_index (int, x->vertices, 0);
|
|
|
935
|
|
|
936 if (bitmap_bit_p (processed, v))
|
|
|
937 continue;
|
|
|
938
|
|
|
939 np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
|
|
|
940 other_stores);
|
|
|
941 bitmap_ior_into (partition, np);
|
|
|
942 bitmap_ior_into (processed, np);
|
|
|
943 BITMAP_FREE (np);
|
|
|
944
|
|
|
945 if (part_has_writes)
|
|
|
946 {
|
|
|
947 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
948 {
|
|
|
949 fprintf (dump_file, "ldist useful partition:\n");
|
|
|
950 dump_bitmap (dump_file, partition);
|
|
|
951 }
|
|
|
952
|
|
|
953 VEC_safe_push (bitmap, heap, *partitions, partition);
|
|
|
954 partition = BITMAP_ALLOC (NULL);
|
|
|
955 }
|
|
|
956 }
|
|
|
957
|
|
|
958 /* Add the nodes from the RDG that were not marked as processed, and
|
|
|
959 that are used outside the current loop. These are scalar
|
|
|
960 computations that are not yet part of previous partitions. */
|
|
|
961 for (i = 0; i < rdg->n_vertices; i++)
|
|
|
962 if (!bitmap_bit_p (processed, i)
|
|
|
963 && rdg_defs_used_in_other_loops_p (rdg, i))
|
|
|
964 VEC_safe_push (int, heap, *other_stores, i);
|
|
|
965
|
|
|
966 /* If there are still statements left in the OTHER_STORES array,
|
|
|
967 create other components and partitions with these stores and
|
|
|
968 their dependences. */
|
|
|
969 if (VEC_length (int, *other_stores) > 0)
|
|
|
970 {
|
|
|
971 VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
|
|
|
972 VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
|
|
|
973
|
|
|
974 rdg_build_components (rdg, *other_stores, &comps);
|
|
|
975 rdg_build_partitions (rdg, comps, &foo, partitions, processed);
|
|
|
976
|
|
|
977 VEC_free (int, heap, foo);
|
|
|
978 free_rdg_components (comps);
|
|
|
979 }
|
|
|
980
|
|
|
981 /* If there is something left in the last partition, save it. */
|
|
|
982 if (bitmap_count_bits (partition) > 0)
|
|
|
983 VEC_safe_push (bitmap, heap, *partitions, partition);
|
|
|
984 else
|
|
|
985 BITMAP_FREE (partition);
|
|
|
986 }
|
|
|
987
|
|
|
988 /* Dump to FILE the PARTITIONS. */
|
|
|
989
|
|
|
990 static void
|
|
|
991 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
|
|
|
992 {
|
|
|
993 int i;
|
|
|
994 bitmap partition;
|
|
|
995
|
|
|
996 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
|
|
|
997 debug_bitmap_file (file, partition);
|
|
|
998 }
|
|
|
999
|
|
|
1000 /* Debug PARTITIONS. */
|
|
|
1001 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
|
|
|
1002
|
|
|
1003 void
|
|
|
1004 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
|
|
|
1005 {
|
|
|
1006 dump_rdg_partitions (stderr, partitions);
|
|
|
1007 }
|
|
|
1008
|
|
|
1009 /* Returns the number of read and write operations in the RDG. */
|
|
|
1010
|
|
|
1011 static int
|
|
|
1012 number_of_rw_in_rdg (struct graph *rdg)
|
|
|
1013 {
|
|
|
1014 int i, res = 0;
|
|
|
1015
|
|
|
1016 for (i = 0; i < rdg->n_vertices; i++)
|
|
|
1017 {
|
|
|
1018 if (RDG_MEM_WRITE_STMT (rdg, i))
|
|
|
1019 ++res;
|
|
|
1020
|
|
|
1021 if (RDG_MEM_READS_STMT (rdg, i))
|
|
|
1022 ++res;
|
|
|
1023 }
|
|
|
1024
|
|
|
1025 return res;
|
|
|
1026 }
|
|
|
1027
|
|
|
1028 /* Returns the number of read and write operations in a PARTITION of
|
|
|
1029 the RDG. */
|
|
|
1030
|
|
|
1031 static int
|
|
|
1032 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
|
|
|
1033 {
|
|
|
1034 int res = 0;
|
|
|
1035 unsigned i;
|
|
|
1036 bitmap_iterator ii;
|
|
|
1037
|
|
|
1038 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
|
|
|
1039 {
|
|
|
1040 if (RDG_MEM_WRITE_STMT (rdg, i))
|
|
|
1041 ++res;
|
|
|
1042
|
|
|
1043 if (RDG_MEM_READS_STMT (rdg, i))
|
|
|
1044 ++res;
|
|
|
1045 }
|
|
|
1046
|
|
|
1047 return res;
|
|
|
1048 }
|
|
|
1049
|
|
|
1050 /* Returns true when one of the PARTITIONS contains all the read or
|
|
|
1051 write operations of RDG. */
|
|
|
1052
|
|
|
1053 static bool
|
|
|
1054 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
|
|
|
1055 {
|
|
|
1056 int i;
|
|
|
1057 bitmap partition;
|
|
|
1058 int nrw = number_of_rw_in_rdg (rdg);
|
|
|
1059
|
|
|
1060 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
|
|
|
1061 if (nrw == number_of_rw_in_partition (rdg, partition))
|
|
|
1062 return true;
|
|
|
1063
|
|
|
1064 return false;
|
|
|
1065 }
|
|
|
1066
|
|
|
1067 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
|
|
|
1068 distributed loops. */
|
|
|
1069
|
|
|
1070 static int
|
|
|
1071 ldist_gen (struct loop *loop, struct graph *rdg,
|
|
|
1072 VEC (int, heap) *starting_vertices)
|
|
|
1073 {
|
|
|
1074 int i, nbp;
|
|
|
1075 VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
|
|
|
1076 VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
|
|
|
1077 VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
|
|
|
1078 bitmap partition, processed = BITMAP_ALLOC (NULL);
|
|
|
1079
|
|
|
1080 remaining_stmts = BITMAP_ALLOC (NULL);
|
|
|
1081 upstream_mem_writes = BITMAP_ALLOC (NULL);
|
|
|
1082
|
|
|
1083 for (i = 0; i < rdg->n_vertices; i++)
|
|
|
1084 {
|
|
|
1085 bitmap_set_bit (remaining_stmts, i);
|
|
|
1086
|
|
|
1087 /* Save in OTHER_STORES all the memory writes that are not in
|
|
|
1088 STARTING_VERTICES. */
|
|
|
1089 if (RDG_MEM_WRITE_STMT (rdg, i))
|
|
|
1090 {
|
|
|
1091 int v;
|
|
|
1092 unsigned j;
|
|
|
1093 bool found = false;
|
|
|
1094
|
|
|
1095 for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++)
|
|
|
1096 if (i == v)
|
|
|
1097 {
|
|
|
1098 found = true;
|
|
|
1099 break;
|
|
|
1100 }
|
|
|
1101
|
|
|
1102 if (!found)
|
|
|
1103 VEC_safe_push (int, heap, other_stores, i);
|
|
|
1104 }
|
|
|
1105 }
|
|
|
1106
|
|
|
1107 mark_nodes_having_upstream_mem_writes (rdg);
|
|
|
1108 rdg_build_components (rdg, starting_vertices, &components);
|
|
|
1109 rdg_build_partitions (rdg, components, &other_stores, &partitions,
|
|
|
1110 processed);
|
|
|
1111 BITMAP_FREE (processed);
|
|
|
1112 nbp = VEC_length (bitmap, partitions);
|
|
|
1113
|
|
|
1114 if (nbp <= 1
|
|
|
1115 || partition_contains_all_rw (rdg, partitions))
|
|
|
1116 goto ldist_done;
|
|
|
1117
|
|
|
1118 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1119 dump_rdg_partitions (dump_file, partitions);
|
|
|
1120
|
|
|
1121 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
|
|
|
1122 if (!generate_code_for_partition (loop, partition, i < nbp - 1))
|
|
|
1123 goto ldist_done;
|
|
|
1124
|
|
|
1125 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
|
|
|
1126 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
|
|
|
1127
|
|
|
1128 ldist_done:
|
|
|
1129
|
|
|
1130 BITMAP_FREE (remaining_stmts);
|
|
|
1131 BITMAP_FREE (upstream_mem_writes);
|
|
|
1132
|
|
|
1133 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
|
|
|
1134 BITMAP_FREE (partition);
|
|
|
1135
|
|
|
1136 VEC_free (int, heap, other_stores);
|
|
|
1137 VEC_free (bitmap, heap, partitions);
|
|
|
1138 free_rdg_components (components);
|
|
|
1139 return nbp;
|
|
|
1140 }
|
|
|
1141
|
|
|
1142 /* Distributes the code from LOOP in such a way that producer
|
|
|
1143 statements are placed before consumer statements. When STMTS is
|
|
|
1144 NULL, performs the maximal distribution, if STMTS is not NULL,
|
|
|
1145 tries to separate only these statements from the LOOP's body.
|
|
|
1146 Returns the number of distributed loops. */
|
|
|
1147
|
|
|
1148 static int
|
|
|
1149 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
|
|
|
1150 {
|
|
|
1151 bool res = false;
|
|
|
1152 struct graph *rdg;
|
|
|
1153 gimple s;
|
|
|
1154 unsigned i;
|
|
|
1155 VEC (int, heap) *vertices;
|
|
|
1156
|
|
|
1157 if (loop->num_nodes > 2)
|
|
|
1158 {
|
|
|
1159 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1160 fprintf (dump_file,
|
|
|
1161 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
|
|
|
1162 loop->num);
|
|
|
1163
|
|
|
1164 return res;
|
|
|
1165 }
|
|
|
1166
|
|
|
1167 rdg = build_rdg (loop);
|
|
|
1168
|
|
|
1169 if (!rdg)
|
|
|
1170 {
|
|
|
1171 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1172 fprintf (dump_file,
|
|
|
1173 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
|
|
|
1174 loop->num);
|
|
|
1175
|
|
|
1176 return res;
|
|
|
1177 }
|
|
|
1178
|
|
|
1179 vertices = VEC_alloc (int, heap, 3);
|
|
|
1180
|
|
|
1181 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1182 dump_rdg (dump_file, rdg);
|
|
|
1183
|
|
|
1184 for (i = 0; VEC_iterate (gimple, stmts, i, s); i++)
|
|
|
1185 {
|
|
|
1186 int v = rdg_vertex_for_stmt (rdg, s);
|
|
|
1187
|
|
|
1188 if (v >= 0)
|
|
|
1189 {
|
|
|
1190 VEC_safe_push (int, heap, vertices, v);
|
|
|
1191
|
|
|
1192 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1193 fprintf (dump_file,
|
|
|
1194 "ldist asked to generate code for vertex %d\n", v);
|
|
|
1195 }
|
|
|
1196 }
|
|
|
1197
|
|
|
1198 res = ldist_gen (loop, rdg, vertices);
|
|
|
1199 VEC_free (int, heap, vertices);
|
|
|
1200 free_rdg (rdg);
|
|
|
1201
|
|
|
1202 return res;
|
|
|
1203 }
|
|
|
1204
|
|
|
1205 /* Distribute all loops in the current function. */
|
|
|
1206
|
|
|
1207 static unsigned int
|
|
|
1208 tree_loop_distribution (void)
|
|
|
1209 {
|
|
|
1210 struct loop *loop;
|
|
|
1211 loop_iterator li;
|
|
|
1212 int nb_generated_loops = 0;
|
|
|
1213
|
|
|
1214 todo = 0;
|
|
|
1215
|
|
|
1216 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1217 {
|
|
|
1218 VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3);
|
|
|
1219
|
|
|
1220 /* With the following working list, we're asking distribute_loop
|
|
|
1221 to separate the stores of the loop: when dependences allow,
|
|
|
1222 it will end on having one store per loop. */
|
|
|
1223 stores_from_loop (loop, &work_list);
|
|
|
1224
|
|
|
1225 /* A simple heuristic for cache locality is to not split stores
|
|
|
1226 to the same array. Without this call, an unrolled loop would
|
|
|
1227 be split into as many loops as unroll factor, each loop
|
|
|
1228 storing in the same array. */
|
|
|
1229 remove_similar_memory_refs (&work_list);
|
|
|
1230
|
|
|
1231 nb_generated_loops = distribute_loop (loop, work_list);
|
|
|
1232
|
|
|
1233 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1234 {
|
|
|
1235 if (nb_generated_loops > 1)
|
|
|
1236 fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
|
|
|
1237 loop->num, nb_generated_loops);
|
|
|
1238 else
|
|
|
1239 fprintf (dump_file, "Loop %d is the same.\n", loop->num);
|
|
|
1240 }
|
|
|
1241
|
|
|
1242 verify_loop_structure ();
|
|
|
1243
|
|
|
1244 VEC_free (gimple, heap, work_list);
|
|
|
1245 }
|
|
|
1246
|
|
|
1247 return todo;
|
|
|
1248 }
|
|
|
1249
|
|
|
1250 static bool
|
|
|
1251 gate_tree_loop_distribution (void)
|
|
|
1252 {
|
|
|
1253 return flag_tree_loop_distribution != 0;
|
|
|
1254 }
|
|
|
1255
|
|
|
1256 struct gimple_opt_pass pass_loop_distribution =
|
|
|
1257 {
|
|
|
1258 {
|
|
|
1259 GIMPLE_PASS,
|
|
|
1260 "ldist", /* name */
|
|
|
1261 gate_tree_loop_distribution, /* gate */
|
|
|
1262 tree_loop_distribution, /* execute */
|
|
|
1263 NULL, /* sub */
|
|
|
1264 NULL, /* next */
|
|
|
1265 0, /* static_pass_number */
|
|
|
1266 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
|
|
|
1267 PROP_cfg | PROP_ssa, /* properties_required */
|
|
|
1268 0, /* properties_provided */
|
|
|
1269 0, /* properties_destroyed */
|
|
|
1270 0, /* todo_flags_start */
|
|
|
1271 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */
|
|
|
1272 }
|
|
|
1273 };
|
