[ssaupdate] Local dominance info

[ssaupdate] Local dominance info

[Zdenek Dvorak]

Hello,

this patch adds dominance information to statements, i.e. it makes it
possible to decide whether a statement precedes other one inside a basic
block without need to scan the whole block.

To enable this, statements inside basic block are numbered (the
numbering contains holes, so that new statements may be inserted).  This
seems to work good enough (no measurable impact on compile time).

Zdenek

	* tree-cfg.c (LDN_BITS, LDN_STARTING_VALUE, LDN_FINAL_EXPAND,
	LDN_MIDDLE_EXPAND): New constants.
	(set_ldn, get_ldn):
	(make_blocks): Set local dominance number for statements.
	(tree_merge_blocks, bsi_replace): Update local dominance numbers.
	(set_bb_for_stmt, update_new_stmt): Work only for single statements.
	(bsi_insert_before_1, bsi_insert_after_1): New functions.
	(bsi_insert_before, bsi_insert_after): Add statements one by one.
	(find_ldn_expand, dump_ldn, verify_local_dominance,
	setup_local_dom_number): New functions.
	(bsi_commit_edge_inserts_1, bsi_insert_on_edge_immediate):
	Pass BSI_CONTINUE_LINKING to bsi_insert_*.
	(tree_verify_flow_info): Call verify_local_dominance.
	(stmt_dominated_by_p): New function.
	* tree-flow.h (struct stmt_ann_d): Add local_dom_number field.
	(stmt_dominated_by_p): Declare.
	* tree-ssa-loop-ivopts.c (stmt_after_ip_original_pos): Use
	stmt_dominated_by_p.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.73.4.1
diff -c -3 -p -r2.73.4.1 tree-cfg.c
*** tree-cfg.c	17 Oct 2004 08:12:14 -0000	2.73.4.1
--- tree-cfg.c	19 Oct 2004 11:45:19 -0000
*************** static edge find_taken_edge_switch_expr 
*** 107,112 ****
--- 107,127 ----
  static tree find_case_label_for_value (tree, tree);
  static bool phi_alternatives_equal (basic_block, edge, edge);
  
+ /* Value from that the numbering of statements inside block starts
+    for purposes of recording local dominance information.  */
+ 
+ #define LDN_BITS (CHAR_BIT * SIZEOF_INT)
+ #define LDN_STARTING_VALUE (1u << (LDN_BITS - 2))
+ 
+ /* Amount by that local dominance number is increased at the end of
+    block.  */
+ 
+ #define LDN_FINAL_EXPAND (1u << 10)
+ 
+ /* Amount by that local dominance number is spaced if it needs to be
+    renumbered in the middle of a basic block.  */
+ 
+ #define LDN_MIDDLE_EXPAND (1u << 8)
  
  /*---------------------------------------------------------------------------
  			      Create basic blocks
*************** clear_blocks_annotations (void)
*** 319,324 ****
--- 334,354 ----
      bb->tree_annotations = NULL;
  }
  
+ /* Set local dominance number for statement STMT to NUM.  */
+ 
+ static void
+ set_ldn (tree stmt, unsigned num)
+ {
+   stmt_ann (stmt)->local_dom_number = num;
+ }
+ 
+ /* Returns local dominance number for statement STMT.  */
+ 
+ static unsigned
+ get_ldn (tree stmt)
+ {
+   return stmt_ann (stmt)->local_dom_number;
+ }
  
  /* Build a flowgraph for the statement_list STMT_LIST.  */
  
*************** make_blocks (tree stmt_list)
*** 364,369 ****
--- 394,411 ----
        tsi_next (&i);
        first_stmt_of_list = false;
      }
+ 
+   FOR_EACH_BB (bb)
+     {
+       block_stmt_iterator bsi;
+       unsigned act = LDN_STARTING_VALUE;
+ 
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	{
+ 	  set_ldn (bsi_stmt (bsi), act);
+ 	  act += LDN_FINAL_EXPAND;
+ 	}
+     }
  }
  
  
*************** tree_can_merge_blocks_p (basic_block a, 
*** 1065,1071 ****
    return true;
  }
  
- 
  /* Merge block B into block A.  */
  
  static void
