Needs -O3:

char a;
int b;
void fn1(char *p1, int p2, int p3) {
  int x;
  for (; b;) {
    for (x = 0; x < p3; x++) {
      *p1 = a;
      p1--;
    }
    p1 += p2;
  }
}

Started with r228599.

It looks like unswitching of outer loops pass simply triggers the issue and this tree-ssa-loop-ivopts issue.

Indeed, there is an issue with outer-loop unswitching - it should not be performed for infinite loops. But if we slightly modify test if finite outer-loop we will get the same error: 
char a;
void fn1(char *p1, int p2, int p3) {
  int i, x;
  for (i = 0; i < 10; i++) {
    for (x = 0; x < p3; x++) {
      *p1 = a;
      p1--;
    }
    p1 += p2;
  }
}

I assume that  sccp is responsible for it.

Hi HJ

I added my evaluation to bug. It looks like my changes are not
responsible for ICE.

2015-10-20 13:20 GMT+03:00 hjl.tools at gmail dot com
<gcc-bugzilla@gcc.gnu.org>:
> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68021
>
> H.J. Lu <hjl.tools at gmail dot com> changed:
>
>            What    |Removed                     |Added
> ----------------------------------------------------------------------------
>                  CC|                            |ysrumyan at gmail dot com
>
> --
> You are receiving this mail because:
> You are on the CC list for the bug.

Even the #c4 testcase started to ICE with r228599 though.

*** Bug 69163 has been marked as a duplicate of this bug. ***

Seems the problem is that we have use->iv->step
(_2 - (sizetype) ((unsigned int) p3_11(D) + 4294967295)) + 18446744073709551615;
and cand->iv->step
(_2 - (sizetype) ((unsigned int) p3_11(D) + 4294967295)) - 1;
Both are really equivalent, but when constant_multiple_of is called on these, it calls operand_equal_p and that will return they are not equal and thus not multiple of each other.
This boils down to the canonicalization we do on MINUS_EXPR:
      /* A - B -> A + (-B) if B is easily negatable.  */
      if (negate_expr_p (op1)
          && ! TYPE_OVERFLOW_SANITIZED (type)
          && ((FLOAT_TYPE_P (type)
               /* Avoid this transformation if B is a positive REAL_CST.  */
               && (TREE_CODE (op1) != REAL_CST
                   || REAL_VALUE_NEGATIVE (TREE_REAL_CST (op1))))
              || INTEGRAL_TYPE_P (type)))
        return fold_build2_loc (loc, PLUS_EXPR, type,
                                fold_convert_loc (loc, type, arg0),
                                negate_expr (op1));
but don't really do it in associate_trees.
The caller of associate_trees has worrying comments on that though:
              /* Preserve the MINUS_EXPR if the negative part of the literal is
                 greater than the positive part.  Otherwise, the multiplicative
                 folding code (i.e extract_muldiv) may be fooled in case
                 unsigned constants are subtracted, like in the following
                 example: ((X*2 + 4) - 8U)/2.  */
which is pretty much the case here, - 1 constant is smaller than + (-1UL).
So, are we ok that this isn't really canonicalized always the same?
Shall operand_equal_p be treating those two cases as equal (perhaps under some flag)?  Or shall constant_multiple_of be using some different comparison?
Or shall something much earlier in the IVOPTS code just give up if the steps aren't really equal/multiples of each other?

Sorry for missing this.  I will study the case.

