Patchwork Inter-bb range test optimization (PRs tree-optimization/19105, tree-optimization/21643, tree-optimization/46309)

login
register
mail settings
Submitter Jakub Jelinek
Date Oct. 26, 2012, 5:27 p.m.
Message ID <20121026172743.GB1752@tucnak.redhat.com>
Download mbox | patch
Permalink /patch/194544/
State New
Headers show

Comments

Jakub Jelinek - Oct. 26, 2012, 5:27 p.m.
Hi!

This patch extends optimize_range_tests optimization, so that it
handles also the cases where the truth && or || has been gimplifed
as a series of GIMPLE_CONDs or mixture thereof and BIT_{AND,IOR}_EXPR
stmts.

Example of code it handles is e.g.:
  <bb 2>:
  v1_3 = a_2(D) != 3;
  v2_4 = a_2(D) != 1;
  v3_5 = a_2(D) != 4;
  v4_6 = a_2(D) != 2;
  v5_7 = a_2(D) != 7;
  v6_8 = a_2(D) != 5;
  v7_9 = a_2(D) != 8;
  v8_10 = a_2(D) != 6;
  _11 = v1_3 & v2_4;
  if (_11 != 0)
    goto <bb 3>;
  else
    goto <bb 7>;

  <bb 3>:
  _13 = v3_5 & v4_6;
  if (_13 != 0)
    goto <bb 4>;
  else
    goto <bb 7>;

  <bb 4>:
  _14 = v5_7 & v6_8;
  if (_14 != 0)
    goto <bb 5>;
  else
    goto <bb 7>;

  <bb 5>:
  _15 = v7_9 & v8_10;
  if (_15 != 0)
    goto <bb 6>;
  else
    goto <bb 7>;

or:

  <bb 2>:
  _3 = c_2(D) == 34;
  _4 = c_2(D) == 32;
  _5 = _3 | _4;
  if (_5 != 0)
    goto <bb 4>;
  else
    goto <bb 3>;

  <bb 3>:
  _8 = c_2(D) <= 31;
  _7 = (int) _8;

  <bb 4>:
  # _1 = PHI <_7(3), 1(2)>

It is implemented in reassociate_bb, as that is where all the
infrastructure already is, but isn't done as part of normal
reassociation, but before reassociating first bb that represents
a series of && or || operands.  As post-dominator sons aren't
particularly ordered, it can happen that the optimization is performed
on the first, last or middle bb of the series of bbs, so it searches
both forward and backward to find suitable basic blocks.
The last bb in the series (last_bb) can be of the form of bb 3 in the
second example, which is how certain sequencies are gimplified when
assigning && or || result to a variable or returning it.

Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

2012-10-26  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/19105
	PR tree-optimization/21643
	PR tree-optimization/46309
	* tree-ssa-reassoc.c (init_range_entry): Add STMT argument
	and use it if EXP is NULL.
	(update_range_test): Handle OPCODE equal to ERROR_MARK
	and oe->op NULL.
	(optimize_range_tests): Likewise.
	(final_range_test_p, suitable_cond_bb, no_side_effect_bb, get_ops,
	maybe_optimize_range_tests): New functions.
	(reassociate_bb): Call maybe_optimize_range_tests if last
	stmt of bb is GIMPLE_COND that hasn't been visited yet.

	* gcc.dg/pr19105.c: New test.
	* gcc.dg/pr21643.c: New test.
	* gcc.dg/pr46309-2.c: New test.
	* gcc.c-torture/execute/pr46309.c: New test.


	Jakub
Jakub Jelinek - Oct. 26, 2012, 10:10 p.m.
On Fri, Oct 26, 2012 at 07:27:43PM +0200, Jakub Jelinek wrote:
> This patch extends optimize_range_tests optimization, so that it
> handles also the cases where the truth && or || has been gimplifed
> as a series of GIMPLE_CONDs or mixture thereof and BIT_{AND,IOR}_EXPR
> stmts.

Some statistics from x86_64-linux and i686-linux bootstraps
(--enable-checking=yes,rtl --enable-languages=all,obj-c++,ada,go
for x86_64 and the same without ada for i686).
I've gathered how many calls to update_range_test there were, whether
it was inter-bb (opcode == ERROR_MARK) or normal range merge and how
many range tests were merged into one.  Numberes are split for
-m32 compilations and -m64 compilations during those bootstraps,
vanilla numbers are normal merges with unpatched trunk, patched
are normal merges with patched trunk and inter-bb are inter-bb
merges with patched trunk.  The patched numbers are somewhat
smaller than the vanilla numbers, because some merges are done
by inter-bb, but the sum of normal and inter-bb range test merges
is always bigger. # ranges is how many ranges were merged together,
i.e. count argument to update_range_test + 1.

                |         -m32          |       |         -m64          |
# ranges        vanilla patched inter-bb        vanilla patched inter-bb
 2              57921   57136   19123           62148   61276   18927
 3                               2965                            3359
 4                  2       2     879               2       2    1010
 5                                111                             127
 6                                242                             243
 7                                 13                              19
 8                                 23                              23
 9                                 12                               9
10                                  4                               4
11                                  6                              12
12                                  2                               2


	Jakub
Richard Guenther - Oct. 30, 2012, 2:56 p.m.
On Fri, Oct 26, 2012 at 7:27 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> This patch extends optimize_range_tests optimization, so that it
> handles also the cases where the truth && or || has been gimplifed
> as a series of GIMPLE_CONDs or mixture thereof and BIT_{AND,IOR}_EXPR
> stmts.
>
> Example of code it handles is e.g.:
>   <bb 2>:
>   v1_3 = a_2(D) != 3;
>   v2_4 = a_2(D) != 1;
>   v3_5 = a_2(D) != 4;
>   v4_6 = a_2(D) != 2;
>   v5_7 = a_2(D) != 7;
>   v6_8 = a_2(D) != 5;
>   v7_9 = a_2(D) != 8;
>   v8_10 = a_2(D) != 6;
>   _11 = v1_3 & v2_4;
>   if (_11 != 0)
>     goto <bb 3>;
>   else
>     goto <bb 7>;
>
>   <bb 3>:
>   _13 = v3_5 & v4_6;
>   if (_13 != 0)
>     goto <bb 4>;
>   else
>     goto <bb 7>;
>
>   <bb 4>:
>   _14 = v5_7 & v6_8;
>   if (_14 != 0)
>     goto <bb 5>;
>   else
>     goto <bb 7>;
>
>   <bb 5>:
>   _15 = v7_9 & v8_10;
>   if (_15 != 0)
>     goto <bb 6>;
>   else
>     goto <bb 7>;
>
> or:
>
>   <bb 2>:
>   _3 = c_2(D) == 34;
>   _4 = c_2(D) == 32;
>   _5 = _3 | _4;
>   if (_5 != 0)
>     goto <bb 4>;
>   else
>     goto <bb 3>;
>
>   <bb 3>:
>   _8 = c_2(D) <= 31;
>   _7 = (int) _8;
>
>   <bb 4>:
>   # _1 = PHI <_7(3), 1(2)>
>
> It is implemented in reassociate_bb, as that is where all the
> infrastructure already is, but isn't done as part of normal
> reassociation, but before reassociating first bb that represents
> a series of && or || operands.  As post-dominator sons aren't
> particularly ordered, it can happen that the optimization is performed
> on the first, last or middle bb of the series of bbs, so it searches
> both forward and backward to find suitable basic blocks.
> The last bb in the series (last_bb) can be of the form of bb 3 in the
> second example, which is how certain sequencies are gimplified when
> assigning && or || result to a variable or returning it.
>
> Bootstrapped/regtested on x86_64-linux and i686-linux, ok for trunk?

Ok, but the code could really really have some more comments - functions
not fitting in my 80x24 terminal without seeing any comment what happens
here are a maintainance nightmare.

Thanks,
Richard.

