|
111
|
1 /* Tail merging for gimple.
|
|
|
2 Copyright (C) 2011-2017 Free Software Foundation, Inc.
|
|
|
3 Contributed by Tom de Vries (tom@codesourcery.com)
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify
|
|
|
8 it under the terms of the GNU General Public License as published by
|
|
|
9 the Free Software Foundation; either version 3, or (at your option)
|
|
|
10 any later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful,
|
|
|
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
|
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
|
15 GNU General Public License for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 /* Pass overview.
|
|
|
22
|
|
|
23
|
|
|
24 MOTIVATIONAL EXAMPLE
|
|
|
25
|
|
|
26 gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
|
|
|
27
|
|
|
28 hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
|
|
|
29 {
|
|
|
30 struct FILED.1638 * fpD.2605;
|
|
|
31 charD.1 fileNameD.2604[1000];
|
|
|
32 intD.0 D.3915;
|
|
|
33 const charD.1 * restrict outputFileName.0D.3914;
|
|
|
34
|
|
|
35 # BLOCK 2 freq:10000
|
|
|
36 # PRED: ENTRY [100.0%] (fallthru,exec)
|
|
|
37 # PT = nonlocal { D.3926 } (restr)
|
|
|
38 outputFileName.0D.3914_3
|
|
|
39 = (const charD.1 * restrict) outputFileNameD.2600_2(D);
|
|
|
40 # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
|
|
|
41 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
42 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
43 sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
|
|
|
44 # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
|
|
|
45 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
46 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
47 D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
|
|
|
48 if (D.3915_4 == 0)
|
|
|
49 goto <bb 3>;
|
|
|
50 else
|
|
|
51 goto <bb 4>;
|
|
|
52 # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
|
|
|
53
|
|
|
54 # BLOCK 3 freq:1000
|
|
|
55 # PRED: 2 [10.0%] (true,exec)
|
|
|
56 # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
|
|
|
57 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
58 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
59 freeD.898 (ctxD.2601_5(D));
|
|
|
60 goto <bb 7>;
|
|
|
61 # SUCC: 7 [100.0%] (fallthru,exec)
|
|
|
62
|
|
|
63 # BLOCK 4 freq:9000
|
|
|
64 # PRED: 2 [90.0%] (false,exec)
|
|
|
65 # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
|
|
|
66 # PT = nonlocal escaped
|
|
|
67 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
68 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
69 fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
|
|
|
70 if (fpD.2605_8 == 0B)
|
|
|
71 goto <bb 5>;
|
|
|
72 else
|
|
|
73 goto <bb 6>;
|
|
|
74 # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
|
|
|
75
|
|
|
76 # BLOCK 5 freq:173
|
|
|
77 # PRED: 4 [1.9%] (true,exec)
|
|
|
78 # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
|
|
|
79 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
80 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
81 freeD.898 (ctxD.2601_5(D));
|
|
|
82 goto <bb 7>;
|
|
|
83 # SUCC: 7 [100.0%] (fallthru,exec)
|
|
|
84
|
|
|
85 # BLOCK 6 freq:8827
|
|
|
86 # PRED: 4 [98.1%] (false,exec)
|
|
|
87 # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
|
|
|
88 # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
89 # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
|
|
|
90 fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
|
|
|
91 # SUCC: 7 [100.0%] (fallthru,exec)
|
|
|
92
|
|
|
93 # BLOCK 7 freq:10000
|
|
|
94 # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
|
|
|
95 6 [100.0%] (fallthru,exec)
|
|
|
96 # PT = nonlocal null
|
|
|
97
|
|
|
98 # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
|
|
|
99 # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
|
|
|
100 .MEMD.3923_18(6)>
|
|
|
101 # VUSE <.MEMD.3923_11>
|
|
|
102 return ctxD.2601_1;
|
|
|
103 # SUCC: EXIT [100.0%]
|
|
|
104 }
|
|
|
105
|
|
|
106 bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
|
|
|
107 same successors, and the same operations.
|
|
|
108
|
|
|
109
|
|
|
110 CONTEXT
|
|
|
111
|
|
|
112 A technique called tail merging (or cross jumping) can fix the example
|
|
|
113 above. For a block, we look for common code at the end (the tail) of the
|
|
|
114 predecessor blocks, and insert jumps from one block to the other.
|
|
|
115 The example is a special case for tail merging, in that 2 whole blocks
|
|
|
116 can be merged, rather than just the end parts of it.
|
|
|
117 We currently only focus on whole block merging, so in that sense
|
|
|
118 calling this pass tail merge is a bit of a misnomer.
|
|
|
119
|
|
|
120 We distinguish 2 kinds of situations in which blocks can be merged:
|
|
|
121 - same operations, same predecessors. The successor edges coming from one
|
|
|
122 block are redirected to come from the other block.
|
|
|
123 - same operations, same successors. The predecessor edges entering one block
|
|
|
124 are redirected to enter the other block. Note that this operation might
|
|
|
125 involve introducing phi operations.
|
|
|
126
|
|
|
127 For efficient implementation, we would like to value numbers the blocks, and
|
|
|
128 have a comparison operator that tells us whether the blocks are equal.
|
|
|
129 Besides being runtime efficient, block value numbering should also abstract
|
|
|
130 from irrelevant differences in order of operations, much like normal value
|
|
|
131 numbering abstracts from irrelevant order of operations.
|
|
|
132
|
|
|
133 For the first situation (same_operations, same predecessors), normal value
|
|
|
134 numbering fits well. We can calculate a block value number based on the
|
|
|
135 value numbers of the defs and vdefs.
|
|
|
136
|
|
|
137 For the second situation (same operations, same successors), this approach
|
|
|
138 doesn't work so well. We can illustrate this using the example. The calls
|
|
|
139 to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
|
|
|
140 remain different in value numbering, since they represent different memory
|
|
|
141 states. So the resulting vdefs of the frees will be different in value
|
|
|
142 numbering, so the block value numbers will be different.
|
|
|
143
|
|
|
144 The reason why we call the blocks equal is not because they define the same
|
|
|
145 values, but because uses in the blocks use (possibly different) defs in the
|
|
|
146 same way. To be able to detect this efficiently, we need to do some kind of
|
|
|
147 reverse value numbering, meaning number the uses rather than the defs, and
|
|
|
148 calculate a block value number based on the value number of the uses.
|
|
|
149 Ideally, a block comparison operator will also indicate which phis are needed
|
|
|
150 to merge the blocks.
|
|
|
151
|
|
|
152 For the moment, we don't do block value numbering, but we do insn-by-insn
|
|
|
153 matching, using scc value numbers to match operations with results, and
|
|
|
154 structural comparison otherwise, while ignoring vop mismatches.
|
|
|
155
|
|
|
156
|
|
|
157 IMPLEMENTATION
|
|
|
158
|
|
|
159 1. The pass first determines all groups of blocks with the same successor
|
|
|
160 blocks.
|
|
|
161 2. Within each group, it tries to determine clusters of equal basic blocks.
|
|
|
162 3. The clusters are applied.
|
|
|
163 4. The same successor groups are updated.
|
|
|
164 5. This process is repeated from 2 onwards, until no more changes.
|
|
|
165
|
|
|
166
|
|
|
167 LIMITATIONS/TODO
|
|
|
168
|
|
|
169 - block only
|
|
|
170 - handles only 'same operations, same successors'.
|
|
|
171 It handles same predecessors as a special subcase though.
|
|
|
172 - does not implement the reverse value numbering and block value numbering.
|
|
|
173 - improve memory allocation: use garbage collected memory, obstacks,
|
|
|
174 allocpools where appropriate.
|
|
|
175 - no insertion of gimple_reg phis, We only introduce vop-phis.
|
|
|
176 - handle blocks with gimple_reg phi_nodes.
|
|
|
177
|
|
|
178
|
|
|
179 PASS PLACEMENT
|
|
|
180 This 'pass' is not a stand-alone gimple pass, but runs as part of
|
|
|
181 pass_pre, in order to share the value numbering.
|
|
|
182
|
|
|
183
|
|
|
184 SWITCHES
|
|
|
185
|
|
|
186 - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
|
|
|
187
|
|
|
188 #include "config.h"
|
|
|
189 #include "system.h"
|
|
|
190 #include "coretypes.h"
|
|
|
191 #include "backend.h"
|
|
|
192 #include "tree.h"
|
|
|
193 #include "gimple.h"
|
|
|
194 #include "cfghooks.h"
|
|
|
195 #include "tree-pass.h"
|
|
|
196 #include "ssa.h"
|
|
|
197 #include "fold-const.h"
|
|
|
198 #include "trans-mem.h"
|
|
|
199 #include "cfganal.h"
|
|
|
200 #include "cfgcleanup.h"
|
|
|
201 #include "gimple-iterator.h"
|
|
|
202 #include "tree-cfg.h"
|
|
|
203 #include "tree-into-ssa.h"
|
|
|
204 #include "params.h"
|
|
|
205 #include "tree-ssa-sccvn.h"
|
|
|
206 #include "cfgloop.h"
|
|
|
207 #include "tree-eh.h"
|
|
|
208 #include "tree-cfgcleanup.h"
|
|
|
209
|
|
|
210 const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE;
|
|
|
211
|
|
|
212 /* Describes a group of bbs with the same successors. The successor bbs are
|
|
|
213 cached in succs, and the successor edge flags are cached in succ_flags.
|
|
|
214 If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
|
|
|
215 it's marked in inverse.
|
|
|
216 Additionally, the hash value for the struct is cached in hashval, and
|
|
|
217 in_worklist indicates whether it's currently part of worklist. */
|
|
|
218
|
|
|
219 struct same_succ : pointer_hash <same_succ>
|
|
|
220 {
|
|
|
221 /* The bbs that have the same successor bbs. */
|
|
|
222 bitmap bbs;
|
|
|
223 /* The successor bbs. */
|
|
|
224 bitmap succs;
|
|
|
225 /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
|
|
|
226 bb. */
|
|
|
227 bitmap inverse;
|
|
|
228 /* The edge flags for each of the successor bbs. */
|
|
|
229 vec<int> succ_flags;
|
|
|
230 /* Indicates whether the struct is currently in the worklist. */
|
|
|
231 bool in_worklist;
|
|
|
232 /* The hash value of the struct. */
|
|
|
233 hashval_t hashval;
|
|
|
234
|
|
|
235 /* hash_table support. */
|
|
|
236 static inline hashval_t hash (const same_succ *);
|
|
|
237 static int equal (const same_succ *, const same_succ *);
|
|
|
238 static void remove (same_succ *);
|
|
|
239 };
|
|
|
240
|
|
|
241 /* hash routine for hash_table support, returns hashval of E. */
|
|
|
242
|
|
|
243 inline hashval_t
|
|
|
244 same_succ::hash (const same_succ *e)
|
|
|
245 {
|
|
|
246 return e->hashval;
|
|
|
247 }
|
|
|
248
|
|
|
249 /* A group of bbs where 1 bb from bbs can replace the other bbs. */
|
|
|
250
|
|
|
251 struct bb_cluster
|
|
|
252 {
|
|
|
253 /* The bbs in the cluster. */
|
|
|
254 bitmap bbs;
|
|
|
255 /* The preds of the bbs in the cluster. */
|
|
|
256 bitmap preds;
|
|
|
257 /* Index in all_clusters vector. */
|
|
|
258 int index;
|
|
|
259 /* The bb to replace the cluster with. */
|
|
|
260 basic_block rep_bb;
|
|
|
261 };
|
|
|
262
|
|
|
263 /* Per bb-info. */
|
|
|
264
|
|
|
265 struct aux_bb_info
|
|
|
266 {
|
|
|
267 /* The number of non-debug statements in the bb. */
|
|
|
268 int size;
|
|
|
269 /* The same_succ that this bb is a member of. */
|
|
|
270 same_succ *bb_same_succ;
|
|
|
271 /* The cluster that this bb is a member of. */
|
|
|
272 bb_cluster *cluster;
|
|
|
273 /* The vop state at the exit of a bb. This is shortlived data, used to
|
|
|
274 communicate data between update_block_by and update_vuses. */
|
|
|
275 tree vop_at_exit;
|
|
|
276 /* The bb that either contains or is dominated by the dependencies of the
|
|
|
277 bb. */
|
|
|
278 basic_block dep_bb;
|
|
|
279 };
|
|
|
280
|
|
|
281 /* Macros to access the fields of struct aux_bb_info. */
|
|
|
282
|
|
|
283 #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
|
|
|
284 #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
|
|
|
285 #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
|
|
|
286 #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
|
|
|
287 #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
|
|
|
288
|
|
|
289 /* Returns true if the only effect a statement STMT has, is to define locally
|
|
|
290 used SSA_NAMEs. */
|
|
|
291
|
|
|
292 static bool
|
|
|
293 stmt_local_def (gimple *stmt)
|
|
|
294 {
|
|
|
295 basic_block bb, def_bb;
|
|
|
296 imm_use_iterator iter;
|
|
|
297 use_operand_p use_p;
|
|
|
298 tree val;
|
|
|
299 def_operand_p def_p;
|
|
|
300
|
|
|
301 if (gimple_vdef (stmt) != NULL_TREE
|
|
|
302 || gimple_has_side_effects (stmt)
|
|
|
303 || gimple_could_trap_p_1 (stmt, false, false)
|
|
|
304 || gimple_vuse (stmt) != NULL_TREE)
|
|
|
305 return false;
|
|
|
306
|
|
|
307 def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
|
|
|
308 if (def_p == NULL)
|
|
|
309 return false;
|
|
|
310
|
|
|
311 val = DEF_FROM_PTR (def_p);
|
|
|
312 if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
|
|
|
313 return false;
|
|
|
314
|
|
|
315 def_bb = gimple_bb (stmt);
|
|
|
316
|
|
|
317 FOR_EACH_IMM_USE_FAST (use_p, iter, val)
|
|
|
318 {
|
|
|
319 if (is_gimple_debug (USE_STMT (use_p)))
|
|
|
320 continue;
|
|
|
321 bb = gimple_bb (USE_STMT (use_p));
|
|
|
322 if (bb == def_bb)
|
|
|
323 continue;
|
|
|
324
|
|
|
325 if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
|
|
|
326 && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
|
|
|
327 continue;
|
|
|
328
|
|
|
329 return false;
|
|
|
330 }
|
|
|
331
|
|
|
332 return true;
|
|
|
333 }
|
|
|
334
|
|
|
335 /* Let GSI skip forwards over local defs. */
|
|
|
336
|
|
|
337 static void
|
|
|
338 gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
|
|
|
339 {
|
|
|
340 gimple *stmt;
|
|
|
341
|
|
|
342 while (true)
|
|
|
343 {
|
|
|
344 if (gsi_end_p (*gsi))
|
|
|
345 return;
|
|
|
346 stmt = gsi_stmt (*gsi);
|
|
|
347 if (!stmt_local_def (stmt))
|
|
|
348 return;
|
|
|
349 gsi_next_nondebug (gsi);
|
|
|
350 }
|
|
|
351 }
|
|
|
352
|
|
|
353 /* VAL1 and VAL2 are either:
|
|
|
354 - uses in BB1 and BB2, or
|
|
|
355 - phi alternatives for BB1 and BB2.
|
|
|
356 Return true if the uses have the same gvn value. */
|
|
|
357
|
|
|
358 static bool
|
|
|
359 gvn_uses_equal (tree val1, tree val2)
|
|
|
360 {
|
|
|
361 gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
|
|
|
362
|
|
|
363 if (val1 == val2)
|
|
|
364 return true;
|
|
|
365
|
|
|
366 if (vn_valueize (val1) != vn_valueize (val2))
|
|
|
367 return false;
|
|
|
368
|
|
|
369 return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
|
|
|
370 && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
|
|
|
371 }
|
|
|
372
|
|
|
373 /* Prints E to FILE. */
|
|
|
374
|
|
|
375 static void
|
|
|
376 same_succ_print (FILE *file, const same_succ *e)
|
|
|
377 {
|
|
|
378 unsigned int i;
|
|
|
379 bitmap_print (file, e->bbs, "bbs:", "\n");
|
|
|
380 bitmap_print (file, e->succs, "succs:", "\n");
|
|
|
381 bitmap_print (file, e->inverse, "inverse:", "\n");
|
|
|
382 fprintf (file, "flags:");
|
|
|
383 for (i = 0; i < e->succ_flags.length (); ++i)
|
|
|
384 fprintf (file, " %x", e->succ_flags[i]);
|
|
|
385 fprintf (file, "\n");
|
|
|
386 }
|
|
|
387
|
|
|
388 /* Prints same_succ VE to VFILE. */
|
|
|
389
|
|
|
390 inline int
|
|
|
391 ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
|
|
|
392 {
|
|
|
393 const same_succ *e = *pe;
|
|
|
394 same_succ_print (file, e);
|
|
|
395 return 1;
|
|
|
396 }
|
|
|
397
|
|
|
398 /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
|
|
|
399
|
|
|
400 static void
|
|
|
401 update_dep_bb (basic_block use_bb, tree val)
|
|
|
402 {
|
|
|
403 basic_block dep_bb;
|
|
|
404
|
|
|
405 /* Not a dep. */
|
|
|
406 if (TREE_CODE (val) != SSA_NAME)
|
|
|
407 return;
|
|
|
408
|
|
|
409 /* Skip use of global def. */
|
|
|
410 if (SSA_NAME_IS_DEFAULT_DEF (val))
|
|
|
411 return;
|
|
|
412
|
|
|
413 /* Skip use of local def. */
|
|
|
414 dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
|
|
|
415 if (dep_bb == use_bb)
|
|
|
416 return;
|
|
|
417
|
|
|
418 if (BB_DEP_BB (use_bb) == NULL
|
|
|
419 || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
|
|
|
420 BB_DEP_BB (use_bb) = dep_bb;
|
|
|
421 }
|
|
|
422
|
|
|
423 /* Update BB_DEP_BB, given the dependencies in STMT. */
|
|
|
424
|
|
|
425 static void
|
|
|
426 stmt_update_dep_bb (gimple *stmt)
|
|
|
427 {
|
|
|
428 ssa_op_iter iter;
|
|
|
429 use_operand_p use;
|
|
|
430
|
|
|
431 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
|
|
432 update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
|
|
|
433 }
|
|
|
434
|
|
|
435 /* Calculates hash value for same_succ VE. */
|
|
|
436
|
|
|
437 static hashval_t
|
|
|
438 same_succ_hash (const same_succ *e)
|
|
|
439 {
|
|
|
440 inchash::hash hstate (bitmap_hash (e->succs));
|
|
|
441 int flags;
|
|
|
442 unsigned int i;
|
|
|
443 unsigned int first = bitmap_first_set_bit (e->bbs);
|
|
|
444 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
|
|
|
445 int size = 0;
|
|
|
446 gimple *stmt;
|
|
|
447 tree arg;
|
|
|
448 unsigned int s;
|
|
|
449 bitmap_iterator bs;
|
|
|
450
|
|
|
451 for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
|
|
|
452 !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
|
|
|
453 {
|
|
|
454 stmt = gsi_stmt (gsi);
|
|
|
455 stmt_update_dep_bb (stmt);
|
|
|
456 if (stmt_local_def (stmt))
|
|
|
457 continue;
|
|
|
458 size++;
|
|
|
459
|
|
|
460 hstate.add_int (gimple_code (stmt));
|
|
|
461 if (is_gimple_assign (stmt))
|
|
|
462 hstate.add_int (gimple_assign_rhs_code (stmt));
|
|
|
463 if (!is_gimple_call (stmt))
|
|
|
464 continue;
|
|
|
465 if (gimple_call_internal_p (stmt))
|
|
|
466 hstate.add_int (gimple_call_internal_fn (stmt));
|
|
|
467 else
|
|
|
468 {
|
|
|
469 inchash::add_expr (gimple_call_fn (stmt), hstate);
|
|
|
470 if (gimple_call_chain (stmt))
|
|
|
471 inchash::add_expr (gimple_call_chain (stmt), hstate);
|
|
|
472 }
|
|
|
473 for (i = 0; i < gimple_call_num_args (stmt); i++)
|
|
|
474 {
|
|
|
475 arg = gimple_call_arg (stmt, i);
|
|
|
476 arg = vn_valueize (arg);
|
|
|
477 inchash::add_expr (arg, hstate);
|
|
|
478 }
|
|
|
479 }
|
|
|
480
|
|
|
481 hstate.add_int (size);
|
|
|
482 BB_SIZE (bb) = size;
|
|
|
483
|
|
|
484 hstate.add_int (bb->loop_father->num);
|
|
|
485
|
|
|
486 for (i = 0; i < e->succ_flags.length (); ++i)
|
|
|
487 {
|
|
|
488 flags = e->succ_flags[i];
|
|
|
489 flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
|
|
490 hstate.add_int (flags);
|
|
|
491 }
|
|
|
492
|
|
|
493 EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
|
|
|
494 {
|
|
|
495 int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
|
|
|
496 for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
|
|
|
497 !gsi_end_p (gsi);
|
|
|
498 gsi_next (&gsi))
|
|
|
499 {
|
|
|
500 gphi *phi = gsi.phi ();
|
|
|
501 tree lhs = gimple_phi_result (phi);
|
|
|
502 tree val = gimple_phi_arg_def (phi, n);
|
|
|
503
|
|
|
504 if (virtual_operand_p (lhs))
|
|
|
505 continue;
|
|
|
506 update_dep_bb (bb, val);
|
|
|
507 }
|
|
|
508 }
|
|
|
509
|
|
|
510 return hstate.end ();
|
|
|
511 }
|
|
|
512
|
|
|
513 /* Returns true if E1 and E2 have 2 successors, and if the successor flags
|
|
|
514 are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
|
|
|
515 the other edge flags. */
|
|
|
516
|
|
|
517 static bool
|
|
|
518 inverse_flags (const same_succ *e1, const same_succ *e2)
|
|
|
519 {
|
|
|
520 int f1a, f1b, f2a, f2b;
|
|
|
521 int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
|
|
|
522
|
|
|
523 if (e1->succ_flags.length () != 2)
|
|
|
524 return false;
|
|
|
525
|
|
|
526 f1a = e1->succ_flags[0];
|
|
|
527 f1b = e1->succ_flags[1];
|
|
|
528 f2a = e2->succ_flags[0];
|
|
|
529 f2b = e2->succ_flags[1];
|
|
|
530
|
|
|
531 if (f1a == f2a && f1b == f2b)
|
|
|
532 return false;
|
|
|
533
|
|
|
534 return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
|
|
|
535 }
|
|
|
536
|
|
|
537 /* Compares SAME_SUCCs E1 and E2. */
|
|
|
538
|
|
|
539 int
|
|
|
540 same_succ::equal (const same_succ *e1, const same_succ *e2)
|
|
|
541 {
|
|
|
542 unsigned int i, first1, first2;
|
|
|
543 gimple_stmt_iterator gsi1, gsi2;
|
|
|
544 gimple *s1, *s2;
|
|
|
545 basic_block bb1, bb2;
|
|
|
546
|
|
|
547 if (e1 == e2)
|
|
|
548 return 1;
|
|
|
549
|
|
|
550 if (e1->hashval != e2->hashval)
|
|
|
551 return 0;
|
|
|
552
|
|
|
553 if (e1->succ_flags.length () != e2->succ_flags.length ())
|
|
|
554 return 0;
|
|
|
555
|
|
|
556 if (!bitmap_equal_p (e1->succs, e2->succs))
|
|
|
557 return 0;
|
|
|
558
|
|
|
559 if (!inverse_flags (e1, e2))
|
|
|
560 {
|
|
|
561 for (i = 0; i < e1->succ_flags.length (); ++i)
|
|
|
562 if (e1->succ_flags[i] != e2->succ_flags[i])
|
|
|
563 return 0;
|
|
|
564 }
|
|
|
565
|
|
|
566 first1 = bitmap_first_set_bit (e1->bbs);
|
|
|
567 first2 = bitmap_first_set_bit (e2->bbs);
|
|
|
568
|
|
|
569 bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
|
|
|
570 bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
|
|
|
571
|
|
|
572 if (BB_SIZE (bb1) != BB_SIZE (bb2))
|
|
|
573 return 0;
|
|
|
574
|
|
|
575 if (bb1->loop_father != bb2->loop_father)
|
|
|
576 return 0;
|
|
|
577
|
|
|
578 gsi1 = gsi_start_nondebug_bb (bb1);
|
|
|
579 gsi2 = gsi_start_nondebug_bb (bb2);
|
|
|
580 gsi_advance_fw_nondebug_nonlocal (&gsi1);
|
|
|
581 gsi_advance_fw_nondebug_nonlocal (&gsi2);
|
|
|
582 while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
|
|
|
583 {
|
|
|
584 s1 = gsi_stmt (gsi1);
|
|
|
585 s2 = gsi_stmt (gsi2);
|
|
|
586 if (gimple_code (s1) != gimple_code (s2))
|
|
|
587 return 0;
|
|
|
588 if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
|
|
|
589 return 0;
|
|
|
590 gsi_next_nondebug (&gsi1);
|
|
|
591 gsi_next_nondebug (&gsi2);
|
|
|
592 gsi_advance_fw_nondebug_nonlocal (&gsi1);
|
|
|
593 gsi_advance_fw_nondebug_nonlocal (&gsi2);
|
|
|
594 }
|
|
|
595
|
|
|
596 return 1;
|
|
|
597 }
|
|
|
598
|
|
|
599 /* Alloc and init a new SAME_SUCC. */
|
|
|
600
|
|
|
601 static same_succ *
|
|
|
602 same_succ_alloc (void)
|
|
|
603 {
|
|
|
604 same_succ *same = XNEW (struct same_succ);
|
|
|
605
|
|
|
606 same->bbs = BITMAP_ALLOC (NULL);
|
|
|
607 same->succs = BITMAP_ALLOC (NULL);
|
|
|
608 same->inverse = BITMAP_ALLOC (NULL);
|
|
|
609 same->succ_flags.create (10);
|
|
|
610 same->in_worklist = false;
|
|
|
611
|
|
|
612 return same;
|
|
|
613 }
|
|
|
614
|
|
|
615 /* Delete same_succ E. */
|
|
|
616
|
|
|
617 void
|
|
|
618 same_succ::remove (same_succ *e)
|
|
|
619 {
|
|
|
620 BITMAP_FREE (e->bbs);
|
|
|
621 BITMAP_FREE (e->succs);
|
|
|
622 BITMAP_FREE (e->inverse);
|
|
|
623 e->succ_flags.release ();
|
|
|
624
|
|
|
625 XDELETE (e);
|
|
|
626 }
|
|
|
627
|
|
|
628 /* Reset same_succ SAME. */
|
|
|
629
|
|
|
630 static void
|
|
|
631 same_succ_reset (same_succ *same)
|
|
|
632 {
|
|
|
633 bitmap_clear (same->bbs);
|
|
|
634 bitmap_clear (same->succs);
|
|
|
635 bitmap_clear (same->inverse);
|
|
|
636 same->succ_flags.truncate (0);
|
|
|
637 }
|
|
|
638
|
|
|
639 static hash_table<same_succ> *same_succ_htab;
|
|
|
640
|
|
|
641 /* Array that is used to store the edge flags for a successor. */
|
|
|
642
|
|
|
643 static int *same_succ_edge_flags;
|
|
|
644
|
|
|
645 /* Bitmap that is used to mark bbs that are recently deleted. */
|
|
|
646
|
|
|
647 static bitmap deleted_bbs;
|
|
|
648
|
|
|
649 /* Bitmap that is used to mark predecessors of bbs that are
|
|
|
650 deleted. */
|
|
|
651
|
|
|
652 static bitmap deleted_bb_preds;
|
|
|
653
|
|
|
654 /* Prints same_succ_htab to stderr. */
|
|
|
655
|
|
|
656 extern void debug_same_succ (void);
|
|
|
657 DEBUG_FUNCTION void
|
|
|
658 debug_same_succ ( void)
|
|
|
659 {
|
|
|
660 same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
|
|
|
661 }
|
|
|
662
|
|
|
663
|
|
|
664 /* Vector of bbs to process. */
|
|
|
665
|
|
|
666 static vec<same_succ *> worklist;
|
|
|
667
|
|
|
668 /* Prints worklist to FILE. */
|
|
|
669
|
|
|
670 static void
|
|
|
671 print_worklist (FILE *file)
|
|
|
672 {
|
|
|
673 unsigned int i;
|
|
|
674 for (i = 0; i < worklist.length (); ++i)
|
|
|
675 same_succ_print (file, worklist[i]);
|
|
|
676 }
|
|
|
677
|
|
|
678 /* Adds SAME to worklist. */
|
|
|
679
|
|
|
680 static void
|
|
|
681 add_to_worklist (same_succ *same)
|
|
|
682 {
|
|
|
683 if (same->in_worklist)
|
|
|
684 return;
|
|
|
685
|
|
|
686 if (bitmap_count_bits (same->bbs) < 2)
|
|
|
687 return;
|
|
|
688
|
|
|
689 same->in_worklist = true;
|
|
|
690 worklist.safe_push (same);
|
|
|
691 }
|
|
|
692
|
|
|
693 /* Add BB to same_succ_htab. */
|
|
|
694
|
|
|
695 static void
|
|
|
696 find_same_succ_bb (basic_block bb, same_succ **same_p)
|
|
|
697 {
|
|
|
698 unsigned int j;
|
|
|
699 bitmap_iterator bj;
|
|
|
700 same_succ *same = *same_p;
|
|
|
701 same_succ **slot;
|
|
|
702 edge_iterator ei;
|
|
|
703 edge e;
|
|
|
704
|
|
|
705 if (bb == NULL)
|
|
|
706 return;
|
|
|
707 bitmap_set_bit (same->bbs, bb->index);
|
|
|
708 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
709 {
|
|
|
710 int index = e->dest->index;
|
|
|
711 bitmap_set_bit (same->succs, index);
|
|
|
712 same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
|
|
|
713 }
|
|
|
714 EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
|
|
|
715 same->succ_flags.safe_push (same_succ_edge_flags[j]);
|
|
|
716
|
|
|
717 same->hashval = same_succ_hash (same);
|
|
|
718
|
|
|
719 slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
|
|
|
720 if (*slot == NULL)
|
|
|
721 {
|
|
|
722 *slot = same;
|
|
|
723 BB_SAME_SUCC (bb) = same;
|
|
|
724 add_to_worklist (same);
|
|
|
725 *same_p = NULL;
|
|
|
726 }
|
|
|
727 else
|
|
|
728 {
|
|
|
729 bitmap_set_bit ((*slot)->bbs, bb->index);
|
|
|
730 BB_SAME_SUCC (bb) = *slot;
|
|
|
731 add_to_worklist (*slot);
|
|
|
732 if (inverse_flags (same, *slot))
|
|
|
733 bitmap_set_bit ((*slot)->inverse, bb->index);
|
|
|
734 same_succ_reset (same);
|
|
|
735 }
|
|
|
736 }
|
|
|
737
|
|
|
738 /* Find bbs with same successors. */
|
|
|
739
|
|
|
740 static void
|
|
|
741 find_same_succ (void)
|
|
|
742 {
|
|
|
743 same_succ *same = same_succ_alloc ();
|
|
|
744 basic_block bb;
|
|
|
745
|
|
|
746 FOR_EACH_BB_FN (bb, cfun)
|
|
|
747 {
|
|
|
748 find_same_succ_bb (bb, &same);
|
|
|
749 if (same == NULL)
|
|
|
750 same = same_succ_alloc ();
|
|
|
751 }
|
|
|
752
|
|
|
753 same_succ::remove (same);
|
|
|
754 }
|
|
|
755
|
|
|
756 /* Initializes worklist administration. */
|
|
|
757
|
|
|
758 static void
|
|
|
759 init_worklist (void)
|
|
|
760 {
|
|
|
761 alloc_aux_for_blocks (sizeof (struct aux_bb_info));
|
|
|
762 same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
|
|
|
763 same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
|
|
|
764 deleted_bbs = BITMAP_ALLOC (NULL);
|
|
|
765 deleted_bb_preds = BITMAP_ALLOC (NULL);
|
|
|
766 worklist.create (n_basic_blocks_for_fn (cfun));
|
|
|
767 find_same_succ ();
|
|
|
768
|
|
|
769 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
770 {
|
|
|
771 fprintf (dump_file, "initial worklist:\n");
|
|
|
772 print_worklist (dump_file);
|
|
|
773 }
|
|
|
774 }
|
|
|
775
|
|
|
776 /* Deletes worklist administration. */
|
|
|
777
|
|
|
778 static void
|
|
|
779 delete_worklist (void)
|
|
|
780 {
|
|
|
781 free_aux_for_blocks ();
|
|
|
782 delete same_succ_htab;
|
|
|
783 same_succ_htab = NULL;
|
|
|
784 XDELETEVEC (same_succ_edge_flags);
|
|
|
785 same_succ_edge_flags = NULL;
|
|
|
786 BITMAP_FREE (deleted_bbs);
|
|
|
787 BITMAP_FREE (deleted_bb_preds);
|
|
|
788 worklist.release ();
|
|
|
789 }
|
|
|
790
|
|
|
791 /* Mark BB as deleted, and mark its predecessors. */
|
|
|
792
|
|
|
793 static void
|
|
|
794 mark_basic_block_deleted (basic_block bb)
|
|
|
795 {
|
|
|
796 edge e;
|
|
|
797 edge_iterator ei;
|
|
|
798
|
|
|
799 bitmap_set_bit (deleted_bbs, bb->index);
|
|
|
800
|
|
|
801 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
802 bitmap_set_bit (deleted_bb_preds, e->src->index);
|
|
|
803 }
|
|
|
804
|
|
|
805 /* Removes BB from its corresponding same_succ. */
|
|
|
806
|
|
|
807 static void
|
|
|
808 same_succ_flush_bb (basic_block bb)
|
|
|
809 {
|
|
|
810 same_succ *same = BB_SAME_SUCC (bb);
|
|
|
811 if (! same)
|
|
|
812 return;
|
|
|
813
|
|
|
814 BB_SAME_SUCC (bb) = NULL;
|
|
|
815 if (bitmap_single_bit_set_p (same->bbs))
|
|
|
816 same_succ_htab->remove_elt_with_hash (same, same->hashval);
|
|
|
817 else
|
|
|
818 bitmap_clear_bit (same->bbs, bb->index);
|
|
|
819 }
|
|
|
820
|
|
|
821 /* Removes all bbs in BBS from their corresponding same_succ. */
|
|
|
822
|
|
|
823 static void
|
|
|
824 same_succ_flush_bbs (bitmap bbs)
|
|
|
825 {
|
|
|
826 unsigned int i;
|
|
|
827 bitmap_iterator bi;
|
|
|
828
|
|
|
829 EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
|
|
|
830 same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
|
|
|
831 }
|
|
|
832
|
|
|
833 /* Release the last vdef in BB, either normal or phi result. */
|
|
|
834
|
|
|
835 static void
|
|
|
836 release_last_vdef (basic_block bb)
|
|
|
837 {
|
|
|
838 for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
|
|
|
839 gsi_prev_nondebug (&i))
|
|
|
840 {
|
|
|
841 gimple *stmt = gsi_stmt (i);
|
|
|
842 if (gimple_vdef (stmt) == NULL_TREE)
|
|
|
843 continue;
|
|
|
844
|
|
|
845 mark_virtual_operand_for_renaming (gimple_vdef (stmt));
|
|
|
846 return;
|
|
|
847 }
|
|
|
848
|
|
|
849 for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
|
|
|
850 gsi_next (&i))
|
|
|
851 {
|
|
|
852 gphi *phi = i.phi ();
|
|
|
853 tree res = gimple_phi_result (phi);
|
|
|
854
|
|
|
855 if (!virtual_operand_p (res))
|
|
|
856 continue;
|
|
|
857
|
|
|
858 mark_virtual_phi_result_for_renaming (phi);
|
|
|
859 return;
|
|
|
860 }
|
|
|
861 }
|
|
|
862
|
|
|
863 /* For deleted_bb_preds, find bbs with same successors. */
|
|
|
864
|
|
|
865 static void
|
|
|
866 update_worklist (void)
|
|
|
867 {
|
|
|
868 unsigned int i;
|
|
|
869 bitmap_iterator bi;
|
|
|
870 basic_block bb;
|
|
|
871 same_succ *same;
|
|
|
872
|
|
|
873 bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
|
|
|
874 bitmap_clear (deleted_bbs);
|
|
|
875
|
|
|
876 bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
|
|
|
877 same_succ_flush_bbs (deleted_bb_preds);
|
|
|
878
|
|
|
879 same = same_succ_alloc ();
|
|
|
880 EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
|
|
|
881 {
|
|
|
882 bb = BASIC_BLOCK_FOR_FN (cfun, i);
|
|
|
883 gcc_assert (bb != NULL);
|
|
|
884 find_same_succ_bb (bb, &same);
|
|
|
885 if (same == NULL)
|
|
|
886 same = same_succ_alloc ();
|
|
|
887 }
|
|
|
888 same_succ::remove (same);
|
|
|
889 bitmap_clear (deleted_bb_preds);
|
|
|
890 }
|
|
|
891
|
|
|
892 /* Prints cluster C to FILE. */
|
|
|
893
|
|
|
894 static void
|
|
|
895 print_cluster (FILE *file, bb_cluster *c)
|
|
|
896 {
|
|
|
897 if (c == NULL)
|
|
|
898 return;
|
|
|
899 bitmap_print (file, c->bbs, "bbs:", "\n");
|
|
|
900 bitmap_print (file, c->preds, "preds:", "\n");
|
|
|
901 }
|
|
|
902
|
|
|
903 /* Prints cluster C to stderr. */
|
|
|
904
|
|
|
905 extern void debug_cluster (bb_cluster *);
|
|
|
906 DEBUG_FUNCTION void
|
|
|
907 debug_cluster (bb_cluster *c)
|
|
|
908 {
|
|
|
909 print_cluster (stderr, c);
|
|
|
910 }
|
|
|
911
|
|
|
912 /* Update C->rep_bb, given that BB is added to the cluster. */
|
|
|
913
|
|
|
914 static void
|
|
|
915 update_rep_bb (bb_cluster *c, basic_block bb)
|
|
|
916 {
|
|
|
917 /* Initial. */
|
|
|
918 if (c->rep_bb == NULL)
|
|
|
919 {
|
|
|
920 c->rep_bb = bb;
|
|
|
921 return;
|
|
|
922 }
|
|
|
923
|
|
|
924 /* Current needs no deps, keep it. */
|
|
|
925 if (BB_DEP_BB (c->rep_bb) == NULL)
|
|
|
926 return;
|
|
|
927
|
|
|
928 /* Bb needs no deps, change rep_bb. */
|
|
|
929 if (BB_DEP_BB (bb) == NULL)
|
|
|
930 {
|
|
|
931 c->rep_bb = bb;
|
|
|
932 return;
|
|
|
933 }
|
|
|
934
|
|
|
935 /* Bb needs last deps earlier than current, change rep_bb. A potential
|
|
|
936 problem with this, is that the first deps might also be earlier, which
|
|
|
937 would mean we prefer longer lifetimes for the deps. To be able to check
|
|
|
938 for this, we would have to trace BB_FIRST_DEP_BB as well, besides
|
|
|
939 BB_DEP_BB, which is really BB_LAST_DEP_BB.
|
|
|
940 The benefit of choosing the bb with last deps earlier, is that it can
|
|
|
941 potentially be used as replacement for more bbs. */
|
|
|
942 if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
|
|
|
943 c->rep_bb = bb;
|
|
|
944 }
|
|
|
945
|
|
|
946 /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
|
|
|
947
|
|
|
948 static void
|
|
|
949 add_bb_to_cluster (bb_cluster *c, basic_block bb)
|
|
|
950 {
|
|
|
951 edge e;
|
|
|
952 edge_iterator ei;
|
|
|
953
|
|
|
954 bitmap_set_bit (c->bbs, bb->index);
|
|
|
955
|
|
|
956 FOR_EACH_EDGE (e, ei, bb->preds)
|
|
|
957 bitmap_set_bit (c->preds, e->src->index);
|
|
|
958
|
|
|
959 update_rep_bb (c, bb);
|
|
|
960 }
|
|
|
961
|
|
|
962 /* Allocate and init new cluster. */
|
|
|
963
|
|
|
964 static bb_cluster *
|
|
|
965 new_cluster (void)
|
|
|
966 {
|
|
|
967 bb_cluster *c;
|
|
|
968 c = XCNEW (bb_cluster);
|
|
|
969 c->bbs = BITMAP_ALLOC (NULL);
|
|
|
970 c->preds = BITMAP_ALLOC (NULL);
|
|
|
971 c->rep_bb = NULL;
|
|
|
972 return c;
|
|
|
973 }
|
|
|
974
|
|
|
975 /* Delete clusters. */
|
|
|
976
|
|
|
977 static void
|
|
|
978 delete_cluster (bb_cluster *c)
|
|
|
979 {
|
|
|
980 if (c == NULL)
|
|
|
981 return;
|
|
|
982 BITMAP_FREE (c->bbs);
|
|
|
983 BITMAP_FREE (c->preds);
|
|
|
984 XDELETE (c);
|
|
|
985 }
|
|
|
986
|
|
|
987
|
|
|
988 /* Array that contains all clusters. */
|
|
|
989
|
|
|
990 static vec<bb_cluster *> all_clusters;
|
|
|
991
|
|
|
992 /* Allocate all cluster vectors. */
|
|
|
993
|
|
|
994 static void
|
|
|
995 alloc_cluster_vectors (void)
|
|
|
996 {
|
|
|
997 all_clusters.create (n_basic_blocks_for_fn (cfun));
|
|
|
998 }
|
|
|
999
|
|
|
1000 /* Reset all cluster vectors. */
|
|
|
1001
|
|
|
1002 static void
|
|
|
1003 reset_cluster_vectors (void)
|
|
|
1004 {
|
|
|
1005 unsigned int i;
|
|
|
1006 basic_block bb;
|
|
|
1007 for (i = 0; i < all_clusters.length (); ++i)
|
|
|
1008 delete_cluster (all_clusters[i]);
|
|
|
1009 all_clusters.truncate (0);
|
|
|
1010 FOR_EACH_BB_FN (bb, cfun)
|
|
|
1011 BB_CLUSTER (bb) = NULL;
|
|
|
1012 }
|
|
|
1013
|
|
|
1014 /* Delete all cluster vectors. */
|
|
|
1015
|
|
|
1016 static void
|
|
|
1017 delete_cluster_vectors (void)
|
|
|
1018 {
|
|
|
1019 unsigned int i;
|
|
|
1020 for (i = 0; i < all_clusters.length (); ++i)
|
|
|
1021 delete_cluster (all_clusters[i]);
|
|
|
1022 all_clusters.release ();
|
|
|
1023 }
|
|
|
1024
|
|
|
1025 /* Merge cluster C2 into C1. */
|
|
|
1026
|
|
|
1027 static void
|
|
|
1028 merge_clusters (bb_cluster *c1, bb_cluster *c2)
|
|
|
1029 {
|
|
|
1030 bitmap_ior_into (c1->bbs, c2->bbs);
|
|
|
1031 bitmap_ior_into (c1->preds, c2->preds);
|
|
|
1032 }
|
|
|
1033
|
|
|
1034 /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
|
|
|
1035 all_clusters, or merge c with existing cluster. */
|
|
|
1036
|
|
|
1037 static void
|
|
|
1038 set_cluster (basic_block bb1, basic_block bb2)
|
|
|
1039 {
|
|
|
1040 basic_block merge_bb, other_bb;
|
|
|
1041 bb_cluster *merge, *old, *c;
|
|
|
1042
|
|
|
1043 if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
|
|
|
1044 {
|
|
|
1045 c = new_cluster ();
|
|
|
1046 add_bb_to_cluster (c, bb1);
|
|
|
1047 add_bb_to_cluster (c, bb2);
|
|
|
1048 BB_CLUSTER (bb1) = c;
|
|
|
1049 BB_CLUSTER (bb2) = c;
|
|
|
1050 c->index = all_clusters.length ();
|
|
|
1051 all_clusters.safe_push (c);
|
|
|
1052 }
|
|
|
1053 else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
|
|
|
1054 {
|
|
|
1055 merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
|
|
|
1056 other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
|
|
|
1057 merge = BB_CLUSTER (merge_bb);
|
|
|
1058 add_bb_to_cluster (merge, other_bb);
|
|
|
1059 BB_CLUSTER (other_bb) = merge;
|
|
|
1060 }
|
|
|
1061 else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
|
|
|
1062 {
|
|
|
1063 unsigned int i;
|
|
|
1064 bitmap_iterator bi;
|
|
|
1065
|
|
|
1066 old = BB_CLUSTER (bb2);
|
|
|
1067 merge = BB_CLUSTER (bb1);
|
|
|
1068 merge_clusters (merge, old);
|
|
|
1069 EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
|
|
|
1070 BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
|
|
|
1071 all_clusters[old->index] = NULL;
|
|
|
1072 update_rep_bb (merge, old->rep_bb);
|
|
|
1073 delete_cluster (old);
|
|
|
1074 }
|
|
|
1075 else
|
|
|
1076 gcc_unreachable ();
|
|
|
1077 }
|
|
|
1078
|
|
|
1079 /* Return true if gimple operands T1 and T2 have the same value. */
|
|
|
1080
|
|
|
1081 static bool
|
|
|
1082 gimple_operand_equal_value_p (tree t1, tree t2)
|
|
|
1083 {
|
|
|
1084 if (t1 == t2)
|
|
|
1085 return true;
|
|
|
1086
|
|
|
1087 if (t1 == NULL_TREE
|
|
|
1088 || t2 == NULL_TREE)
|
|
|
1089 return false;
|
|
|
1090
|
|
|
1091 if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
|
|
|
1092 return true;
|
|
|
1093
|
|
|
1094 return gvn_uses_equal (t1, t2);
|
|
|
1095 }
|
|
|
1096
|
|
|
1097 /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
|
|
|
1098 gimple_bb (s2) are members of SAME_SUCC. */
|
|
|
1099
|
|
|
1100 static bool
|
|
|
1101 gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
|
|
|
1102 {
|
|
|
1103 unsigned int i;
|
|
|
1104 tree lhs1, lhs2;
|
|
|
1105 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
|
|
|
1106 tree t1, t2;
|
|
|
1107 bool inv_cond;
|
|
|
1108 enum tree_code code1, code2;
|
|
|
1109
|
|
|
1110 if (gimple_code (s1) != gimple_code (s2))
|
|
|
1111 return false;
|
|
|
1112
|
|
|
1113 switch (gimple_code (s1))
|
|
|
1114 {
|
|
|
1115 case GIMPLE_CALL:
|
|
|
1116 if (!gimple_call_same_target_p (s1, s2))
|
|
|
1117 return false;
|
|
|
1118
|
|
|
1119 t1 = gimple_call_chain (s1);
|
|
|
1120 t2 = gimple_call_chain (s2);
|
|
|
1121 if (!gimple_operand_equal_value_p (t1, t2))
|
|
|
1122 return false;
|
|
|
1123
|
|
|
1124 if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
|
|
|
1125 return false;
|
|
|
1126
|
|
|
1127 for (i = 0; i < gimple_call_num_args (s1); ++i)
|
|
|
1128 {
|
|
|
1129 t1 = gimple_call_arg (s1, i);
|
|
|
1130 t2 = gimple_call_arg (s2, i);
|
|
|
1131 if (!gimple_operand_equal_value_p (t1, t2))
|
|
|
1132 return false;
|
|
|
1133 }
|
|
|
1134
|
|
|
1135 lhs1 = gimple_get_lhs (s1);
|
|
|
1136 lhs2 = gimple_get_lhs (s2);
|
|
|
1137 if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
|
|
|
1138 return true;
|
|
|
1139 if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
|
|
|
1140 return false;
|
|
|
1141 if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
|
|
|
1142 return vn_valueize (lhs1) == vn_valueize (lhs2);
|
|
|
1143 return operand_equal_p (lhs1, lhs2, 0);
|
|
|
1144
|
|
|
1145 case GIMPLE_ASSIGN:
|
|
|
1146 lhs1 = gimple_get_lhs (s1);
|
|
|
1147 lhs2 = gimple_get_lhs (s2);
|
|
|
1148 if (TREE_CODE (lhs1) != SSA_NAME
|
|
|
1149 && TREE_CODE (lhs2) != SSA_NAME)
|
|
|
1150 return (operand_equal_p (lhs1, lhs2, 0)
|
|
|
1151 && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
|
|
|
1152 gimple_assign_rhs1 (s2)));
|
|
|
1153 else if (TREE_CODE (lhs1) == SSA_NAME
|
|
|
1154 && TREE_CODE (lhs2) == SSA_NAME)
|
|
|
1155 return operand_equal_p (gimple_assign_rhs1 (s1),
|
|
|
1156 gimple_assign_rhs1 (s2), 0);
|
|
|
1157 return false;
|
|
|
1158
|
|
|
1159 case GIMPLE_COND:
|
|
|
1160 t1 = gimple_cond_lhs (s1);
|
|
|
1161 t2 = gimple_cond_lhs (s2);
|
|
|
1162 if (!gimple_operand_equal_value_p (t1, t2))
|
|
|
1163 return false;
|
|
|
1164
|
|
|
1165 t1 = gimple_cond_rhs (s1);
|
|
|
1166 t2 = gimple_cond_rhs (s2);
|
|
|
1167 if (!gimple_operand_equal_value_p (t1, t2))
|
|
|
1168 return false;
|
|
|
1169
|
|
|
1170 code1 = gimple_expr_code (s1);
|
|
|
1171 code2 = gimple_expr_code (s2);
|
|
|
1172 inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
|
|
|
1173 != bitmap_bit_p (same_succ->inverse, bb2->index));
|
|
|
1174 if (inv_cond)
|
|
|
1175 {
|
|
|
1176 bool honor_nans = HONOR_NANS (t1);
|
|
|
1177 code2 = invert_tree_comparison (code2, honor_nans);
|
|
|
1178 }
|
|
|
1179 return code1 == code2;
|
|
|
1180
|
|
|
1181 default:
|
|
|
1182 return false;
|
|
|
1183 }
|
|
|
1184 }
|
|
|
1185
|
|
|
1186 /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
|
|
|
1187 Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
|
|
|
1188 processed statements. */
|
|
|
1189
|
|
|
1190 static void
|
|
|
1191 gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
|
|
|
1192 bool *vuse_escaped)
|
|
|
1193 {
|
|
|
1194 gimple *stmt;
|
|
|
1195 tree lvuse;
|
|
|
1196
|
|
|
1197 while (true)
|
|
|
1198 {
|
|
|
1199 if (gsi_end_p (*gsi))
|
|
|
1200 return;
|
|
|
1201 stmt = gsi_stmt (*gsi);
|
|
|
1202
|
|
|
1203 lvuse = gimple_vuse (stmt);
|
|
|
1204 if (lvuse != NULL_TREE)
|
|
|
1205 {
|
|
|
1206 *vuse = lvuse;
|
|
|
1207 if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
|
|
|
1208 *vuse_escaped = true;
|
|
|
1209 }
|
|
|
1210
|
|
|
1211 if (!stmt_local_def (stmt))
|
|
|
1212 return;
|
|
|
1213 gsi_prev_nondebug (gsi);
|
|
|
1214 }
|
|
|
1215 }
|
|
|
1216
|
|
|
1217 /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
|
|
|
1218 STMT2 are allowed to be merged. */
|
|
|
1219
|
|
|
1220 static bool
|
|
|
1221 merge_stmts_p (gimple *stmt1, gimple *stmt2)
|
|
|
1222 {
|
|
|
1223 /* What could be better than this here is to blacklist the bb
|
|
|
1224 containing the stmt, when encountering the stmt f.i. in
|
|
|
1225 same_succ_hash. */
|
|
|
1226 if (is_tm_ending (stmt1))
|
|
|
1227 return false;
|
|
|
1228
|
|
|
1229 /* Verify EH landing pads. */
|
|
|
1230 if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
|
|
|
1231 return false;
|
|
|
1232
|
|
|
1233 if (is_gimple_call (stmt1)
|
|
|
1234 && gimple_call_internal_p (stmt1))
|
|
|
1235 switch (gimple_call_internal_fn (stmt1))
|
|
|
1236 {
|
|
|
1237 case IFN_UBSAN_NULL:
|
|
|
1238 case IFN_UBSAN_BOUNDS:
|
|
|
1239 case IFN_UBSAN_VPTR:
|
|
|
1240 case IFN_UBSAN_CHECK_ADD:
|
|
|
1241 case IFN_UBSAN_CHECK_SUB:
|
|
|
1242 case IFN_UBSAN_CHECK_MUL:
|
|
|
1243 case IFN_UBSAN_OBJECT_SIZE:
|
|
|
1244 case IFN_UBSAN_PTR:
|
|
|
1245 case IFN_ASAN_CHECK:
|
|
|
1246 /* For these internal functions, gimple_location is an implicit
|
|
|
1247 parameter, which will be used explicitly after expansion.
|
|
|
1248 Merging these statements may cause confusing line numbers in
|
|
|
1249 sanitizer messages. */
|
|
|
1250 return gimple_location (stmt1) == gimple_location (stmt2);
|
|
|
1251 default:
|
|
|
1252 break;
|
|
|
1253 }
|
|
|
1254
|
|
|
1255 return true;
|
|
|
1256 }
|
|
|
1257
|
|
|
1258 /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
|
|
|
1259 clusters them. */
|
|
|
1260
|
|
|
1261 static void
|
|
|
1262 find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
|
|
|
1263 {
|
|
|
1264 gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
|
|
|
1265 gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
|
|
|
1266 tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
|
|
|
1267 bool vuse_escaped = false;
|
|
|
1268
|
|
|
1269 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
|
|
|
1270 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
|
|
|
1271
|
|
|
1272 while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
|
|
|
1273 {
|
|
|
1274 gimple *stmt1 = gsi_stmt (gsi1);
|
|
|
1275 gimple *stmt2 = gsi_stmt (gsi2);
|
|
|
1276
|
|
|
1277 if (gimple_code (stmt1) == GIMPLE_LABEL
|
|
|
1278 && gimple_code (stmt2) == GIMPLE_LABEL)
|
|
|
1279 break;
|
|
|
1280
|
|
|
1281 if (!gimple_equal_p (same_succ, stmt1, stmt2))
|
|
|
1282 return;
|
|
|
1283
|
|
|
1284 if (!merge_stmts_p (stmt1, stmt2))
|
|
|
1285 return;
|
|
|
1286
|
|
|
1287 gsi_prev_nondebug (&gsi1);
|
|
|
1288 gsi_prev_nondebug (&gsi2);
|
|
|
1289 gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
|
|
|
1290 gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
|
|
|
1291 }
|
|
|
1292
|
|
|
1293 while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
|
|
|
1294 {
|
|
|
1295 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
|
|
|
1296 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
|
|
|
1297 return;
|
|
|
1298 gsi_prev (&gsi1);
|
|
|
1299 }
|
|
|
1300 while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
|
|
|
1301 {
|
|
|
1302 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
|
|
|
1303 if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
|
|
|
1304 return;
|
|
|
1305 gsi_prev (&gsi2);
|
|
|
1306 }
|
|
|
1307 if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
|
|
|
1308 return;
|
|
|
1309
|
|
|
1310 /* If the incoming vuses are not the same, and the vuse escaped into an
|
|
|
1311 SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
|
|
|
1312 which potentially means the semantics of one of the blocks will be changed.
|
|
|
1313 TODO: make this check more precise. */
|
|
|
1314 if (vuse_escaped && vuse1 != vuse2)
|
|
|
1315 return;
|
|
|
1316
|
|
|
1317 if (dump_file)
|
|
|
1318 fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
|
|
|
1319 bb1->index, bb2->index);
|
|
|
1320
|
|
|
1321 set_cluster (bb1, bb2);
|
|
|
1322 }
|
|
|
1323
|
|
|
1324 /* Returns whether for all phis in DEST the phi alternatives for E1 and
|
|
|
1325 E2 are equal. */
|
|
|
1326
|
|
|
1327 static bool
|
|
|
1328 same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
|
|
|
1329 {
|
|
|
1330 int n1 = e1->dest_idx, n2 = e2->dest_idx;
|
|
|
1331 gphi_iterator gsi;
|
|
|
1332
|
|
|
1333 for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1334 {
|
|
|
1335 gphi *phi = gsi.phi ();
|
|
|
1336 tree lhs = gimple_phi_result (phi);
|
|
|
1337 tree val1 = gimple_phi_arg_def (phi, n1);
|
|
|
1338 tree val2 = gimple_phi_arg_def (phi, n2);
|
|
|
1339
|
|
|
1340 if (virtual_operand_p (lhs))
|
|
|
1341 continue;
|
|
|
1342
|
|
|
1343 if (operand_equal_for_phi_arg_p (val1, val2))
|
|
|
1344 continue;
|
|
|
1345 if (gvn_uses_equal (val1, val2))
|
|
|
1346 continue;
|
|
|
1347
|
|
|
1348 return false;
|
|
|
1349 }
|
|
|
1350
|
|
|
1351 return true;
|
|
|
1352 }
|
|
|
1353
|
|
|
1354 /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
|
|
|
1355 phi alternatives for BB1 and BB2 are equal. */
|
|
|
1356
|
|
|
1357 static bool
|
|
|
1358 same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
|
|
|
1359 {
|
|
|
1360 unsigned int s;
|
|
|
1361 bitmap_iterator bs;
|
|
|
1362 edge e1, e2;
|
|
|
1363 basic_block succ;
|
|
|
1364
|
|
|
1365 EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
|
|
|
1366 {
|
|
|
1367 succ = BASIC_BLOCK_FOR_FN (cfun, s);
|
|
|
1368 e1 = find_edge (bb1, succ);
|
|
|
1369 e2 = find_edge (bb2, succ);
|
|
|
1370 if (e1->flags & EDGE_COMPLEX
|
|
|
1371 || e2->flags & EDGE_COMPLEX)
|
|
|
1372 return false;
|
|
|
1373
|
|
|
1374 /* For all phis in bb, the phi alternatives for e1 and e2 need to have
|
|
|
1375 the same value. */
|
|
|
1376 if (!same_phi_alternatives_1 (succ, e1, e2))
|
|
|
1377 return false;
|
|
|
1378 }
|
|
|
1379
|
|
|
1380 return true;
|
|
|
1381 }
|
|
|
1382
|
|
|
1383 /* Return true if BB has non-vop phis. */
|
|
|
1384
|
|
|
1385 static bool
|
|
|
1386 bb_has_non_vop_phi (basic_block bb)
|
|
|
1387 {
|
|
|
1388 gimple_seq phis = phi_nodes (bb);
|
|
|
1389 gimple *phi;
|
|
|
1390
|
|
|
1391 if (phis == NULL)
|
|
|
1392 return false;
|
|
|
1393
|
|
|
1394 if (!gimple_seq_singleton_p (phis))
|
|
|
1395 return true;
|
|
|
1396
|
|
|
1397 phi = gimple_seq_first_stmt (phis);
|
|
|
1398 return !virtual_operand_p (gimple_phi_result (phi));
|
|
|
1399 }
|
|
|
1400
|
|
|
1401 /* Returns true if redirecting the incoming edges of FROM to TO maintains the
|
|
|
1402 invariant that uses in FROM are dominates by their defs. */
|
|
|
1403
|
|
|
1404 static bool
|
|
|
1405 deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
|
|
|
1406 {
|
|
|
1407 basic_block cd, dep_bb = BB_DEP_BB (to);
|
|
|
1408 edge_iterator ei;
|
|
|
1409 edge e;
|
|
|
1410
|
|
|
1411 if (dep_bb == NULL)
|
|
|
1412 return true;
|
|
|
1413
|
|
|
1414 bitmap from_preds = BITMAP_ALLOC (NULL);
|
|
|
1415 FOR_EACH_EDGE (e, ei, from->preds)
|
|
|
1416 bitmap_set_bit (from_preds, e->src->index);
|
|
|
1417 cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
|
|
|
1418 BITMAP_FREE (from_preds);
|
|
|
1419
|
|
|
1420 return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
|
|
|
1421 }
|
|
|
1422
|
|
|
1423 /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
|
|
|
1424 replacement bb) and vice versa maintains the invariant that uses in the
|
|
|
1425 replacement are dominates by their defs. */
|
|
|
1426
|
|
|
1427 static bool
|
|
|
1428 deps_ok_for_redirect (basic_block bb1, basic_block bb2)
|
|
|
1429 {
|
|
|
1430 if (BB_CLUSTER (bb1) != NULL)
|
|
|
1431 bb1 = BB_CLUSTER (bb1)->rep_bb;
|
|
|
1432
|
|
|
1433 if (BB_CLUSTER (bb2) != NULL)
|
|
|
1434 bb2 = BB_CLUSTER (bb2)->rep_bb;
|
|
|
1435
|
|
|
1436 return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
|
|
|
1437 && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
|
|
|
1438 }
|
|
|
1439
|
|
|
1440 /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
|
|
|
1441
|
|
|
1442 static void
|
|
|
1443 find_clusters_1 (same_succ *same_succ)
|
|
|
1444 {
|
|
|
1445 basic_block bb1, bb2;
|
|
|
1446 unsigned int i, j;
|
|
|
1447 bitmap_iterator bi, bj;
|
|
|
1448 int nr_comparisons;
|
|
|
1449 int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
|
|
|
1450
|
|
|
1451 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
|
|
|
1452 {
|
|
|
1453 bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
|
|
|
1454
|
|
|
1455 /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
|
|
|
1456 phi-nodes in bb1 and bb2, with the same alternatives for the same
|
|
|
1457 preds. */
|
|
|
1458 if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1))
|
|
|
1459 continue;
|
|
|
1460
|
|
|
1461 nr_comparisons = 0;
|
|
|
1462 EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
|
|
|
1463 {
|
|
|
1464 bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
|
|
|
1465
|
|
|
1466 if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2))
|
|
|
1467 continue;
|
|
|
1468
|
|
|
1469 if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
|
|
|
1470 continue;
|
|
|
1471
|
|
|
1472 /* Limit quadratic behavior. */
|
|
|
1473 nr_comparisons++;
|
|
|
1474 if (nr_comparisons > max_comparisons)
|
|
|
1475 break;
|
|
|
1476
|
|
|
1477 /* This is a conservative dependency check. We could test more
|
|
|
1478 precise for allowed replacement direction. */
|
|
|
1479 if (!deps_ok_for_redirect (bb1, bb2))
|
|
|
1480 continue;
|
|
|
1481
|
|
|
1482 if (!(same_phi_alternatives (same_succ, bb1, bb2)))
|
|
|
1483 continue;
|
|
|
1484
|
|
|
1485 find_duplicate (same_succ, bb1, bb2);
|
|
|
1486 }
|
|
|
1487 }
|
|
|
1488 }
|
|
|
1489
|
|
|
1490 /* Find clusters of bbs which can be merged. */
|
|
|
1491
|
|
|
1492 static void
|
|
|
1493 find_clusters (void)
|
|
|
1494 {
|
|
|
1495 same_succ *same;
|
|
|
1496
|
|
|
1497 while (!worklist.is_empty ())
|
|
|
1498 {
|
|
|
1499 same = worklist.pop ();
|
|
|
1500 same->in_worklist = false;
|
|
|
1501 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1502 {
|
|
|
1503 fprintf (dump_file, "processing worklist entry\n");
|
|
|
1504 same_succ_print (dump_file, same);
|
|
|
1505 }
|
|
|
1506 find_clusters_1 (same);
|
|
|
1507 }
|
|
|
1508 }
|
|
|
1509
|
|
|
1510 /* Returns the vop phi of BB, if any. */
|
|
|
1511
|
|
|
1512 static gphi *
|
|
|
1513 vop_phi (basic_block bb)
|
|
|
1514 {
|
|
|
1515 gphi *stmt;
|
|
|
1516 gphi_iterator gsi;
|
|
|
1517 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1518 {
|
|
|
1519 stmt = gsi.phi ();
|
|
|
1520 if (! virtual_operand_p (gimple_phi_result (stmt)))
|
|
|
1521 continue;
|
|
|
1522 return stmt;
|
|
|
1523 }
|
|
|
1524 return NULL;
|
|
|
1525 }
|
|
|
1526
|
|
|
1527 /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
|
|
|
1528
|
|
|
1529 static void
|
|
|
1530 replace_block_by (basic_block bb1, basic_block bb2)
|
|
|
1531 {
|
|
|
1532 edge pred_edge;
|
|
|
1533 edge e1, e2;
|
|
|
1534 edge_iterator ei;
|
|
|
1535 unsigned int i;
|
|
|
1536 gphi *bb2_phi;
|
|
|
1537
|
|
|
1538 bb2_phi = vop_phi (bb2);
|
|
|
1539
|
|
|
1540 /* Mark the basic block as deleted. */
|
|
|
1541 mark_basic_block_deleted (bb1);
|
|
|
1542
|
|
|
1543 /* Redirect the incoming edges of bb1 to bb2. */
|
|
|
1544 for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
|
|
|
1545 {
|
|
|
1546 pred_edge = EDGE_PRED (bb1, i - 1);
|
|
|
1547 pred_edge = redirect_edge_and_branch (pred_edge, bb2);
|
|
|
1548 gcc_assert (pred_edge != NULL);
|
|
|
1549
|
|
|
1550 if (bb2_phi == NULL)
|
|
|
1551 continue;
|
|
|
1552
|
|
|
1553 /* The phi might have run out of capacity when the redirect added an
|
|
|
1554 argument, which means it could have been replaced. Refresh it. */
|
|
|
1555 bb2_phi = vop_phi (bb2);
|
|
|
1556
|
|
|
1557 add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
|
|
|
1558 pred_edge, UNKNOWN_LOCATION);
|
|
|
1559 }
|
|
|
1560
|
|
|
1561 bb2->count += bb1->count;
|
|
|
1562
|
|
|
1563 /* Merge the outgoing edge counts from bb1 onto bb2. */
|
|
|
1564 profile_count out_sum = profile_count::zero ();
|
|
|
1565 int out_freq_sum = 0;
|
|
|
1566
|
|
|
1567 /* Recompute the edge probabilities from the new merged edge count.
|
|
|
1568 Use the sum of the new merged edge counts computed above instead
|
|
|
1569 of bb2's merged count, in case there are profile count insanities
|
|
|
1570 making the bb count inconsistent with the edge weights. */
|
|
|
1571 FOR_EACH_EDGE (e1, ei, bb1->succs)
|
|
|
1572 {
|
|
|
1573 if (e1->count ().initialized_p ())
|
|
|
1574 out_sum += e1->count ();
|
|
|
1575 out_freq_sum += EDGE_FREQUENCY (e1);
|
|
|
1576 }
|
|
|
1577 FOR_EACH_EDGE (e1, ei, bb2->succs)
|
|
|
1578 {
|
|
|
1579 if (e1->count ().initialized_p ())
|
|
|
1580 out_sum += e1->count ();
|
|
|
1581 out_freq_sum += EDGE_FREQUENCY (e1);
|
|
|
1582 }
|
|
|
1583
|
|
|
1584 FOR_EACH_EDGE (e1, ei, bb1->succs)
|
|
|
1585 {
|
|
|
1586 e2 = find_edge (bb2, e1->dest);
|
|
|
1587 gcc_assert (e2);
|
|
|
1588 if (out_sum > 0 && e2->count ().initialized_p ())
|
|
|
1589 {
|
|
|
1590 e2->probability = e2->count ().probability_in (bb2->count);
|
|
|
1591 }
|
|
|
1592 else if (bb1->frequency && bb2->frequency)
|
|
|
1593 e2->probability = e1->probability;
|
|
|
1594 else if (bb2->frequency && !bb1->frequency)
|
|
|
1595 ;
|
|
|
1596 else if (out_freq_sum)
|
|
|
1597 e2->probability = profile_probability::from_reg_br_prob_base
|
|
|
1598 (GCOV_COMPUTE_SCALE (EDGE_FREQUENCY (e1)
|
|
|
1599 + EDGE_FREQUENCY (e2),
|
|
|
1600 out_freq_sum));
|
|
|
1601 out_sum += e2->count ();
|
|
|
1602 }
|
|
|
1603 bb2->frequency += bb1->frequency;
|
|
|
1604 if (bb2->frequency > BB_FREQ_MAX)
|
|
|
1605 bb2->frequency = BB_FREQ_MAX;
|
|
|
1606
|
|
|
1607 /* Move over any user labels from bb1 after the bb2 labels. */
|
|
|
1608 gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
|
|
|
1609 if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
|
|
|
1610 {
|
|
|
1611 gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
|
|
|
1612 while (!gsi_end_p (gsi1)
|
|
|
1613 && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
|
|
|
1614 {
|
|
|
1615 tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
|
|
|
1616 gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
|
|
|
1617 if (DECL_ARTIFICIAL (label))
|
|
|
1618 gsi_next (&gsi1);
|
|
|
1619 else
|
|
|
1620 gsi_move_before (&gsi1, &gsi2);
|
|
|
1621 }
|
|
|
1622 }
|
|
|
1623
|
|
|
1624 /* Clear range info from all stmts in BB2 -- this transformation
|
|
|
1625 could make them out of date. */
|
|
|
1626 reset_flow_sensitive_info_in_bb (bb2);
|
|
|
1627
|
|
|
1628 /* Do updates that use bb1, before deleting bb1. */
|
|
|
1629 release_last_vdef (bb1);
|
|
|
1630 same_succ_flush_bb (bb1);
|
|
|
1631
|
|
|
1632 delete_basic_block (bb1);
|
|
|
1633 }
|
|
|
1634
|
|
|
1635 /* Bbs for which update_debug_stmt need to be called. */
|
|
|
1636
|
|
|
1637 static bitmap update_bbs;
|
|
|
1638
|
|
|
1639 /* For each cluster in all_clusters, merge all cluster->bbs. Returns
|
|
|
1640 number of bbs removed. */
|
|
|
1641
|
|
|
1642 static int
|
|
|
1643 apply_clusters (void)
|
|
|
1644 {
|
|
|
1645 basic_block bb1, bb2;
|
|
|
1646 bb_cluster *c;
|
|
|
1647 unsigned int i, j;
|
|
|
1648 bitmap_iterator bj;
|
|
|
1649 int nr_bbs_removed = 0;
|
|
|
1650
|
|
|
1651 for (i = 0; i < all_clusters.length (); ++i)
|
|
|
1652 {
|
|
|
1653 c = all_clusters[i];
|
|
|
1654 if (c == NULL)
|
|
|
1655 continue;
|
|
|
1656
|
|
|
1657 bb2 = c->rep_bb;
|
|
|
1658 bitmap_set_bit (update_bbs, bb2->index);
|
|
|
1659
|
|
|
1660 bitmap_clear_bit (c->bbs, bb2->index);
|
|
|
1661 EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
|
|
|
1662 {
|
|
|
1663 bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
|
|
|
1664 bitmap_clear_bit (update_bbs, bb1->index);
|
|
|
1665
|
|
|
1666 replace_block_by (bb1, bb2);
|
|
|
1667 nr_bbs_removed++;
|
|
|
1668 }
|
|
|
1669 }
|
|
|
1670
|
|
|
1671 return nr_bbs_removed;
|
|
|
1672 }
|
|
|
1673
|
|
|
1674 /* Resets debug statement STMT if it has uses that are not dominated by their
|
|
|
1675 defs. */
|
|
|
1676
|
|
|
1677 static void
|
|
|
1678 update_debug_stmt (gimple *stmt)
|
|
|
1679 {
|
|
|
1680 use_operand_p use_p;
|
|
|
1681 ssa_op_iter oi;
|
|
|
1682 basic_block bbuse;
|
|
|
1683
|
|
|
1684 if (!gimple_debug_bind_p (stmt))
|
|
|
1685 return;
|
|
|
1686
|
|
|
1687 bbuse = gimple_bb (stmt);
|
|
|
1688 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
|
|
|
1689 {
|
|
|
1690 tree name = USE_FROM_PTR (use_p);
|
|
|
1691 gimple *def_stmt = SSA_NAME_DEF_STMT (name);
|
|
|
1692 basic_block bbdef = gimple_bb (def_stmt);
|
|
|
1693 if (bbdef == NULL || bbuse == bbdef
|
|
|
1694 || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
|
|
|
1695 continue;
|
|
|
1696
|
|
|
1697 gimple_debug_bind_reset_value (stmt);
|
|
|
1698 update_stmt (stmt);
|
|
|
1699 break;
|
|
|
1700 }
|
|
|
1701 }
|
|
|
1702
|
|
|
1703 /* Resets all debug statements that have uses that are not
|
|
|
1704 dominated by their defs. */
|
|
|
1705
|
|
|
1706 static void
|
|
|
1707 update_debug_stmts (void)
|
|
|
1708 {
|
|
|
1709 basic_block bb;
|
|
|
1710 bitmap_iterator bi;
|
|
|
1711 unsigned int i;
|
|
|
1712
|
|
|
1713 EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
|
|
|
1714 {
|
|
|
1715 gimple *stmt;
|
|
|
1716 gimple_stmt_iterator gsi;
|
|
|
1717
|
|
|
1718 bb = BASIC_BLOCK_FOR_FN (cfun, i);
|
|
|
1719 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1720 {
|
|
|
1721 stmt = gsi_stmt (gsi);
|
|
|
1722 if (!is_gimple_debug (stmt))
|
|
|
1723 continue;
|
|
|
1724 update_debug_stmt (stmt);
|
|
|
1725 }
|
|
|
1726 }
|
|
|
1727 }
|
|
|
1728
|
|
|
1729 /* Runs tail merge optimization. */
|
|
|
1730
|
|
|
1731 unsigned int
|
|
|
1732 tail_merge_optimize (unsigned int todo)
|
|
|
1733 {
|
|
|
1734 int nr_bbs_removed_total = 0;
|
|
|
1735 int nr_bbs_removed;
|
|
|
1736 bool loop_entered = false;
|
|
|
1737 int iteration_nr = 0;
|
|
|
1738 int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
|
|
|
1739
|
|
|
1740 if (!flag_tree_tail_merge
|
|
|
1741 || max_iterations == 0)
|
|
|
1742 return 0;
|
|
|
1743
|
|
|
1744 timevar_push (TV_TREE_TAIL_MERGE);
|
|
|
1745
|
|
|
1746 /* We enter from PRE which has critical edges split. Elimination
|
|
|
1747 does not process trivially dead code so cleanup the CFG if we
|
|
|
1748 are told so. And re-split critical edges then. */
|
|
|
1749 if (todo & TODO_cleanup_cfg)
|
|
|
1750 {
|
|
|
1751 cleanup_tree_cfg ();
|
|
|
1752 todo &= ~TODO_cleanup_cfg;
|
|
|
1753 split_critical_edges ();
|
|
|
1754 }
|
|
|
1755
|
|
|
1756 if (!dom_info_available_p (CDI_DOMINATORS))
|
|
|
1757 {
|
|
|
1758 /* PRE can leave us with unreachable blocks, remove them now. */
|
|
|
1759 delete_unreachable_blocks ();
|
|
|
1760 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
1761 }
|
|
|
1762 init_worklist ();
|
|
|
1763
|
|
|
1764 while (!worklist.is_empty ())
|
|
|
1765 {
|
|
|
1766 if (!loop_entered)
|
|
|
1767 {
|
|
|
1768 loop_entered = true;
|
|
|
1769 alloc_cluster_vectors ();
|
|
|
1770 update_bbs = BITMAP_ALLOC (NULL);
|
|
|
1771 }
|
|
|
1772 else
|
|
|
1773 reset_cluster_vectors ();
|
|
|
1774
|
|
|
1775 iteration_nr++;
|
|
|
1776 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1777 fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
|
|
|
1778
|
|
|
1779 find_clusters ();
|
|
|
1780 gcc_assert (worklist.is_empty ());
|
|
|
1781 if (all_clusters.is_empty ())
|
|
|
1782 break;
|
|
|
1783
|
|
|
1784 nr_bbs_removed = apply_clusters ();
|
|
|
1785 nr_bbs_removed_total += nr_bbs_removed;
|
|
|
1786 if (nr_bbs_removed == 0)
|
|
|
1787 break;
|
|
|
1788
|
|
|
1789 free_dominance_info (CDI_DOMINATORS);
|
|
|
1790
|
|
|
1791 if (iteration_nr == max_iterations)
|
|
|
1792 break;
|
|
|
1793
|
|
|
1794 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
1795 update_worklist ();
|
|
|
1796 }
|
|
|
1797
|
|
|
1798 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1799 fprintf (dump_file, "htab collision / search: %f\n",
|
|
|
1800 same_succ_htab->collisions ());
|
|
|
1801
|
|
|
1802 if (nr_bbs_removed_total > 0)
|
|
|
1803 {
|
|
|
1804 if (MAY_HAVE_DEBUG_STMTS)
|
|
|
1805 {
|
|
|
1806 calculate_dominance_info (CDI_DOMINATORS);
|
|
|
1807 update_debug_stmts ();
|
|
|
1808 }
|
|
|
1809
|
|
|
1810 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1811 {
|
|
|
1812 fprintf (dump_file, "Before TODOs.\n");
|
|
|
1813 dump_function_to_file (current_function_decl, dump_file, dump_flags);
|
|
|
1814 }
|
|
|
1815
|
|
|
1816 mark_virtual_operands_for_renaming (cfun);
|
|
|
1817 }
|
|
|
1818
|
|
|
1819 delete_worklist ();
|
|
|
1820 if (loop_entered)
|
|
|
1821 {
|
|
|
1822 delete_cluster_vectors ();
|
|
|
1823 BITMAP_FREE (update_bbs);
|
|
|
1824 }
|
|
|
1825
|
|
|
1826 timevar_pop (TV_TREE_TAIL_MERGE);
|
|
|
1827
|
|
|
1828 return todo;
|
|
|
1829 }
|
