138fd1498Szrj /* Tail merging for gimple.
238fd1498Szrj Copyright (C) 2011-2018 Free Software Foundation, Inc.
338fd1498Szrj Contributed by Tom de Vries (tom@codesourcery.com)
438fd1498Szrj
538fd1498Szrj This file is part of GCC.
638fd1498Szrj
738fd1498Szrj GCC is free software; you can redistribute it and/or modify
838fd1498Szrj it under the terms of the GNU General Public License as published by
938fd1498Szrj the Free Software Foundation; either version 3, or (at your option)
1038fd1498Szrj any later version.
1138fd1498Szrj
1238fd1498Szrj GCC is distributed in the hope that it will be useful,
1338fd1498Szrj but WITHOUT ANY WARRANTY; without even the implied warranty of
1438fd1498Szrj MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
1538fd1498Szrj GNU General Public License for more details.
1638fd1498Szrj
1738fd1498Szrj You should have received a copy of the GNU General Public License
1838fd1498Szrj along with GCC; see the file COPYING3. If not see
1938fd1498Szrj <http://www.gnu.org/licenses/>. */
2038fd1498Szrj
2138fd1498Szrj /* Pass overview.
2238fd1498Szrj
2338fd1498Szrj
2438fd1498Szrj MOTIVATIONAL EXAMPLE
2538fd1498Szrj
2638fd1498Szrj gimple representation of gcc/testsuite/gcc.dg/pr43864.c at
2738fd1498Szrj
2838fd1498Szrj hprofStartupp (charD.1 * outputFileNameD.2600, charD.1 * ctxD.2601)
2938fd1498Szrj {
3038fd1498Szrj struct FILED.1638 * fpD.2605;
3138fd1498Szrj charD.1 fileNameD.2604[1000];
3238fd1498Szrj intD.0 D.3915;
3338fd1498Szrj const charD.1 * restrict outputFileName.0D.3914;
3438fd1498Szrj
3538fd1498Szrj # BLOCK 2 freq:10000
3638fd1498Szrj # PRED: ENTRY [100.0%] (fallthru,exec)
3738fd1498Szrj # PT = nonlocal { D.3926 } (restr)
3838fd1498Szrj outputFileName.0D.3914_3
3938fd1498Szrj = (const charD.1 * restrict) outputFileNameD.2600_2(D);
4038fd1498Szrj # .MEMD.3923_13 = VDEF <.MEMD.3923_12(D)>
4138fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
4238fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
4338fd1498Szrj sprintfD.759 (&fileNameD.2604, outputFileName.0D.3914_3);
4438fd1498Szrj # .MEMD.3923_14 = VDEF <.MEMD.3923_13>
4538fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
4638fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
4738fd1498Szrj D.3915_4 = accessD.2606 (&fileNameD.2604, 1);
4838fd1498Szrj if (D.3915_4 == 0)
4938fd1498Szrj goto <bb 3>;
5038fd1498Szrj else
5138fd1498Szrj goto <bb 4>;
5238fd1498Szrj # SUCC: 3 [10.0%] (true,exec) 4 [90.0%] (false,exec)
5338fd1498Szrj
5438fd1498Szrj # BLOCK 3 freq:1000
5538fd1498Szrj # PRED: 2 [10.0%] (true,exec)
5638fd1498Szrj # .MEMD.3923_15 = VDEF <.MEMD.3923_14>
5738fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
5838fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
5938fd1498Szrj freeD.898 (ctxD.2601_5(D));
6038fd1498Szrj goto <bb 7>;
6138fd1498Szrj # SUCC: 7 [100.0%] (fallthru,exec)
6238fd1498Szrj
6338fd1498Szrj # BLOCK 4 freq:9000
6438fd1498Szrj # PRED: 2 [90.0%] (false,exec)
6538fd1498Szrj # .MEMD.3923_16 = VDEF <.MEMD.3923_14>
6638fd1498Szrj # PT = nonlocal escaped
6738fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
6838fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
6938fd1498Szrj fpD.2605_8 = fopenD.1805 (&fileNameD.2604[0], 0B);
7038fd1498Szrj if (fpD.2605_8 == 0B)
7138fd1498Szrj goto <bb 5>;
7238fd1498Szrj else
7338fd1498Szrj goto <bb 6>;
7438fd1498Szrj # SUCC: 5 [1.9%] (true,exec) 6 [98.1%] (false,exec)
7538fd1498Szrj
7638fd1498Szrj # BLOCK 5 freq:173
7738fd1498Szrj # PRED: 4 [1.9%] (true,exec)
7838fd1498Szrj # .MEMD.3923_17 = VDEF <.MEMD.3923_16>
7938fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
8038fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
8138fd1498Szrj freeD.898 (ctxD.2601_5(D));
8238fd1498Szrj goto <bb 7>;
8338fd1498Szrj # SUCC: 7 [100.0%] (fallthru,exec)
8438fd1498Szrj
8538fd1498Szrj # BLOCK 6 freq:8827
8638fd1498Szrj # PRED: 4 [98.1%] (false,exec)
8738fd1498Szrj # .MEMD.3923_18 = VDEF <.MEMD.3923_16>
8838fd1498Szrj # USE = nonlocal null { fileNameD.2604 D.3926 } (restr)
8938fd1498Szrj # CLB = nonlocal null { fileNameD.2604 D.3926 } (restr)
9038fd1498Szrj fooD.2599 (outputFileNameD.2600_2(D), fpD.2605_8);
9138fd1498Szrj # SUCC: 7 [100.0%] (fallthru,exec)
9238fd1498Szrj
9338fd1498Szrj # BLOCK 7 freq:10000
9438fd1498Szrj # PRED: 3 [100.0%] (fallthru,exec) 5 [100.0%] (fallthru,exec)
9538fd1498Szrj 6 [100.0%] (fallthru,exec)
9638fd1498Szrj # PT = nonlocal null
9738fd1498Szrj
9838fd1498Szrj # ctxD.2601_1 = PHI <0B(3), 0B(5), ctxD.2601_5(D)(6)>
9938fd1498Szrj # .MEMD.3923_11 = PHI <.MEMD.3923_15(3), .MEMD.3923_17(5),
10038fd1498Szrj .MEMD.3923_18(6)>
10138fd1498Szrj # VUSE <.MEMD.3923_11>
10238fd1498Szrj return ctxD.2601_1;
10338fd1498Szrj # SUCC: EXIT [100.0%]
10438fd1498Szrj }
10538fd1498Szrj
10638fd1498Szrj bb 3 and bb 5 can be merged. The blocks have different predecessors, but the
10738fd1498Szrj same successors, and the same operations.
10838fd1498Szrj
10938fd1498Szrj
11038fd1498Szrj CONTEXT
11138fd1498Szrj
11238fd1498Szrj A technique called tail merging (or cross jumping) can fix the example
11338fd1498Szrj above. For a block, we look for common code at the end (the tail) of the
11438fd1498Szrj predecessor blocks, and insert jumps from one block to the other.
11538fd1498Szrj The example is a special case for tail merging, in that 2 whole blocks
11638fd1498Szrj can be merged, rather than just the end parts of it.
11738fd1498Szrj We currently only focus on whole block merging, so in that sense
11838fd1498Szrj calling this pass tail merge is a bit of a misnomer.
11938fd1498Szrj
12038fd1498Szrj We distinguish 2 kinds of situations in which blocks can be merged:
12138fd1498Szrj - same operations, same predecessors. The successor edges coming from one
12238fd1498Szrj block are redirected to come from the other block.
12338fd1498Szrj - same operations, same successors. The predecessor edges entering one block
12438fd1498Szrj are redirected to enter the other block. Note that this operation might
12538fd1498Szrj involve introducing phi operations.
12638fd1498Szrj
12738fd1498Szrj For efficient implementation, we would like to value numbers the blocks, and
12838fd1498Szrj have a comparison operator that tells us whether the blocks are equal.
12938fd1498Szrj Besides being runtime efficient, block value numbering should also abstract
13038fd1498Szrj from irrelevant differences in order of operations, much like normal value
13138fd1498Szrj numbering abstracts from irrelevant order of operations.
13238fd1498Szrj
13338fd1498Szrj For the first situation (same_operations, same predecessors), normal value
13438fd1498Szrj numbering fits well. We can calculate a block value number based on the
13538fd1498Szrj value numbers of the defs and vdefs.
13638fd1498Szrj
13738fd1498Szrj For the second situation (same operations, same successors), this approach
13838fd1498Szrj doesn't work so well. We can illustrate this using the example. The calls
13938fd1498Szrj to free use different vdefs: MEMD.3923_16 and MEMD.3923_14, and these will
14038fd1498Szrj remain different in value numbering, since they represent different memory
14138fd1498Szrj states. So the resulting vdefs of the frees will be different in value
14238fd1498Szrj numbering, so the block value numbers will be different.
14338fd1498Szrj
14438fd1498Szrj The reason why we call the blocks equal is not because they define the same
14538fd1498Szrj values, but because uses in the blocks use (possibly different) defs in the
14638fd1498Szrj same way. To be able to detect this efficiently, we need to do some kind of
14738fd1498Szrj reverse value numbering, meaning number the uses rather than the defs, and
14838fd1498Szrj calculate a block value number based on the value number of the uses.
14938fd1498Szrj Ideally, a block comparison operator will also indicate which phis are needed
15038fd1498Szrj to merge the blocks.
15138fd1498Szrj
15238fd1498Szrj For the moment, we don't do block value numbering, but we do insn-by-insn
15338fd1498Szrj matching, using scc value numbers to match operations with results, and
15438fd1498Szrj structural comparison otherwise, while ignoring vop mismatches.
15538fd1498Szrj
15638fd1498Szrj
15738fd1498Szrj IMPLEMENTATION
15838fd1498Szrj
15938fd1498Szrj 1. The pass first determines all groups of blocks with the same successor
16038fd1498Szrj blocks.
16138fd1498Szrj 2. Within each group, it tries to determine clusters of equal basic blocks.
16238fd1498Szrj 3. The clusters are applied.
16338fd1498Szrj 4. The same successor groups are updated.
16438fd1498Szrj 5. This process is repeated from 2 onwards, until no more changes.
16538fd1498Szrj
16638fd1498Szrj
16738fd1498Szrj LIMITATIONS/TODO
16838fd1498Szrj
16938fd1498Szrj - block only
17038fd1498Szrj - handles only 'same operations, same successors'.
17138fd1498Szrj It handles same predecessors as a special subcase though.
17238fd1498Szrj - does not implement the reverse value numbering and block value numbering.
17338fd1498Szrj - improve memory allocation: use garbage collected memory, obstacks,
17438fd1498Szrj allocpools where appropriate.
17538fd1498Szrj - no insertion of gimple_reg phis, We only introduce vop-phis.
17638fd1498Szrj - handle blocks with gimple_reg phi_nodes.
17738fd1498Szrj
17838fd1498Szrj
17938fd1498Szrj PASS PLACEMENT
18038fd1498Szrj This 'pass' is not a stand-alone gimple pass, but runs as part of
18138fd1498Szrj pass_pre, in order to share the value numbering.
18238fd1498Szrj
18338fd1498Szrj
18438fd1498Szrj SWITCHES
18538fd1498Szrj
18638fd1498Szrj - ftree-tail-merge. On at -O2. We may have to enable it only at -Os. */
18738fd1498Szrj
18838fd1498Szrj #include "config.h"
18938fd1498Szrj #include "system.h"
19038fd1498Szrj #include "coretypes.h"
19138fd1498Szrj #include "backend.h"
19238fd1498Szrj #include "tree.h"
19338fd1498Szrj #include "gimple.h"
19438fd1498Szrj #include "cfghooks.h"
19538fd1498Szrj #include "tree-pass.h"
19638fd1498Szrj #include "ssa.h"
19738fd1498Szrj #include "fold-const.h"
19838fd1498Szrj #include "trans-mem.h"
19938fd1498Szrj #include "cfganal.h"
20038fd1498Szrj #include "cfgcleanup.h"
20138fd1498Szrj #include "gimple-iterator.h"
20238fd1498Szrj #include "tree-cfg.h"
20338fd1498Szrj #include "tree-into-ssa.h"
20438fd1498Szrj #include "params.h"
20538fd1498Szrj #include "tree-ssa-sccvn.h"
20638fd1498Szrj #include "cfgloop.h"
20738fd1498Szrj #include "tree-eh.h"
20838fd1498Szrj #include "tree-cfgcleanup.h"
20938fd1498Szrj
21038fd1498Szrj const int ignore_edge_flags = EDGE_DFS_BACK | EDGE_EXECUTABLE;
21138fd1498Szrj
21238fd1498Szrj /* Describes a group of bbs with the same successors. The successor bbs are
21338fd1498Szrj cached in succs, and the successor edge flags are cached in succ_flags.
21438fd1498Szrj If a bb has the EDGE_TRUE/FALSE_VALUE flags swapped compared to succ_flags,
21538fd1498Szrj it's marked in inverse.
21638fd1498Szrj Additionally, the hash value for the struct is cached in hashval, and
21738fd1498Szrj in_worklist indicates whether it's currently part of worklist. */
21838fd1498Szrj
21938fd1498Szrj struct same_succ : pointer_hash <same_succ>
22038fd1498Szrj {
22138fd1498Szrj /* The bbs that have the same successor bbs. */
22238fd1498Szrj bitmap bbs;
22338fd1498Szrj /* The successor bbs. */
22438fd1498Szrj bitmap succs;
22538fd1498Szrj /* Indicates whether the EDGE_TRUE/FALSE_VALUEs of succ_flags are swapped for
22638fd1498Szrj bb. */
22738fd1498Szrj bitmap inverse;
22838fd1498Szrj /* The edge flags for each of the successor bbs. */
22938fd1498Szrj vec<int> succ_flags;
23038fd1498Szrj /* Indicates whether the struct is currently in the worklist. */
23138fd1498Szrj bool in_worklist;
23238fd1498Szrj /* The hash value of the struct. */
23338fd1498Szrj hashval_t hashval;
23438fd1498Szrj
23538fd1498Szrj /* hash_table support. */
23638fd1498Szrj static inline hashval_t hash (const same_succ *);
23738fd1498Szrj static int equal (const same_succ *, const same_succ *);
23838fd1498Szrj static void remove (same_succ *);
23938fd1498Szrj };
24038fd1498Szrj
24138fd1498Szrj /* hash routine for hash_table support, returns hashval of E. */
24238fd1498Szrj
24338fd1498Szrj inline hashval_t
hash(const same_succ * e)24438fd1498Szrj same_succ::hash (const same_succ *e)
24538fd1498Szrj {
24638fd1498Szrj return e->hashval;
24738fd1498Szrj }
24838fd1498Szrj
24938fd1498Szrj /* A group of bbs where 1 bb from bbs can replace the other bbs. */
25038fd1498Szrj
25138fd1498Szrj struct bb_cluster
25238fd1498Szrj {
25338fd1498Szrj /* The bbs in the cluster. */
25438fd1498Szrj bitmap bbs;
25538fd1498Szrj /* The preds of the bbs in the cluster. */
25638fd1498Szrj bitmap preds;
25738fd1498Szrj /* Index in all_clusters vector. */
25838fd1498Szrj int index;
25938fd1498Szrj /* The bb to replace the cluster with. */
26038fd1498Szrj basic_block rep_bb;
26138fd1498Szrj };
26238fd1498Szrj
26338fd1498Szrj /* Per bb-info. */
26438fd1498Szrj
26538fd1498Szrj struct aux_bb_info
26638fd1498Szrj {
26738fd1498Szrj /* The number of non-debug statements in the bb. */
26838fd1498Szrj int size;
26938fd1498Szrj /* The same_succ that this bb is a member of. */
27038fd1498Szrj same_succ *bb_same_succ;
27138fd1498Szrj /* The cluster that this bb is a member of. */
27238fd1498Szrj bb_cluster *cluster;
27338fd1498Szrj /* The vop state at the exit of a bb. This is shortlived data, used to
27438fd1498Szrj communicate data between update_block_by and update_vuses. */
27538fd1498Szrj tree vop_at_exit;
27638fd1498Szrj /* The bb that either contains or is dominated by the dependencies of the
27738fd1498Szrj bb. */
27838fd1498Szrj basic_block dep_bb;
27938fd1498Szrj };
28038fd1498Szrj
28138fd1498Szrj /* Macros to access the fields of struct aux_bb_info. */
28238fd1498Szrj
28338fd1498Szrj #define BB_SIZE(bb) (((struct aux_bb_info *)bb->aux)->size)
28438fd1498Szrj #define BB_SAME_SUCC(bb) (((struct aux_bb_info *)bb->aux)->bb_same_succ)
28538fd1498Szrj #define BB_CLUSTER(bb) (((struct aux_bb_info *)bb->aux)->cluster)
28638fd1498Szrj #define BB_VOP_AT_EXIT(bb) (((struct aux_bb_info *)bb->aux)->vop_at_exit)
28738fd1498Szrj #define BB_DEP_BB(bb) (((struct aux_bb_info *)bb->aux)->dep_bb)
28838fd1498Szrj
289*58e805e6Szrj /* Valueization helper querying the VN lattice. */
290*58e805e6Szrj
291*58e805e6Szrj static tree
tail_merge_valueize(tree name)292*58e805e6Szrj tail_merge_valueize (tree name)
293*58e805e6Szrj {
294*58e805e6Szrj if (TREE_CODE (name) == SSA_NAME
295*58e805e6Szrj && has_VN_INFO (name))
296*58e805e6Szrj {
297*58e805e6Szrj tree tem = VN_INFO (name)->valnum;
298*58e805e6Szrj if (tem != VN_TOP)
299*58e805e6Szrj return tem;
300*58e805e6Szrj }
301*58e805e6Szrj return name;
302*58e805e6Szrj }
303*58e805e6Szrj
30438fd1498Szrj /* Returns true if the only effect a statement STMT has, is to define locally
30538fd1498Szrj used SSA_NAMEs. */
30638fd1498Szrj
30738fd1498Szrj static bool
stmt_local_def(gimple * stmt)30838fd1498Szrj stmt_local_def (gimple *stmt)
30938fd1498Szrj {
31038fd1498Szrj basic_block bb, def_bb;
31138fd1498Szrj imm_use_iterator iter;
31238fd1498Szrj use_operand_p use_p;
31338fd1498Szrj tree val;
31438fd1498Szrj def_operand_p def_p;
31538fd1498Szrj
31638fd1498Szrj if (gimple_vdef (stmt) != NULL_TREE
31738fd1498Szrj || gimple_has_side_effects (stmt)
31838fd1498Szrj || gimple_could_trap_p_1 (stmt, false, false)
319*58e805e6Szrj || gimple_vuse (stmt) != NULL_TREE
320*58e805e6Szrj /* Copied from tree-ssa-ifcombine.c:bb_no_side_effects_p():
321*58e805e6Szrj const calls don't match any of the above, yet they could
322*58e805e6Szrj still have some side-effects - they could contain
323*58e805e6Szrj gimple_could_trap_p statements, like floating point
324*58e805e6Szrj exceptions or integer division by zero. See PR70586.
325*58e805e6Szrj FIXME: perhaps gimple_has_side_effects or gimple_could_trap_p
326*58e805e6Szrj should handle this. */
327*58e805e6Szrj || is_gimple_call (stmt))
32838fd1498Szrj return false;
32938fd1498Szrj
33038fd1498Szrj def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
33138fd1498Szrj if (def_p == NULL)
33238fd1498Szrj return false;
33338fd1498Szrj
33438fd1498Szrj val = DEF_FROM_PTR (def_p);
33538fd1498Szrj if (val == NULL_TREE || TREE_CODE (val) != SSA_NAME)
33638fd1498Szrj return false;
33738fd1498Szrj
33838fd1498Szrj def_bb = gimple_bb (stmt);
33938fd1498Szrj
34038fd1498Szrj FOR_EACH_IMM_USE_FAST (use_p, iter, val)
34138fd1498Szrj {
34238fd1498Szrj if (is_gimple_debug (USE_STMT (use_p)))
34338fd1498Szrj continue;
34438fd1498Szrj bb = gimple_bb (USE_STMT (use_p));
34538fd1498Szrj if (bb == def_bb)
34638fd1498Szrj continue;
34738fd1498Szrj
34838fd1498Szrj if (gimple_code (USE_STMT (use_p)) == GIMPLE_PHI
34938fd1498Szrj && EDGE_PRED (bb, PHI_ARG_INDEX_FROM_USE (use_p))->src == def_bb)
35038fd1498Szrj continue;
35138fd1498Szrj
35238fd1498Szrj return false;
35338fd1498Szrj }
35438fd1498Szrj
35538fd1498Szrj return true;
35638fd1498Szrj }
35738fd1498Szrj
35838fd1498Szrj /* Let GSI skip forwards over local defs. */
35938fd1498Szrj
36038fd1498Szrj static void
gsi_advance_fw_nondebug_nonlocal(gimple_stmt_iterator * gsi)36138fd1498Szrj gsi_advance_fw_nondebug_nonlocal (gimple_stmt_iterator *gsi)
36238fd1498Szrj {
36338fd1498Szrj gimple *stmt;
36438fd1498Szrj
36538fd1498Szrj while (true)
36638fd1498Szrj {
36738fd1498Szrj if (gsi_end_p (*gsi))
36838fd1498Szrj return;
36938fd1498Szrj stmt = gsi_stmt (*gsi);
37038fd1498Szrj if (!stmt_local_def (stmt))
37138fd1498Szrj return;
37238fd1498Szrj gsi_next_nondebug (gsi);
37338fd1498Szrj }
37438fd1498Szrj }
37538fd1498Szrj
37638fd1498Szrj /* VAL1 and VAL2 are either:
37738fd1498Szrj - uses in BB1 and BB2, or
37838fd1498Szrj - phi alternatives for BB1 and BB2.
37938fd1498Szrj Return true if the uses have the same gvn value. */
38038fd1498Szrj
38138fd1498Szrj static bool
gvn_uses_equal(tree val1,tree val2)38238fd1498Szrj gvn_uses_equal (tree val1, tree val2)
38338fd1498Szrj {
38438fd1498Szrj gcc_checking_assert (val1 != NULL_TREE && val2 != NULL_TREE);
38538fd1498Szrj
38638fd1498Szrj if (val1 == val2)
38738fd1498Szrj return true;
38838fd1498Szrj
389*58e805e6Szrj if (tail_merge_valueize (val1) != tail_merge_valueize (val2))
39038fd1498Szrj return false;
39138fd1498Szrj
39238fd1498Szrj return ((TREE_CODE (val1) == SSA_NAME || CONSTANT_CLASS_P (val1))
39338fd1498Szrj && (TREE_CODE (val2) == SSA_NAME || CONSTANT_CLASS_P (val2)));
39438fd1498Szrj }
39538fd1498Szrj
39638fd1498Szrj /* Prints E to FILE. */
39738fd1498Szrj
39838fd1498Szrj static void
same_succ_print(FILE * file,const same_succ * e)39938fd1498Szrj same_succ_print (FILE *file, const same_succ *e)
40038fd1498Szrj {
40138fd1498Szrj unsigned int i;
40238fd1498Szrj bitmap_print (file, e->bbs, "bbs:", "\n");
40338fd1498Szrj bitmap_print (file, e->succs, "succs:", "\n");
40438fd1498Szrj bitmap_print (file, e->inverse, "inverse:", "\n");
40538fd1498Szrj fprintf (file, "flags:");
40638fd1498Szrj for (i = 0; i < e->succ_flags.length (); ++i)
40738fd1498Szrj fprintf (file, " %x", e->succ_flags[i]);
40838fd1498Szrj fprintf (file, "\n");
40938fd1498Szrj }
41038fd1498Szrj
41138fd1498Szrj /* Prints same_succ VE to VFILE. */
41238fd1498Szrj
41338fd1498Szrj inline int
ssa_same_succ_print_traverse(same_succ ** pe,FILE * file)41438fd1498Szrj ssa_same_succ_print_traverse (same_succ **pe, FILE *file)
41538fd1498Szrj {
41638fd1498Szrj const same_succ *e = *pe;
41738fd1498Szrj same_succ_print (file, e);
41838fd1498Szrj return 1;
41938fd1498Szrj }
42038fd1498Szrj
42138fd1498Szrj /* Update BB_DEP_BB (USE_BB), given a use of VAL in USE_BB. */
42238fd1498Szrj
42338fd1498Szrj static void
update_dep_bb(basic_block use_bb,tree val)42438fd1498Szrj update_dep_bb (basic_block use_bb, tree val)
42538fd1498Szrj {
42638fd1498Szrj basic_block dep_bb;
42738fd1498Szrj
42838fd1498Szrj /* Not a dep. */
42938fd1498Szrj if (TREE_CODE (val) != SSA_NAME)
43038fd1498Szrj return;
43138fd1498Szrj
43238fd1498Szrj /* Skip use of global def. */
43338fd1498Szrj if (SSA_NAME_IS_DEFAULT_DEF (val))
43438fd1498Szrj return;
43538fd1498Szrj
43638fd1498Szrj /* Skip use of local def. */
43738fd1498Szrj dep_bb = gimple_bb (SSA_NAME_DEF_STMT (val));
43838fd1498Szrj if (dep_bb == use_bb)
43938fd1498Szrj return;
44038fd1498Szrj
44138fd1498Szrj if (BB_DEP_BB (use_bb) == NULL
44238fd1498Szrj || dominated_by_p (CDI_DOMINATORS, dep_bb, BB_DEP_BB (use_bb)))
44338fd1498Szrj BB_DEP_BB (use_bb) = dep_bb;
44438fd1498Szrj }
44538fd1498Szrj
44638fd1498Szrj /* Update BB_DEP_BB, given the dependencies in STMT. */
44738fd1498Szrj
44838fd1498Szrj static void
stmt_update_dep_bb(gimple * stmt)44938fd1498Szrj stmt_update_dep_bb (gimple *stmt)
45038fd1498Szrj {
45138fd1498Szrj ssa_op_iter iter;
45238fd1498Szrj use_operand_p use;
45338fd1498Szrj
45438fd1498Szrj FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
45538fd1498Szrj update_dep_bb (gimple_bb (stmt), USE_FROM_PTR (use));
45638fd1498Szrj }
45738fd1498Szrj
45838fd1498Szrj /* Calculates hash value for same_succ VE. */
45938fd1498Szrj
46038fd1498Szrj static hashval_t
same_succ_hash(const same_succ * e)46138fd1498Szrj same_succ_hash (const same_succ *e)
46238fd1498Szrj {
46338fd1498Szrj inchash::hash hstate (bitmap_hash (e->succs));
46438fd1498Szrj int flags;
46538fd1498Szrj unsigned int i;
46638fd1498Szrj unsigned int first = bitmap_first_set_bit (e->bbs);
46738fd1498Szrj basic_block bb = BASIC_BLOCK_FOR_FN (cfun, first);
46838fd1498Szrj int size = 0;
46938fd1498Szrj gimple *stmt;
47038fd1498Szrj tree arg;
47138fd1498Szrj unsigned int s;
47238fd1498Szrj bitmap_iterator bs;
47338fd1498Szrj
47438fd1498Szrj for (gimple_stmt_iterator gsi = gsi_start_nondebug_bb (bb);
47538fd1498Szrj !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
47638fd1498Szrj {
47738fd1498Szrj stmt = gsi_stmt (gsi);
47838fd1498Szrj stmt_update_dep_bb (stmt);
47938fd1498Szrj if (stmt_local_def (stmt))
48038fd1498Szrj continue;
48138fd1498Szrj size++;
48238fd1498Szrj
48338fd1498Szrj hstate.add_int (gimple_code (stmt));
48438fd1498Szrj if (is_gimple_assign (stmt))
48538fd1498Szrj hstate.add_int (gimple_assign_rhs_code (stmt));
48638fd1498Szrj if (!is_gimple_call (stmt))
48738fd1498Szrj continue;
48838fd1498Szrj if (gimple_call_internal_p (stmt))
48938fd1498Szrj hstate.add_int (gimple_call_internal_fn (stmt));
49038fd1498Szrj else
49138fd1498Szrj {
49238fd1498Szrj inchash::add_expr (gimple_call_fn (stmt), hstate);
49338fd1498Szrj if (gimple_call_chain (stmt))
49438fd1498Szrj inchash::add_expr (gimple_call_chain (stmt), hstate);
49538fd1498Szrj }
49638fd1498Szrj for (i = 0; i < gimple_call_num_args (stmt); i++)
49738fd1498Szrj {
49838fd1498Szrj arg = gimple_call_arg (stmt, i);
499*58e805e6Szrj arg = tail_merge_valueize (arg);
50038fd1498Szrj inchash::add_expr (arg, hstate);
50138fd1498Szrj }
50238fd1498Szrj }
50338fd1498Szrj
50438fd1498Szrj hstate.add_int (size);
50538fd1498Szrj BB_SIZE (bb) = size;
50638fd1498Szrj
50738fd1498Szrj hstate.add_int (bb->loop_father->num);
50838fd1498Szrj
50938fd1498Szrj for (i = 0; i < e->succ_flags.length (); ++i)
51038fd1498Szrj {
51138fd1498Szrj flags = e->succ_flags[i];
51238fd1498Szrj flags = flags & ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
51338fd1498Szrj hstate.add_int (flags);
51438fd1498Szrj }
51538fd1498Szrj
51638fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (e->succs, 0, s, bs)
51738fd1498Szrj {
51838fd1498Szrj int n = find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, s))->dest_idx;
51938fd1498Szrj for (gphi_iterator gsi = gsi_start_phis (BASIC_BLOCK_FOR_FN (cfun, s));
52038fd1498Szrj !gsi_end_p (gsi);
52138fd1498Szrj gsi_next (&gsi))
52238fd1498Szrj {
52338fd1498Szrj gphi *phi = gsi.phi ();
52438fd1498Szrj tree lhs = gimple_phi_result (phi);
52538fd1498Szrj tree val = gimple_phi_arg_def (phi, n);
52638fd1498Szrj
52738fd1498Szrj if (virtual_operand_p (lhs))
52838fd1498Szrj continue;
52938fd1498Szrj update_dep_bb (bb, val);
53038fd1498Szrj }
53138fd1498Szrj }
53238fd1498Szrj
53338fd1498Szrj return hstate.end ();
53438fd1498Szrj }
53538fd1498Szrj
53638fd1498Szrj /* Returns true if E1 and E2 have 2 successors, and if the successor flags
53738fd1498Szrj are inverse for the EDGE_TRUE_VALUE and EDGE_FALSE_VALUE flags, and equal for
53838fd1498Szrj the other edge flags. */
53938fd1498Szrj
54038fd1498Szrj static bool
inverse_flags(const same_succ * e1,const same_succ * e2)54138fd1498Szrj inverse_flags (const same_succ *e1, const same_succ *e2)
54238fd1498Szrj {
54338fd1498Szrj int f1a, f1b, f2a, f2b;
54438fd1498Szrj int mask = ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
54538fd1498Szrj
54638fd1498Szrj if (e1->succ_flags.length () != 2)
54738fd1498Szrj return false;
54838fd1498Szrj
54938fd1498Szrj f1a = e1->succ_flags[0];
55038fd1498Szrj f1b = e1->succ_flags[1];
55138fd1498Szrj f2a = e2->succ_flags[0];
55238fd1498Szrj f2b = e2->succ_flags[1];
55338fd1498Szrj
55438fd1498Szrj if (f1a == f2a && f1b == f2b)
55538fd1498Szrj return false;
55638fd1498Szrj
55738fd1498Szrj return (f1a & mask) == (f2a & mask) && (f1b & mask) == (f2b & mask);
55838fd1498Szrj }
55938fd1498Szrj
56038fd1498Szrj /* Compares SAME_SUCCs E1 and E2. */
56138fd1498Szrj
56238fd1498Szrj int
equal(const same_succ * e1,const same_succ * e2)56338fd1498Szrj same_succ::equal (const same_succ *e1, const same_succ *e2)
56438fd1498Szrj {
56538fd1498Szrj unsigned int i, first1, first2;
56638fd1498Szrj gimple_stmt_iterator gsi1, gsi2;
56738fd1498Szrj gimple *s1, *s2;
56838fd1498Szrj basic_block bb1, bb2;
56938fd1498Szrj
57038fd1498Szrj if (e1 == e2)
57138fd1498Szrj return 1;
57238fd1498Szrj
57338fd1498Szrj if (e1->hashval != e2->hashval)
57438fd1498Szrj return 0;
57538fd1498Szrj
57638fd1498Szrj if (e1->succ_flags.length () != e2->succ_flags.length ())
57738fd1498Szrj return 0;
57838fd1498Szrj
57938fd1498Szrj if (!bitmap_equal_p (e1->succs, e2->succs))
58038fd1498Szrj return 0;
58138fd1498Szrj
58238fd1498Szrj if (!inverse_flags (e1, e2))
58338fd1498Szrj {
58438fd1498Szrj for (i = 0; i < e1->succ_flags.length (); ++i)
58538fd1498Szrj if (e1->succ_flags[i] != e2->succ_flags[i])
58638fd1498Szrj return 0;
58738fd1498Szrj }
58838fd1498Szrj
58938fd1498Szrj first1 = bitmap_first_set_bit (e1->bbs);
59038fd1498Szrj first2 = bitmap_first_set_bit (e2->bbs);
59138fd1498Szrj
59238fd1498Szrj bb1 = BASIC_BLOCK_FOR_FN (cfun, first1);
59338fd1498Szrj bb2 = BASIC_BLOCK_FOR_FN (cfun, first2);
59438fd1498Szrj
59538fd1498Szrj if (BB_SIZE (bb1) != BB_SIZE (bb2))
59638fd1498Szrj return 0;
59738fd1498Szrj
59838fd1498Szrj if (bb1->loop_father != bb2->loop_father)
59938fd1498Szrj return 0;
60038fd1498Szrj
60138fd1498Szrj gsi1 = gsi_start_nondebug_bb (bb1);
60238fd1498Szrj gsi2 = gsi_start_nondebug_bb (bb2);
60338fd1498Szrj gsi_advance_fw_nondebug_nonlocal (&gsi1);
60438fd1498Szrj gsi_advance_fw_nondebug_nonlocal (&gsi2);
60538fd1498Szrj while (!(gsi_end_p (gsi1) || gsi_end_p (gsi2)))
60638fd1498Szrj {
60738fd1498Szrj s1 = gsi_stmt (gsi1);
60838fd1498Szrj s2 = gsi_stmt (gsi2);
60938fd1498Szrj if (gimple_code (s1) != gimple_code (s2))
61038fd1498Szrj return 0;
61138fd1498Szrj if (is_gimple_call (s1) && !gimple_call_same_target_p (s1, s2))
61238fd1498Szrj return 0;
61338fd1498Szrj gsi_next_nondebug (&gsi1);
61438fd1498Szrj gsi_next_nondebug (&gsi2);
61538fd1498Szrj gsi_advance_fw_nondebug_nonlocal (&gsi1);
61638fd1498Szrj gsi_advance_fw_nondebug_nonlocal (&gsi2);
61738fd1498Szrj }
61838fd1498Szrj
61938fd1498Szrj return 1;
62038fd1498Szrj }
62138fd1498Szrj
62238fd1498Szrj /* Alloc and init a new SAME_SUCC. */
62338fd1498Szrj
62438fd1498Szrj static same_succ *
same_succ_alloc(void)62538fd1498Szrj same_succ_alloc (void)
62638fd1498Szrj {
62738fd1498Szrj same_succ *same = XNEW (struct same_succ);
62838fd1498Szrj
62938fd1498Szrj same->bbs = BITMAP_ALLOC (NULL);
63038fd1498Szrj same->succs = BITMAP_ALLOC (NULL);
63138fd1498Szrj same->inverse = BITMAP_ALLOC (NULL);
63238fd1498Szrj same->succ_flags.create (10);
63338fd1498Szrj same->in_worklist = false;
63438fd1498Szrj
63538fd1498Szrj return same;
63638fd1498Szrj }
63738fd1498Szrj
63838fd1498Szrj /* Delete same_succ E. */
63938fd1498Szrj
64038fd1498Szrj void
remove(same_succ * e)64138fd1498Szrj same_succ::remove (same_succ *e)
64238fd1498Szrj {
64338fd1498Szrj BITMAP_FREE (e->bbs);
64438fd1498Szrj BITMAP_FREE (e->succs);
64538fd1498Szrj BITMAP_FREE (e->inverse);
64638fd1498Szrj e->succ_flags.release ();
64738fd1498Szrj
64838fd1498Szrj XDELETE (e);
64938fd1498Szrj }
65038fd1498Szrj
65138fd1498Szrj /* Reset same_succ SAME. */
65238fd1498Szrj
65338fd1498Szrj static void
same_succ_reset(same_succ * same)65438fd1498Szrj same_succ_reset (same_succ *same)
65538fd1498Szrj {
65638fd1498Szrj bitmap_clear (same->bbs);
65738fd1498Szrj bitmap_clear (same->succs);
65838fd1498Szrj bitmap_clear (same->inverse);
65938fd1498Szrj same->succ_flags.truncate (0);
66038fd1498Szrj }
66138fd1498Szrj
66238fd1498Szrj static hash_table<same_succ> *same_succ_htab;
66338fd1498Szrj
66438fd1498Szrj /* Array that is used to store the edge flags for a successor. */
66538fd1498Szrj
66638fd1498Szrj static int *same_succ_edge_flags;
66738fd1498Szrj
66838fd1498Szrj /* Bitmap that is used to mark bbs that are recently deleted. */
66938fd1498Szrj
67038fd1498Szrj static bitmap deleted_bbs;
67138fd1498Szrj
67238fd1498Szrj /* Bitmap that is used to mark predecessors of bbs that are
67338fd1498Szrj deleted. */
67438fd1498Szrj
67538fd1498Szrj static bitmap deleted_bb_preds;
67638fd1498Szrj
67738fd1498Szrj /* Prints same_succ_htab to stderr. */
67838fd1498Szrj
67938fd1498Szrj extern void debug_same_succ (void);
68038fd1498Szrj DEBUG_FUNCTION void
debug_same_succ(void)68138fd1498Szrj debug_same_succ ( void)
68238fd1498Szrj {
68338fd1498Szrj same_succ_htab->traverse <FILE *, ssa_same_succ_print_traverse> (stderr);
68438fd1498Szrj }
68538fd1498Szrj
68638fd1498Szrj
68738fd1498Szrj /* Vector of bbs to process. */
68838fd1498Szrj
68938fd1498Szrj static vec<same_succ *> worklist;
69038fd1498Szrj
69138fd1498Szrj /* Prints worklist to FILE. */
69238fd1498Szrj
69338fd1498Szrj static void
print_worklist(FILE * file)69438fd1498Szrj print_worklist (FILE *file)
69538fd1498Szrj {
69638fd1498Szrj unsigned int i;
69738fd1498Szrj for (i = 0; i < worklist.length (); ++i)
69838fd1498Szrj same_succ_print (file, worklist[i]);
69938fd1498Szrj }
70038fd1498Szrj
70138fd1498Szrj /* Adds SAME to worklist. */
70238fd1498Szrj
70338fd1498Szrj static void
add_to_worklist(same_succ * same)70438fd1498Szrj add_to_worklist (same_succ *same)
70538fd1498Szrj {
70638fd1498Szrj if (same->in_worklist)
70738fd1498Szrj return;
70838fd1498Szrj
70938fd1498Szrj if (bitmap_count_bits (same->bbs) < 2)
71038fd1498Szrj return;
71138fd1498Szrj
71238fd1498Szrj same->in_worklist = true;
71338fd1498Szrj worklist.safe_push (same);
71438fd1498Szrj }
71538fd1498Szrj
71638fd1498Szrj /* Add BB to same_succ_htab. */
71738fd1498Szrj
71838fd1498Szrj static void
find_same_succ_bb(basic_block bb,same_succ ** same_p)71938fd1498Szrj find_same_succ_bb (basic_block bb, same_succ **same_p)
72038fd1498Szrj {
72138fd1498Szrj unsigned int j;
72238fd1498Szrj bitmap_iterator bj;
72338fd1498Szrj same_succ *same = *same_p;
72438fd1498Szrj same_succ **slot;
72538fd1498Szrj edge_iterator ei;
72638fd1498Szrj edge e;
72738fd1498Szrj
72838fd1498Szrj if (bb == NULL)
72938fd1498Szrj return;
73038fd1498Szrj bitmap_set_bit (same->bbs, bb->index);
73138fd1498Szrj FOR_EACH_EDGE (e, ei, bb->succs)
73238fd1498Szrj {
73338fd1498Szrj int index = e->dest->index;
73438fd1498Szrj bitmap_set_bit (same->succs, index);
73538fd1498Szrj same_succ_edge_flags[index] = (e->flags & ~ignore_edge_flags);
73638fd1498Szrj }
73738fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (same->succs, 0, j, bj)
73838fd1498Szrj same->succ_flags.safe_push (same_succ_edge_flags[j]);
73938fd1498Szrj
74038fd1498Szrj same->hashval = same_succ_hash (same);
74138fd1498Szrj
74238fd1498Szrj slot = same_succ_htab->find_slot_with_hash (same, same->hashval, INSERT);
74338fd1498Szrj if (*slot == NULL)
74438fd1498Szrj {
74538fd1498Szrj *slot = same;
74638fd1498Szrj BB_SAME_SUCC (bb) = same;
74738fd1498Szrj add_to_worklist (same);
74838fd1498Szrj *same_p = NULL;
74938fd1498Szrj }
75038fd1498Szrj else
75138fd1498Szrj {
75238fd1498Szrj bitmap_set_bit ((*slot)->bbs, bb->index);
75338fd1498Szrj BB_SAME_SUCC (bb) = *slot;
75438fd1498Szrj add_to_worklist (*slot);
75538fd1498Szrj if (inverse_flags (same, *slot))
75638fd1498Szrj bitmap_set_bit ((*slot)->inverse, bb->index);
75738fd1498Szrj same_succ_reset (same);
75838fd1498Szrj }
75938fd1498Szrj }
76038fd1498Szrj
76138fd1498Szrj /* Find bbs with same successors. */
76238fd1498Szrj
76338fd1498Szrj static void
find_same_succ(void)76438fd1498Szrj find_same_succ (void)
76538fd1498Szrj {
76638fd1498Szrj same_succ *same = same_succ_alloc ();
76738fd1498Szrj basic_block bb;
76838fd1498Szrj
76938fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
77038fd1498Szrj {
77138fd1498Szrj find_same_succ_bb (bb, &same);
77238fd1498Szrj if (same == NULL)
77338fd1498Szrj same = same_succ_alloc ();
77438fd1498Szrj }
77538fd1498Szrj
77638fd1498Szrj same_succ::remove (same);
77738fd1498Szrj }
77838fd1498Szrj
77938fd1498Szrj /* Initializes worklist administration. */
78038fd1498Szrj
78138fd1498Szrj static void
init_worklist(void)78238fd1498Szrj init_worklist (void)
78338fd1498Szrj {
78438fd1498Szrj alloc_aux_for_blocks (sizeof (struct aux_bb_info));
78538fd1498Szrj same_succ_htab = new hash_table<same_succ> (n_basic_blocks_for_fn (cfun));
78638fd1498Szrj same_succ_edge_flags = XCNEWVEC (int, last_basic_block_for_fn (cfun));
78738fd1498Szrj deleted_bbs = BITMAP_ALLOC (NULL);
78838fd1498Szrj deleted_bb_preds = BITMAP_ALLOC (NULL);
78938fd1498Szrj worklist.create (n_basic_blocks_for_fn (cfun));
79038fd1498Szrj find_same_succ ();
79138fd1498Szrj
79238fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
79338fd1498Szrj {
79438fd1498Szrj fprintf (dump_file, "initial worklist:\n");
79538fd1498Szrj print_worklist (dump_file);
79638fd1498Szrj }
79738fd1498Szrj }
79838fd1498Szrj
79938fd1498Szrj /* Deletes worklist administration. */
80038fd1498Szrj
80138fd1498Szrj static void
delete_worklist(void)80238fd1498Szrj delete_worklist (void)
80338fd1498Szrj {
80438fd1498Szrj free_aux_for_blocks ();
80538fd1498Szrj delete same_succ_htab;
80638fd1498Szrj same_succ_htab = NULL;
80738fd1498Szrj XDELETEVEC (same_succ_edge_flags);
80838fd1498Szrj same_succ_edge_flags = NULL;
80938fd1498Szrj BITMAP_FREE (deleted_bbs);
81038fd1498Szrj BITMAP_FREE (deleted_bb_preds);
81138fd1498Szrj worklist.release ();
81238fd1498Szrj }
81338fd1498Szrj
81438fd1498Szrj /* Mark BB as deleted, and mark its predecessors. */
81538fd1498Szrj
81638fd1498Szrj static void
mark_basic_block_deleted(basic_block bb)81738fd1498Szrj mark_basic_block_deleted (basic_block bb)
81838fd1498Szrj {
81938fd1498Szrj edge e;
82038fd1498Szrj edge_iterator ei;
82138fd1498Szrj
82238fd1498Szrj bitmap_set_bit (deleted_bbs, bb->index);
82338fd1498Szrj
82438fd1498Szrj FOR_EACH_EDGE (e, ei, bb->preds)
82538fd1498Szrj bitmap_set_bit (deleted_bb_preds, e->src->index);
82638fd1498Szrj }
82738fd1498Szrj
82838fd1498Szrj /* Removes BB from its corresponding same_succ. */
82938fd1498Szrj
83038fd1498Szrj static void
same_succ_flush_bb(basic_block bb)83138fd1498Szrj same_succ_flush_bb (basic_block bb)
83238fd1498Szrj {
83338fd1498Szrj same_succ *same = BB_SAME_SUCC (bb);
83438fd1498Szrj if (! same)
83538fd1498Szrj return;
83638fd1498Szrj
83738fd1498Szrj BB_SAME_SUCC (bb) = NULL;
83838fd1498Szrj if (bitmap_single_bit_set_p (same->bbs))
83938fd1498Szrj same_succ_htab->remove_elt_with_hash (same, same->hashval);
84038fd1498Szrj else
84138fd1498Szrj bitmap_clear_bit (same->bbs, bb->index);
84238fd1498Szrj }
84338fd1498Szrj
84438fd1498Szrj /* Removes all bbs in BBS from their corresponding same_succ. */
84538fd1498Szrj
84638fd1498Szrj static void
same_succ_flush_bbs(bitmap bbs)84738fd1498Szrj same_succ_flush_bbs (bitmap bbs)
84838fd1498Szrj {
84938fd1498Szrj unsigned int i;
85038fd1498Szrj bitmap_iterator bi;
85138fd1498Szrj
85238fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (bbs, 0, i, bi)
85338fd1498Szrj same_succ_flush_bb (BASIC_BLOCK_FOR_FN (cfun, i));
85438fd1498Szrj }
85538fd1498Szrj
85638fd1498Szrj /* Release the last vdef in BB, either normal or phi result. */
85738fd1498Szrj
85838fd1498Szrj static void
release_last_vdef(basic_block bb)85938fd1498Szrj release_last_vdef (basic_block bb)
86038fd1498Szrj {
86138fd1498Szrj for (gimple_stmt_iterator i = gsi_last_bb (bb); !gsi_end_p (i);
86238fd1498Szrj gsi_prev_nondebug (&i))
86338fd1498Szrj {
86438fd1498Szrj gimple *stmt = gsi_stmt (i);
86538fd1498Szrj if (gimple_vdef (stmt) == NULL_TREE)
86638fd1498Szrj continue;
86738fd1498Szrj
86838fd1498Szrj mark_virtual_operand_for_renaming (gimple_vdef (stmt));
86938fd1498Szrj return;
87038fd1498Szrj }
87138fd1498Szrj
87238fd1498Szrj for (gphi_iterator i = gsi_start_phis (bb); !gsi_end_p (i);
87338fd1498Szrj gsi_next (&i))
87438fd1498Szrj {
87538fd1498Szrj gphi *phi = i.phi ();
87638fd1498Szrj tree res = gimple_phi_result (phi);
87738fd1498Szrj
87838fd1498Szrj if (!virtual_operand_p (res))
87938fd1498Szrj continue;
88038fd1498Szrj
88138fd1498Szrj mark_virtual_phi_result_for_renaming (phi);
88238fd1498Szrj return;
88338fd1498Szrj }
88438fd1498Szrj }
88538fd1498Szrj
88638fd1498Szrj /* For deleted_bb_preds, find bbs with same successors. */
88738fd1498Szrj
88838fd1498Szrj static void
update_worklist(void)88938fd1498Szrj update_worklist (void)
89038fd1498Szrj {
89138fd1498Szrj unsigned int i;
89238fd1498Szrj bitmap_iterator bi;
89338fd1498Szrj basic_block bb;
89438fd1498Szrj same_succ *same;
89538fd1498Szrj
89638fd1498Szrj bitmap_and_compl_into (deleted_bb_preds, deleted_bbs);
89738fd1498Szrj bitmap_clear (deleted_bbs);
89838fd1498Szrj
89938fd1498Szrj bitmap_clear_bit (deleted_bb_preds, ENTRY_BLOCK);
90038fd1498Szrj same_succ_flush_bbs (deleted_bb_preds);
90138fd1498Szrj
90238fd1498Szrj same = same_succ_alloc ();
90338fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (deleted_bb_preds, 0, i, bi)
90438fd1498Szrj {
90538fd1498Szrj bb = BASIC_BLOCK_FOR_FN (cfun, i);
90638fd1498Szrj gcc_assert (bb != NULL);
90738fd1498Szrj find_same_succ_bb (bb, &same);
90838fd1498Szrj if (same == NULL)
90938fd1498Szrj same = same_succ_alloc ();
91038fd1498Szrj }
91138fd1498Szrj same_succ::remove (same);
91238fd1498Szrj bitmap_clear (deleted_bb_preds);
91338fd1498Szrj }
91438fd1498Szrj
91538fd1498Szrj /* Prints cluster C to FILE. */
91638fd1498Szrj
91738fd1498Szrj static void
print_cluster(FILE * file,bb_cluster * c)91838fd1498Szrj print_cluster (FILE *file, bb_cluster *c)
91938fd1498Szrj {
92038fd1498Szrj if (c == NULL)
92138fd1498Szrj return;
92238fd1498Szrj bitmap_print (file, c->bbs, "bbs:", "\n");
92338fd1498Szrj bitmap_print (file, c->preds, "preds:", "\n");
92438fd1498Szrj }
92538fd1498Szrj
92638fd1498Szrj /* Prints cluster C to stderr. */
92738fd1498Szrj
92838fd1498Szrj extern void debug_cluster (bb_cluster *);
92938fd1498Szrj DEBUG_FUNCTION void
debug_cluster(bb_cluster * c)93038fd1498Szrj debug_cluster (bb_cluster *c)
93138fd1498Szrj {
93238fd1498Szrj print_cluster (stderr, c);
93338fd1498Szrj }
93438fd1498Szrj
93538fd1498Szrj /* Update C->rep_bb, given that BB is added to the cluster. */
93638fd1498Szrj
93738fd1498Szrj static void
update_rep_bb(bb_cluster * c,basic_block bb)93838fd1498Szrj update_rep_bb (bb_cluster *c, basic_block bb)
93938fd1498Szrj {
94038fd1498Szrj /* Initial. */
94138fd1498Szrj if (c->rep_bb == NULL)
94238fd1498Szrj {
94338fd1498Szrj c->rep_bb = bb;
94438fd1498Szrj return;
94538fd1498Szrj }
94638fd1498Szrj
94738fd1498Szrj /* Current needs no deps, keep it. */
94838fd1498Szrj if (BB_DEP_BB (c->rep_bb) == NULL)
94938fd1498Szrj return;
95038fd1498Szrj
95138fd1498Szrj /* Bb needs no deps, change rep_bb. */
95238fd1498Szrj if (BB_DEP_BB (bb) == NULL)
95338fd1498Szrj {
95438fd1498Szrj c->rep_bb = bb;
95538fd1498Szrj return;
95638fd1498Szrj }
95738fd1498Szrj
95838fd1498Szrj /* Bb needs last deps earlier than current, change rep_bb. A potential
95938fd1498Szrj problem with this, is that the first deps might also be earlier, which
96038fd1498Szrj would mean we prefer longer lifetimes for the deps. To be able to check
96138fd1498Szrj for this, we would have to trace BB_FIRST_DEP_BB as well, besides
96238fd1498Szrj BB_DEP_BB, which is really BB_LAST_DEP_BB.
96338fd1498Szrj The benefit of choosing the bb with last deps earlier, is that it can
96438fd1498Szrj potentially be used as replacement for more bbs. */
96538fd1498Szrj if (dominated_by_p (CDI_DOMINATORS, BB_DEP_BB (c->rep_bb), BB_DEP_BB (bb)))
96638fd1498Szrj c->rep_bb = bb;
96738fd1498Szrj }
96838fd1498Szrj
96938fd1498Szrj /* Add BB to cluster C. Sets BB in C->bbs, and preds of BB in C->preds. */
97038fd1498Szrj
97138fd1498Szrj static void
add_bb_to_cluster(bb_cluster * c,basic_block bb)97238fd1498Szrj add_bb_to_cluster (bb_cluster *c, basic_block bb)
97338fd1498Szrj {
97438fd1498Szrj edge e;
97538fd1498Szrj edge_iterator ei;
97638fd1498Szrj
97738fd1498Szrj bitmap_set_bit (c->bbs, bb->index);
97838fd1498Szrj
97938fd1498Szrj FOR_EACH_EDGE (e, ei, bb->preds)
98038fd1498Szrj bitmap_set_bit (c->preds, e->src->index);
98138fd1498Szrj
98238fd1498Szrj update_rep_bb (c, bb);
98338fd1498Szrj }
98438fd1498Szrj
98538fd1498Szrj /* Allocate and init new cluster. */
98638fd1498Szrj
98738fd1498Szrj static bb_cluster *
new_cluster(void)98838fd1498Szrj new_cluster (void)
98938fd1498Szrj {
99038fd1498Szrj bb_cluster *c;
99138fd1498Szrj c = XCNEW (bb_cluster);
99238fd1498Szrj c->bbs = BITMAP_ALLOC (NULL);
99338fd1498Szrj c->preds = BITMAP_ALLOC (NULL);
99438fd1498Szrj c->rep_bb = NULL;
99538fd1498Szrj return c;
99638fd1498Szrj }
99738fd1498Szrj
99838fd1498Szrj /* Delete clusters. */
99938fd1498Szrj
100038fd1498Szrj static void
delete_cluster(bb_cluster * c)100138fd1498Szrj delete_cluster (bb_cluster *c)
100238fd1498Szrj {
100338fd1498Szrj if (c == NULL)
100438fd1498Szrj return;
100538fd1498Szrj BITMAP_FREE (c->bbs);
100638fd1498Szrj BITMAP_FREE (c->preds);
100738fd1498Szrj XDELETE (c);
100838fd1498Szrj }
100938fd1498Szrj
101038fd1498Szrj
101138fd1498Szrj /* Array that contains all clusters. */
101238fd1498Szrj
101338fd1498Szrj static vec<bb_cluster *> all_clusters;
101438fd1498Szrj
101538fd1498Szrj /* Allocate all cluster vectors. */
101638fd1498Szrj
101738fd1498Szrj static void
alloc_cluster_vectors(void)101838fd1498Szrj alloc_cluster_vectors (void)
101938fd1498Szrj {
102038fd1498Szrj all_clusters.create (n_basic_blocks_for_fn (cfun));
102138fd1498Szrj }
102238fd1498Szrj
102338fd1498Szrj /* Reset all cluster vectors. */
102438fd1498Szrj
102538fd1498Szrj static void
reset_cluster_vectors(void)102638fd1498Szrj reset_cluster_vectors (void)
102738fd1498Szrj {
102838fd1498Szrj unsigned int i;
102938fd1498Szrj basic_block bb;
103038fd1498Szrj for (i = 0; i < all_clusters.length (); ++i)
103138fd1498Szrj delete_cluster (all_clusters[i]);
103238fd1498Szrj all_clusters.truncate (0);
103338fd1498Szrj FOR_EACH_BB_FN (bb, cfun)
103438fd1498Szrj BB_CLUSTER (bb) = NULL;
103538fd1498Szrj }
103638fd1498Szrj
103738fd1498Szrj /* Delete all cluster vectors. */
103838fd1498Szrj
103938fd1498Szrj static void
delete_cluster_vectors(void)104038fd1498Szrj delete_cluster_vectors (void)
104138fd1498Szrj {
104238fd1498Szrj unsigned int i;
104338fd1498Szrj for (i = 0; i < all_clusters.length (); ++i)
104438fd1498Szrj delete_cluster (all_clusters[i]);
104538fd1498Szrj all_clusters.release ();
104638fd1498Szrj }
104738fd1498Szrj
104838fd1498Szrj /* Merge cluster C2 into C1. */
104938fd1498Szrj
105038fd1498Szrj static void
merge_clusters(bb_cluster * c1,bb_cluster * c2)105138fd1498Szrj merge_clusters (bb_cluster *c1, bb_cluster *c2)
105238fd1498Szrj {
105338fd1498Szrj bitmap_ior_into (c1->bbs, c2->bbs);
105438fd1498Szrj bitmap_ior_into (c1->preds, c2->preds);
105538fd1498Szrj }
105638fd1498Szrj
105738fd1498Szrj /* Register equivalence of BB1 and BB2 (members of cluster C). Store c in
105838fd1498Szrj all_clusters, or merge c with existing cluster. */
105938fd1498Szrj
106038fd1498Szrj static void
set_cluster(basic_block bb1,basic_block bb2)106138fd1498Szrj set_cluster (basic_block bb1, basic_block bb2)
106238fd1498Szrj {
106338fd1498Szrj basic_block merge_bb, other_bb;
106438fd1498Szrj bb_cluster *merge, *old, *c;
106538fd1498Szrj
106638fd1498Szrj if (BB_CLUSTER (bb1) == NULL && BB_CLUSTER (bb2) == NULL)
106738fd1498Szrj {
106838fd1498Szrj c = new_cluster ();
106938fd1498Szrj add_bb_to_cluster (c, bb1);
107038fd1498Szrj add_bb_to_cluster (c, bb2);
107138fd1498Szrj BB_CLUSTER (bb1) = c;
107238fd1498Szrj BB_CLUSTER (bb2) = c;
107338fd1498Szrj c->index = all_clusters.length ();
107438fd1498Szrj all_clusters.safe_push (c);
107538fd1498Szrj }
107638fd1498Szrj else if (BB_CLUSTER (bb1) == NULL || BB_CLUSTER (bb2) == NULL)
107738fd1498Szrj {
107838fd1498Szrj merge_bb = BB_CLUSTER (bb1) == NULL ? bb2 : bb1;
107938fd1498Szrj other_bb = BB_CLUSTER (bb1) == NULL ? bb1 : bb2;
108038fd1498Szrj merge = BB_CLUSTER (merge_bb);
108138fd1498Szrj add_bb_to_cluster (merge, other_bb);
108238fd1498Szrj BB_CLUSTER (other_bb) = merge;
108338fd1498Szrj }
108438fd1498Szrj else if (BB_CLUSTER (bb1) != BB_CLUSTER (bb2))
108538fd1498Szrj {
108638fd1498Szrj unsigned int i;
108738fd1498Szrj bitmap_iterator bi;
108838fd1498Szrj
108938fd1498Szrj old = BB_CLUSTER (bb2);
109038fd1498Szrj merge = BB_CLUSTER (bb1);
109138fd1498Szrj merge_clusters (merge, old);
109238fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (old->bbs, 0, i, bi)
109338fd1498Szrj BB_CLUSTER (BASIC_BLOCK_FOR_FN (cfun, i)) = merge;
109438fd1498Szrj all_clusters[old->index] = NULL;
109538fd1498Szrj update_rep_bb (merge, old->rep_bb);
109638fd1498Szrj delete_cluster (old);
109738fd1498Szrj }
109838fd1498Szrj else
109938fd1498Szrj gcc_unreachable ();
110038fd1498Szrj }
110138fd1498Szrj
110238fd1498Szrj /* Return true if gimple operands T1 and T2 have the same value. */
110338fd1498Szrj
110438fd1498Szrj static bool
gimple_operand_equal_value_p(tree t1,tree t2)110538fd1498Szrj gimple_operand_equal_value_p (tree t1, tree t2)
110638fd1498Szrj {
110738fd1498Szrj if (t1 == t2)
110838fd1498Szrj return true;
110938fd1498Szrj
111038fd1498Szrj if (t1 == NULL_TREE
111138fd1498Szrj || t2 == NULL_TREE)
111238fd1498Szrj return false;
111338fd1498Szrj
111438fd1498Szrj if (operand_equal_p (t1, t2, OEP_MATCH_SIDE_EFFECTS))
111538fd1498Szrj return true;
111638fd1498Szrj
111738fd1498Szrj return gvn_uses_equal (t1, t2);
111838fd1498Szrj }
111938fd1498Szrj
112038fd1498Szrj /* Return true if gimple statements S1 and S2 are equal. Gimple_bb (s1) and
112138fd1498Szrj gimple_bb (s2) are members of SAME_SUCC. */
112238fd1498Szrj
112338fd1498Szrj static bool
gimple_equal_p(same_succ * same_succ,gimple * s1,gimple * s2)112438fd1498Szrj gimple_equal_p (same_succ *same_succ, gimple *s1, gimple *s2)
112538fd1498Szrj {
112638fd1498Szrj unsigned int i;
112738fd1498Szrj tree lhs1, lhs2;
112838fd1498Szrj basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
112938fd1498Szrj tree t1, t2;
113038fd1498Szrj bool inv_cond;
113138fd1498Szrj enum tree_code code1, code2;
113238fd1498Szrj
113338fd1498Szrj if (gimple_code (s1) != gimple_code (s2))
113438fd1498Szrj return false;
113538fd1498Szrj
113638fd1498Szrj switch (gimple_code (s1))
113738fd1498Szrj {
113838fd1498Szrj case GIMPLE_CALL:
113938fd1498Szrj if (!gimple_call_same_target_p (s1, s2))
114038fd1498Szrj return false;
114138fd1498Szrj
114238fd1498Szrj t1 = gimple_call_chain (s1);
114338fd1498Szrj t2 = gimple_call_chain (s2);
114438fd1498Szrj if (!gimple_operand_equal_value_p (t1, t2))
114538fd1498Szrj return false;
114638fd1498Szrj
114738fd1498Szrj if (gimple_call_num_args (s1) != gimple_call_num_args (s2))
114838fd1498Szrj return false;
114938fd1498Szrj
115038fd1498Szrj for (i = 0; i < gimple_call_num_args (s1); ++i)
115138fd1498Szrj {
115238fd1498Szrj t1 = gimple_call_arg (s1, i);
115338fd1498Szrj t2 = gimple_call_arg (s2, i);
115438fd1498Szrj if (!gimple_operand_equal_value_p (t1, t2))
115538fd1498Szrj return false;
115638fd1498Szrj }
115738fd1498Szrj
115838fd1498Szrj lhs1 = gimple_get_lhs (s1);
115938fd1498Szrj lhs2 = gimple_get_lhs (s2);
116038fd1498Szrj if (lhs1 == NULL_TREE && lhs2 == NULL_TREE)
116138fd1498Szrj return true;
116238fd1498Szrj if (lhs1 == NULL_TREE || lhs2 == NULL_TREE)
116338fd1498Szrj return false;
116438fd1498Szrj if (TREE_CODE (lhs1) == SSA_NAME && TREE_CODE (lhs2) == SSA_NAME)
1165*58e805e6Szrj return tail_merge_valueize (lhs1) == tail_merge_valueize (lhs2);
116638fd1498Szrj return operand_equal_p (lhs1, lhs2, 0);
116738fd1498Szrj
116838fd1498Szrj case GIMPLE_ASSIGN:
116938fd1498Szrj lhs1 = gimple_get_lhs (s1);
117038fd1498Szrj lhs2 = gimple_get_lhs (s2);
117138fd1498Szrj if (TREE_CODE (lhs1) != SSA_NAME
117238fd1498Szrj && TREE_CODE (lhs2) != SSA_NAME)
117338fd1498Szrj return (operand_equal_p (lhs1, lhs2, 0)
117438fd1498Szrj && gimple_operand_equal_value_p (gimple_assign_rhs1 (s1),
117538fd1498Szrj gimple_assign_rhs1 (s2)));
117638fd1498Szrj else if (TREE_CODE (lhs1) == SSA_NAME
117738fd1498Szrj && TREE_CODE (lhs2) == SSA_NAME)
117838fd1498Szrj return operand_equal_p (gimple_assign_rhs1 (s1),
117938fd1498Szrj gimple_assign_rhs1 (s2), 0);
118038fd1498Szrj return false;
118138fd1498Szrj
118238fd1498Szrj case GIMPLE_COND:
118338fd1498Szrj t1 = gimple_cond_lhs (s1);
118438fd1498Szrj t2 = gimple_cond_lhs (s2);
118538fd1498Szrj if (!gimple_operand_equal_value_p (t1, t2))
118638fd1498Szrj return false;
118738fd1498Szrj
118838fd1498Szrj t1 = gimple_cond_rhs (s1);
118938fd1498Szrj t2 = gimple_cond_rhs (s2);
119038fd1498Szrj if (!gimple_operand_equal_value_p (t1, t2))
119138fd1498Szrj return false;
119238fd1498Szrj
119338fd1498Szrj code1 = gimple_expr_code (s1);
119438fd1498Szrj code2 = gimple_expr_code (s2);
119538fd1498Szrj inv_cond = (bitmap_bit_p (same_succ->inverse, bb1->index)
119638fd1498Szrj != bitmap_bit_p (same_succ->inverse, bb2->index));
119738fd1498Szrj if (inv_cond)
119838fd1498Szrj {
119938fd1498Szrj bool honor_nans = HONOR_NANS (t1);
120038fd1498Szrj code2 = invert_tree_comparison (code2, honor_nans);
120138fd1498Szrj }
120238fd1498Szrj return code1 == code2;
120338fd1498Szrj
120438fd1498Szrj default:
120538fd1498Szrj return false;
120638fd1498Szrj }
120738fd1498Szrj }
120838fd1498Szrj
120938fd1498Szrj /* Let GSI skip backwards over local defs. Return the earliest vuse in VUSE.
121038fd1498Szrj Return true in VUSE_ESCAPED if the vuse influenced a SSA_OP_DEF of one of the
121138fd1498Szrj processed statements. */
121238fd1498Szrj
121338fd1498Szrj static void
gsi_advance_bw_nondebug_nonlocal(gimple_stmt_iterator * gsi,tree * vuse,bool * vuse_escaped)121438fd1498Szrj gsi_advance_bw_nondebug_nonlocal (gimple_stmt_iterator *gsi, tree *vuse,
121538fd1498Szrj bool *vuse_escaped)
121638fd1498Szrj {
121738fd1498Szrj gimple *stmt;
121838fd1498Szrj tree lvuse;
121938fd1498Szrj
122038fd1498Szrj while (true)
122138fd1498Szrj {
122238fd1498Szrj if (gsi_end_p (*gsi))
122338fd1498Szrj return;
122438fd1498Szrj stmt = gsi_stmt (*gsi);
122538fd1498Szrj
122638fd1498Szrj lvuse = gimple_vuse (stmt);
122738fd1498Szrj if (lvuse != NULL_TREE)
122838fd1498Szrj {
122938fd1498Szrj *vuse = lvuse;
123038fd1498Szrj if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_DEF))
123138fd1498Szrj *vuse_escaped = true;
123238fd1498Szrj }
123338fd1498Szrj
123438fd1498Szrj if (!stmt_local_def (stmt))
123538fd1498Szrj return;
123638fd1498Szrj gsi_prev_nondebug (gsi);
123738fd1498Szrj }
123838fd1498Szrj }
123938fd1498Szrj
124038fd1498Szrj /* Return true if equal (in the sense of gimple_equal_p) statements STMT1 and
124138fd1498Szrj STMT2 are allowed to be merged. */
124238fd1498Szrj
124338fd1498Szrj static bool
merge_stmts_p(gimple * stmt1,gimple * stmt2)124438fd1498Szrj merge_stmts_p (gimple *stmt1, gimple *stmt2)
124538fd1498Szrj {
124638fd1498Szrj /* What could be better than this here is to blacklist the bb
124738fd1498Szrj containing the stmt, when encountering the stmt f.i. in
124838fd1498Szrj same_succ_hash. */
124938fd1498Szrj if (is_tm_ending (stmt1))
125038fd1498Szrj return false;
125138fd1498Szrj
125238fd1498Szrj /* Verify EH landing pads. */
125338fd1498Szrj if (lookup_stmt_eh_lp_fn (cfun, stmt1) != lookup_stmt_eh_lp_fn (cfun, stmt2))
125438fd1498Szrj return false;
125538fd1498Szrj
125638fd1498Szrj if (is_gimple_call (stmt1)
125738fd1498Szrj && gimple_call_internal_p (stmt1))
125838fd1498Szrj switch (gimple_call_internal_fn (stmt1))
125938fd1498Szrj {
126038fd1498Szrj case IFN_UBSAN_NULL:
126138fd1498Szrj case IFN_UBSAN_BOUNDS:
126238fd1498Szrj case IFN_UBSAN_VPTR:
126338fd1498Szrj case IFN_UBSAN_CHECK_ADD:
126438fd1498Szrj case IFN_UBSAN_CHECK_SUB:
126538fd1498Szrj case IFN_UBSAN_CHECK_MUL:
126638fd1498Szrj case IFN_UBSAN_OBJECT_SIZE:
126738fd1498Szrj case IFN_UBSAN_PTR:
126838fd1498Szrj case IFN_ASAN_CHECK:
126938fd1498Szrj /* For these internal functions, gimple_location is an implicit
127038fd1498Szrj parameter, which will be used explicitly after expansion.
127138fd1498Szrj Merging these statements may cause confusing line numbers in
127238fd1498Szrj sanitizer messages. */
127338fd1498Szrj return gimple_location (stmt1) == gimple_location (stmt2);
127438fd1498Szrj default:
127538fd1498Szrj break;
127638fd1498Szrj }
127738fd1498Szrj
127838fd1498Szrj return true;
127938fd1498Szrj }
128038fd1498Szrj
128138fd1498Szrj /* Determines whether BB1 and BB2 (members of same_succ) are duplicates. If so,
128238fd1498Szrj clusters them. */
128338fd1498Szrj
128438fd1498Szrj static void
find_duplicate(same_succ * same_succ,basic_block bb1,basic_block bb2)128538fd1498Szrj find_duplicate (same_succ *same_succ, basic_block bb1, basic_block bb2)
128638fd1498Szrj {
128738fd1498Szrj gimple_stmt_iterator gsi1 = gsi_last_nondebug_bb (bb1);
128838fd1498Szrj gimple_stmt_iterator gsi2 = gsi_last_nondebug_bb (bb2);
128938fd1498Szrj tree vuse1 = NULL_TREE, vuse2 = NULL_TREE;
129038fd1498Szrj bool vuse_escaped = false;
129138fd1498Szrj
129238fd1498Szrj gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
129338fd1498Szrj gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
129438fd1498Szrj
129538fd1498Szrj while (!gsi_end_p (gsi1) && !gsi_end_p (gsi2))
129638fd1498Szrj {
129738fd1498Szrj gimple *stmt1 = gsi_stmt (gsi1);
129838fd1498Szrj gimple *stmt2 = gsi_stmt (gsi2);
129938fd1498Szrj
130038fd1498Szrj if (gimple_code (stmt1) == GIMPLE_LABEL
130138fd1498Szrj && gimple_code (stmt2) == GIMPLE_LABEL)
130238fd1498Szrj break;
130338fd1498Szrj
130438fd1498Szrj if (!gimple_equal_p (same_succ, stmt1, stmt2))
130538fd1498Szrj return;
130638fd1498Szrj
130738fd1498Szrj if (!merge_stmts_p (stmt1, stmt2))
130838fd1498Szrj return;
130938fd1498Szrj
131038fd1498Szrj gsi_prev_nondebug (&gsi1);
131138fd1498Szrj gsi_prev_nondebug (&gsi2);
131238fd1498Szrj gsi_advance_bw_nondebug_nonlocal (&gsi1, &vuse1, &vuse_escaped);
131338fd1498Szrj gsi_advance_bw_nondebug_nonlocal (&gsi2, &vuse2, &vuse_escaped);
131438fd1498Szrj }
131538fd1498Szrj
131638fd1498Szrj while (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
131738fd1498Szrj {
131838fd1498Szrj tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
131938fd1498Szrj if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
132038fd1498Szrj return;
132138fd1498Szrj gsi_prev (&gsi1);
132238fd1498Szrj }
132338fd1498Szrj while (!gsi_end_p (gsi2) && gimple_code (gsi_stmt (gsi2)) == GIMPLE_LABEL)
132438fd1498Szrj {
132538fd1498Szrj tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi2)));
132638fd1498Szrj if (DECL_NONLOCAL (label) || FORCED_LABEL (label))
132738fd1498Szrj return;
132838fd1498Szrj gsi_prev (&gsi2);
132938fd1498Szrj }
133038fd1498Szrj if (!(gsi_end_p (gsi1) && gsi_end_p (gsi2)))
133138fd1498Szrj return;
133238fd1498Szrj
133338fd1498Szrj /* If the incoming vuses are not the same, and the vuse escaped into an
133438fd1498Szrj SSA_OP_DEF, then merging the 2 blocks will change the value of the def,
133538fd1498Szrj which potentially means the semantics of one of the blocks will be changed.
133638fd1498Szrj TODO: make this check more precise. */
133738fd1498Szrj if (vuse_escaped && vuse1 != vuse2)
133838fd1498Szrj return;
133938fd1498Szrj
134038fd1498Szrj if (dump_file)
134138fd1498Szrj fprintf (dump_file, "find_duplicates: <bb %d> duplicate of <bb %d>\n",
134238fd1498Szrj bb1->index, bb2->index);
134338fd1498Szrj
134438fd1498Szrj set_cluster (bb1, bb2);
134538fd1498Szrj }
134638fd1498Szrj
134738fd1498Szrj /* Returns whether for all phis in DEST the phi alternatives for E1 and
134838fd1498Szrj E2 are equal. */
134938fd1498Szrj
135038fd1498Szrj static bool
same_phi_alternatives_1(basic_block dest,edge e1,edge e2)135138fd1498Szrj same_phi_alternatives_1 (basic_block dest, edge e1, edge e2)
135238fd1498Szrj {
135338fd1498Szrj int n1 = e1->dest_idx, n2 = e2->dest_idx;
135438fd1498Szrj gphi_iterator gsi;
135538fd1498Szrj
135638fd1498Szrj for (gsi = gsi_start_phis (dest); !gsi_end_p (gsi); gsi_next (&gsi))
135738fd1498Szrj {
135838fd1498Szrj gphi *phi = gsi.phi ();
135938fd1498Szrj tree lhs = gimple_phi_result (phi);
136038fd1498Szrj tree val1 = gimple_phi_arg_def (phi, n1);
136138fd1498Szrj tree val2 = gimple_phi_arg_def (phi, n2);
136238fd1498Szrj
136338fd1498Szrj if (virtual_operand_p (lhs))
136438fd1498Szrj continue;
136538fd1498Szrj
136638fd1498Szrj if (operand_equal_for_phi_arg_p (val1, val2))
136738fd1498Szrj continue;
136838fd1498Szrj if (gvn_uses_equal (val1, val2))
136938fd1498Szrj continue;
137038fd1498Szrj
137138fd1498Szrj return false;
137238fd1498Szrj }
137338fd1498Szrj
137438fd1498Szrj return true;
137538fd1498Szrj }
137638fd1498Szrj
137738fd1498Szrj /* Returns whether for all successors of BB1 and BB2 (members of SAME_SUCC), the
137838fd1498Szrj phi alternatives for BB1 and BB2 are equal. */
137938fd1498Szrj
138038fd1498Szrj static bool
same_phi_alternatives(same_succ * same_succ,basic_block bb1,basic_block bb2)138138fd1498Szrj same_phi_alternatives (same_succ *same_succ, basic_block bb1, basic_block bb2)
138238fd1498Szrj {
138338fd1498Szrj unsigned int s;
138438fd1498Szrj bitmap_iterator bs;
138538fd1498Szrj edge e1, e2;
138638fd1498Szrj basic_block succ;
138738fd1498Szrj
138838fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (same_succ->succs, 0, s, bs)
138938fd1498Szrj {
139038fd1498Szrj succ = BASIC_BLOCK_FOR_FN (cfun, s);
139138fd1498Szrj e1 = find_edge (bb1, succ);
139238fd1498Szrj e2 = find_edge (bb2, succ);
139338fd1498Szrj if (e1->flags & EDGE_COMPLEX
139438fd1498Szrj || e2->flags & EDGE_COMPLEX)
139538fd1498Szrj return false;
139638fd1498Szrj
139738fd1498Szrj /* For all phis in bb, the phi alternatives for e1 and e2 need to have
139838fd1498Szrj the same value. */
139938fd1498Szrj if (!same_phi_alternatives_1 (succ, e1, e2))
140038fd1498Szrj return false;
140138fd1498Szrj }
140238fd1498Szrj
140338fd1498Szrj return true;
140438fd1498Szrj }
140538fd1498Szrj
140638fd1498Szrj /* Return true if BB has non-vop phis. */
140738fd1498Szrj
140838fd1498Szrj static bool
bb_has_non_vop_phi(basic_block bb)140938fd1498Szrj bb_has_non_vop_phi (basic_block bb)
141038fd1498Szrj {
141138fd1498Szrj gimple_seq phis = phi_nodes (bb);
141238fd1498Szrj gimple *phi;
141338fd1498Szrj
141438fd1498Szrj if (phis == NULL)
141538fd1498Szrj return false;
141638fd1498Szrj
141738fd1498Szrj if (!gimple_seq_singleton_p (phis))
141838fd1498Szrj return true;
141938fd1498Szrj
142038fd1498Szrj phi = gimple_seq_first_stmt (phis);
142138fd1498Szrj return !virtual_operand_p (gimple_phi_result (phi));
142238fd1498Szrj }
142338fd1498Szrj
142438fd1498Szrj /* Returns true if redirecting the incoming edges of FROM to TO maintains the
142538fd1498Szrj invariant that uses in FROM are dominates by their defs. */
142638fd1498Szrj
142738fd1498Szrj static bool
deps_ok_for_redirect_from_bb_to_bb(basic_block from,basic_block to)142838fd1498Szrj deps_ok_for_redirect_from_bb_to_bb (basic_block from, basic_block to)
142938fd1498Szrj {
143038fd1498Szrj basic_block cd, dep_bb = BB_DEP_BB (to);
143138fd1498Szrj edge_iterator ei;
143238fd1498Szrj edge e;
143338fd1498Szrj
143438fd1498Szrj if (dep_bb == NULL)
143538fd1498Szrj return true;
143638fd1498Szrj
143738fd1498Szrj bitmap from_preds = BITMAP_ALLOC (NULL);
143838fd1498Szrj FOR_EACH_EDGE (e, ei, from->preds)
143938fd1498Szrj bitmap_set_bit (from_preds, e->src->index);
144038fd1498Szrj cd = nearest_common_dominator_for_set (CDI_DOMINATORS, from_preds);
144138fd1498Szrj BITMAP_FREE (from_preds);
144238fd1498Szrj
144338fd1498Szrj return dominated_by_p (CDI_DOMINATORS, dep_bb, cd);
144438fd1498Szrj }
144538fd1498Szrj
144638fd1498Szrj /* Returns true if replacing BB1 (or its replacement bb) by BB2 (or its
144738fd1498Szrj replacement bb) and vice versa maintains the invariant that uses in the
144838fd1498Szrj replacement are dominates by their defs. */
144938fd1498Szrj
145038fd1498Szrj static bool
deps_ok_for_redirect(basic_block bb1,basic_block bb2)145138fd1498Szrj deps_ok_for_redirect (basic_block bb1, basic_block bb2)
145238fd1498Szrj {
145338fd1498Szrj if (BB_CLUSTER (bb1) != NULL)
145438fd1498Szrj bb1 = BB_CLUSTER (bb1)->rep_bb;
145538fd1498Szrj
145638fd1498Szrj if (BB_CLUSTER (bb2) != NULL)
145738fd1498Szrj bb2 = BB_CLUSTER (bb2)->rep_bb;
145838fd1498Szrj
145938fd1498Szrj return (deps_ok_for_redirect_from_bb_to_bb (bb1, bb2)
146038fd1498Szrj && deps_ok_for_redirect_from_bb_to_bb (bb2, bb1));
146138fd1498Szrj }
146238fd1498Szrj
146338fd1498Szrj /* Within SAME_SUCC->bbs, find clusters of bbs which can be merged. */
146438fd1498Szrj
146538fd1498Szrj static void
find_clusters_1(same_succ * same_succ)146638fd1498Szrj find_clusters_1 (same_succ *same_succ)
146738fd1498Szrj {
146838fd1498Szrj basic_block bb1, bb2;
146938fd1498Szrj unsigned int i, j;
147038fd1498Szrj bitmap_iterator bi, bj;
147138fd1498Szrj int nr_comparisons;
147238fd1498Szrj int max_comparisons = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_COMPARISONS);
147338fd1498Szrj
147438fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, 0, i, bi)
147538fd1498Szrj {
147638fd1498Szrj bb1 = BASIC_BLOCK_FOR_FN (cfun, i);
147738fd1498Szrj
147838fd1498Szrj /* TODO: handle blocks with phi-nodes. We'll have to find corresponding
147938fd1498Szrj phi-nodes in bb1 and bb2, with the same alternatives for the same
148038fd1498Szrj preds. */
148138fd1498Szrj if (bb_has_non_vop_phi (bb1) || bb_has_eh_pred (bb1)
148238fd1498Szrj || bb_has_abnormal_pred (bb1))
148338fd1498Szrj continue;
148438fd1498Szrj
148538fd1498Szrj nr_comparisons = 0;
148638fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (same_succ->bbs, i + 1, j, bj)
148738fd1498Szrj {
148838fd1498Szrj bb2 = BASIC_BLOCK_FOR_FN (cfun, j);
148938fd1498Szrj
149038fd1498Szrj if (bb_has_non_vop_phi (bb2) || bb_has_eh_pred (bb2)
149138fd1498Szrj || bb_has_abnormal_pred (bb2))
149238fd1498Szrj continue;
149338fd1498Szrj
149438fd1498Szrj if (BB_CLUSTER (bb1) != NULL && BB_CLUSTER (bb1) == BB_CLUSTER (bb2))
149538fd1498Szrj continue;
149638fd1498Szrj
149738fd1498Szrj /* Limit quadratic behavior. */
149838fd1498Szrj nr_comparisons++;
149938fd1498Szrj if (nr_comparisons > max_comparisons)
150038fd1498Szrj break;
150138fd1498Szrj
150238fd1498Szrj /* This is a conservative dependency check. We could test more
150338fd1498Szrj precise for allowed replacement direction. */
150438fd1498Szrj if (!deps_ok_for_redirect (bb1, bb2))
150538fd1498Szrj continue;
150638fd1498Szrj
150738fd1498Szrj if (!(same_phi_alternatives (same_succ, bb1, bb2)))
150838fd1498Szrj continue;
150938fd1498Szrj
151038fd1498Szrj find_duplicate (same_succ, bb1, bb2);
151138fd1498Szrj }
151238fd1498Szrj }
151338fd1498Szrj }
151438fd1498Szrj
151538fd1498Szrj /* Find clusters of bbs which can be merged. */
151638fd1498Szrj
151738fd1498Szrj static void
find_clusters(void)151838fd1498Szrj find_clusters (void)
151938fd1498Szrj {
152038fd1498Szrj same_succ *same;
152138fd1498Szrj
152238fd1498Szrj while (!worklist.is_empty ())
152338fd1498Szrj {
152438fd1498Szrj same = worklist.pop ();
152538fd1498Szrj same->in_worklist = false;
152638fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
152738fd1498Szrj {
152838fd1498Szrj fprintf (dump_file, "processing worklist entry\n");
152938fd1498Szrj same_succ_print (dump_file, same);
153038fd1498Szrj }
153138fd1498Szrj find_clusters_1 (same);
153238fd1498Szrj }
153338fd1498Szrj }
153438fd1498Szrj
153538fd1498Szrj /* Returns the vop phi of BB, if any. */
153638fd1498Szrj
153738fd1498Szrj static gphi *
vop_phi(basic_block bb)153838fd1498Szrj vop_phi (basic_block bb)
153938fd1498Szrj {
154038fd1498Szrj gphi *stmt;
154138fd1498Szrj gphi_iterator gsi;
154238fd1498Szrj for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
154338fd1498Szrj {
154438fd1498Szrj stmt = gsi.phi ();
154538fd1498Szrj if (! virtual_operand_p (gimple_phi_result (stmt)))
154638fd1498Szrj continue;
154738fd1498Szrj return stmt;
154838fd1498Szrj }
154938fd1498Szrj return NULL;
155038fd1498Szrj }
155138fd1498Szrj
155238fd1498Szrj /* Redirect all edges from BB1 to BB2, removes BB1 and marks it as removed. */
155338fd1498Szrj
155438fd1498Szrj static void
replace_block_by(basic_block bb1,basic_block bb2)155538fd1498Szrj replace_block_by (basic_block bb1, basic_block bb2)
155638fd1498Szrj {
155738fd1498Szrj edge pred_edge;
155838fd1498Szrj unsigned int i;
155938fd1498Szrj gphi *bb2_phi;
156038fd1498Szrj
156138fd1498Szrj bb2_phi = vop_phi (bb2);
156238fd1498Szrj
156338fd1498Szrj /* Mark the basic block as deleted. */
156438fd1498Szrj mark_basic_block_deleted (bb1);
156538fd1498Szrj
156638fd1498Szrj /* Redirect the incoming edges of bb1 to bb2. */
156738fd1498Szrj for (i = EDGE_COUNT (bb1->preds); i > 0 ; --i)
156838fd1498Szrj {
156938fd1498Szrj pred_edge = EDGE_PRED (bb1, i - 1);
157038fd1498Szrj pred_edge = redirect_edge_and_branch (pred_edge, bb2);
157138fd1498Szrj gcc_assert (pred_edge != NULL);
157238fd1498Szrj
157338fd1498Szrj if (bb2_phi == NULL)
157438fd1498Szrj continue;
157538fd1498Szrj
157638fd1498Szrj /* The phi might have run out of capacity when the redirect added an
157738fd1498Szrj argument, which means it could have been replaced. Refresh it. */
157838fd1498Szrj bb2_phi = vop_phi (bb2);
157938fd1498Szrj
158038fd1498Szrj add_phi_arg (bb2_phi, SSA_NAME_VAR (gimple_phi_result (bb2_phi)),
158138fd1498Szrj pred_edge, UNKNOWN_LOCATION);
158238fd1498Szrj }
158338fd1498Szrj
158438fd1498Szrj
158538fd1498Szrj /* Merge the outgoing edge counts from bb1 onto bb2. */
158638fd1498Szrj edge e1, e2;
158738fd1498Szrj edge_iterator ei;
158838fd1498Szrj
158938fd1498Szrj if (bb2->count.initialized_p ())
159038fd1498Szrj FOR_EACH_EDGE (e1, ei, bb1->succs)
159138fd1498Szrj {
159238fd1498Szrj e2 = find_edge (bb2, e1->dest);
159338fd1498Szrj gcc_assert (e2);
159438fd1498Szrj
159538fd1498Szrj /* If probabilities are same, we are done.
159638fd1498Szrj If counts are nonzero we can distribute accordingly. In remaining
159738fd1498Szrj cases just avreage the values and hope for the best. */
159838fd1498Szrj e2->probability = e1->probability.combine_with_count
159938fd1498Szrj (bb1->count, e2->probability, bb2->count);
160038fd1498Szrj }
160138fd1498Szrj bb2->count += bb1->count;
160238fd1498Szrj
160338fd1498Szrj /* Move over any user labels from bb1 after the bb2 labels. */
160438fd1498Szrj gimple_stmt_iterator gsi1 = gsi_start_bb (bb1);
160538fd1498Szrj if (!gsi_end_p (gsi1) && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
160638fd1498Szrj {
160738fd1498Szrj gimple_stmt_iterator gsi2 = gsi_after_labels (bb2);
160838fd1498Szrj while (!gsi_end_p (gsi1)
160938fd1498Szrj && gimple_code (gsi_stmt (gsi1)) == GIMPLE_LABEL)
161038fd1498Szrj {
161138fd1498Szrj tree label = gimple_label_label (as_a <glabel *> (gsi_stmt (gsi1)));
161238fd1498Szrj gcc_assert (!DECL_NONLOCAL (label) && !FORCED_LABEL (label));
161338fd1498Szrj if (DECL_ARTIFICIAL (label))
161438fd1498Szrj gsi_next (&gsi1);
161538fd1498Szrj else
161638fd1498Szrj gsi_move_before (&gsi1, &gsi2);
161738fd1498Szrj }
161838fd1498Szrj }
161938fd1498Szrj
162038fd1498Szrj /* Clear range info from all stmts in BB2 -- this transformation
162138fd1498Szrj could make them out of date. */
162238fd1498Szrj reset_flow_sensitive_info_in_bb (bb2);
162338fd1498Szrj
162438fd1498Szrj /* Do updates that use bb1, before deleting bb1. */
162538fd1498Szrj release_last_vdef (bb1);
162638fd1498Szrj same_succ_flush_bb (bb1);
162738fd1498Szrj
162838fd1498Szrj delete_basic_block (bb1);
162938fd1498Szrj }
163038fd1498Szrj
163138fd1498Szrj /* Bbs for which update_debug_stmt need to be called. */
163238fd1498Szrj
163338fd1498Szrj static bitmap update_bbs;
163438fd1498Szrj
163538fd1498Szrj /* For each cluster in all_clusters, merge all cluster->bbs. Returns
163638fd1498Szrj number of bbs removed. */
163738fd1498Szrj
163838fd1498Szrj static int
apply_clusters(void)163938fd1498Szrj apply_clusters (void)
164038fd1498Szrj {
164138fd1498Szrj basic_block bb1, bb2;
164238fd1498Szrj bb_cluster *c;
164338fd1498Szrj unsigned int i, j;
164438fd1498Szrj bitmap_iterator bj;
164538fd1498Szrj int nr_bbs_removed = 0;
164638fd1498Szrj
164738fd1498Szrj for (i = 0; i < all_clusters.length (); ++i)
164838fd1498Szrj {
164938fd1498Szrj c = all_clusters[i];
165038fd1498Szrj if (c == NULL)
165138fd1498Szrj continue;
165238fd1498Szrj
165338fd1498Szrj bb2 = c->rep_bb;
165438fd1498Szrj bitmap_set_bit (update_bbs, bb2->index);
165538fd1498Szrj
165638fd1498Szrj bitmap_clear_bit (c->bbs, bb2->index);
165738fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (c->bbs, 0, j, bj)
165838fd1498Szrj {
165938fd1498Szrj bb1 = BASIC_BLOCK_FOR_FN (cfun, j);
166038fd1498Szrj bitmap_clear_bit (update_bbs, bb1->index);
166138fd1498Szrj
166238fd1498Szrj replace_block_by (bb1, bb2);
166338fd1498Szrj nr_bbs_removed++;
166438fd1498Szrj }
166538fd1498Szrj }
166638fd1498Szrj
166738fd1498Szrj return nr_bbs_removed;
166838fd1498Szrj }
166938fd1498Szrj
167038fd1498Szrj /* Resets debug statement STMT if it has uses that are not dominated by their
167138fd1498Szrj defs. */
167238fd1498Szrj
167338fd1498Szrj static void
update_debug_stmt(gimple * stmt)167438fd1498Szrj update_debug_stmt (gimple *stmt)
167538fd1498Szrj {
167638fd1498Szrj use_operand_p use_p;
167738fd1498Szrj ssa_op_iter oi;
167838fd1498Szrj basic_block bbuse;
167938fd1498Szrj
168038fd1498Szrj if (!gimple_debug_bind_p (stmt))
168138fd1498Szrj return;
168238fd1498Szrj
168338fd1498Szrj bbuse = gimple_bb (stmt);
168438fd1498Szrj FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE)
168538fd1498Szrj {
168638fd1498Szrj tree name = USE_FROM_PTR (use_p);
168738fd1498Szrj gimple *def_stmt = SSA_NAME_DEF_STMT (name);
168838fd1498Szrj basic_block bbdef = gimple_bb (def_stmt);
168938fd1498Szrj if (bbdef == NULL || bbuse == bbdef
169038fd1498Szrj || dominated_by_p (CDI_DOMINATORS, bbuse, bbdef))
169138fd1498Szrj continue;
169238fd1498Szrj
169338fd1498Szrj gimple_debug_bind_reset_value (stmt);
169438fd1498Szrj update_stmt (stmt);
169538fd1498Szrj break;
169638fd1498Szrj }
169738fd1498Szrj }
169838fd1498Szrj
169938fd1498Szrj /* Resets all debug statements that have uses that are not
170038fd1498Szrj dominated by their defs. */
170138fd1498Szrj
170238fd1498Szrj static void
update_debug_stmts(void)170338fd1498Szrj update_debug_stmts (void)
170438fd1498Szrj {
170538fd1498Szrj basic_block bb;
170638fd1498Szrj bitmap_iterator bi;
170738fd1498Szrj unsigned int i;
170838fd1498Szrj
170938fd1498Szrj EXECUTE_IF_SET_IN_BITMAP (update_bbs, 0, i, bi)
171038fd1498Szrj {
171138fd1498Szrj gimple *stmt;
171238fd1498Szrj gimple_stmt_iterator gsi;
171338fd1498Szrj
171438fd1498Szrj bb = BASIC_BLOCK_FOR_FN (cfun, i);
171538fd1498Szrj for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
171638fd1498Szrj {
171738fd1498Szrj stmt = gsi_stmt (gsi);
171838fd1498Szrj if (!is_gimple_debug (stmt))
171938fd1498Szrj continue;
172038fd1498Szrj update_debug_stmt (stmt);
172138fd1498Szrj }
172238fd1498Szrj }
172338fd1498Szrj }
172438fd1498Szrj
172538fd1498Szrj /* Runs tail merge optimization. */
172638fd1498Szrj
172738fd1498Szrj unsigned int
tail_merge_optimize(unsigned int todo)172838fd1498Szrj tail_merge_optimize (unsigned int todo)
172938fd1498Szrj {
173038fd1498Szrj int nr_bbs_removed_total = 0;
173138fd1498Szrj int nr_bbs_removed;
173238fd1498Szrj bool loop_entered = false;
173338fd1498Szrj int iteration_nr = 0;
173438fd1498Szrj int max_iterations = PARAM_VALUE (PARAM_MAX_TAIL_MERGE_ITERATIONS);
173538fd1498Szrj
173638fd1498Szrj if (!flag_tree_tail_merge
173738fd1498Szrj || max_iterations == 0)
173838fd1498Szrj return 0;
173938fd1498Szrj
174038fd1498Szrj timevar_push (TV_TREE_TAIL_MERGE);
174138fd1498Szrj
174238fd1498Szrj /* We enter from PRE which has critical edges split. Elimination
174338fd1498Szrj does not process trivially dead code so cleanup the CFG if we
174438fd1498Szrj are told so. And re-split critical edges then. */
174538fd1498Szrj if (todo & TODO_cleanup_cfg)
174638fd1498Szrj {
174738fd1498Szrj cleanup_tree_cfg ();
174838fd1498Szrj todo &= ~TODO_cleanup_cfg;
174938fd1498Szrj split_critical_edges ();
175038fd1498Szrj }
175138fd1498Szrj
175238fd1498Szrj if (!dom_info_available_p (CDI_DOMINATORS))
175338fd1498Szrj {
175438fd1498Szrj /* PRE can leave us with unreachable blocks, remove them now. */
175538fd1498Szrj delete_unreachable_blocks ();
175638fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
175738fd1498Szrj }
175838fd1498Szrj init_worklist ();
175938fd1498Szrj
176038fd1498Szrj while (!worklist.is_empty ())
176138fd1498Szrj {
176238fd1498Szrj if (!loop_entered)
176338fd1498Szrj {
176438fd1498Szrj loop_entered = true;
176538fd1498Szrj alloc_cluster_vectors ();
176638fd1498Szrj update_bbs = BITMAP_ALLOC (NULL);
176738fd1498Szrj }
176838fd1498Szrj else
176938fd1498Szrj reset_cluster_vectors ();
177038fd1498Szrj
177138fd1498Szrj iteration_nr++;
177238fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
177338fd1498Szrj fprintf (dump_file, "worklist iteration #%d\n", iteration_nr);
177438fd1498Szrj
177538fd1498Szrj find_clusters ();
177638fd1498Szrj gcc_assert (worklist.is_empty ());
177738fd1498Szrj if (all_clusters.is_empty ())
177838fd1498Szrj break;
177938fd1498Szrj
178038fd1498Szrj nr_bbs_removed = apply_clusters ();
178138fd1498Szrj nr_bbs_removed_total += nr_bbs_removed;
178238fd1498Szrj if (nr_bbs_removed == 0)
178338fd1498Szrj break;
178438fd1498Szrj
178538fd1498Szrj free_dominance_info (CDI_DOMINATORS);
178638fd1498Szrj
178738fd1498Szrj if (iteration_nr == max_iterations)
178838fd1498Szrj break;
178938fd1498Szrj
179038fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
179138fd1498Szrj update_worklist ();
179238fd1498Szrj }
179338fd1498Szrj
179438fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
179538fd1498Szrj fprintf (dump_file, "htab collision / search: %f\n",
179638fd1498Szrj same_succ_htab->collisions ());
179738fd1498Szrj
179838fd1498Szrj if (nr_bbs_removed_total > 0)
179938fd1498Szrj {
180038fd1498Szrj if (MAY_HAVE_DEBUG_BIND_STMTS)
180138fd1498Szrj {
180238fd1498Szrj calculate_dominance_info (CDI_DOMINATORS);
180338fd1498Szrj update_debug_stmts ();
180438fd1498Szrj }
180538fd1498Szrj
180638fd1498Szrj if (dump_file && (dump_flags & TDF_DETAILS))
180738fd1498Szrj {
180838fd1498Szrj fprintf (dump_file, "Before TODOs.\n");
180938fd1498Szrj dump_function_to_file (current_function_decl, dump_file, dump_flags);
181038fd1498Szrj }
181138fd1498Szrj
181238fd1498Szrj mark_virtual_operands_for_renaming (cfun);
181338fd1498Szrj }
181438fd1498Szrj
181538fd1498Szrj delete_worklist ();
181638fd1498Szrj if (loop_entered)
181738fd1498Szrj {
181838fd1498Szrj delete_cluster_vectors ();
181938fd1498Szrj BITMAP_FREE (update_bbs);
182038fd1498Szrj }
182138fd1498Szrj
182238fd1498Szrj timevar_pop (TV_TREE_TAIL_MERGE);
182338fd1498Szrj
182438fd1498Szrj return todo;
182538fd1498Szrj }
1826