> 2012-10-26  Jakub Jelinek  <jakub@redhat.com>
>
>         PR tree-optimization/19105
>         PR tree-optimization/21643
>         PR tree-optimization/46309
>         * tree-ssa-reassoc.c (init_range_entry): Add STMT argument
>         and use it if EXP is NULL.
>         (update_range_test): Handle OPCODE equal to ERROR_MARK
>         and oe->op NULL.
>         (optimize_range_tests): Likewise.
>         (final_range_test_p, suitable_cond_bb, no_side_effect_bb, get_ops,
>         maybe_optimize_range_tests): New functions.
>         (reassociate_bb): Call maybe_optimize_range_tests if last
>         stmt of bb is GIMPLE_COND that hasn't been visited yet.
>
>         * gcc.dg/pr19105.c: New test.
>         * gcc.dg/pr21643.c: New test.
>         * gcc.dg/pr46309-2.c: New test.
>         * gcc.c-torture/execute/pr46309.c: New test.
>
> --- gcc/tree-ssa-reassoc.c.jj   2012-10-25 09:21:08.657049321 +0200
> +++ gcc/tree-ssa-reassoc.c      2012-10-26 15:51:13.398025229 +0200
> @@ -1,5 +1,5 @@
>  /* Reassociation for trees.
> -   Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
> +   Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
>     Free Software Foundation, Inc.
>     Contributed by Daniel Berlin <dan@dberlin.org>
>
> @@ -1713,10 +1713,12 @@ struct range_entry
>  };
>
>  /* This is similar to make_range in fold-const.c, but on top of
> -   GIMPLE instead of trees.  */
> +   GIMPLE instead of trees.  If EXP is non-NULL, it should be
> +   an SSA_NAME and STMT argument is ignored, otherwise STMT
> +   argument should be a GIMPLE_COND.  */
>
>  static void
> -init_range_entry (struct range_entry *r, tree exp)
> +init_range_entry (struct range_entry *r, tree exp, gimple stmt)
>  {
>    int in_p;
>    tree low, high;
> @@ -1727,7 +1729,8 @@ init_range_entry (struct range_entry *r,
>    r->strict_overflow_p = false;
>    r->low = NULL_TREE;
>    r->high = NULL_TREE;
> -  if (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp)))
> +  if (exp != NULL_TREE
> +      && (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))))
>      return;
>
>    /* Start with simply saying "EXP != 0" and then look at the code of EXP
> @@ -1735,12 +1738,14 @@ init_range_entry (struct range_entry *r,
>       happen, but it doesn't seem worth worrying about this.  We "continue"
>       the outer loop when we've changed something; otherwise we "break"
>       the switch, which will "break" the while.  */
> -  low = build_int_cst (TREE_TYPE (exp), 0);
> +  low = exp ? build_int_cst (TREE_TYPE (exp), 0) : boolean_false_node;
>    high = low;
>    in_p = 0;
>    strict_overflow_p = false;
>    is_bool = false;
> -  if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
> +  if (exp == NULL_TREE)
> +    is_bool = true;
> +  else if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
>      {
>        if (TYPE_UNSIGNED (TREE_TYPE (exp)))
>         is_bool = true;
> @@ -1752,25 +1757,35 @@ init_range_entry (struct range_entry *r,
>
>    while (1)
>      {
> -      gimple stmt;
>        enum tree_code code;
>        tree arg0, arg1, exp_type;
>        tree nexp;
>        location_t loc;
>
> -      if (TREE_CODE (exp) != SSA_NAME)
> -       break;
> +      if (exp != NULL_TREE)
> +       {
> +         if (TREE_CODE (exp) != SSA_NAME)
> +           break;
>
> -      stmt = SSA_NAME_DEF_STMT (exp);
> -      if (!is_gimple_assign (stmt))
> -       break;
> +         stmt = SSA_NAME_DEF_STMT (exp);
> +         if (!is_gimple_assign (stmt))
> +           break;
> +
> +         code = gimple_assign_rhs_code (stmt);
> +         arg0 = gimple_assign_rhs1 (stmt);
> +         arg1 = gimple_assign_rhs2 (stmt);
> +         exp_type = TREE_TYPE (exp);
> +       }
> +      else
> +       {
> +         code = gimple_cond_code (stmt);
> +         arg0 = gimple_cond_lhs (stmt);
> +         arg1 = gimple_cond_rhs (stmt);
> +         exp_type = boolean_type_node;
> +       }
>
> -      code = gimple_assign_rhs_code (stmt);
> -      arg0 = gimple_assign_rhs1 (stmt);
>        if (TREE_CODE (arg0) != SSA_NAME)
>         break;
> -      arg1 = gimple_assign_rhs2 (stmt);
> -      exp_type = TREE_TYPE (exp);
>        loc = gimple_location (stmt);
>        switch (code)
>         {
> @@ -1916,7 +1931,11 @@ range_entry_cmp (const void *a, const vo
>     [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
>     RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
>     OPCODE and OPS are arguments of optimize_range_tests.  Return
> -   true if the range merge has been successful.  */
> +   true if the range merge has been successful.
> +   If OPCODE is ERROR_MARK, this is called from within
> +   maybe_optimize_range_tests and is performing inter-bb range optimization.
> +   Changes should be then performed right away, and whether an op is
> +   BIT_AND_EXPR or BIT_IOR_EXPR is found in oe->rank.  */
>
>  static bool
>  update_range_test (struct range_entry *range, struct range_entry *otherrange,
> @@ -1924,9 +1943,12 @@ update_range_test (struct range_entry *r
>                    VEC (operand_entry_t, heap) **ops, tree exp, bool in_p,
>                    tree low, tree high, bool strict_overflow_p)
>  {
> -  tree op = VEC_index (operand_entry_t, *ops, range->idx)->op;
> -  location_t loc = gimple_location (SSA_NAME_DEF_STMT (op));
> -  tree tem = build_range_check (loc, TREE_TYPE (op), exp, in_p, low, high);
> +  operand_entry_t oe = VEC_index (oeprand_entry_t, *ops, range->idx);
> +  tree op = oe->op;
> +  gimple stmt = op ? SSA_NAME_DEF_STMT (op) : last_stmt (BASIC_BLOCK (oe->id));
> +  location_t loc = gimple_location (stmt);
> +  tree optype = op ? TREE_TYPE (op) : boolean_type_node;
> +  tree tem = build_range_check (loc, optype, exp, in_p, low, high);
>    enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
>    gimple_stmt_iterator gsi;
>
> @@ -1961,15 +1983,41 @@ update_range_test (struct range_entry *r
>        fprintf (dump_file, "\n");
>      }
>
> -  if (opcode == BIT_IOR_EXPR)
> +  if (opcode == BIT_IOR_EXPR
> +      || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
>      tem = invert_truthvalue_loc (loc, tem);
>
> -  tem = fold_convert_loc (loc, TREE_TYPE (op), tem);
> -  gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (op));
> +  tem = fold_convert_loc (loc, optype, tem);
> +  gsi = gsi_for_stmt (stmt);
>    tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
>                                   GSI_SAME_STMT);
>
> -  VEC_index (operand_entry_t, *ops, range->idx)->op = tem;
> +  if (opcode == ERROR_MARK)
> +    {
> +      if (op)
> +       {
> +         imm_use_iterator iter;
> +         use_operand_p use_p;
> +         gimple use_stmt;
> +
> +         FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
> +           {
> +             if (is_gimple_debug (use_stmt))
> +               continue;
> +             FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
> +               SET_USE (use_p, tem);
> +             update_stmt (use_stmt);
> +           }
> +       }
> +      else
> +       {
> +         gimple_cond_set_code (stmt, NE_EXPR);
> +         gimple_cond_set_lhs (stmt, tem);
> +         gimple_cond_set_rhs (stmt, boolean_false_node);
> +         update_stmt (stmt);
> +       }
> +    }
> +  oe->op = tem;
>    range->exp = exp;
>    range->low = low;
>    range->high = high;
> @@ -1978,7 +2026,73 @@ update_range_test (struct range_entry *r
>
>    for (range = otherrange; range < otherrange + count; range++)
>      {
> -      VEC_index (operand_entry_t, *ops, range->idx)->op = error_mark_node;
> +      oe = VEC_index (oeprand_entry_t, *ops, range->idx);
> +      if (opcode == ERROR_MARK)
> +       {
> +         if (oe->op)
> +           {
> +             imm_use_iterator iter;
> +             use_operand_p use_p;
> +             gimple use_stmt;
> +
> +             FOR_EACH_IMM_USE_STMT (use_stmt, iter, oe->op)
> +               {
> +                 if (is_gimple_debug (use_stmt))
> +                   continue;
> +                 if (is_gimple_assign (use_stmt)
> +                     && gimple_assign_rhs_code (use_stmt) == oe->rank)
> +                   {
> +                     tree expr = NULL_TREE;
> +                     if (oe->op == gimple_assign_rhs1 (use_stmt))
> +                       expr = gimple_assign_rhs2 (use_stmt);
> +                     else if (oe->op == gimple_assign_rhs2 (use_stmt))
> +                       expr = gimple_assign_rhs1 (use_stmt);
> +                     if (expr
> +                         && expr != oe->op
> +                         && TREE_CODE (expr) == SSA_NAME)
> +                       {
> +                         gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
> +                         gimple_assign_set_rhs_with_ops (&gsi2, SSA_NAME,
> +                                                         expr, NULL_TREE);
> +                         update_stmt (use_stmt);
> +                         continue;
> +                       }
> +                     if (gimple_assign_cast_p (use_stmt)
> +                         && oe->op == gimple_assign_rhs1 (use_stmt))
> +                       {
> +                         tree lhs = gimple_assign_lhs (use_stmt);
> +                         if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
> +                           {
> +                             gimple_stmt_iterator gsi2
> +                               = gsi_for_stmt (use_stmt);
> +                             expr = build_int_cst (TREE_TYPE (lhs),
> +                                                   oe->rank == BIT_IOR_EXPR
> +                                                   ? 0 : 1);
> +                             gimple_assign_set_rhs_with_ops (&gsi2,
> +                                                             INTEGER_CST,
> +                                                             expr, NULL_TREE);
> +                           }
> +                       }
> +                   }
> +                 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
> +                   SET_USE (use_p,
> +                            build_int_cst (TREE_TYPE (oe->op),
> +                                           oe->rank == BIT_IOR_EXPR
> +                                           ? 0 : 1));
> +                 update_stmt (use_stmt);
> +               }
> +           }
> +         else
> +           {
> +             stmt = last_stmt (BASIC_BLOCK (oe->id));
> +             if (oe->rank == BIT_IOR_EXPR)
> +               gimple_cond_make_false (stmt);
> +             else
> +               gimple_cond_make_true (stmt);
> +             update_stmt (stmt);
> +           }
> +       }
> +      oe->op = error_mark_node;
>        range->exp = NULL_TREE;
>      }
>    return true;
> @@ -1986,7 +2100,12 @@ update_range_test (struct range_entry *r
>
>  /* Optimize range tests, similarly how fold_range_test optimizes
>     it on trees.  The tree code for the binary
> -   operation between all the operands is OPCODE.  */
> +   operation between all the operands is OPCODE.
> +   If OPCODE is ERROR_MARK, optimize_range_tests is called from within
> +   maybe_optimize_range_tests for inter-bb range optimization.
> +   In that case if oe->op is NULL, oe->id is bb->index whose
> +   GIMPLE_COND is && or ||ed into the test, and oe->rank says
> +   the actual opcode.  */
>
>  static void
>  optimize_range_tests (enum tree_code opcode,
> @@ -2003,11 +2122,14 @@ optimize_range_tests (enum tree_code opc
>    ranges = XNEWVEC (struct range_entry, length);
>    for (i = 0; i < length; i++)
>      {
> +      oe = VEC_index (operand_entry_t, *ops, i);
>        ranges[i].idx = i;
> -      init_range_entry (ranges + i, VEC_index (operand_entry_t, *ops, i)->op);
> +      init_range_entry (ranges + i, oe->op,
> +                       oe->op ? NULL : last_stmt (BASIC_BLOCK (oe->id)));
>        /* For | invert it now, we will invert it again before emitting
>          the optimized expression.  */
> -      if (opcode == BIT_IOR_EXPR)
> +      if (opcode == BIT_IOR_EXPR
> +         || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
>         ranges[i].in_p = !ranges[i].in_p;
>      }
>
> @@ -2124,7 +2246,7 @@ optimize_range_tests (enum tree_code opc
>         }
>      }
>
> -  if (any_changes)
> +  if (any_changes && opcode != ERROR_MARK)
>      {
>        j = 0;
>        FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe)
> @@ -2141,6 +2263,398 @@ optimize_range_tests (enum tree_code opc
>    XDELETEVEC (ranges);
>  }
>
> +/* Return true if STMT is a cast like:
> +   <bb N>:
> +   ...
> +   _123 = (int) _234;
> +
> +   <bb M>:
> +   # _345 = PHI <_123(N), 1(...), 1(...)>
> +   where _234 has bool type, _123 has single use and
> +   bb N has a single successor M.  This is commonly used in
> +   the last block of a range test.  */
> +
> +static bool
> +final_range_test_p (gimple stmt)
> +{
> +  basic_block bb, rhs_bb;
> +  edge e;
> +  tree lhs, rhs;
> +  use_operand_p use_p;
> +  gimple use_stmt;
> +
> +  if (!gimple_assign_cast_p (stmt))
> +    return false;
> +  bb = gimple_bb (stmt);
> +  if (!single_succ_p (bb))
> +    return false;
> +  e = single_succ_edge (bb);
> +  if (e->flags & EDGE_COMPLEX)
> +    return false;
> +
> +  lhs = gimple_assign_lhs (stmt);
> +  rhs = gimple_assign_rhs1 (stmt);
> +  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +      || TREE_CODE (rhs) != SSA_NAME
> +      || TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
> +    return false;
> +
> +  if (!single_imm_use (lhs, &use_p, &use_stmt))
> +    return false;
> +
> +  if (gimple_code (use_stmt) != GIMPLE_PHI
> +      || gimple_bb (use_stmt) != e->dest)
> +    return false;
> +
> +  rhs_bb = gimple_bb (SSA_NAME_DEF_STMT (rhs));
> +  if (rhs_bb == NULL
> +      || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), rhs_bb))
> +    return false;
> +
> +  return true;
> +}
> +
> +/* Return true if BB is suitable basic block for inter-bb range test
> +   optimization.  If BACKWARD is true, BB should be the only predecessor
> +   of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
> +   or compared with to find a common basic block to which all conditions
> +   branch to if true resp. false.  If BACKWARD is false, TEST_BB should
> +   be the only predecessor of BB.  */
> +
> +static bool
> +suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
> +                 bool backward)
> +{
> +  edge_iterator ei, ei2;
> +  edge e, e2;
> +  gimple stmt;
> +  gimple_stmt_iterator gsi;
> +  bool other_edge_seen = false;
> +  bool is_cond;
> +
> +  if (test_bb == bb)
> +    return false;
> +  stmt = last_stmt (bb);
> +  if (stmt == NULL
> +      || (gimple_code (stmt) != GIMPLE_COND
> +         && (backward || !final_range_test_p (stmt)))
> +      || gimple_visited_p (stmt)
> +      || stmt_could_throw_p (stmt)
> +      || *other_bb == bb)
> +    return false;
> +  is_cond = gimple_code (stmt) == GIMPLE_COND;
> +  if (is_cond)
> +    {
> +      if (EDGE_COUNT (bb->succs) != 2)
> +       return false;
> +      FOR_EACH_EDGE (e, ei, bb->succs)
> +       {
> +         if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> +           return false;
> +         if (e->dest == test_bb)
> +           {
> +             if (backward)
> +               continue;
> +             else
> +               return false;
> +           }
> +         if (e->dest == bb)
> +           return false;
> +         if (*other_bb == NULL)
> +           {
> +             FOR_EACH_EDGE (e2, ei2, test_bb->succs)
> +               if (!(e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
> +                 return false;
> +               else if (e->dest == e2->dest)
> +                 *other_bb = e->dest;
> +             if (*other_bb == NULL)
> +               return false;
> +           }
> +         if (e->dest == *other_bb)
> +           other_edge_seen = true;
> +         else if (backward)
> +           return false;
> +       }
> +      if (*other_bb == NULL || !other_edge_seen)
> +       return false;
> +    }
> +  else if (single_succ (bb) != *other_bb)
> +    return false;
> +
> +  e = find_edge (bb, *other_bb);
> +  e2 = find_edge (test_bb, *other_bb);
> +  for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
> +    {
> +      gimple phi = gsi_stmt (gsi);
> +      if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
> +                           gimple_phi_arg_def (phi, e2->dest_idx), 0))
> +       {
> +         if (!is_cond)
> +           {
> +             if (gimple_phi_arg_def (phi, e->dest_idx)
> +                 == gimple_assign_lhs (stmt)
> +                 && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
> +                     || integer_onep (gimple_phi_arg_def (phi,
> +                                                          e2->dest_idx))))
> +               continue;
> +           }
> +         else
> +           {
> +             gimple test_last = last_stmt (test_bb);
> +             if (gimple_code (test_last) != GIMPLE_COND
> +                 && gimple_phi_arg_def (phi, e2->dest_idx)
> +                    == gimple_assign_lhs (test_last)
> +                 && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
> +                     || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
> +               continue;
> +           }
> +
> +         return false;
> +       }
> +    }
> +  return true;
> +}
> +
> +/* Return true if BB doesn't have side-effects that would disallow
> +   range test optimization, all SSA_NAMEs set in the bb are consumed
> +   in the bb and there are no PHIs.  */
> +
> +static bool
> +no_side_effect_bb (basic_block bb)
> +{
> +  gimple_stmt_iterator gsi;
> +  gimple last;
> +
> +  if (!gimple_seq_empty_p (phi_nodes (bb)))
> +    return false;
> +  last = last_stmt (bb);
> +  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
> +    {
> +      gimple stmt = gsi_stmt (gsi);
> +      tree lhs;
> +      imm_use_iterator imm_iter;
> +      use_operand_p use_p;
> +
> +      if (is_gimple_debug (stmt))
> +       continue;
> +      if (gimple_has_side_effects (stmt))
> +       return false;
> +      if (stmt == last)
> +       return true;
> +      if (!is_gimple_assign (stmt))
> +       return false;
> +      lhs = gimple_assign_lhs (stmt);
> +      if (TREE_CODE (lhs) != SSA_NAME)
> +       return false;
> +      if (gimple_assign_rhs_could_trap_p (stmt))
> +       return false;
> +      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
> +       {
> +         gimple use_stmt = USE_STMT (use_p);
> +         if (is_gimple_debug (use_stmt))
> +           continue;
> +         if (gimple_bb (use_stmt) != bb)
> +           return false;
> +       }
> +    }
> +  return false;
> +}
> +
> +/* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
> +   return true and fill in *OPS recursively.  */
> +
> +static bool
> +get_ops (tree var, enum tree_code code, VEC(operand_entry_t, heap) **ops,
> +        struct loop *loop)
> +{
> +  gimple stmt = SSA_NAME_DEF_STMT (var);
> +  tree rhs[2];
> +  int i;
> +
> +  if (!is_reassociable_op (stmt, code, loop))
> +    return false;
> +
> +  rhs[0] = gimple_assign_rhs1 (stmt);
> +  rhs[1] = gimple_assign_rhs2 (stmt);
> +  gimple_set_visited (stmt, true);
> +  for (i = 0; i < 2; i++)
> +    if (TREE_CODE (rhs[i]) == SSA_NAME
> +       && !get_ops (rhs[i], code, ops, loop)
> +       && has_single_use (rhs[i]))
> +      {
> +       operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
> +
> +       oe->op = rhs[i];
> +       oe->rank = code;
> +       oe->id = 0;
> +       oe->count = 1;
> +       VEC_safe_push (operand_entry_t, heap, *ops, oe);
> +      }
> +  return true;
> +}
> +
> +/* Inter-bb range test optimization.  */
> +
> +static void
> +maybe_optimize_range_tests (gimple stmt)
> +{
> +  basic_block first_bb = gimple_bb (stmt);
> +  basic_block last_bb = first_bb;
> +  basic_block other_bb = NULL;
> +  basic_block bb;
> +  edge_iterator ei;
> +  edge e;
> +  VEC(operand_entry_t, heap) *ops = NULL;
> +
> +  if (gimple_code (stmt) == GIMPLE_COND)
> +    {
> +      if (EDGE_COUNT (first_bb->succs) != 2)
> +       return;
> +    }
> +  else if (final_range_test_p (stmt))
> +    other_bb = single_succ (first_bb);
> +  else
> +    return;
> +
> +  if (stmt_could_throw_p (stmt))
> +    return;
> +
> +  while (single_pred_p (first_bb))
> +    {
> +      basic_block pred_bb = single_pred (first_bb);
> +      if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
> +       break;
> +      if (!no_side_effect_bb (first_bb))
> +       break;
> +      first_bb = pred_bb;
> +    }
> +  if (first_bb == last_bb)
> +    {
> +      other_bb = NULL;
> +      if (gimple_code (stmt) != GIMPLE_COND)
> +       return;
> +      FOR_EACH_EDGE (e, ei, first_bb->succs)
> +       if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
> +           || e->dest == first_bb)
> +         return;
> +       else if (single_pred_p (e->dest))
> +         {
> +           stmt = last_stmt (e->dest);
> +           if (stmt
> +               && gimple_code (stmt) == GIMPLE_COND
> +               && EDGE_COUNT (e->dest->succs) == 2)
> +             {
> +               if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
> +                 break;
> +               else
> +                 other_bb = NULL;
> +             }
> +           else if (stmt
> +                    && final_range_test_p (stmt)
> +                    && find_edge (first_bb, single_succ (e->dest)))
> +             {
> +               other_bb = single_succ (e->dest);
> +               if (other_bb == first_bb)
> +                 other_bb = NULL;
> +             }
> +         }
> +      if (other_bb == NULL)
> +       return;
> +    }
> +  while (EDGE_COUNT (last_bb->succs) == 2)
> +    {
> +      FOR_EACH_EDGE (e, ei, last_bb->succs)
> +       if (e->dest != other_bb)
> +         break;
> +      if (e == NULL)
> +       break;
> +      if (!single_pred_p (e->dest))
> +       break;
> +      if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
> +       break;
> +      if (!no_side_effect_bb (e->dest))
> +       break;
> +      last_bb = e->dest;
> +    }
> +  if (first_bb == last_bb)
> +    return;
> +  for (bb = last_bb; ; bb = single_pred (bb))
> +    {
> +      enum tree_code code;
> +      tree lhs, rhs;
> +
> +      e = find_edge (bb, other_bb);
> +      stmt = last_stmt (bb);
> +      gimple_set_visited (stmt, true);
> +      if (gimple_code (stmt) != GIMPLE_COND)
> +       {
> +         use_operand_p use_p;
> +         gimple phi;
> +         edge e2;
> +         unsigned int d;
> +
> +         lhs = gimple_assign_lhs (stmt);
> +         rhs = gimple_assign_rhs1 (stmt);
> +         gcc_assert (bb == last_bb);
> +
> +         single_imm_use (lhs, &use_p, &phi);
> +         gcc_assert (gimple_code (phi) == GIMPLE_PHI);
> +         e2 = find_edge (first_bb, other_bb);
> +         d = e2->dest_idx;
> +         gcc_assert (gimple_phi_arg_def (phi, e->dest_idx) == lhs);
> +         if (integer_zerop (gimple_phi_arg_def (phi, d)))
> +           code = BIT_AND_EXPR;
> +         else
> +           {
> +             gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi, d)));
> +             code = BIT_IOR_EXPR;
> +           }
> +
> +         if (!get_ops (rhs, code, &ops,
> +                       loop_containing_stmt (stmt))
> +             && has_single_use (rhs))
> +           {
> +             operand_entry_t oe
> +               = (operand_entry_t) pool_alloc (operand_entry_pool);
> +
> +             oe->op = rhs;
> +             oe->rank = code;
> +             oe->id = 0;
> +             oe->count = 1;
> +             VEC_safe_push (operand_entry_t, heap, ops, oe);
> +           }
> +         continue;
> +       }
> +      code = gimple_cond_code (stmt);
> +      lhs = gimple_cond_lhs (stmt);
> +      rhs = gimple_cond_rhs (stmt);
> +      if (TREE_CODE (lhs) == SSA_NAME
> +         && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
> +         && ((code != EQ_EXPR && code != NE_EXPR)
> +             || rhs != boolean_false_node
> +             || !get_ops (lhs, (((e->flags & EDGE_TRUE_VALUE) == 0)
> +                                ^ (code == EQ_EXPR))
> +                               ? BIT_AND_EXPR : BIT_IOR_EXPR, &ops,
> +                          loop_containing_stmt (stmt))))
> +       {
> +         operand_entry_t oe
> +           = (operand_entry_t) pool_alloc (operand_entry_pool);
> +
> +         oe->op = NULL;
> +         oe->rank = (e->flags & EDGE_TRUE_VALUE)
> +                    ? BIT_IOR_EXPR : BIT_AND_EXPR;
> +         oe->id = bb->index;
> +         oe->count = 1;
> +         VEC_safe_push (operand_entry_t, heap, ops, oe);
> +       }
> +      if (bb == first_bb)
> +       break;
> +    }
> +  if (VEC_length (operand_entry_t, ops) > 1)
> +    optimize_range_tests (ERROR_MARK, &ops);
> +  VEC_free (operand_entry_t, heap, ops);
> +}
> +
>  /* Return true if OPERAND is defined by a PHI node which uses the LHS
>     of STMT in it's operands.  This is also known as a "destructive
>     update" operation.  */
> @@ -3427,10 +3941,14 @@ reassociate_bb (basic_block bb)
>  {
>    gimple_stmt_iterator gsi;
>    basic_block son;
> +  gimple stmt = last_stmt (bb);
> +
> +  if (stmt && !gimple_visited_p (stmt))
> +    maybe_optimize_range_tests (stmt);
>
>    for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
>      {
> -      gimple stmt = gsi_stmt (gsi);
> +      stmt = gsi_stmt (gsi);
>
>        if (is_gimple_assign (stmt)
>           && !stmt_could_throw_p (stmt))
> --- gcc/testsuite/gcc.dg/pr19105.c.jj   2012-10-26 15:12:04.191828571 +0200
> +++ gcc/testsuite/gcc.dg/pr19105.c      2012-10-26 15:11:41.000000000 +0200
> @@ -0,0 +1,22 @@
> +/* PR tree-optimization/19105 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
> +
> +enum e
> +{
> +  a, b, c, d, e, f, g, h
> +};
> +
> +int range1 (enum e v, int x)
> +{
> +  return x && v != c && v != d && v != e;
> +}
> +
> +int range2 (enum e v, int x)
> +{
> +  return x && (v != c && v != d && v != e);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests v_\[0-9\]*.D. -.2, 2. and -.3, 4.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> +
> --- gcc/testsuite/gcc.dg/pr21643.c.jj   2012-10-26 15:00:14.588063088 +0200
> +++ gcc/testsuite/gcc.dg/pr21643.c      2012-10-26 15:01:31.199598891 +0200
> @@ -0,0 +1,90 @@
> +/* PR tree-optimization/21643 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
> +
> +int
> +f1 (unsigned char c)
> +{
> +  if (c == 0x22 || c == 0x20 || c < 0x20)
> +    return 1;
> +  return 0;
> +}
> +
> +int
> +f2 (unsigned char c)
> +{
> +  if (c == 0x22 || c <= 0x20)
> +    return 1;
> +  return 0;
> +}
> +
> +int
> +f3 (unsigned char c)
> +{
> +  if (c == 0x22)
> +    return 1;
> +  if (c == 0x20)
> +    return 1;
> +  if (c < 0x20)
> +    return 1;
> +  return 0;
> +}
> +
> +int
> +f4 (unsigned char c)
> +{
> +  if (c == 0x22 || c == 0x20 || c < 0x20)
> +    return 2;
> +  return 0;
> +}
> +
> +int
> +f5 (unsigned char c)
> +{
> +  if (c == 0x22 || c <= 0x20)
> +    return 2;
> +  return 0;
> +}
> +
> +int
> +f6 (unsigned char c)
> +{
> +  if (c == 0x22)
> +    return 2;
> +  if (c == 0x20)
> +    return 2;
> +  if (c < 0x20)
> +    return 2;
> +  return 0;
> +}
> +
> +int
> +f7 (unsigned char c)
> +{
> +  if (c != 0x22 && c != 0x20 && c >= 0x20)
> +    return 0;
> +  return 1;
> +}
> +
> +int
> +f8 (unsigned char c)
> +{
> +  if (c == 0x22 && c <= 0x20)
> +    return 0;
> +  return 1;
> +}
> +
> +int
> +f9 (unsigned char c)
> +{
> +  if (c == 0x22)
> +    return 0;
> +  if (c == 0x20)
> +    return 0;
> +  if (c < 0x20)
> +    return 0;
> +  return 1;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> --- gcc/testsuite/gcc.dg/pr46309-2.c.jj 2012-10-25 16:30:42.623578285 +0200
> +++ gcc/testsuite/gcc.dg/pr46309-2.c    2012-10-26 15:16:38.404212168 +0200
> @@ -0,0 +1,147 @@
> +/* PR tree-optimization/46309 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-reassoc-details" } */
> +
> +int foo (void);
> +
> +void
> +f1 (int a)
> +{
> +  _Bool v1 = (a == 3);
> +  _Bool v2 = (a == 1);
> +  _Bool v3 = (a == 4);
> +  _Bool v4 = (a == 2);
> +  if (v1 || v2 || v3 || v4)
> +    foo ();
> +}
> +
> +void
> +f2 (int a)
> +{
> +  _Bool v1 = (a == 1);
> +  _Bool v2 = (a == 2);
> +  _Bool v3 = (a == 3);
> +  _Bool v4 = (a == 4);
> +  if (v1 || v2 || v3 || v4)
> +    foo ();
> +}
> +
> +void
> +f3 (unsigned int a)
> +{
> +  _Bool v1 = (a <= 31);
> +  _Bool v2 = (a >= 64 && a <= 95);
> +  _Bool v3 = (a >= 128 && a <= 159);
> +  _Bool v4 = (a >= 192 && a <= 223);
> +  if (v1 || v2 || v3 || v4)
> +    foo ();
> +}
> +
> +void
> +f4 (int a)
> +{
> +  _Bool v1 = (a == 3);
> +  _Bool v2 = (a == 1);
> +  _Bool v3 = (a == 4);
> +  _Bool v4 = (a == 2);
> +  _Bool v5 = (a == 7);
> +  _Bool v6 = (a == 5);
> +  _Bool v7 = (a == 8);
> +  _Bool v8 = (a == 6);
> +  if (v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8)
> +    foo ();
> +}
> +
> +void
> +f5 (int a)
> +{
> +  _Bool v1 = (a != 3);
> +  _Bool v2 = (a != 1);
> +  _Bool v3 = (a != 4);
> +  _Bool v4 = (a != 2);
> +  _Bool v5 = (a != 7);
> +  _Bool v6 = (a != 5);
> +  _Bool v7 = (a != 8);
> +  _Bool v8 = (a != 6);
> +  if (v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8)
> +    foo ();
> +}
> +
> +void
> +f6 (int a)
> +{
> +  _Bool v1 = (a != 3);
> +  _Bool v2 = (a != 1);
> +  _Bool v3 = (a != 4);
> +  _Bool v4 = (a != 2);
> +  _Bool v5 = (a != 7);
> +  _Bool v6 = (a != 5);
> +  _Bool v7 = (a != 8);
> +  _Bool v8 = (a != 6);
> +  if ((v1 && v2 && v3 && v4) && (v5 && v6 && v7 && v8))
> +    foo ();
> +}
> +
> +int
> +f7 (int a)
> +{
> +  _Bool v1 = (a == 3);
> +  _Bool v2 = (a == 1);
> +  _Bool v3 = (a == 4);
> +  _Bool v4 = (a == 2);
> +  _Bool v5 = (a == 7);
> +  _Bool v6 = (a == 5);
> +  _Bool v7 = (a == 8);
> +  _Bool v8 = (a == 6);
> +  return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
> +}
> +
> +_Bool
> +f8 (int a)
> +{
> +  _Bool v1 = (a == 3);
> +  _Bool v2 = (a == 1);
> +  _Bool v3 = (a == 4);
> +  _Bool v4 = (a == 2);
> +  _Bool v5 = (a == 7);
> +  _Bool v6 = (a == 5);
> +  _Bool v7 = (a == 8);
> +  _Bool v8 = (a == 6);
> +  return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
> +}
> +
> +int
> +f9 (int a)
> +{
> +  _Bool v1 = (a != 3);
> +  _Bool v2 = (a != 1);
> +  _Bool v3 = (a != 4);
> +  _Bool v4 = (a != 2);
> +  _Bool v5 = (a != 7);
> +  _Bool v6 = (a != 5);
> +  _Bool v7 = (a != 8);
> +  _Bool v8 = (a != 6);
> +  return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
> +}
> +
> +_Bool
> +f10 (int a)
> +{
> +  _Bool v1 = (a != 3);
> +  _Bool v2 = (a != 1);
> +  _Bool v3 = (a != 4);
> +  _Bool v4 = (a != 2);
> +  _Bool v5 = (a != 7);
> +  _Bool v6 = (a != 5);
> +  _Bool v7 = (a != 8);
> +  _Bool v8 = (a != 6);
> +  return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4.\[\n\r\]* into" 2 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.0, 31. and -.64, 95.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.128, 159. and -.192, 223.\[\n\r\]* into" 1 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4. and -.5, 5. and -.6, 6. and -.7, 7. and -.8, 8.\[\n\r\]* into" 7 "reassoc1" } } */
> +/* { dg-final { scan-tree-dump-times "Optimizing range tests \[^\r\n\]*_\[0-9\]* -.0, 31. and -.128, 159.\[\n\r\]* into" 1 "reassoc2" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc1" } } */
> +/* { dg-final { cleanup-tree-dump "reassoc2" } } */
> --- gcc/testsuite/gcc.c-torture/execute/pr46309.c.jj    2012-10-26 10:10:28.403238295 +0200
> +++ gcc/testsuite/gcc.c-torture/execute/pr46309.c       2012-10-26 10:10:11.000000000 +0200
> @@ -0,0 +1,31 @@
> +/* PR tree-optimization/46309 */
> +
> +extern void abort (void);
> +
> +unsigned int *q;
> +
> +__attribute__((noinline, noclone)) void
> +bar (unsigned int *p)
> +{
> +  if (*p != 2 && *p != 3)
> +    (!(!(*q & 263) || *p != 1)) ? abort () : 0;
> +}
> +
> +int
> +main ()
> +{
> +  unsigned int x, y;
> +  asm volatile ("" : : : "memory");
> +  x = 2;
> +  bar (&x);
> +  x = 3;
> +  bar (&x);
> +  y = 1;
> +  x = 0;
> +  q = &y;
> +  bar (&x);
> +  y = 0;
> +  x = 1;
> +  bar (&x);
> +  return 0;
> +}
>
>         Jakub

Patch

--- gcc/tree-ssa-reassoc.c.jj	2012-10-25 09:21:08.657049321 +0200
+++ gcc/tree-ssa-reassoc.c	2012-10-26 15:51:13.398025229 +0200
@@ -1,5 +1,5 @@ 
 /* Reassociation for trees.
-   Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011
+   Copyright (C) 2005, 2007, 2008, 2009, 2010, 2011, 2012
    Free Software Foundation, Inc.
    Contributed by Daniel Berlin <dan@dberlin.org>
 
@@ -1713,10 +1713,12 @@  struct range_entry
 };
 
 /* This is similar to make_range in fold-const.c, but on top of
-   GIMPLE instead of trees.  */
+   GIMPLE instead of trees.  If EXP is non-NULL, it should be
+   an SSA_NAME and STMT argument is ignored, otherwise STMT
+   argument should be a GIMPLE_COND.  */
 
 static void
-init_range_entry (struct range_entry *r, tree exp)
+init_range_entry (struct range_entry *r, tree exp, gimple stmt)
 {
   int in_p;
   tree low, high;
@@ -1727,7 +1729,8 @@  init_range_entry (struct range_entry *r,
   r->strict_overflow_p = false;
   r->low = NULL_TREE;
   r->high = NULL_TREE;
-  if (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp)))
+  if (exp != NULL_TREE
+      && (TREE_CODE (exp) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (exp))))
     return;
 
   /* Start with simply saying "EXP != 0" and then look at the code of EXP
@@ -1735,12 +1738,14 @@  init_range_entry (struct range_entry *r,
      happen, but it doesn't seem worth worrying about this.  We "continue"
      the outer loop when we've changed something; otherwise we "break"
      the switch, which will "break" the while.  */
-  low = build_int_cst (TREE_TYPE (exp), 0);
+  low = exp ? build_int_cst (TREE_TYPE (exp), 0) : boolean_false_node;
   high = low;
   in_p = 0;
   strict_overflow_p = false;
   is_bool = false;
-  if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
+  if (exp == NULL_TREE)
+    is_bool = true;
+  else if (TYPE_PRECISION (TREE_TYPE (exp)) == 1)
     {
       if (TYPE_UNSIGNED (TREE_TYPE (exp)))
 	is_bool = true;
@@ -1752,25 +1757,35 @@  init_range_entry (struct range_entry *r,
 
   while (1)
     {
-      gimple stmt;
       enum tree_code code;
       tree arg0, arg1, exp_type;
       tree nexp;
       location_t loc;
 
-      if (TREE_CODE (exp) != SSA_NAME)
-	break;
+      if (exp != NULL_TREE)
+	{
+	  if (TREE_CODE (exp) != SSA_NAME)
+	    break;
 
-      stmt = SSA_NAME_DEF_STMT (exp);
-      if (!is_gimple_assign (stmt))
-	break;
+	  stmt = SSA_NAME_DEF_STMT (exp);
+	  if (!is_gimple_assign (stmt))
+	    break;
+
+	  code = gimple_assign_rhs_code (stmt);
+	  arg0 = gimple_assign_rhs1 (stmt);
+	  arg1 = gimple_assign_rhs2 (stmt);
+	  exp_type = TREE_TYPE (exp);
+	}
+      else
+	{
+	  code = gimple_cond_code (stmt);
+	  arg0 = gimple_cond_lhs (stmt);
+	  arg1 = gimple_cond_rhs (stmt);
+	  exp_type = boolean_type_node;
+	}
 
-      code = gimple_assign_rhs_code (stmt);
-      arg0 = gimple_assign_rhs1 (stmt);
       if (TREE_CODE (arg0) != SSA_NAME)
 	break;
-      arg1 = gimple_assign_rhs2 (stmt);
-      exp_type = TREE_TYPE (exp);
       loc = gimple_location (stmt);
       switch (code)
 	{
@@ -1916,7 +1931,11 @@  range_entry_cmp (const void *a, const vo
    [EXP, IN_P, LOW, HIGH, STRICT_OVERFLOW_P] is a merged range for
    RANGE and OTHERRANGE through OTHERRANGE + COUNT - 1 ranges,
    OPCODE and OPS are arguments of optimize_range_tests.  Return
-   true if the range merge has been successful.  */
+   true if the range merge has been successful.
+   If OPCODE is ERROR_MARK, this is called from within
+   maybe_optimize_range_tests and is performing inter-bb range optimization.
+   Changes should be then performed right away, and whether an op is
+   BIT_AND_EXPR or BIT_IOR_EXPR is found in oe->rank.  */
 
 static bool
 update_range_test (struct range_entry *range, struct range_entry *otherrange,
@@ -1924,9 +1943,12 @@  update_range_test (struct range_entry *r
 		   VEC (operand_entry_t, heap) **ops, tree exp, bool in_p,
 		   tree low, tree high, bool strict_overflow_p)
 {
-  tree op = VEC_index (operand_entry_t, *ops, range->idx)->op;
-  location_t loc = gimple_location (SSA_NAME_DEF_STMT (op));
-  tree tem = build_range_check (loc, TREE_TYPE (op), exp, in_p, low, high);
+  operand_entry_t oe = VEC_index (oeprand_entry_t, *ops, range->idx);
+  tree op = oe->op;
+  gimple stmt = op ? SSA_NAME_DEF_STMT (op) : last_stmt (BASIC_BLOCK (oe->id));
+  location_t loc = gimple_location (stmt);
+  tree optype = op ? TREE_TYPE (op) : boolean_type_node;
+  tree tem = build_range_check (loc, optype, exp, in_p, low, high);
   enum warn_strict_overflow_code wc = WARN_STRICT_OVERFLOW_COMPARISON;
   gimple_stmt_iterator gsi;
 
@@ -1961,15 +1983,41 @@  update_range_test (struct range_entry *r
       fprintf (dump_file, "\n");
     }
 
-  if (opcode == BIT_IOR_EXPR)
+  if (opcode == BIT_IOR_EXPR
+      || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
     tem = invert_truthvalue_loc (loc, tem);
 
-  tem = fold_convert_loc (loc, TREE_TYPE (op), tem);
-  gsi = gsi_for_stmt (SSA_NAME_DEF_STMT (op));
+  tem = fold_convert_loc (loc, optype, tem);
+  gsi = gsi_for_stmt (stmt);
   tem = force_gimple_operand_gsi (&gsi, tem, true, NULL_TREE, true,
 				  GSI_SAME_STMT);
 
-  VEC_index (operand_entry_t, *ops, range->idx)->op = tem;
+  if (opcode == ERROR_MARK)
+    {
+      if (op)
+	{
+	  imm_use_iterator iter;
+	  use_operand_p use_p;
+	  gimple use_stmt;
+
+	  FOR_EACH_IMM_USE_STMT (use_stmt, iter, op)
+	    {
+	      if (is_gimple_debug (use_stmt))
+		continue;
+	      FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+		SET_USE (use_p, tem);
+	      update_stmt (use_stmt);
+	    }
+	}
+      else
+	{
+	  gimple_cond_set_code (stmt, NE_EXPR);
+	  gimple_cond_set_lhs (stmt, tem);
+	  gimple_cond_set_rhs (stmt, boolean_false_node);
+	  update_stmt (stmt);
+	}
+    }
+  oe->op = tem;
   range->exp = exp;
   range->low = low;
   range->high = high;
@@ -1978,7 +2026,73 @@  update_range_test (struct range_entry *r
 
   for (range = otherrange; range < otherrange + count; range++)
     {
-      VEC_index (operand_entry_t, *ops, range->idx)->op = error_mark_node;
+      oe = VEC_index (oeprand_entry_t, *ops, range->idx);
+      if (opcode == ERROR_MARK)
+	{
+	  if (oe->op)
+	    {
+	      imm_use_iterator iter;
+	      use_operand_p use_p;
+	      gimple use_stmt;
+
+	      FOR_EACH_IMM_USE_STMT (use_stmt, iter, oe->op)
+		{
+		  if (is_gimple_debug (use_stmt))
+		    continue;
+		  if (is_gimple_assign (use_stmt)
+		      && gimple_assign_rhs_code (use_stmt) == oe->rank)
+		    {
+		      tree expr = NULL_TREE;
+		      if (oe->op == gimple_assign_rhs1 (use_stmt))
+			expr = gimple_assign_rhs2 (use_stmt);
+		      else if (oe->op == gimple_assign_rhs2 (use_stmt))
+			expr = gimple_assign_rhs1 (use_stmt);
+		      if (expr
+			  && expr != oe->op
+			  && TREE_CODE (expr) == SSA_NAME)
+			{
+			  gimple_stmt_iterator gsi2 = gsi_for_stmt (use_stmt);
+			  gimple_assign_set_rhs_with_ops (&gsi2, SSA_NAME,
+							  expr, NULL_TREE);
+			  update_stmt (use_stmt);
+			  continue;
+			}
+		      if (gimple_assign_cast_p (use_stmt)
+			  && oe->op == gimple_assign_rhs1 (use_stmt))
+			{
+			  tree lhs = gimple_assign_lhs (use_stmt);
+			  if (INTEGRAL_TYPE_P (TREE_TYPE (lhs)))
+			    {
+			      gimple_stmt_iterator gsi2
+				= gsi_for_stmt (use_stmt);
+			      expr = build_int_cst (TREE_TYPE (lhs),
+						    oe->rank == BIT_IOR_EXPR
+						    ? 0 : 1);
+			      gimple_assign_set_rhs_with_ops (&gsi2,
+							      INTEGER_CST,
+							      expr, NULL_TREE);
+			    }
+			}
+		    }
+		  FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
+		    SET_USE (use_p,
+			     build_int_cst (TREE_TYPE (oe->op),
+					    oe->rank == BIT_IOR_EXPR
+					    ? 0 : 1));
+		  update_stmt (use_stmt);
+		}
+	    }
+	  else
+	    {
+	      stmt = last_stmt (BASIC_BLOCK (oe->id));
+	      if (oe->rank == BIT_IOR_EXPR)
+		gimple_cond_make_false (stmt);
+	      else
+		gimple_cond_make_true (stmt);
+	      update_stmt (stmt);
+	    }
+	}
+      oe->op = error_mark_node;
       range->exp = NULL_TREE;
     }
   return true;
@@ -1986,7 +2100,12 @@  update_range_test (struct range_entry *r
 
 /* Optimize range tests, similarly how fold_range_test optimizes
    it on trees.  The tree code for the binary
-   operation between all the operands is OPCODE.  */
+   operation between all the operands is OPCODE.
+   If OPCODE is ERROR_MARK, optimize_range_tests is called from within
+   maybe_optimize_range_tests for inter-bb range optimization.
+   In that case if oe->op is NULL, oe->id is bb->index whose
+   GIMPLE_COND is && or ||ed into the test, and oe->rank says
+   the actual opcode.  */
 
 static void
 optimize_range_tests (enum tree_code opcode,
@@ -2003,11 +2122,14 @@  optimize_range_tests (enum tree_code opc
   ranges = XNEWVEC (struct range_entry, length);
   for (i = 0; i < length; i++)
     {
+      oe = VEC_index (operand_entry_t, *ops, i);
       ranges[i].idx = i;
-      init_range_entry (ranges + i, VEC_index (operand_entry_t, *ops, i)->op);
+      init_range_entry (ranges + i, oe->op,
+			oe->op ? NULL : last_stmt (BASIC_BLOCK (oe->id)));
       /* For | invert it now, we will invert it again before emitting
 	 the optimized expression.  */
-      if (opcode == BIT_IOR_EXPR)
+      if (opcode == BIT_IOR_EXPR
+	  || (opcode == ERROR_MARK && oe->rank == BIT_IOR_EXPR))
 	ranges[i].in_p = !ranges[i].in_p;
     }
 
@@ -2124,7 +2246,7 @@  optimize_range_tests (enum tree_code opc
 	}
     }
 
-  if (any_changes)
+  if (any_changes && opcode != ERROR_MARK)
     {
       j = 0;
       FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe)
@@ -2141,6 +2263,398 @@  optimize_range_tests (enum tree_code opc
   XDELETEVEC (ranges);
 }
 
+/* Return true if STMT is a cast like:
+   <bb N>:
+   ...
+   _123 = (int) _234;
+
+   <bb M>:
+   # _345 = PHI <_123(N), 1(...), 1(...)>
+   where _234 has bool type, _123 has single use and
+   bb N has a single successor M.  This is commonly used in
+   the last block of a range test.  */
+
+static bool
+final_range_test_p (gimple stmt)
+{
+  basic_block bb, rhs_bb;
+  edge e;
+  tree lhs, rhs;
+  use_operand_p use_p;
+  gimple use_stmt;
+
+  if (!gimple_assign_cast_p (stmt))
+    return false;
+  bb = gimple_bb (stmt);
+  if (!single_succ_p (bb))
+    return false;
+  e = single_succ_edge (bb);
+  if (e->flags & EDGE_COMPLEX)
+    return false;
+
+  lhs = gimple_assign_lhs (stmt);
+  rhs = gimple_assign_rhs1 (stmt);
+  if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+      || TREE_CODE (rhs) != SSA_NAME
+      || TREE_CODE (TREE_TYPE (rhs)) != BOOLEAN_TYPE)
+    return false;
+
+  if (!single_imm_use (lhs, &use_p, &use_stmt))
+    return false;
+
+  if (gimple_code (use_stmt) != GIMPLE_PHI
+      || gimple_bb (use_stmt) != e->dest)
+    return false;
+
+  rhs_bb = gimple_bb (SSA_NAME_DEF_STMT (rhs));
+  if (rhs_bb == NULL
+      || !flow_bb_inside_loop_p (loop_containing_stmt (stmt), rhs_bb))
+    return false;
+
+  return true;
+}
+
+/* Return true if BB is suitable basic block for inter-bb range test
+   optimization.  If BACKWARD is true, BB should be the only predecessor
+   of TEST_BB, and *OTHER_BB is either NULL and filled by the routine,
+   or compared with to find a common basic block to which all conditions
+   branch to if true resp. false.  If BACKWARD is false, TEST_BB should
+   be the only predecessor of BB.  */
+
+static bool
+suitable_cond_bb (basic_block bb, basic_block test_bb, basic_block *other_bb,
+		  bool backward)
+{
+  edge_iterator ei, ei2;
+  edge e, e2;
+  gimple stmt;
+  gimple_stmt_iterator gsi;
+  bool other_edge_seen = false;
+  bool is_cond;
+
+  if (test_bb == bb)
+    return false;
+  stmt = last_stmt (bb);
+  if (stmt == NULL
+      || (gimple_code (stmt) != GIMPLE_COND
+	  && (backward || !final_range_test_p (stmt)))
+      || gimple_visited_p (stmt)
+      || stmt_could_throw_p (stmt)
+      || *other_bb == bb)
+    return false;
+  is_cond = gimple_code (stmt) == GIMPLE_COND;
+  if (is_cond)
+    {
+      if (EDGE_COUNT (bb->succs) != 2)
+	return false;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	{
+	  if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+	    return false;
+	  if (e->dest == test_bb)
+	    {
+	      if (backward)
+		continue;
+	      else
+		return false;
+	    }
+	  if (e->dest == bb)
+	    return false;
+	  if (*other_bb == NULL)
+	    {
+	      FOR_EACH_EDGE (e2, ei2, test_bb->succs)
+		if (!(e2->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+		  return false;
+		else if (e->dest == e2->dest)
+		  *other_bb = e->dest;
+	      if (*other_bb == NULL)
+		return false;
+	    }
+	  if (e->dest == *other_bb)
+	    other_edge_seen = true;
+	  else if (backward)
+	    return false;
+	}
+      if (*other_bb == NULL || !other_edge_seen)
+	return false;
+    }
+  else if (single_succ (bb) != *other_bb)
+    return false;
+
+  e = find_edge (bb, *other_bb);
+  e2 = find_edge (test_bb, *other_bb);
+  for (gsi = gsi_start_phis (e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+      if (!operand_equal_p (gimple_phi_arg_def (phi, e->dest_idx),
+			    gimple_phi_arg_def (phi, e2->dest_idx), 0))
+	{
+	  if (!is_cond)
+	    {
+	      if (gimple_phi_arg_def (phi, e->dest_idx)
+		  == gimple_assign_lhs (stmt)
+		  && (integer_zerop (gimple_phi_arg_def (phi, e2->dest_idx))
+		      || integer_onep (gimple_phi_arg_def (phi,
+							   e2->dest_idx))))
+		continue;
+	    }
+	  else
+	    {
+	      gimple test_last = last_stmt (test_bb);
+	      if (gimple_code (test_last) != GIMPLE_COND
+		  && gimple_phi_arg_def (phi, e2->dest_idx)
+		     == gimple_assign_lhs (test_last)
+		  && (integer_zerop (gimple_phi_arg_def (phi, e->dest_idx))
+		      || integer_onep (gimple_phi_arg_def (phi, e->dest_idx))))
+		continue;
+	    }
+
+	  return false;
+	}
+    }
+  return true;
+}
+
+/* Return true if BB doesn't have side-effects that would disallow
+   range test optimization, all SSA_NAMEs set in the bb are consumed
+   in the bb and there are no PHIs.  */
+
+static bool
+no_side_effect_bb (basic_block bb)
+{
+  gimple_stmt_iterator gsi;
+  gimple last;
+
+  if (!gimple_seq_empty_p (phi_nodes (bb)))
+    return false;
+  last = last_stmt (bb);
+  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple stmt = gsi_stmt (gsi);
+      tree lhs;
+      imm_use_iterator imm_iter;
+      use_operand_p use_p;
+
+      if (is_gimple_debug (stmt))
+	continue;
+      if (gimple_has_side_effects (stmt))
+	return false;
+      if (stmt == last)
+	return true;
+      if (!is_gimple_assign (stmt))
+	return false;
+      lhs = gimple_assign_lhs (stmt);
+      if (TREE_CODE (lhs) != SSA_NAME)
+	return false;
+      if (gimple_assign_rhs_could_trap_p (stmt))
+	return false;
+      FOR_EACH_IMM_USE_FAST (use_p, imm_iter, lhs)
+	{
+	  gimple use_stmt = USE_STMT (use_p);
+	  if (is_gimple_debug (use_stmt))
+	    continue;
+	  if (gimple_bb (use_stmt) != bb)
+	    return false;
+	}
+    }
+  return false;
+}
+
+/* If VAR is set by CODE (BIT_{AND,IOR}_EXPR) which is reassociable,
+   return true and fill in *OPS recursively.  */
+
+static bool
+get_ops (tree var, enum tree_code code, VEC(operand_entry_t, heap) **ops,
+	 struct loop *loop)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (var);
+  tree rhs[2];
+  int i;
+
+  if (!is_reassociable_op (stmt, code, loop))
+    return false;
+
+  rhs[0] = gimple_assign_rhs1 (stmt);
+  rhs[1] = gimple_assign_rhs2 (stmt);
+  gimple_set_visited (stmt, true);
+  for (i = 0; i < 2; i++)
+    if (TREE_CODE (rhs[i]) == SSA_NAME
+	&& !get_ops (rhs[i], code, ops, loop)
+	&& has_single_use (rhs[i]))
+      {
+	operand_entry_t oe = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+	oe->op = rhs[i];
+	oe->rank = code;
+	oe->id = 0;
+	oe->count = 1;
+	VEC_safe_push (operand_entry_t, heap, *ops, oe);
+      }
+  return true;
+}
+
+/* Inter-bb range test optimization.  */
+
+static void
+maybe_optimize_range_tests (gimple stmt)
+{
+  basic_block first_bb = gimple_bb (stmt);
+  basic_block last_bb = first_bb;
+  basic_block other_bb = NULL;
+  basic_block bb;
+  edge_iterator ei;
+  edge e;
+  VEC(operand_entry_t, heap) *ops = NULL;
+
+  if (gimple_code (stmt) == GIMPLE_COND)
+    {
+      if (EDGE_COUNT (first_bb->succs) != 2)
+	return;
+    }
+  else if (final_range_test_p (stmt))
+    other_bb = single_succ (first_bb);
+  else
+    return;
+
+  if (stmt_could_throw_p (stmt))
+    return;
+
+  while (single_pred_p (first_bb))
+    {
+      basic_block pred_bb = single_pred (first_bb);
+      if (!suitable_cond_bb (pred_bb, first_bb, &other_bb, true))
+	break;
+      if (!no_side_effect_bb (first_bb))
+	break;
+      first_bb = pred_bb;
+    }
+  if (first_bb == last_bb)
+    {
+      other_bb = NULL;
+      if (gimple_code (stmt) != GIMPLE_COND)
+	return;
+      FOR_EACH_EDGE (e, ei, first_bb->succs)
+	if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE))
+	    || e->dest == first_bb)
+	  return;
+	else if (single_pred_p (e->dest))
+	  {
+	    stmt = last_stmt (e->dest);
+	    if (stmt
+		&& gimple_code (stmt) == GIMPLE_COND
+		&& EDGE_COUNT (e->dest->succs) == 2)
+	      {
+		if (suitable_cond_bb (first_bb, e->dest, &other_bb, true))
+		  break;
+		else
+		  other_bb = NULL;
+	      }
+	    else if (stmt
+		     && final_range_test_p (stmt)
+		     && find_edge (first_bb, single_succ (e->dest)))
+	      {
+		other_bb = single_succ (e->dest);
+		if (other_bb == first_bb)
+		  other_bb = NULL;
+	      }
+	  }
+      if (other_bb == NULL)
+	return;
+    }
+  while (EDGE_COUNT (last_bb->succs) == 2)
+    {
+      FOR_EACH_EDGE (e, ei, last_bb->succs)
+	if (e->dest != other_bb)
+	  break;
+      if (e == NULL)
+	break;
+      if (!single_pred_p (e->dest))
+	break;
+      if (!suitable_cond_bb (e->dest, last_bb, &other_bb, false))
+	break;
+      if (!no_side_effect_bb (e->dest))
+	break;
+      last_bb = e->dest;
+    }
+  if (first_bb == last_bb)
+    return;
+  for (bb = last_bb; ; bb = single_pred (bb))
+    {
+      enum tree_code code;
+      tree lhs, rhs;
+
+      e = find_edge (bb, other_bb);
+      stmt = last_stmt (bb);
+      gimple_set_visited (stmt, true);
+      if (gimple_code (stmt) != GIMPLE_COND)
+	{
+	  use_operand_p use_p;
+	  gimple phi;
+	  edge e2;
+	  unsigned int d;
+
+	  lhs = gimple_assign_lhs (stmt);
+	  rhs = gimple_assign_rhs1 (stmt);
+	  gcc_assert (bb == last_bb);
+
+	  single_imm_use (lhs, &use_p, &phi);
+	  gcc_assert (gimple_code (phi) == GIMPLE_PHI);
+	  e2 = find_edge (first_bb, other_bb);
+	  d = e2->dest_idx;
+	  gcc_assert (gimple_phi_arg_def (phi, e->dest_idx) == lhs);
+	  if (integer_zerop (gimple_phi_arg_def (phi, d)))
+	    code = BIT_AND_EXPR;
+	  else
+	    {
+	      gcc_checking_assert (integer_onep (gimple_phi_arg_def (phi, d)));
+	      code = BIT_IOR_EXPR;
+	    }
+
+	  if (!get_ops (rhs, code, &ops,
+			loop_containing_stmt (stmt))
+	      && has_single_use (rhs))
+	    {
+	      operand_entry_t oe
+		= (operand_entry_t) pool_alloc (operand_entry_pool);
+
+	      oe->op = rhs;
+	      oe->rank = code;
+	      oe->id = 0;
+	      oe->count = 1;
+	      VEC_safe_push (operand_entry_t, heap, ops, oe);
+	    }
+	  continue;
+	}
+      code = gimple_cond_code (stmt);
+      lhs = gimple_cond_lhs (stmt);
+      rhs = gimple_cond_rhs (stmt);
+      if (TREE_CODE (lhs) == SSA_NAME
+	  && INTEGRAL_TYPE_P (TREE_TYPE (lhs))
+	  && ((code != EQ_EXPR && code != NE_EXPR)
+	      || rhs != boolean_false_node
+	      || !get_ops (lhs, (((e->flags & EDGE_TRUE_VALUE) == 0)
+				 ^ (code == EQ_EXPR))
+				? BIT_AND_EXPR : BIT_IOR_EXPR, &ops,
+			   loop_containing_stmt (stmt))))
+	{
+	  operand_entry_t oe
+	    = (operand_entry_t) pool_alloc (operand_entry_pool);
+
+	  oe->op = NULL;
+	  oe->rank = (e->flags & EDGE_TRUE_VALUE)
+		     ? BIT_IOR_EXPR : BIT_AND_EXPR;
+	  oe->id = bb->index;
+	  oe->count = 1;
+	  VEC_safe_push (operand_entry_t, heap, ops, oe);
+	}
+      if (bb == first_bb)
+	break;
+    }
+  if (VEC_length (operand_entry_t, ops) > 1)
+    optimize_range_tests (ERROR_MARK, &ops);
+  VEC_free (operand_entry_t, heap, ops);
+}
+
 /* Return true if OPERAND is defined by a PHI node which uses the LHS
    of STMT in it's operands.  This is also known as a "destructive
    update" operation.  */
@@ -3427,10 +3941,14 @@  reassociate_bb (basic_block bb)
 {
   gimple_stmt_iterator gsi;
   basic_block son;
+  gimple stmt = last_stmt (bb);
+
+  if (stmt && !gimple_visited_p (stmt))
+    maybe_optimize_range_tests (stmt);
 
   for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
     {
-      gimple stmt = gsi_stmt (gsi);
+      stmt = gsi_stmt (gsi);
 
       if (is_gimple_assign (stmt)
 	  && !stmt_could_throw_p (stmt))
--- gcc/testsuite/gcc.dg/pr19105.c.jj	2012-10-26 15:12:04.191828571 +0200
+++ gcc/testsuite/gcc.dg/pr19105.c	2012-10-26 15:11:41.000000000 +0200
@@ -0,0 +1,22 @@ 
+/* PR tree-optimization/19105 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+
+enum e
+{
+  a, b, c, d, e, f, g, h
+};
+
+int range1 (enum e v, int x)
+{
+  return x && v != c && v != d && v != e;
+}
+
+int range2 (enum e v, int x)
+{
+  return x && (v != c && v != d && v != e);
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests v_\[0-9\]*.D. -.2, 2. and -.3, 4.\[\n\r\]* into" 1 "reassoc1" } } */
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
+
--- gcc/testsuite/gcc.dg/pr21643.c.jj	2012-10-26 15:00:14.588063088 +0200
+++ gcc/testsuite/gcc.dg/pr21643.c	2012-10-26 15:01:31.199598891 +0200
@@ -0,0 +1,90 @@ 
+/* PR tree-optimization/21643 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+
+int
+f1 (unsigned char c)
+{
+  if (c == 0x22 || c == 0x20 || c < 0x20)
+    return 1;
+  return 0;
+}
+
+int
+f2 (unsigned char c)
+{
+  if (c == 0x22 || c <= 0x20)
+    return 1;
+  return 0;
+}
+
+int
+f3 (unsigned char c)
+{
+  if (c == 0x22)
+    return 1;
+  if (c == 0x20)
+    return 1;
+  if (c < 0x20)
+    return 1;
+  return 0;
+}
+
+int
+f4 (unsigned char c)
+{
+  if (c == 0x22 || c == 0x20 || c < 0x20)
+    return 2;
+  return 0;
+}
+
+int
+f5 (unsigned char c)
+{
+  if (c == 0x22 || c <= 0x20)
+    return 2;
+  return 0;
+}
+
+int
+f6 (unsigned char c)
+{
+  if (c == 0x22)
+    return 2;
+  if (c == 0x20)
+    return 2;
+  if (c < 0x20)
+    return 2;
+  return 0;
+}
+
+int
+f7 (unsigned char c)
+{
+  if (c != 0x22 && c != 0x20 && c >= 0x20)
+    return 0;
+  return 1;
+}
+
+int
+f8 (unsigned char c)
+{
+  if (c == 0x22 && c <= 0x20)
+    return 0;
+  return 1;
+}
+
+int
+f9 (unsigned char c)
+{
+  if (c == 0x22)
+    return 0;
+  if (c == 0x20)
+    return 0;
+  if (c < 0x20)
+    return 0;
+  return 1;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests c_\[0-9\]*.D. -.0, 31. and -.32, 32.\[\n\r\]* into" 6 "reassoc1" } } */
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
--- gcc/testsuite/gcc.dg/pr46309-2.c.jj	2012-10-25 16:30:42.623578285 +0200
+++ gcc/testsuite/gcc.dg/pr46309-2.c	2012-10-26 15:16:38.404212168 +0200
@@ -0,0 +1,147 @@ 
+/* PR tree-optimization/46309 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc-details" } */
+
+int foo (void);
+
+void
+f1 (int a)
+{
+  _Bool v1 = (a == 3);
+  _Bool v2 = (a == 1);
+  _Bool v3 = (a == 4);
+  _Bool v4 = (a == 2);
+  if (v1 || v2 || v3 || v4)
+    foo ();
+}
+
+void
+f2 (int a)
+{
+  _Bool v1 = (a == 1);
+  _Bool v2 = (a == 2);
+  _Bool v3 = (a == 3);
+  _Bool v4 = (a == 4);
+  if (v1 || v2 || v3 || v4)
+    foo ();
+}
+
+void
+f3 (unsigned int a)
+{
+  _Bool v1 = (a <= 31);
+  _Bool v2 = (a >= 64 && a <= 95);
+  _Bool v3 = (a >= 128 && a <= 159);
+  _Bool v4 = (a >= 192 && a <= 223);
+  if (v1 || v2 || v3 || v4)
+    foo ();
+}
+
+void
+f4 (int a)
+{
+  _Bool v1 = (a == 3);
+  _Bool v2 = (a == 1);
+  _Bool v3 = (a == 4);
+  _Bool v4 = (a == 2);
+  _Bool v5 = (a == 7);
+  _Bool v6 = (a == 5);
+  _Bool v7 = (a == 8);
+  _Bool v8 = (a == 6);
+  if (v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8)
+    foo ();
+}
+
+void
+f5 (int a)
+{
+  _Bool v1 = (a != 3);
+  _Bool v2 = (a != 1);
+  _Bool v3 = (a != 4);
+  _Bool v4 = (a != 2);
+  _Bool v5 = (a != 7);
+  _Bool v6 = (a != 5);
+  _Bool v7 = (a != 8);
+  _Bool v8 = (a != 6);
+  if (v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8)
+    foo ();
+}
+
+void
+f6 (int a)
+{
+  _Bool v1 = (a != 3);
+  _Bool v2 = (a != 1);
+  _Bool v3 = (a != 4);
+  _Bool v4 = (a != 2);
+  _Bool v5 = (a != 7);
+  _Bool v6 = (a != 5);
+  _Bool v7 = (a != 8);
+  _Bool v8 = (a != 6);
+  if ((v1 && v2 && v3 && v4) && (v5 && v6 && v7 && v8))
+    foo ();
+}
+
+int
+f7 (int a)
+{
+  _Bool v1 = (a == 3);
+  _Bool v2 = (a == 1);
+  _Bool v3 = (a == 4);
+  _Bool v4 = (a == 2);
+  _Bool v5 = (a == 7);
+  _Bool v6 = (a == 5);
+  _Bool v7 = (a == 8);
+  _Bool v8 = (a == 6);
+  return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
+}
+
+_Bool
+f8 (int a)
+{
+  _Bool v1 = (a == 3);
+  _Bool v2 = (a == 1);
+  _Bool v3 = (a == 4);
+  _Bool v4 = (a == 2);
+  _Bool v5 = (a == 7);
+  _Bool v6 = (a == 5);
+  _Bool v7 = (a == 8);
+  _Bool v8 = (a == 6);
+  return v1 || v2 || v3 || v4 || v5 || v6 || v7 || v8;
+}
+
+int
+f9 (int a)
+{
+  _Bool v1 = (a != 3);
+  _Bool v2 = (a != 1);
+  _Bool v3 = (a != 4);
+  _Bool v4 = (a != 2);
+  _Bool v5 = (a != 7);
+  _Bool v6 = (a != 5);
+  _Bool v7 = (a != 8);
+  _Bool v8 = (a != 6);
+  return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
+}
+
+_Bool
+f10 (int a)
+{
+  _Bool v1 = (a != 3);
+  _Bool v2 = (a != 1);
+  _Bool v3 = (a != 4);
+  _Bool v4 = (a != 2);
+  _Bool v5 = (a != 7);
+  _Bool v6 = (a != 5);
+  _Bool v7 = (a != 8);
+  _Bool v8 = (a != 6);
+  return v1 && v2 && v3 && v4 && v5 && v6 && v7 && v8;
+}
+
+/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4.\[\n\r\]* into" 2 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.0, 31. and -.64, 95.\[\n\r\]* into" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.128, 159. and -.192, 223.\[\n\r\]* into" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests a_\[0-9\]*.D. -.1, 1. and -.2, 2. and -.3, 3. and -.4, 4. and -.5, 5. and -.6, 6. and -.7, 7. and -.8, 8.\[\n\r\]* into" 7 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "Optimizing range tests \[^\r\n\]*_\[0-9\]* -.0, 31. and -.128, 159.\[\n\r\]* into" 1 "reassoc2" } } */
+/* { dg-final { cleanup-tree-dump "reassoc1" } } */
+/* { dg-final { cleanup-tree-dump "reassoc2" } } */
--- gcc/testsuite/gcc.c-torture/execute/pr46309.c.jj	2012-10-26 10:10:28.403238295 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr46309.c	2012-10-26 10:10:11.000000000 +0200
@@ -0,0 +1,31 @@ 
+/* PR tree-optimization/46309 */
+
+extern void abort (void);
+
+unsigned int *q;
+
+__attribute__((noinline, noclone)) void
+bar (unsigned int *p)
+{
+  if (*p != 2 && *p != 3)
+    (!(!(*q & 263) || *p != 1)) ? abort () : 0;
+}
+
+int
+main ()
+{
+  unsigned int x, y;
+  asm volatile ("" : : : "memory");
+  x = 2;
+  bar (&x);
+  x = 3;
+  bar (&x);
+  y = 1;
+  x = 0;
+  q = &y;
+  bar (&x);
+  y = 0;
+  x = 1;
+  bar (&x);
+  return 0;
+}