diff options
author | Richard Biener <rguenther@suse.de> | 2018-08-27 10:55:53 +0000 |
---|---|---|
committer | Richard Biener <rguenth@gcc.gnu.org> | 2018-08-27 10:55:53 +0000 |
commit | 78ea9abc2018243af7f7ada6135144ac90c6ad27 (patch) | |
tree | 54378267ac437a8e59e1ddd669550b60dd8f788f /gcc/cfganal.c | |
parent | 8d2d69eba471b77adc69e80f224b841c41f48cf6 (diff) | |
download | gcc-78ea9abc2018243af7f7ada6135144ac90c6ad27.tar.gz |
cfganal.h (rev_post_order_and_mark_dfs_back_seme): Declare.
2018-08-27 Richard Biener <rguenther@suse.de>
* cfganal.h (rev_post_order_and_mark_dfs_back_seme): Declare.
* cfganal.c (rev_post_order_and_mark_dfs_back_seme): New function.
* tree-ssa-sccvn.h (struct vn_pval): New structure.
(struct vn_nary_op_s): Add unwind_to member. Add
predicated_values flag and put result into a union together
with a linked list of vn_pval.
(struct vn_ssa_aux): Add name member to make maintaining
a map of SSA name to vn_ssa_aux possible. Remove no longer
needed info, dfsnum, low, visited, on_sccstack, use_processed
and range_info_anti_range_p members.
(run_scc_vn, vn_eliminate, free_scc_vn, vn_valueize): Remove.
(do_rpo_vn, run_rpo_vn, eliminate_with_rpo_vn, free_rpo_vn):
New functions.
(vn_valueize): New global.
(vn_context_bb): Likewise.
(VN_INFO_RANGE_INFO, VN_INFO_ANTI_RANGE_P, VN_INFO_RANGE_TYPE,
VN_INFO_PTR_INFO): Remove.
* tree-ssa-sccvn.c: ... (rewrite)
(pass_fre::execute): For -O2+ initialize loops and run
RPO VN in optimistic mode (iterating). For -O1 and -Og
run RPO VN in non-optimistic mode.
* params.def (PARAM_SCCVN_MAX_SCC_SIZE): Remove.
(PARAM_RPO_VN_MAX_LOOP_DEPTH): Add.
* doc/invoke.texi (sccvn-max-scc-size): Remove.
(rpo-vn-max-loop-depth): Document.
* tree-ssa-alias.c (walk_non_aliased_vuses): Stop walking
when valuezing the VUSE signals we walked out of the region.
* tree-ssa-pre.c (phi_translate_1): Ignore predicated values.
(phi_translate): Set VN context block to use for availability
lookup.
(compute_avail): Likewise.
(pre_valueize): New function.
(pass_pre::execute): Adjust to the RPO VN API.
* tree-ssa-loop-ivcanon.c: Include tree-ssa-sccvn.h.
(propagate_constants_for_unrolling): Remove.
(tree_unroll_loops_completely): Perform value-numbering
on the unrolled bodies loop parent.
* g++.dg/torture/20180705-1.C: New testcase.
* gcc.dg/tree-ssa/ssa-fre-67.c: Likewise.
* gcc.dg/tree-ssa/ssa-ccp-14.c: Scan FRE dump.
* gcc.dg/tree-ssa/ssa-fre-46.c: Use -O2.
* gcc.dg/tree-ssa/vrp92.c: Disable FRE.
* gcc.dg/pr83666.c: Drop --param=sccvn-max-scc-size option.
* gcc.dg/pr85195.c: Likewise.
* gcc.dg/pr85467.c: Likewise.
* gcc.dg/torture/pr81790.c: Likewise.
* gfortran.dg/reassoc_4.f: Change max-completely-peeled-insns
param to current default.
From-SVN: r263875
Diffstat (limited to 'gcc/cfganal.c')
-rw-r--r-- | gcc/cfganal.c | 115 |
1 files changed, 114 insertions, 1 deletions
diff --git a/gcc/cfganal.c b/gcc/cfganal.c index b9944c6ef98..3b80758e8f2 100644 --- a/gcc/cfganal.c +++ b/gcc/cfganal.c @@ -1057,8 +1057,121 @@ pre_and_rev_post_order_compute (int *pre_order, int *rev_post_order, return pre_order_num; } +/* Unlike pre_and_rev_post_order_compute we fill rev_post_order backwards + so iterating in RPO order needs to start with rev_post_order[n - 1] + going to rev_post_order[0]. If FOR_ITERATION is true then try to + make CFG cycles fit into small contiguous regions of the RPO order. + When FOR_ITERATION is true this requires up-to-date loop structures. */ + +int +rev_post_order_and_mark_dfs_back_seme (struct function *fn, edge entry, + bitmap exit_bbs, bool for_iteration, + int *rev_post_order) +{ + int pre_order_num = 0; + int rev_post_order_num = 0; + + /* Allocate stack for back-tracking up CFG. Worst case we need + O(n^2) edges but the following should suffice in practice without + a need to re-allocate. */ + auto_vec<edge, 20> stack (2 * n_basic_blocks_for_fn (fn)); + + int *pre = XNEWVEC (int, 2 * last_basic_block_for_fn (fn)); + int *post = pre + last_basic_block_for_fn (fn); + + /* BB flag to track nodes that have been visited. */ + auto_bb_flag visited (fn); + /* BB flag to track which nodes have post[] assigned to avoid + zeroing post. */ + auto_bb_flag post_assigned (fn); + + /* Push the first edge on to the stack. */ + stack.quick_push (entry); + + while (!stack.is_empty ()) + { + basic_block src; + basic_block dest; + + /* Look at the edge on the top of the stack. */ + int idx = stack.length () - 1; + edge e = stack[idx]; + src = e->src; + dest = e->dest; + e->flags &= ~EDGE_DFS_BACK; + + /* Check if the edge destination has been visited yet. */ + if (! bitmap_bit_p (exit_bbs, dest->index) + && ! (dest->flags & visited)) + { + /* Mark that we have visited the destination. */ + dest->flags |= visited; + + pre[dest->index] = pre_order_num++; + + if (EDGE_COUNT (dest->succs) > 0) + { + /* Since the DEST node has been visited for the first + time, check its successors. */ + /* Push the edge vector in reverse to match previous behavior. */ + stack.reserve (EDGE_COUNT (dest->succs)); + for (int i = EDGE_COUNT (dest->succs) - 1; i >= 0; --i) + stack.quick_push (EDGE_SUCC (dest, i)); + /* Generalize to handle more successors? */ + if (for_iteration + && EDGE_COUNT (dest->succs) == 2) + { + edge &e1 = stack[stack.length () - 2]; + if (loop_exit_edge_p (e1->src->loop_father, e1)) + std::swap (e1, stack.last ()); + } + } + else + { + /* There are no successors for the DEST node so assign + its reverse completion number. */ + post[dest->index] = rev_post_order_num; + dest->flags |= post_assigned; + rev_post_order[rev_post_order_num] = dest->index; + rev_post_order_num++; + } + } + else + { + if (dest->flags & visited + && src != entry->src + && pre[src->index] >= pre[dest->index] + && !(dest->flags & post_assigned)) + e->flags |= EDGE_DFS_BACK; + + if (idx != 0 && stack[idx - 1]->src != src) + { + /* There are no more successors for the SRC node + so assign its reverse completion number. */ + post[src->index] = rev_post_order_num; + src->flags |= post_assigned; + rev_post_order[rev_post_order_num] = src->index; + rev_post_order_num++; + } + + stack.pop (); + } + } + + XDELETEVEC (pre); + + /* Clear the temporarily allocated flags. */ + for (int i = 0; i < rev_post_order_num; ++i) + BASIC_BLOCK_FOR_FN (fn, rev_post_order[i])->flags + &= ~(post_assigned|visited); + + return rev_post_order_num; +} + + + /* Compute the depth first search order on the _reverse_ graph and - store in the array DFS_ORDER, marking the nodes visited in VISITED. + store it in the array DFS_ORDER, marking the nodes visited in VISITED. Returns the number of nodes visited. The computation is split into three pieces: |