This is an ivopt bug all the time.  As designed, ivopt tries to identify and reuse induction variables in the original input.  Apparently we don't need to compute such original biv with new code because the computation is already there.  Every time an iv use is rewritten, ivopt checks if the candidate is an original biv using below code:

  /* An important special case -- if we are asked to express value of
     the original iv by itself, just exit; there is no need to
     introduce a new computation (that might also need casting the
     variable to unsigned and back).  */
  if (cand->pos == IP_ORIGINAL
      && cand->incremented_at == use->stmt)
    {
      enum tree_code stmt_code;

      gcc_assert (is_gimple_assign (use->stmt));
      gcc_assert (gimple_assign_lhs (use->stmt) == cand->var_after);

      /* Check whether we may leave the computation unchanged.
	 This is the case only if it does not rely on other
	 computations in the loop -- otherwise, the computation
	 we rely upon may be removed in remove_unused_ivs,
	 thus leading to ICE.  */
      stmt_code = gimple_assign_rhs_code (use->stmt);
      if (stmt_code == PLUS_EXPR
	  || stmt_code == MINUS_EXPR
	  || stmt_code == POINTER_PLUS_EXPR)
	{
	  if (gimple_assign_rhs1 (use->stmt) == cand->var_before)
	    op = gimple_assign_rhs2 (use->stmt);
	  else if (gimple_assign_rhs2 (use->stmt) == cand->var_before)
	    op = gimple_assign_rhs1 (use->stmt);
	  else
	    op = NULL_TREE;
	}
      else
	op = NULL_TREE;

      if (op && expr_invariant_in_loop_p (data->current_loop, op))
	return;
    }

Note this code can only handle specific form biv, in which there is an explicit increment stmt in the form of "biv_after = biv_before + step".

Unfortunately, in rare case like this, the biv is increased in two stmts, like:
  biv_x = biv_before + step_part_1;
  biv_after = biv_x + step_part_2;

That's why control flow goes to ICE point.  We don't need to fix the ICE point because:
1) We shouldn't rewrite biv candidate.  Even there is no correctness issue, it will introduce redundant code by rewriting it.
2) For non biv candidate, all the computation at ICE point has already been done at iv cost computation part.  In other words, if control flow goes here, gcc_assert (comp != NULL" will be true.

Back to this issue, I have two possible fixes.  First one is to specially rewrite mentioned increment stmts into:
  biv_after = biv_before + step
This fix need more work because after candidate creation point we need to compute step in loop pre-header.

Another fix is just don't add biv for such case.  In this way, we check stricter condition when adding biv candidate, thus control flow doesn't go to ICE point.  It won't cause worse code since we add exact the same candidate anyway (which is non biv candidate).  As a matter of fact, we create/use another candidate which has the same {base, step} as the biv.  The computation of biv now becomes dead code and removed by following passes.

Testing a patch using 2nd method.

void bar (void);

void
foo (int p2, int p3)
{
  unsigned long a = p2;
  unsigned long b = (~(unsigned long) ((unsigned int) p3 + -1U)) + a;
  unsigned long c = (a - (unsigned long) ((unsigned int) p3 + -1U)) + (-1UL);
  if (b != c)
    bar ();
}

shows this folding inconsistency in the *.original dump:
  long unsigned int a = (long unsigned int) p2;
  long unsigned int b = (a - (long unsigned int) ((unsigned int) p3 + 4294967295)) - 1;
  long unsigned int c = (a - (long unsigned int) ((unsigned int) p3 + 4294967295)) + 18446744073709551615;
but *.gimple already canonicalizes it, so that it does + 18446744073709551615 at the end in both cases.

(In reply to Jakub Jelinek from comment #11)
> void bar (void);
> 
> void
> foo (int p2, int p3)
> {
>   unsigned long a = p2;
>   unsigned long b = (~(unsigned long) ((unsigned int) p3 + -1U)) + a;
>   unsigned long c = (a - (unsigned long) ((unsigned int) p3 + -1U)) + (-1UL);
>   if (b != c)
>     bar ();
> }
> 
> shows this folding inconsistency in the *.original dump:
>   long unsigned int a = (long unsigned int) p2;
>   long unsigned int b = (a - (long unsigned int) ((unsigned int) p3 +
> 4294967295)) - 1;
>   long unsigned int c = (a - (long unsigned int) ((unsigned int) p3 +
> 4294967295)) + 18446744073709551615;
> but *.gimple already canonicalizes it, so that it does +
> 18446744073709551615 at the end in both cases.

associate_trees doesn't re-fold the result (due to fear of recursion I guess)

Hmm, I posted a patch at https://gcc.gnu.org/ml/gcc-patches/2016-02/msg00447.html
But after digging deeper I think the posted is unnecessary and it should be fixed in fold stuff.

The ivopt logic is
1) create iv use for original biv candidate chosen by the algorithm.
2) rewrite iv use created in 1) using the original biv in rewrite_use_nonlinear_expr.  (Here we use nonlinear use as the example)
3) If the iv use is exact the candidate increment stmt, then skip rewriting since the computation is already there.
4) If that's not the case (in 3), it falls through  and uses get_computation to rewrite the use.  As commented in #10, this may introduce redundant code, we rely on following passes to remove them.