--- 1107,1112 ----
*************** tree_merge_blocks (basic_block a, basic_
*** 1073,1078 ****
--- 1114,1121 ----
  {
    block_stmt_iterator bsi;
    tree_stmt_iterator last;
+   unsigned ldn = LDN_STARTING_VALUE;
+   tree stmt;
  
    if (dump_file)
      fprintf (dump_file, "Merging blocks %d and %d\n", a->index, b->index);
*************** tree_merge_blocks (basic_block a, basic_
*** 1083,1089 ****
    gcc_assert (EDGE_SUCC (a, 0)->flags & EDGE_FALLTHRU);
    gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
  
!   /* Remove labels from B and set bb_for_stmt to A for other statements.  */
    for (bsi = bsi_start (b); !bsi_end_p (bsi);)
      {
        if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
--- 1126,1138 ----
    gcc_assert (EDGE_SUCC (a, 0)->flags & EDGE_FALLTHRU);
    gcc_assert (!last_stmt (a) || !stmt_ends_bb_p (last_stmt (a)));
  
!   /* Find the maximum local dominance number of A.  */
!   stmt = last_stmt (a);
!   if (stmt)
!     ldn = get_ldn (stmt) + LDN_FINAL_EXPAND;
! 
!   /* Remove labels from B, set bb_for_stmt to A and local_dom_number
!      for other statements.  */
    for (bsi = bsi_start (b); !bsi_end_p (bsi);)
      {
        if (TREE_CODE (bsi_stmt (bsi)) == LABEL_EXPR)
*************** tree_merge_blocks (basic_block a, basic_
*** 1091,1096 ****
--- 1140,1147 ----
        else
  	{
  	  set_bb_for_stmt (bsi_stmt (bsi), a);
+ 	  set_ldn (bsi_stmt (bsi), ldn);
+ 	  ldn += LDN_FINAL_EXPAND;
  	  bsi_next (&bsi);
  	}
      }
*************** last_and_only_stmt (basic_block bb)
*** 2600,2638 ****
  void
  set_bb_for_stmt (tree t, basic_block bb)
  {
    if (TREE_CODE (t) == PHI_NODE)
-     PHI_BB (t) = bb;
-   else if (TREE_CODE (t) == STATEMENT_LIST)
      {
!       tree_stmt_iterator i;
!       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
! 	set_bb_for_stmt (tsi_stmt (i), bb);
      }
!   else
!     {
!       stmt_ann_t ann = get_stmt_ann (t);
!       ann->bb = bb;
  
!       /* If the statement is a label, add the label to block-to-labels map
! 	 so that we can speed up edge creation for GOTO_EXPRs.  */
!       if (TREE_CODE (t) == LABEL_EXPR)
! 	{
! 	  int uid;
! 
! 	  t = LABEL_EXPR_LABEL (t);
! 	  uid = LABEL_DECL_UID (t);
! 	  if (uid == -1)
! 	    {
! 	      LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
! 	      if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
! 		VARRAY_GROW (label_to_block_map, 3 * uid / 2);
! 	    }
! 	  else
! 	    /* We're moving an existing label.  Make sure that we've
! 		removed it from the old block.  */
! 	    gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
! 	  VARRAY_BB (label_to_block_map, uid) = bb;
  	}
      }
  }
  
--- 2651,2688 ----
  void
  set_bb_for_stmt (tree t, basic_block bb)
  {
+   stmt_ann_t ann;
+ 
+   gcc_assert (TREE_CODE (t) != STATEMENT_LIST);
+ 
    if (TREE_CODE (t) == PHI_NODE)
      {
!       PHI_BB (t) = bb;
!       return;
      }
!       
!   ann = get_stmt_ann (t);
!   ann->bb = bb;
  
!   /* If the statement is a label, add the label to block-to-labels map
!      so that we can speed up edge creation for GOTO_EXPRs.  */
!   if (TREE_CODE (t) == LABEL_EXPR)
!     {
!       int uid;
! 
!       t = LABEL_EXPR_LABEL (t);
!       uid = LABEL_DECL_UID (t);
!       if (uid == -1)
! 	{
! 	  LABEL_DECL_UID (t) = uid = cfun->last_label_uid++;
! 	  if (VARRAY_SIZE (label_to_block_map) <= (unsigned) uid)
! 	    VARRAY_GROW (label_to_block_map, 3 * uid / 2);
  	}
+       else
+ 	/* We're moving an existing label.  Make sure that we've
+ 	   removed it from the old block.  */
+ 	gcc_assert (!bb || !VARRAY_BB (label_to_block_map, uid));
+       VARRAY_BB (label_to_block_map, uid) = bb;
      }
  }
  
*************** stmt_for_bsi (tree stmt)
*** 2654,2700 ****
  static inline void
  update_new_stmt (tree t)
  {
!   if (TREE_CODE (t) == STATEMENT_LIST)
      {
!       tree_stmt_iterator i;
!       tree stmt;
!       for (i = tsi_start (t); !tsi_end_p (i); tsi_next (&i))
!         {
! 	  stmt = tsi_stmt (i);
! 	  if (stmt_modified_p (stmt))
! 	    get_stmt_operands (stmt);
  	}
      }
-   else
-     if (stmt_modified_p (t))
-       get_stmt_operands (t);
  }
  
! /* Insert statement (or statement list) T before the statement
!    pointed-to by iterator I.  M specifies how to update iterator I
!    after insertion (see enum bsi_iterator_update).  */
  
! void
! bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
    update_new_stmt (t);
!   tsi_link_before (&i->tsi, t, m);
  }
  
! 
! /* Insert statement (or statement list) T after the statement
!    pointed-to by iterator I.  M specifies how to update iterator I
!    after insertion (see enum bsi_iterator_update).  */
  
  void
! bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
    update_new_stmt (t);
!   tsi_link_after (&i->tsi, t, m);
  }
  
  
  /* Remove the statement pointed to by iterator I.  The iterator is updated
     to the next statement.  */
--- 2704,2987 ----
  static inline void
  update_new_stmt (tree t)
  {
!   gcc_assert (TREE_CODE (t) != STATEMENT_LIST);
!   if (stmt_modified_p (t))
!     get_stmt_operands (t);
! }
! 
! /* Returns direction in that local dominance numbering should be expanded
!    from BSI.  DIST is the distance to that it needs to be expanded.
!    MIN and MAX are the minimal and the maximal number of the statement
!    in the area.  */
! 
! static int
! find_ldn_expand (block_stmt_iterator bsi, unsigned *dist,
! 		 unsigned *min, unsigned *max)
! {
!   block_stmt_iterator bsip = bsi, bsin = bsi;
!   unsigned valp = LDN_STARTING_VALUE, valn = LDN_STARTING_VALUE;
!   unsigned reqdiff = 2 * LDN_MIDDLE_EXPAND;
! 
!   *dist = 0;
!   *min = LDN_STARTING_VALUE;
!   *max = LDN_STARTING_VALUE;
! 
!   while (1)
      {
!       bsi_prev (&bsip);
!       bsi_next (&bsin);
! 
!       if (*dist == 0)
! 	{
! 	  if (!bsi_end_p (bsip))
! 	    valp = get_ldn (bsi_stmt (bsip)) + LDN_FINAL_EXPAND;
! 
! 	  if (!bsi_end_p (bsin))
! 	    valn = get_ldn (bsi_stmt (bsin)) - LDN_FINAL_EXPAND;
! 	}
! 
!       if (bsi_end_p (bsin))
! 	{
! 	  *min = valp;
! 	  return 1;
! 	}
! 
!       if (bsi_end_p (bsip))
! 	{
! 	  *max = valn;
! 	  return -1;
  	}
+ 
+       *min = get_ldn (bsi_stmt (bsip));
+       *max = get_ldn (bsi_stmt (bsin));
+ 
+       if (*dist == 0 && *max > *min + 1)
+ 	return 0;
+ 
+       (*dist)++;
+ 
+       if (*max > *min + reqdiff)
+ 	return 0;
+ 
+       reqdiff += 2 * LDN_MIDDLE_EXPAND;
      }
  }
  
! /* Dumps local dominance numbers in basic block BB to file F.  */
  
! static void
! dump_ldn (FILE *f, basic_block bb)
! {
!   block_stmt_iterator bsi;
! 
!   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
!     fprintf (f, "%d\n", get_ldn (bsi_stmt (bsi)));
! }
! 
! /* Checks that local dominance numbers grow monotonically in basic block BB.
!    Return false if it is the case, true otherwise.  */
! 
! static bool
! verify_local_dominance (basic_block bb)
! {
!   unsigned least_local_dom_number = 0;
!   block_stmt_iterator bsi;
!   tree stmt;
! 
!   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
!     {
!       stmt = bsi_stmt (bsi);
!       if (get_ldn (stmt) < least_local_dom_number)
! 	{
! 	  error ("Local dominance information corrupted in block %d\n",
! 		 bb->index);
! 	  dump_ldn (stderr, bb);
! 
! 	  return true;
! 	}
!       least_local_dom_number = get_ldn (stmt) + 1;
!     }
! 
!   return false;
! }
! 
! /* Set local dominance number for statement pointed to by BSI, and
!    renumber surrounding statements if necessary.  */
! 
! static void
! setup_local_dom_number (block_stmt_iterator bsi)
! {
!   unsigned dist, min, max, i, step, act, mid;
!   int dir;
!   block_stmt_iterator absi;
! 
!   dir = find_ldn_expand (bsi, &dist, &min, &max);
! 
!   if (dir < 0)
!     {
!       /* Expand numbering towards start of the basic block.  */
!       act = max;
!       for (; !bsi_end_p (bsi); bsi_prev (&bsi), act -= LDN_FINAL_EXPAND)
! 	set_ldn (bsi_stmt (bsi), act);
!       return;
!     }
!   
!   if (dir > 0)
!     {
!       /* Expand numbering towards end of the basic block.  */
!       act = min;
!       for (; !bsi_end_p (bsi); bsi_next (&bsi), act += LDN_FINAL_EXPAND)
! 	set_ldn (bsi_stmt (bsi), act);
!       return;
!     }
! 
!   mid = (min + max) / 2;
!   set_ldn (bsi_stmt (bsi), mid);
! 
!   if (dist == 0)
!     return;
! 
!   /* We need to renumber area around bsi.  */
!   step = (mid - min) / dist;
!   absi = bsi;
!   act = mid;
!   for (i = 0; i < dist; i++)
!     {
!       bsi_prev (&absi);
!       act -= step;
!       set_ldn (bsi_stmt (absi), act);
!     }
! 
!   step = (max - mid) / dist;
!   absi = bsi;
!   act = mid;
!   for (i = 0; i < dist; i++)
!     {
!       bsi_next (&absi);
!       act += step;
!       set_ldn (bsi_stmt (absi), act);
!     }
! }
! 
! /* Insert single statement T before the statement pointed-to by iterator I.
!    Iterator is always moved to the new statement.  */
! 
! static void
! bsi_insert_before_1 (block_stmt_iterator *i, tree t)
  {
    set_bb_for_stmt (t, i->bb);
    update_new_stmt (t);
!   tsi_link_before (&i->tsi, t, TSI_NEW_STMT);
!   setup_local_dom_number (*i);
  }
  
! /* Insert statement (or list of statements) T before the statement pointed-to
!    by iterator I.  M specifies how to update iterator I after insertion (see
!    enum bsi_iterator_update).  */
  
  void
! bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
! {
!   tree_stmt_iterator tsi;
!   unsigned n;
! 
!   if (TREE_CODE (t) != STATEMENT_LIST)
!     {
!       bsi_insert_before_1 (i, t);
! 
!       if (m == BSI_SAME_STMT)
! 	bsi_next (i);
! 
!       return;
!     }
! 
!   for (tsi = tsi_last (t), n = 0; !tsi_end_p (tsi); tsi_prev (&tsi), n++)
!     bsi_insert_before_1 (i, tsi_stmt (tsi));
! 
!   gcc_assert (n != 0);
! 
!   switch (m)
!     {
!     case BSI_SAME_STMT:
!       break;
! 
!     case BSI_CHAIN_END:
!       n--;
!       break;
! 
!     case BSI_CHAIN_START:
!     case BSI_CONTINUE_LINKING:
!       n = 0;
!       break;
! 
!     case BSI_NEW_STMT:
!     default:
!       gcc_unreachable ();
!     }
! 
!   while (n--)
!     bsi_next (i);
! }
! 
! /* Insert single statement T after the statement pointed-to by iterator I.
!    Iterator is always moved to the new statement.  */
! 
! static void
! bsi_insert_after_1 (block_stmt_iterator *i, tree t)
  {
    set_bb_for_stmt (t, i->bb);
    update_new_stmt (t);
!   tsi_link_after (&i->tsi, t, TSI_NEW_STMT);
!   setup_local_dom_number (*i);
  }
  
+ /* Insert statement (or list of statements) T after the statement pointed-to
+    by iterator I.  M specifies how to update iterator I after insertion (see
+    enum bsi_iterator_update).  */
+ 
+ void
+ bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
+ {
+   tree_stmt_iterator tsi;
+   unsigned n;
+ 
+   if (TREE_CODE (t) != STATEMENT_LIST)
+     {
+       bsi_insert_after_1 (i, t);
+ 
+       if (m == BSI_SAME_STMT)
+ 	bsi_prev (i);
+ 
+       return;
+     }
+ 
+   for (tsi = tsi_start (t), n = 0; !tsi_end_p (tsi); tsi_next (&tsi), n++)
+     bsi_insert_after_1 (i, tsi_stmt (tsi));
+ 
+   gcc_assert (n != 0);
+ 
+   switch (m)
+     {
+     case BSI_SAME_STMT:
+       break;
+ 
+     case BSI_CHAIN_START:
+       n--;
+       break;
+ 
+     case BSI_CHAIN_END:
+     case BSI_CONTINUE_LINKING:
+       n = 0;
+       break;
+ 
+     case BSI_NEW_STMT:
+     default:
+       gcc_unreachable ();
+     }
+ 
+   while (n--)
+     bsi_prev (i);
+ }
  
  /* Remove the statement pointed to by iterator I.  The iterator is updated
     to the next statement.  */
*************** bsi_replace (const block_stmt_iterator *
*** 2771,2776 ****
--- 3058,3064 ----
  
    *bsi_stmt_ptr (*bsi) = stmt;
    update_new_stmt (stmt);
+   set_ldn (stmt, get_ldn (orig_stmt));
  }
  
  
*************** bsi_commit_edge_inserts_1 (edge e)
*** 2909,2917 ****
        PENDING_STMT (e) = NULL_TREE;
  
        if (tree_find_edge_insert_loc (e, &bsi, NULL))
! 	bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
        else
! 	bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
      }
  }
  
--- 3197,3205 ----
        PENDING_STMT (e) = NULL_TREE;
  
        if (tree_find_edge_insert_loc (e, &bsi, NULL))
! 	bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
        else
! 	bsi_insert_before (&bsi, stmt, BSI_CONTINUE_LINKING);
      }
  }
  
