This fixes a quadraticness in region RPO VN which happens because
dom_walker computes whole-function RPO order in its constructor
even though in the end we do not use it. That's an artifact of
C++ (we derive from dom_walker).
The fix is to lazily do costly initialization in the ::walk
method. I'm not sure we can re-use previous edge flag state
for multiple ::walk invocations when the user said
REACHABLE_BLOCKS instead of REACHABLE_BLOCKS_PRESERVING_FLAGS
so I've gone for the safe side (but I'm quite sure we do not
have a consumer walking multiple times using the same class
instance anyways).
This cuts down GIMPLE copy-header time from 11% to 0% on the
second testcase from PR46590, leaving RTL invariant motion
as the worst offender at 50% of the compile-time (through it's use of DF).
Bootstrap / regtest running on x86_64-unknown-linux-gnu.
Richard.
2019-04-01 Richard Biener <rguent...@suse.de>
PR tree-optimization/46590
* domwalk.h (dom_walker::dom_walker): Consolidate constructors.
(dom_walker::m_reachability): Add in place of...
(dom_walker::m_skip_unreachable_blocks): ...this.
* domwalk.c (dom_walker::dom_walker): Consoliate constructors.
Move complex initialization ...
(dom_walker::walk): Here. Especially compute m_bb_to_rpo
lazily and initialize edge flags on each invocation.
(dom_walker::bb_reachable): Use m_reachability.
Index: gcc/domwalk.c
===================================================================
--- gcc/domwalk.c (revision 270053)
+++ gcc/domwalk.c (working copy)
@@ -190,69 +190,11 @@ dom_walker::dom_walker (cdi_direction di
enum reachability reachability,
int *bb_index_to_rpo)
: m_dom_direction (direction),
- m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
- m_user_bb_to_rpo (true),
+ m_reachability (reachability),
+ m_user_bb_to_rpo (bb_index_to_rpo != NULL),
m_unreachable_dom (NULL),
m_bb_to_rpo (bb_index_to_rpo)
{
- /* Set up edge flags if need be. */
- switch (reachability)
- {
- default:
- gcc_unreachable ();
- case ALL_BLOCKS:
- /* No need to touch edge flags. */
- break;
-
- case REACHABLE_BLOCKS:
- set_all_edges_as_executable (cfun);
- break;
-
- case REACHABLE_BLOCKS_PRESERVING_FLAGS:
- /* Preserve the edge flags. */
- break;
- }
-}
-
-/* Constructor for a dom walker. */
-
-dom_walker::dom_walker (cdi_direction direction,
- enum reachability reachability)
- : m_dom_direction (direction),
- m_skip_unreachable_blocks (reachability != ALL_BLOCKS),
- m_user_bb_to_rpo (false),
- m_unreachable_dom (NULL),
- m_bb_to_rpo (NULL)
-{
- /* Compute the basic-block index to RPO mapping. */
- if (direction == CDI_DOMINATORS)
- {
- int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
- int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
- true);
- m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
- for (int i = 0; i < postorder_num; ++i)
- m_bb_to_rpo[postorder[i]] = i;
- free (postorder);
- }
-
- /* Set up edge flags if need be. */
- switch (reachability)
- {
- default:
- gcc_unreachable ();
- case ALL_BLOCKS:
- /* No need to touch edge flags. */
- break;
-
- case REACHABLE_BLOCKS:
- set_all_edges_as_executable (cfun);
- break;
-
- case REACHABLE_BLOCKS_PRESERVING_FLAGS:
- /* Preserve the edge flags. */
- break;
- }
}
/* Destructor. */
@@ -270,7 +212,7 @@ dom_walker::bb_reachable (struct functio
{
/* If we're not skipping unreachable blocks, then assume everything
is reachable. */
- if (!m_skip_unreachable_blocks)
+ if (m_reachability == ALL_BLOCKS)
return true;
/* If any of the predecessor edges that do not come from blocks dominated
@@ -331,6 +273,23 @@ const edge dom_walker::STOP = (edge)-1;
void
dom_walker::walk (basic_block bb)
{
+ /* Compute the basic-block index to RPO mapping lazily. */
+ if (!m_bb_to_rpo
+ && m_dom_direction == CDI_DOMINATORS)
+ {
+ int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (cfun));
+ int postorder_num = pre_and_rev_post_order_compute (NULL, postorder,
+ true);
+ m_bb_to_rpo = XNEWVEC (int, last_basic_block_for_fn (cfun));
+ for (int i = 0; i < postorder_num; ++i)
+ m_bb_to_rpo[postorder[i]] = i;
+ free (postorder);
+ }
+
+ /* Set up edge flags if need be. */
+ if (m_reachability == REACHABLE_BLOCKS)
+ set_all_edges_as_executable (cfun);
+
basic_block dest;
basic_block *worklist = XNEWVEC (basic_block,
n_basic_blocks_for_fn (cfun) * 2);
Index: gcc/domwalk.h
===================================================================
--- gcc/domwalk.h (revision 270053)
+++ gcc/domwalk.h (working copy)
@@ -60,13 +60,12 @@ public:
REACHABLE_BLOCKS_PRESERVING_FLAGS
};
- dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS);
-
/* You can provide a mapping of basic-block index to RPO if you
have that readily available or you do multiple walks. If you
specify NULL as BB_INDEX_TO_RPO dominator children will not be
walked in RPO order. */
- dom_walker (cdi_direction direction, enum reachability, int
*bb_index_to_rpo);
+ dom_walker (cdi_direction direction, enum reachability = ALL_BLOCKS,
+ int *bb_index_to_rpo = NULL);
~dom_walker ();
@@ -94,7 +93,7 @@ private:
if it is set to CDI_POST_DOMINATORS, then we walk the post
dominator tree. */
const ENUM_BITFIELD (cdi_direction) m_dom_direction : 2;
- bool m_skip_unreachable_blocks;
+ const ENUM_BITFIELD (reachability) m_reachability : 2;
bool m_user_bb_to_rpo;
basic_block m_unreachable_dom;
int *m_bb_to_rpo;