So for this case, the iv use created is direct for an original biv var.  The values of the iv use and the original biv are same to each other.  Just the iv use will be rewrite in a different form of computation to the original biv.

In other words, it is guaranteed that the iv use has same value as original candidate when control flow comes to the ICE point.  The ICE really is caused by inconsistent fold behavior.

So IMHO, we may have to fix the fold part...

(In reply to amker from comment #13)
> Hmm, I posted a patch at
> https://gcc.gnu.org/ml/gcc-patches/2016-02/msg00447.html
> But after digging deeper I think the posted is unnecessary and it should be
> fixed in fold stuff.
> 
> The ivopt logic is
> 1) create iv use for original biv candidate chosen by the algorithm.
> 2) rewrite iv use created in 1) using the original biv in
> rewrite_use_nonlinear_expr.  (Here we use nonlinear use as the example)
> 3) If the iv use is exact the candidate increment stmt, then skip rewriting
> since the computation is already there.
> 4) If that's not the case (in 3), it falls through  and uses get_computation
> to rewrite the use.  As commented in #10, this may introduce redundant code,
> we rely on following passes to remove them.
> 
> So for this case, the iv use created is direct for an original biv var.  The
> values of the iv use and the original biv are same to each other.  Just the
> iv use will be rewrite in a different form of computation to the original
> biv.
> 
> In other words, it is guaranteed that the iv use has same value as original
> candidate when control flow comes to the ICE point.  The ICE really is
> caused by inconsistent fold behavior.
> 
> So IMHO, we may have to fix the fold part...

I'm afraid we can't guarantee you'll get always operand_equal_p results from the folding, if you start folding in different orders etc.  The issue mentioned here is just one case we know of.
So, IMHO it must be solved in the IVOPTs side, either by giving up somewhere and not using candidate that would not be recognized during rewriting, or by always folding the same operands in the same order if it is the same thing, or just noting it is the same thing somewhere (and/or remembering the multiply factor) and not trying the constant_multiple_of.
Incremental improvements on the folding side will then incrementally improve stuff on the IVOPTs side, but you won't ICE on arbitrary cases that aren't handled yet.

Though the previous patch can work, I am testing another patch less intrusive.

Author: amker
Date: Wed Feb 10 14:09:05 2016
New Revision: 233269

URL: https://gcc.gnu.org/viewcvs?rev=233269&root=gcc&view=rev
Log:

	PR tree-optimization/68021
	* tree-ssa-loop-ivopts.c (get_computation_aff): Set ratio to 1 if
	when computing the value of biv cand by itself.

	gcc/testsuite/ChangeLog
	PR tree-optimization/68021
	* gcc.dg/tree-ssa/pr68021.c: New test.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr68021.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-loop-ivopts.c

Fixed.

Author: amker
Date: Tue Apr 11 08:15:51 2017
New Revision: 246833

URL: https://gcc.gnu.org/viewcvs?rev=246833&root=gcc&view=rev
Log:
	Backport from mainline
	2016-02-10  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/68021
	* tree-ssa-loop-ivopts.c (get_computation_aff): Set ratio to 1 if
	when computing the value of biv cand by itself.


	gcc/testsuite
	PR tree-optimization/80345
	* gcc.c-torture/compile/pr80345.c

	Backport from mainline
	2016-02-10  Bin Cheng  <bin.cheng@arm.com>

	PR tree-optimization/68021
	* gcc.dg/tree-ssa/pr68021.c: New test.

Added:
    branches/gcc-5-branch/gcc/testsuite/gcc.c-torture/compile/pr80345.c
    branches/gcc-5-branch/gcc/testsuite/gcc.dg/tree-ssa/pr68021.c
Modified:
    branches/gcc-5-branch/gcc/ChangeLog
    branches/gcc-5-branch/gcc/testsuite/ChangeLog
    branches/gcc-5-branch/gcc/tree-ssa-loop-ivopts.c