------- Comment #31 from rakdver at atrey dot karlin dot mff dot cuni dot cz
2006-04-04 10:20 -------
Subject: Re: [4.2 Regression] Repeated SSA update during loop header copying
> Zdenek: are you using walk_data->interesting_blocks to not visit PHI nodes on
> non-interesting blocks?
No, I am keeping lists of interesting phi nodes in each basic block (see
the patch below -- without the time measurement code, of course). Using
just interesting_blocks might be simpler, I will try how much that
helps.
Index: tree-into-ssa.c
===================================================================
*** tree-into-ssa.c (revision 112625)
--- tree-into-ssa.c (working copy)
*************** Boston, MA 02110-1301, USA. */
*** 47,52 ****
--- 47,53 ----
#include "domwalk.h"
#include "ggc.h"
#include "params.h"
+ #include "toplev.h"
/* This file builds the SSA form for a function as described in:
R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and K. Zadeck. Efficiently
*************** get_default_def_for (tree sym)
*** 777,782 ****
--- 778,800 ----
return ddef;
}
+ /* Marks phi node PHI in basic block BB for rewrite. */
+
+ static void
+ mark_phi_for_rewrite (basic_block bb, tree phi)
+ {
+ VEC (tree, heap) *phis_to_rewrite;
+
+ if (REWRITE_THIS_STMT (phi))
+ return;
+
+ phis_to_rewrite = bb->aux;
+ if (!phis_to_rewrite)
+ phis_to_rewrite = VEC_alloc (tree, heap, 10);
+ REWRITE_THIS_STMT (phi) = 1;
+ VEC_safe_push (tree, heap, phis_to_rewrite, phi);
+ bb->aux = phis_to_rewrite;
+ }
/* Insert PHI nodes for variable VAR using the iterated dominance
frontier given in PHI_INSERTION_POINTS. If UPDATE_P is true, this
*************** insert_phi_nodes_for (tree var, bitmap p
*** 846,852 ****
/* Mark this PHI node as interesting for update_ssa. */
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
! REWRITE_THIS_STMT (phi) = 1;
}
}
--- 864,870 ----
/* Mark this PHI node as interesting for update_ssa. */
REGISTER_DEFS_IN_THIS_STMT (phi) = 1;
! mark_phi_for_rewrite (bb, phi);
}
}
*************** replace_use (use_operand_p use_p, tree u
*** 1497,1502 ****
--- 1515,1522 ----
SET_USE (use_p, rdef);
}
+ unsigned long upi_cas_useful, upi_cas_total;
+ unsigned upi_calls, upi_did;
/* Visit all the successor blocks of BB looking for PHI nodes. For
every PHI node found, check if any of its arguments is in
*************** rewrite_update_phi_arguments (struct dom
*** 1509,1527 ****
{
edge e;
edge_iterator ei;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
! for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
tree arg;
use_operand_p arg_p;
! /* Skip PHI nodes that are not marked for rewrite. */
! if (!REWRITE_THIS_STMT (phi))
! continue;
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
arg = USE_FROM_PTR (arg_p);
--- 1529,1556 ----
{
edge e;
edge_iterator ei;
+ unsigned i;
+ unsigned ohi, olo;
+ unsigned long long cas;
+ bool did = false;
+
+ rdtsc(ohi, olo);
+ upi_calls++;
FOR_EACH_EDGE (e, ei, bb->succs)
{
tree phi;
+ VEC (tree, heap) *phis_to_rewrite = e->dest->aux;
! if (!phis_to_rewrite)
! continue;
!
! for (i = 0; VEC_iterate (tree, phis_to_rewrite, i, phi); i++)
{
tree arg;
use_operand_p arg_p;
! gcc_assert (REWRITE_THIS_STMT (phi));
arg_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, e);
arg = USE_FROM_PTR (arg_p);
*************** rewrite_update_phi_arguments (struct dom
*** 1534,1539 ****
--- 1563,1569 ----
/* When updating a PHI node for a recently introduced
symbol we may find NULL arguments. That's why we
take the symbol from the LHS of the PHI node. */
+ did = true;
replace_use (arg_p, SSA_NAME_VAR (PHI_RESULT (phi)));
}
else
*************** rewrite_update_phi_arguments (struct dom
*** 1541,1555 ****
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
if (symbol_marked_for_renaming (sym))
! replace_use (arg_p, sym);
else if (is_old_name (arg))
! replace_use (arg_p, arg);
}
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
}
}
}
--- 1571,1599 ----
tree sym = DECL_P (arg) ? arg : SSA_NAME_VAR (arg);
if (symbol_marked_for_renaming (sym))
! {
! did = true;
! replace_use (arg_p, sym);
! }
else if (is_old_name (arg))
! {
! did = true;
! replace_use (arg_p, arg);
! }
}
if (e->flags & EDGE_ABNORMAL)
SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (arg_p)) = 1;
}
}
+
+ cas = ttm_stop (ohi, olo);
+ if (did)
+ {
+ upi_did++;
+ upi_cas_useful += cas;
+ }
+ upi_cas_total += cas;
}
*************** static inline void
*** 1838,1844 ****
mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
bool insert_phi_p)
{
! REWRITE_THIS_STMT (stmt) = 1;
bitmap_set_bit (blocks, bb->index);
/* If VAR has not been defined in BB, then it is live-on-entry
--- 1882,1891 ----
mark_use_interesting (tree var, tree stmt, basic_block bb, bitmap blocks,
bool insert_phi_p)
{
! if (TREE_CODE (stmt) == PHI_NODE)
! mark_phi_for_rewrite (bb_for_stmt (stmt), stmt);
! else
! REWRITE_THIS_STMT (stmt) = 1;
bitmap_set_bit (blocks, bb->index);
/* If VAR has not been defined in BB, then it is live-on-entry
*************** update_ssa (unsigned update_flags)
*** 2679,2684 ****
--- 2726,2732 ----
block_stmt_iterator si;
tree phi;
+ gcc_assert (bb->aux == NULL);
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
{
REWRITE_THIS_STMT (phi) = 0;
*************** update_ssa (unsigned update_flags)
*** 2835,2840 ****
--- 2883,2897 ----
/* Free allocated memory. */
done:
+ FOR_EACH_BB (bb)
+ {
+ VEC (tree, heap) *phis_to_rewrite = bb->aux;
+ if (!phis_to_rewrite)
+ continue;
+
+ VEC_free (tree, heap, phis_to_rewrite);
+ bb->aux = NULL;
+ }
BITMAP_FREE (blocks);
delete_update_ssa ();
Index: tree-ssa-loop-ch.c
===================================================================
*** tree-ssa-loop-ch.c (revision 112625)
--- tree-ssa-loop-ch.c (working copy)
*************** copy_loop_headers (void)
*** 145,150 ****
--- 145,151 ----
copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
bbs_size = n_basic_blocks;
+ printf ("%d %d\n", loops->num, n_basic_blocks);
for (i = 1; i < loops->num; i++)
{
/* Copy at most 20 insns. */
Index: toplev.h
===================================================================
*** toplev.h (revision 112625)
--- toplev.h (working copy)
*************** exact_log2 (unsigned HOST_WIDE_INT x)
*** 189,192 ****
--- 189,206 ----
extern const char *get_src_pwd (void);
extern bool set_src_pwd (const char *);
+ #define rdtsc(hi,lo) __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi))
+
+ static inline unsigned long ttm_stop(unsigned ohi, unsigned olo)
+ {
+ unsigned nhi, nlo;
+ unsigned long t1, t2;
+
+ rdtsc(nhi, nlo);
+
+ t1 = (((unsigned long) ohi) << 32) | olo;
+ t2 = (((unsigned long) nhi) << 32) | nlo;
+
+ return t2 - t1;
+ }
#endif /* ! GCC_TOPLEV_H */
Index: main.c
===================================================================
*** main.c (revision 112625)
--- main.c (working copy)
*************** Software Foundation, 51 Franklin Street,
*** 25,30 ****
--- 25,33 ----
int main (int argc, char **argv);
+ extern unsigned long upi_cas_useful, upi_cas_total;
+ extern unsigned upi_calls, upi_did;
+
/* We define main() to call toplev_main(), which is defined in toplev.c.
We do this in a separate file in order to allow the language front-end
to define a different main(), if it so desires. */
*************** int main (int argc, char **argv);
*** 32,36 ****
int
main (int argc, char **argv)
{
! return toplev_main (argc, (const char **) argv);
}
--- 35,47 ----
int
main (int argc, char **argv)
{
! int ret;
! unsigned ohi, olo;
! unsigned long total;
!
! rdtsc (ohi, olo);
! ret = toplev_main (argc, (const char **) argv);
! total = ttm_stop (ohi, olo);
! printf ("%lu time (%u calls -- %u useful, %lu useful time), total time
%lu\n", upi_cas_total, upi_calls, upi_did, upi_cas_useful, total);
! return ret;
}
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=26830
