[ssaupdate] Local dominance info

[Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>]

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