diff options
Diffstat (limited to 'gcc/tree-cfg.cc')
| -rw-r--r-- | gcc/tree-cfg.cc | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/gcc/tree-cfg.cc b/gcc/tree-cfg.cc index 1d20e6a..f0a5e05 100644 --- a/gcc/tree-cfg.cc +++ b/gcc/tree-cfg.cc @@ -10173,6 +10173,224 @@ make_pass_fixup_cfg (gcc::context *ctxt) return new pass_fixup_cfg (ctxt); } + +/* Sort PHI argument values for make_forwarders_with_degenerate_phis. */ + +static int +sort_phi_args (const void *a_, const void *b_) +{ + auto *a = (const std::pair<edge, hashval_t> *) a_; + auto *b = (const std::pair<edge, hashval_t> *) b_; + hashval_t ha = a->second; + hashval_t hb = b->second; + if (ha < hb) + return -1; + else if (ha > hb) + return 1; + else if (a->first->dest_idx < b->first->dest_idx) + return -1; + else if (a->first->dest_idx > b->first->dest_idx) + return 1; + else + return 0; +} + +/* Look for a non-virtual PHIs and make a forwarder block when all PHIs + have the same argument on a set of edges. This is to not consider + control dependences of individual edges for same values but only for + the common set. Returns true if changed the CFG. */ + +bool +make_forwarders_with_degenerate_phis (function *fn) +{ + bool didsomething = false; + + basic_block bb; + FOR_EACH_BB_FN (bb, fn) + { + /* Only PHIs with three or more arguments have opportunities. */ + if (EDGE_COUNT (bb->preds) < 3) + continue; + /* Do not touch loop headers or blocks with abnormal predecessors. + ??? This is to avoid creating valid loops here, see PR103458. + We might want to improve things to either explicitely add those + loops or at least consider blocks with no backedges. */ + if (bb->loop_father->header == bb + || bb_has_abnormal_pred (bb)) + continue; + + /* Take one PHI node as template to look for identical + arguments. Build a vector of candidates forming sets + of argument edges with equal values. Note optimality + depends on the particular choice of the template PHI + since equal arguments are unordered leaving other PHIs + with more than one set of equal arguments within this + argument range unsorted. We'd have to break ties by + looking at other PHI nodes. */ + gphi_iterator gsi = gsi_start_nonvirtual_phis (bb); + if (gsi_end_p (gsi)) + continue; + gphi *phi = gsi.phi (); + auto_vec<std::pair<edge, hashval_t>, 8> args; + bool need_resort = false; + for (unsigned i = 0; i < gimple_phi_num_args (phi); ++i) + { + edge e = gimple_phi_arg_edge (phi, i); + /* Skip abnormal edges since we cannot redirect them. */ + if (e->flags & EDGE_ABNORMAL) + continue; + /* Skip loop exit edges when we are in loop-closed SSA form + since the forwarder we'd create does not have a PHI node. */ + if (loops_state_satisfies_p (LOOP_CLOSED_SSA) + && loop_exit_edge_p (e->src->loop_father, e)) + continue; + + tree arg = gimple_phi_arg_def (phi, i); + if (!CONSTANT_CLASS_P (arg) && TREE_CODE (arg) != SSA_NAME) + need_resort = true; + args.safe_push (std::make_pair (e, iterative_hash_expr (arg, 0))); + } + if (args.length () < 2) + continue; + args.qsort (sort_phi_args); + /* The above sorting can be different between -g and -g0, as e.g. decls + can have different uids (-g could have bigger gaps in between them). + So, only use that to determine which args are equal, then change + second from hash value to smallest dest_idx of the edges which have + equal argument and sort again. If all the phi arguments are + constants or SSA_NAME, there is no need for the second sort, the hash + values are stable in that case. */ + hashval_t hash = args[0].second; + args[0].second = args[0].first->dest_idx; + bool any_equal = false; + for (unsigned i = 1; i < args.length (); ++i) + if (hash == args[i].second + && operand_equal_p (PHI_ARG_DEF_FROM_EDGE (phi, args[i - 1].first), + PHI_ARG_DEF_FROM_EDGE (phi, args[i].first))) + { + args[i].second = args[i - 1].second; + any_equal = true; + } + else + { + hash = args[i].second; + args[i].second = args[i].first->dest_idx; + } + if (!any_equal) + continue; + if (need_resort) + args.qsort (sort_phi_args); + + /* From the candidates vector now verify true candidates for + forwarders and create them. */ + gphi *vphi = get_virtual_phi (bb); + unsigned start = 0; + while (start < args.length () - 1) + { + unsigned i; + for (i = start + 1; i < args.length (); ++i) + if (args[start].second != args[i].second) + break; + /* args[start]..args[i-1] are equal. */ + if (start != i - 1) + { + /* Check all PHI nodes for argument equality + except for vops. */ + bool equal = true; + gphi_iterator gsi2 = gsi; + gsi_next (&gsi2); + for (; !gsi_end_p (gsi2); gsi_next (&gsi2)) + { + gphi *phi2 = gsi2.phi (); + if (virtual_operand_p (gimple_phi_result (phi2))) + continue; + tree start_arg + = PHI_ARG_DEF_FROM_EDGE (phi2, args[start].first); + for (unsigned j = start + 1; j < i; ++j) + { + if (!operand_equal_p (start_arg, + PHI_ARG_DEF_FROM_EDGE + (phi2, args[j].first))) + { + /* Another PHI might have a shorter set of + equivalent args. Go for that. */ + i = j; + if (j == start + 1) + equal = false; + break; + } + } + if (!equal) + break; + } + if (equal) + { + /* If we are asked to forward all edges the block + has all degenerate PHIs. Do nothing in that case. */ + if (start == 0 + && i == args.length () + && args.length () == gimple_phi_num_args (phi)) + break; + /* Instead of using make_forwarder_block we are + rolling our own variant knowing that the forwarder + does not need PHI nodes apart from eventually + a virtual one. */ + auto_vec<tree, 8> vphi_args; + if (vphi) + { + vphi_args.reserve_exact (i - start); + for (unsigned j = start; j < i; ++j) + vphi_args.quick_push + (PHI_ARG_DEF_FROM_EDGE (vphi, args[j].first)); + } + free_dominance_info (fn, CDI_DOMINATORS); + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "New forwarder block for edge "); + fprintf (dump_file, "%d -> %d.\n", + args[start].first->src->index, + args[start].first->dest->index); + } + basic_block forwarder = split_edge (args[start].first); + profile_count count = profile_count::zero (); + bool irr = false; + for (unsigned j = start + 1; j < i; ++j) + { + edge e = args[j].first; + if (e->flags & EDGE_IRREDUCIBLE_LOOP) + irr = true; + redirect_edge_and_branch_force (e, forwarder); + redirect_edge_var_map_clear (e); + count += e->count (); + } + forwarder->count = count; + if (irr) + { + forwarder->flags |= BB_IRREDUCIBLE_LOOP; + single_succ_edge (forwarder)->flags + |= EDGE_IRREDUCIBLE_LOOP; + } + + if (vphi) + { + tree def = copy_ssa_name (vphi_args[0]); + gphi *vphi_copy = create_phi_node (def, forwarder); + for (unsigned j = start; j < i; ++j) + add_phi_arg (vphi_copy, vphi_args[j - start], + args[j].first, UNKNOWN_LOCATION); + SET_PHI_ARG_DEF + (vphi, single_succ_edge (forwarder)->dest_idx, def); + } + didsomething = true; + } + } + /* Continue searching for more opportunities. */ + start = i; + } + } + return didsomething; +} + /* Garbage collection support for edge_def. */ extern void gt_ggc_mx (tree&); |