*************** bsi_insert_on_edge_immediate (edge e, tr
*** 2937,2945 ****
    gcc_assert (!PENDING_STMT (e));
  
    if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
!     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
    else
!     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
  
    return new_bb;
  }
--- 3225,3233 ----
    gcc_assert (!PENDING_STMT (e));
  
    if (tree_find_edge_insert_loc (e, &bsi, &new_bb))
!     bsi_insert_after (&bsi, stmt, BSI_CONTINUE_LINKING);
    else
!     bsi_insert_before (&bsi, stmt, BSI_CONTINUE_LINKING);
  
    return new_bb;
  }
*************** tree_verify_flow_info (void)
*** 3418,3423 ****
--- 3706,3715 ----
      {
        bool found_ctrl_stmt = false;
  
+       /* Verify that local dominance info numbers grow monotonically.  */
+       if (verify_local_dominance (bb))
+ 	err = 1;
+       
        /* Skip labels on the start of basic block.  */
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
  	{
*************** extract_true_false_edges_from_block (bas
*** 5297,5302 ****
--- 5589,5621 ----
      }
  }
  
+ /* Returns true if STMT2 dominates STMT1.  */
+ 
+ bool
+ stmt_dominated_by_p (tree stmt1, tree stmt2)
+ {
+   basic_block bb1 = bb_for_stmt (stmt1);
+   basic_block bb2 = bb_for_stmt (stmt2);
+ 
+   if (!dominated_by_p (CDI_DOMINATORS, bb1, bb2))
+     return false;
+ 
+   if (bb1 != bb2)
+     return true;
+ 
+   /* This is a bit doubtful, since it is not quite clear what exactly should
+      this mean -- does the caller ask for the definition in phi node or one of
+      the uses?  We assume the former (which is a bit weird), since we do not
+      have information for the later.  */
+   if (TREE_CODE (stmt1) == PHI_NODE)
+     return false;
+ 
+   if (TREE_CODE (stmt2) == PHI_NODE)
+     return true;
+ 
+   return get_ldn (stmt2) <= get_ldn (stmt1);
+ }
+ 
  struct tree_opt_pass pass_warn_function_return =
  {
    NULL,					/* name */
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow.h,v
retrieving revision 2.52.4.1
diff -c -3 -p -r2.52.4.1 tree-flow.h
*** tree-flow.h	17 Oct 2004 08:12:14 -0000	2.52.4.1
--- tree-flow.h	19 Oct 2004 11:45:19 -0000
*************** struct stmt_ann_d GTY(())
*** 267,272 ****
--- 267,276 ----
    /* Set of variables that have had their address taken in the statement.  */
    bitmap addresses_taken;
  
+   /* Used to decide whether a statement dominates another one locally inside
+      a basic block.  */
+   unsigned local_dom_number;
+   
    /* Unique identifier for this statement.  These ID's are to be created
       by each pass on an as-needed basis in any order convenient for the
       pass which needs statement UIDs.  */
*************** extern tree gimplify_build2 (block_stmt_
*** 491,496 ****
--- 495,501 ----
  			     tree, tree, tree);
  extern tree gimplify_build3 (block_stmt_iterator *, enum tree_code,
  			     tree, tree, tree, tree);
+ bool stmt_dominated_by_p (tree, tree);
  
  /* In tree-pretty-print.c.  */
  extern void dump_generic_bb (FILE *, basic_block, int, int);
Index: tree-ssa-loop-ivopts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-ivopts.c,v
retrieving revision 2.17.6.1
diff -c -3 -p -r2.17.6.1 tree-ssa-loop-ivopts.c
*** tree-ssa-loop-ivopts.c	17 Oct 2004 08:12:15 -0000	2.17.6.1
--- tree-ssa-loop-ivopts.c	19 Oct 2004 11:45:19 -0000
*************** stmt_after_ip_normal_pos (struct loop *l
*** 531,555 ****
  static bool
  stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
  {
!   basic_block cand_bb = bb_for_stmt (cand->incremented_at);
!   basic_block stmt_bb = bb_for_stmt (stmt);
!   block_stmt_iterator bsi;
! 
!   if (!dominated_by_p (CDI_DOMINATORS, stmt_bb, cand_bb))
!     return false;
! 
!   if (stmt_bb != cand_bb)
!     return true;
! 
!   /* Scan the block from the end, since the original ivs are usually
!      incremented at the end of the loop body.  */
!   for (bsi = bsi_last (stmt_bb); ; bsi_prev (&bsi))
!     {
!       if (bsi_stmt (bsi) == cand->incremented_at)
! 	return false;
!       if (bsi_stmt (bsi) == stmt)
! 	return true;
!     }
  }
  
  /* Returns true if STMT if after the place where the induction variable
--- 531,538 ----
  static bool
  stmt_after_ip_original_pos (struct iv_cand *cand, tree stmt)
  {
!   return (stmt != cand->incremented_at
! 	  && stmt_dominated_by_p (stmt, cand->incremented_at));
  }
  
  /* Returns true if STMT if after the place where the induction variable

Re: [ssaupdate] Local dominance info

[Andrew MacLeod]

On Tue, 2004-10-19 at 17:51, Zdenek Dvorak wrote:
> Hello,
> 
> this patch adds dominance information to statements, i.e. it makes it
> possible to decide whether a statement precedes other one inside a basic
> block without need to scan the whole block.
> 
> To enable this, statements inside basic block are numbered (the
> numbering contains holes, so that new statements may be inserted).  This
> seems to work good enough (no measurable impact on compile time).

You want to keep and maintain this information all the time?

This strikes me *much* more as a local thing that an individual pass
might be interested in, and so should number the stmt's itself for the
duration of its interest. 

I think trying to keep numbered order of stmts within blocks for the
duration of SSA is a very bad idea since most optimizations do not care.
So you have the overhead of making sure that you keep things kosher
everytime you ever move anything. You will always have an end case where
the hole isnt big enough, so you'll have to renumber either the entire
block, or parts of it. This will no doubt happen during an optimization
phase that doesn't care about local numbers.

I can see having an aux field in stmts much like edges do, where an
individual pass can use that field for whatever it want, in your case
for these local dominance numbers. If you wish to maintain these numbers
for a series of optimizations and you are interested in having the
insert routines take care of it for you, then at best I could  see
creating  local_dom_insert_before(), local_dom_insert_after(), etc which
call the bsi_* insertion routines, and then update your local dominance
info. Then you could use those routine in areas where you care about it
without affecting anyone else.  This seems like it ought to be pretty
easy to do since you call setup_local_dom_number() as the last thing
after inserting.

I do not thing this should be part of the generic bsi_* routines.

Andrew

Re: [ssaupdate] Local dominance info

[Zdenek Dvorak]

Hello,

> > this patch adds dominance information to statements, i.e. it makes it
> > possible to decide whether a statement precedes other one inside a basic
> > block without need to scan the whole block.
> > 
> > To enable this, statements inside basic block are numbered (the
> > numbering contains holes, so that new statements may be inserted).  This
> > seems to work good enough (no measurable impact on compile time).
> 
> You want to keep and maintain this information all the time?

yes.  Given that it costs nothing, it seems to be the best choice to me.

> This strikes me *much* more as a local thing that an individual pass
> might be interested in, and so should number the stmt's itself for the
> duration of its interest. 

Still you would need some mechanism to update things when statements are
inserted, so this would make things only more complicated.

Zdenek

Re: [ssaupdate] Local dominance info

[Andrew MacLeod]

On Wed, 2004-10-20 at 15:27, Zdenek Dvorak wrote:
> Hello,
> 
> > > this patch adds dominance information to statements, i.e. it makes it
> > > possible to decide whether a statement precedes other one inside a basic
> > > block without need to scan the whole block.
> > > 
> > > To enable this, statements inside basic block are numbered (the
> > > numbering contains holes, so that new statements may be inserted).  This
> > > seems to work good enough (no measurable impact on compile time).
> > 
> > You want to keep and maintain this information all the time?
> 
> yes.  Given that it costs nothing, it seems to be the best choice to me.
> 
> > This strikes me *much* more as a local thing that an individual pass
> > might be interested in, and so should number the stmt's itself for the
> > duration of its interest. 
> 
> Still you would need some mechanism to update things when statements are
> inserted, so this would make things only more complicated.

and what wrong with the local_dom_insert_after() and
local_dom_insert_before() which call the bsi routines? It looks pretty
trivial to do that,  then the info only exists and is maintained when
you want it.

I don't see any reason why it should be kept up to date all the time
when virtually no-one else cares about it. It seems like its a cheap to
calculate on the fly, and if its a big deal to you, then its not
difficult to keep up to date locally if you use local dominator aware
insert routines which call the BSI ones.

Andrew

Re: [ssaupdate] Local dominance info

[Zdenek Dvorak]

Hello,

> > > > this patch adds dominance information to statements, i.e. it makes it
> > > > possible to decide whether a statement precedes other one inside a basic
> > > > block without need to scan the whole block.
> > > > 
> > > > To enable this, statements inside basic block are numbered (the
> > > > numbering contains holes, so that new statements may be inserted).  This
> > > > seems to work good enough (no measurable impact on compile time).
> > > 
> > > You want to keep and maintain this information all the time?
> > 
> > yes.  Given that it costs nothing, it seems to be the best choice to me.
> > 
> > > This strikes me *much* more as a local thing that an individual pass
> > > might be interested in, and so should number the stmt's itself for the
> > > duration of its interest. 
> > 
> > Still you would need some mechanism to update things when statements are
> > inserted, so this would make things only more complicated.
> 
> and what wrong with the local_dom_insert_after() and
> local_dom_insert_before() which call the bsi routines? It looks pretty
> trivial to do that,  then the info only exists and is maintained when
> you want it.
> 
> I don't see any reason why it should be kept up to date all the time
> when virtually no-one else cares about it.

now.  I think this might be useful for SSA form updating (which is why I
comitted this to the branch), in which case it will be useful on large
number of places.

> It seems like its a cheap to
> calculate on the fly, and if its a big deal to you, then its not
> difficult to keep up to date locally if you use local dominator aware
> insert routines which call the BSI ones.

I would tend agree with your argumentation if there were any problems
(compile time or whatever) with the solution I am using now.  There is
not, so I do not see a reason why to change it to something more
complicated.

Zdenek

Re: [ssaupdate] Local dominance info

[Jeffrey A Law]

On Wed, 2004-10-20 at 16:25, Zdenek Dvorak wrote:

> now.  I think this might be useful for SSA form updating (which is why I
> comitted this to the branch), in which case it will be useful on large
> number of places.
I found it useful in SSA updating as well.  Alas the work I did in
that area is on hold.  I believe we use it in DSE as well.

Jeff

Re: [ssaupdate] Local dominance info

[Paolo Bonzini]

> I think trying to keep numbered order of stmts within blocks for the
> duration of SSA is a very bad idea since most optimizations do not care.
> So you have the overhead of making sure that you keep things kosher
> everytime you ever move anything.

Zdenek, do you have an analysis of the amortized worst-case complexity 
of bsi_insert_before and bsi_insert_after?

Thanks,

Paolo

Re: [ssaupdate] Local dominance info

[Zdenek Dvorak]

Hello,

> >I think trying to keep numbered order of stmts within blocks for the
> >duration of SSA is a very bad idea since most optimizations do not care.
> >So you have the overhead of making sure that you keep things kosher
> >everytime you ever move anything.
> 
> Zdenek, do you have an analysis of the amortized worst-case complexity 
> of bsi_insert_before and bsi_insert_after?

no; the algorithm is quite ad-hoc and I believe that it behaves
quite badly from the theoretic point of view.  It should (and seems to)
behave well under "normal" workload (i.e. relatively few insertions on
single place), but it of course would be better to have here something
for that some upper bound could be proved (I am fairly sure it would be
possible, and probably the solution would not be much more complicated
than the current one).

Zdenek

Re: [ssaupdate] Local dominance info

[Paolo Bonzini]

> no; the algorithm is quite ad-hoc and I believe that it behaves
> quite badly from the theoretic point of view.  It should (and seems to)
> behave well under "normal" workload (i.e. relatively few insertions on
> single place), but it of course would be better to have here something
> for that some upper bound could be proved (I am fairly sure it would be
> possible, and probably the solution would not be much more complicated
> than the current one).

I'm thinking about some kind of local algorithm that only looks at a few 
neighbors and spaces them irregularly, such as


S1:10       S1:10        S1:10      S1: 5
                                     S8:11
S2:20       S2:18        S2:18      S2:18
S3:30       S3:24        S3:23      S3:23
        =>   S6:30    =>  S6:28  =>  S6:28
                          S7:33      S7:33
S4:40       S4:36        S4:42      S4:42
S5:50       S5:50        S5:50      S5:50

The algorithm could iterate until it guarantees a spacing of at least a 
few units between two instructions (2 is enough of course, but I think 
it gives bad behavior).

Graph layout algorithms usually work by simulating spring forces between 
nodes.  Something similar can probably be done in this case quite 
efficiently.

Paolo

Re: [ssaupdate] Local dominance info

[Michael Matz]

Hi,

On Wed, 20 Oct 2004, Andrew MacLeod wrote:

> > > This strikes me *much* more as a local thing that an individual pass
> > > might be interested in, and so should number the stmt's itself for the
> > > duration of its interest. 
> > 
> > Still you would need some mechanism to update things when statements are
> > inserted, so this would make things only more complicated.
> 
> and what wrong with the local_dom_insert_after() and
> local_dom_insert_before() which call the bsi routines? It looks pretty
> trivial to do that,  then the info only exists and is maintained when
> you want it.

But then you have to ask yourself everytime you add stmts if you want to 
use these or the normal inserters.  And what about common code which 
inserts statements?  Do we need two versions of them too?

Generally I think there should be exactly one interface to do something 
(inserting stmts), so if maintaining this local numbering doesn't cost 
much it would be much cleaner to do this, instead of relying on special 
case code.

Why exactly would you like to have this keeping of information be factored 
out?

> I don't see any reason why it should be kept up to date all the time
> when virtually no-one else cares about it.

Cleanlyness of interfaces?  Less potential for funny bugs because the 
wrong inserters were used by some common code?


Ciao,
Michael.

Re: [ssaupdate] Local dominance info

[Andrew MacLeod]

On Fri, 2004-10-22 at 12:18, Michael Matz wrote:
> Hi,
> 
> On Wed, 20 Oct 2004, Andrew MacLeod wrote:
> 
> > > > This strikes me *much* more as a local thing that an individual pass
> > > > might be interested in, and so should number the stmt's itself for the
> > > > duration of its interest. 
> > > 
> > > Still you would need some mechanism to update things when statements are
> > > inserted, so this would make things only more complicated.
> > 
> > and what wrong with the local_dom_insert_after() and
> > local_dom_insert_before() which call the bsi routines? It looks pretty
> > trivial to do that,  then the info only exists and is maintained when
> > you want it.
> 
> But then you have to ask yourself everytime you add stmts if you want to 
> use these or the normal inserters.  And what about common code which 
> inserts statements?  Do we need two versions of them too?
> 
> Generally I think there should be exactly one interface to do something 
> (inserting stmts), so if maintaining this local numbering doesn't cost 
> much it would be much cleaner to do this, instead of relying on special 
> case code.
> 
> Why exactly would you like to have this keeping of information be factored 
> out?
> 

the claim is that it is cheap. I claim it will have a cost, perhaps it
is small most of the time, but there is bound to be pathological cases
which do have an impact.

> > I don't see any reason why it should be kept up to date all the time
> > when virtually no-one else cares about it.
> 
> Cleanlyness of interfaces?  Less potential for funny bugs because the 
> wrong inserters were used by some common code?

It depends. I've seen no reason for it. If it turns out that having it
present *will* make a different in updating ssa on the fly, thats
different. I've seen no argument why 70 other optimizations should keep
the information up to date when they dont care about it.

The general renamer has to go through all the basic blocks *anyway* in
order to calculate live-on-entry, so it seems pretty easy to do that
local numbering on the fly since you are making a pass the the IL
anyway.

If there is a more iterative into-ssa solution that can make use of this
info and doesnt have to make a pass through the IL, then thats an
arguement for it.  If there is a reason to keep it up to date other than
that, perhaps that is an argument too. 

So far all Ive seen/heard is keeping the information up to date doesnt
cost a lot, but I see few passes have a use for it.  Tell me how useful
it is, and why its better than calculating it on the fly when you need
it and maybe I am convinced. 

Andrew

Re: [ssaupdate] Local dominance info

[Zdenek Dvorak]

Hello,

> the claim is that it is cheap. I claim it will have a cost, perhaps it
> is small most of the time, but there is bound to be pathological cases
> which do have an impact.
> 
> > > I don't see any reason why it should be kept up to date all the time
> > > when virtually no-one else cares about it.
> > 
> > Cleanlyness of interfaces?  Less potential for funny bugs because the 
> > wrong inserters were used by some common code?
> 
> It depends. I've seen no reason for it. If it turns out that having it
> present *will* make a different in updating ssa on the fly, thats
> different. I've seen no argument why 70 other optimizations should keep
> the information up to date when they dont care about it.
> 
> The general renamer has to go through all the basic blocks *anyway* in
> order to calculate live-on-entry, so it seems pretty easy to do that
> local numbering on the fly since you are making a pass the the IL
> anyway.
> 
> If there is a more iterative into-ssa solution that can make use of this
> info and doesnt have to make a pass through the IL, then thats an
> arguement for it.  If there is a reason to keep it up to date other than
> that, perhaps that is an argument too. 
> 
> So far all Ive seen/heard is keeping the information up to date doesnt
> cost a lot, but I see few passes have a use for it.  Tell me how useful
> it is, and why its better than calculating it on the fly when you need
> it and maybe I am convinced. 

answer to your questions from my side is "I don't know."  I think it
will be useful (obviously :-), but it may turn out that I will be wrong.
Ssaupdate is a development branch, so the way things are done now do not
necessarily have to be the same (or even close to) those that will be in
final version.

Zdenek

Re: [ssaupdate] Local dominance info

[Andrew MacLeod]

On Fri, 2004-10-22 at 17:08, Zdenek Dvorak wrote:
> Hello,

> > 
> > So far all Ive seen/heard is keeping the information up to date doesnt
> > cost a lot, but I see few passes have a use for it.  Tell me how useful
> > it is, and why its better than calculating it on the fly when you need
> > it and maybe I am convinced. 
> 
> answer to your questions from my side is "I don't know."  I think it
> will be useful (obviously :-), but it may turn out that I will be wrong.
> Ssaupdate is a development branch, so the way things are done now do not
> necessarily have to be the same (or even close to) those that will be in
> final version.


Fair enough :-).  I was just watching changes early :-)

Andrew