Created attachment 19395 [details]
preprocessed source

Works on i?86-linux.   I guess stage2 is miscompiled?

rechecked with 20090104. setting BOOT_CFLAGS to -g -O1 lets the gcc bootstrap pass.

  Matthias

I got different error in the same place when configured with:

Target: alpha-linux-gnu
Configured with: ../gcc-svn/trunk/configure --host=alpha-linux-gnu --build=alpha-linux-gnu --target=alpha-linux-gnu --enable-languages=c

~/gcc-build-test/gcc/cc1 -O2 -quiet regex.i
In file included from ../../src/libiberty/regex.c:638:0:
../../src/libiberty/regex.c: In function ‘byte_re_match_2_internal’:
../../src/libiberty/regex.c:5543:1: error: definition in block 8 does not dominate use in block 7
for SSA_NAME: D.7346_246 in statement:
D.7347_247 = regstart_61 + D.7346_246;
../../src/libiberty/regex.c:5543:1: internal compiler error: verify_ssa failed
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

This happens with stage2 compiler.

Minimized testcase (from other bootstrap failure):

--cut here--
typedef struct
{
  struct
  {
    int how;
  } reg[64 + 1];
}
_Unwind_FrameState;

alpha_fallback_frame_state (_Unwind_FrameState * fs)
{
  long i;

  for (i = 0; i < 31; ++i)
    fs->reg[i + 32].how = 0;
}
--cut here--

~/gcc-build-test/gcc/cc1 -O2 -quiet t1.c
t1.c: In function ‘alpha_fallback_frame_state’:
t1.c:10:1: error: definition in block 3 does not dominate use in block 2
for SSA_NAME: i_11 in statement:
D.2028_3 = i_11 + 32;
t1.c:10:1: internal compiler error: verify_ssa failed
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.

So, which stages do ICE on the testcase?

setting BOOT_CFLAGS to -g -O1 lets the build succeed. the testcase from comment #5 doesn't ice. test results for this build at
http://gcc.gnu.org/ml/gcc-testresults/2010-01/msg00501.html

It looks that tree loop IM FUBARs the compilation.

All testcases compile OK with -O2 -fno-tree-loop-im.

The dump for _.c.099t.lim1 looks quite strange (it resembles _.c.024t.ssa):

--cut here--
;; Function alpha_fallback_frame_state (alpha_fallback_frame_state)



Symbols to be put in SSA form

{ .MEM fs___regfs__I_I__howfs___regfs__I_I_I.3 }


Incremental SSA update started at block: 0

Number of blocks in CFG: 6
Number of blocks to update: 5 ( 83%)




SSA replacement table
N_i -> { O_1 ... O_j } means that N_i replaces O_1, ..., O_j

fs___regfs__I_I__howfs___regfs__I_I_I.3_10 -> { fs___regfs__I_I__howfs___regfs__I_I_I.3_9 }

Number of virtual NEW -> OLD mappings:       0
Number of real NEW -> OLD mappings:          1
Number of total NEW -> OLD mappings:         1

Number of virtual symbols: 0


Incremental SSA update started at block: 3

Number of blocks in CFG: 6
Number of blocks to update: 2 ( 33%)



alpha_fallback_frame_state (struct _Unwind_FrameState * fs)
{
  int fs___regfs__I_I__howfs___regfs__I_I_I.3;
  long int pretmp.2;
  long int i;
  long int D.2028;

<bb 2>:
  D.2028_3 = i_11 + 32;
  fs___regfs__I_I__howfs___regfs__I_I_I.3_8 = fs_4(D)->reg[D.2028_3].how;

<bb 3>:
  # i_11 = PHI <i_5(4), 0(2)>
  fs___regfs__I_I__howfs___regfs__I_I_I.3_9 = 0;
  i_5 = i_11 + 1;
  if (i_5 <= 30)
    goto <bb 4>;
  else
    goto <bb 5>;

<bb 4>:
  goto <bb 3>;

<bb 5>:
  # fs___regfs__I_I__howfs___regfs__I_I_I.3_10 = PHI <fs___regfs__I_I__howfs___regfs__I_I_I.3_9(3)>
  fs_4(D)->reg[D.2028_3].how = fs___regfs__I_I__howfs___regfs__I_I_I.3_10;
  return;

}
--cut here--

(In reply to comment #7)
> setting BOOT_CFLAGS to -g -O1 lets the build succeed. the testcase from comment
> #5 doesn't ice. 

It will ICE with default build, with checkings enabled.

Well, I can't see how this wouldn't be a problem on other targets thus I
re-iterate: which stages do show this behavior?  Does the stage1 cc1
reproduce it?

(In reply to comment #10)
> Well, I can't see how this wouldn't be a problem on other targets thus I
> re-iterate: which stages do show this behavior?  Does the stage1 cc1
> reproduce it?

No.

Got the problem. stage1 compiler miscompiles determine_max_movement() from
tree-ssa-loop-im.c.

Following """"patch"""" fixes the testcase from comment #5:

Index: tree-ssa-loop-im.c
===================================================================
--- tree-ssa-loop-im.c	(revision 155643)
+++ tree-ssa-loop-im.c	(working copy)
@@ -677,6 +677,7 @@
     level = superloop_at_depth (loop, 1);
   lim_data->max_loop = level;
 
+  debug_gimple_stmt (stmt);
   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_USE)
     if (!add_dependency (val, lim_data, loop, true))
       return false;

I will restart bootstrap now.

(In reply to comment #12)

> I will restart bootstrap now.

Bootstraps OK for --enable-languages=c.

This bug can be now reproduced with a crosscompiler to alpha-linux-gnu with soon to be attached preprocessed source of tree-ssa-loop-im.i (please note noinline attributes at determine_max_movement and add_dependency).

The problem is that stage1 (or cross-) compiler miscompiles determine_max_movement from tree-ssa-loop-im.c, where cse2 rtl pass removes whole lot of code when -O2 is used.

Created attachment 19483 [details]
preprocessed source

The problem turns out to be quite complex interaction between cse1, cprop3 and cse2 pass.

Let's start with this RTL dump for from:

tree-ssa-loop-im.i.148r.subreg1

;; Function determine_max_movement (determine_max_movement)

...

L34:
   35 NOTE_INSN_BASIC_BLOCK
   36 [r73:DI]=r69:DI
   37 r155:SI=[r152:DI]
   38 r154:QI#0=zero_extract(r155:SI#0,0x8,0x0)
   39 r78:DI=zero_extend(r154:QI)
      REG_EQUAL: zero_extend([r152:DI])
   40 pc={(r78:DI==0x0)?L579:pc}
      REG_BR_PROB: 0x1388
...

L571:
  572 NOTE_INSN_BASIC_BLOCK
  573 r351:SI=[r152:DI]
  574 r350:QI#0=zero_extract(r351:SI#0,0x8,0x0)
  575 r82:DI=zero_extend(r350:QI)
      REG_EQUAL: zero_extend([r152:DI])
L579:
  580 NOTE_INSN_BASIC_BLOCK
  581 r353:SI=[r152:DI]
  582 r352:QI#0=zero_extract(r353:SI#0,0x8,0x0)
  583 r82:DI=zero_extend(r352:QI)
      REG_EQUAL: zero_extend([r152:DI])

Please note REG_EQUALS in (insn 39) and (insn 583).

Next, cse1 does its job and figures that flow jumps to L579 only when [r152:DI] is zero. This zero is also propagated to r82 in (insn 583):

tree-ssa-loop-im.i.150r.cse1:

;; Function determine_max_movement (determine_max_movement)

...

L34:
   35 NOTE_INSN_BASIC_BLOCK
   36 [r73:DI]=r69:DI
   37 r155:SI=[r152:DI]
   38 r154:QI#0=zero_extract(r155:SI#0,0x8,0x0)
   39 r78:DI=zero_extend(r154:QI)
      REG_EQUAL: zero_extend([r152:DI])
   40 pc={(r78:DI==0x0)?L579:pc}
      REG_BR_PROB: 0x1388
...

L571:
  572 NOTE_INSN_BASIC_BLOCK
  573 r351:SI=r155:SI
  574 r350:QI#0=zero_extract(r155:SI#0,0x8,0x0)
  575 r82:DI=r78:DI
      REG_EQUAL: zero_extend([r152:DI])
L579:
  580 NOTE_INSN_BASIC_BLOCK
  581 r353:SI=r155:SI
  582 r352:QI#0=zero_extract(r155:SI#0,0x8,0x0)
  583 r82:DI=0x0
      REG_EQUAL: zero_extend([r152:DI])

After all passes, we find following in cprop3 dump:

tree-ssa-loop-im.i.168r.cprop3:

;; Function determine_max_movement (determine_max_movement)

...

L34:
   35 NOTE_INSN_BASIC_BLOCK
   36 [r73:DI]=r69:DI
      REG_DEAD: r69:DI
   37 r355:SI=[r152:DI]
   38 r154:QI#0=zero_extract(r355:SI#0,0x8,0x0)
   39 r78:DI=zero_extend(r154:QI)
      REG_DEAD: r154:QI
      REG_EQUAL: zero_extend([r152:DI])
  583 r82:DI=0x0
      REG_EQUAL: zero_extend([r152:DI])
   40 pc={(r78:DI==0x0)?L230:pc}
      REG_BR_PROB: 0x1388
...

L230:
  231 NOTE_INSN_BASIC_BLOCK
  232 r104:DI=sign_extend([r73:DI+0x18])
  233 r207:DI=r82:DI==0x1
  633 r356:DI=leu(r82:DI,0x5)
  234 pc={(r207:DI==0x0)?L241:pc}
      REG_DEAD: r207:DI
      REG_BR_PROB: 0x1ae8
  235 NOTE_INSN_BASIC_BLOCK
  236 r209:DI=`compiler_params'
  237 r208:DI=[r209:DI]
      REG_DEAD: r209:DI
      REG_EQUAL: [`compiler_params']
  238 r107:DI=sign_extend([r208:DI+0x748])
      REG_DEAD: r208:DI
...

since both, r78 and r82 equal to the same location, cse2 wisely determines that both are equal to zero and removes all blocks from the conditional jump onward. Things go down the drain from here.

tree-ssa-loop-im.i.169r.cse2:

...

L34:
   35 NOTE_INSN_BASIC_BLOCK
   36 [r73:DI]=r69:DI
      REG_DEAD: r69:DI
   37 r355:SI=[r152:DI]
   38 r154:QI#0=zero_extract(r355:SI#0,0x8,0x0)
  583 r82:DI=0x0
      REG_EQUAL: zero_extend([r152:DI])
  232 r104:DI=sign_extend([r73:DI+0x18])
  233 r207:DI=r82:DI==0x1
  633 r356:DI=leu(r82:DI,0x5)
  234 pc={(r207:DI==0x0)?L241:pc}
      REG_DEAD: r207:DI
      REG_BR_PROB: 0x1ae8
  235 NOTE_INSN_BASIC_BLOCK
  236 r209:DI=`compiler_params'
  237 r208:DI=[r209:DI]
      REG_DEAD: r209:DI
      REG_EQUAL: [`compiler_params']
  238 r107:DI=sign_extend([r208:DI+0x748])
      REG_DEAD: r208:DI
...

So, it looks to me, that when gcc figures a constant in one arm of IF expression, it should either:

a) remove REG_EQUAL expr when constant is propagated, since this constant depends on the location of the insn

b) remove REG_EQUAL when insn is hoisted, for the same reason.

This bug is similar (or even a duplicate of) PR21767. ifcvt.c has a fixup code for cases like this, grep ifcvt.c for:

      /* PR 21767: When moving insns above a conditional branch, REG_EQUAL
	 notes might become invalid.  */

So, let's analyse why this fixup doesn't trigger for attached testcase.

Following patch changes the fix from PR21767 to remove REG_EQUAL notes from all moved instructions, not only from ones that have non-function-invariant sources.

--cut here--
Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 155681)
+++ ifcvt.c	(working copy)
@@ -4079,15 +4079,12 @@ dead_or_predicable (basic_block test_bb,
       insn = head;
       do
 	{
-	  rtx note, set;
+	  rtx note;
 
 	  if (! INSN_P (insn))
 	    continue;
 	  note = find_reg_note (insn, REG_EQUAL, NULL_RTX);
-	  if (! note)
-	    continue;
-	  set = single_set (insn);
-	  if (!set || !function_invariant_p (SET_SRC (set)))
+	  if (note)
 	    remove_note (insn, note);
 	} while (insn != end && (insn = NEXT_INSN (insn)));
 
--cut here--

Matthias, can you please test this patch if it fixes bootstrap for you?

> Following patch changes the fix from PR21767 to remove REG_EQUAL notes from all
> moved instructions, not only from ones that have non-function-invariant
> sources.

This seems like a tad aggressive.  Why not remove the REG_EQUAL note after the constant propagation has happened instead?

(In reply to comment #19)
> > Following patch changes the fix from PR21767 to remove REG_EQUAL notes from all
> > moved instructions, not only from ones that have non-function-invariant
> > sources.
> 
> This seems like a tad aggressive.  Why not remove the REG_EQUAL note after the
> constant propagation has happened instead?

Because at the point of propagation, propagated constant _is_ equal to whatever REG_EQUAL says. Removing this note at the point of propagation would IMO disable much more optimization opportunities.

BTW: This fixup happens in very rare occasions. Although the loop looks scary, it usually processes very small BBs (I didn't found the case where more than one assignment was moved at the top of the test BB.

> Because at the point of propagation, propagated constant _is_ equal to
> whatever REG_EQUAL says. Removing this note at the point of propagation
> would IMO disable much more optimization opportunities.

What kind of opportunities exactly?  The insn is more precise that the note.

> BTW: This fixup happens in very rare occasions. Although the loop looks scary,
> it usually processes very small BBs (I didn't found the case where more than
> one assignment was moved at the top of the test BB.

Yes, but removing REG_EQUAL notes pointing to constants seems a bad idea.

(In reply to comment #21)
> > Because at the point of propagation, propagated constant _is_ equal to
> > whatever REG_EQUAL says. Removing this note at the point of propagation
> > would IMO disable much more optimization opportunities.
> 
> What kind of opportunities exactly?  The insn is more precise that the note.

I'm thinking about the same situation with cse2, where constant assignment (with its REG_EQUAL note) would match another assignment with the same REG_EQUAL note. cse2 can equal this other assignment (through matching REG_EQUAL notes) to the constant - actually the same thing that happens in our problematic case. Since this transformation would happen in the same BB, it would be perfectly valid - and disabled by removing REG_EQUAL note on constant.
> 
> > BTW: This fixup happens in very rare occasions. Although the loop looks scary,
> > it usually processes very small BBs (I didn't found the case where more than
> > one assignment was moved at the top of the test BB.
> 
> Yes, but removing REG_EQUAL notes pointing to constants seems a bad idea.

Sure, but after the assigment was moved, REG_EQUAL points to invalid assignment, see this part from the dumps:

   39 r78:DI=zero_extend(r154:QI)
      REG_DEAD: r154:QI
      REG_EQUAL: zero_extend([r152:DI])
  583 r82:DI=0x0                                  << here
      REG_EQUAL: zero_extend([r152:DI])
   40 pc={(r78:DI==0x0)?L230:pc}
      REG_BR_PROB: 0x1388

The proposed change removes REG_EQUAL note only on moved insn, (insn 538) in our case.

> I'm thinking about the same situation with cse2, where constant assignment
> (with its REG_EQUAL note) would match another assignment with the same
> REG_EQUAL note. cse2 can equal this other assignment (through matching
> REG_EQUAL notes) to the constant - actually the same thing that happens in our
> problematic case. Since this transformation would happen in the same BB, it
> would be perfectly valid - and disabled by removing REG_EQUAL note on 
> constant.

This mechanism very likely results in a bug if the 2 insns are not originally in the same BB, like in the case at hand.  So, assuming they are originally in the same BB and carry the same REG_EQUAL note, the constant will be propagated in both insns.

> Sure, but after the assigment was moved, REG_EQUAL points to invalid
> assignment, see this part from the dumps:
> 
>    39 r78:DI=zero_extend(r154:QI)
>       REG_DEAD: r154:QI
>       REG_EQUAL: zero_extend([r152:DI])
>   583 r82:DI=0x0                                  << here
>       REG_EQUAL: zero_extend([r152:DI])
>    40 pc={(r78:DI==0x0)?L230:pc}
>       REG_BR_PROB: 0x1388
> 
> The proposed change removes REG_EQUAL note only on moved insn, (insn 538) in
> our case.

That's too aggressive in the general case, no need to remove a REG_EQUAL note pointing to a constant if the SRC is also function_invariant_p.  An acceptable
compromise could be to remove the note only if its content is also not itself function_invariant_p.

(In reply to comment #23)

> > The proposed change removes REG_EQUAL note only on moved insn, (insn 538) in
> > our case.
> 
> That's too aggressive in the general case, no need to remove a REG_EQUAL note
> pointing to a constant if the SRC is also function_invariant_p.  An acceptable
> compromise could be to remove the note only if its content is also not itself
> function_invariant_p.

Thanks, I will amend the patch as you suggested and send the patch to gcc-patches@.

New patch revision in testing:

--cut here--
Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 155686)
+++ ifcvt.c	(working copy)
@@ -4087,7 +4087,8 @@ dead_or_predicable (basic_block test_bb,
 	  if (! note)
 	    continue;
 	  set = single_set (insn);
-	  if (!set || !function_invariant_p (SET_SRC (set)))
+	  if ((set && !function_invariant_p (SET_SRC (set)))
+	      || !function_invariant_p (XEXP (note, 0)))
 	    remove_note (insn, note);
 	} while (insn != end && (insn = NEXT_INSN (insn)));
 
--cut here--

Oops, brain dump error. This is correct:

Index: ifcvt.c
===================================================================
--- ifcvt.c	(revision 155686)
+++ ifcvt.c	(working copy)
@@ -4087,7 +4087,8 @@ dead_or_predicable (basic_block test_bb,
 	  if (! note)
 	    continue;
 	  set = single_set (insn);
-	  if (!set || !function_invariant_p (SET_SRC (set)))
+	  if (!set || !function_invariant_p (SET_SRC (set))
+	      || !function_invariant_p (XEXP (note, 0)))
 	    remove_note (insn, note);
 	} while (insn != end && (insn = NEXT_INSN (insn)));
 

Patch at http://gcc.gnu.org/ml/gcc-patches/2010-01/msg00318.html .

the bootstrap succeeds with the patch from comment #18 applied, test results at
http://gcc.gnu.org/ml/gcc-testresults/2010-01/msg00633.html

  Matthias

Subject: Bug 42511

Author: uros
Date: Thu Jan  7 13:02:34 2010
New Revision: 155691

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155691
Log:
	PR target/42511
	* ifcvt.c (dead_or_predicable): Also remove REG_EQUAL note when
	note itself is not function_invariant_p.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ifcvt.c

Fixed.

Subject: Bug 42511

Author: uros
Date: Thu Jan  7 14:59:59 2010
New Revision: 155693

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155693
Log:
	* ifcvt.c (if_convert): Output slim multiple dumps with TDF_SLIM.

	PR target/42511
	* ifcvt.c (dead_or_predicable): Also remove REG_EQUAL note when
	note itself is not function_invariant_p.


Modified:
    branches/gcc-4_4-branch/gcc/ChangeLog
    branches/gcc-4_4-branch/gcc/ifcvt.c

Subject: Bug 42511

Author: uros
Date: Thu Jan  7 17:31:43 2010
New Revision: 155698

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155698
Log:
	* ifcvt.c (if_convert): Output slim multiple dumps with TDF_SLIM.

	PR target/42511
	* ifcvt.c (dead_or_predicable): Also remove REG_EQUAL note when
	note itself is not function_invariant_p.


Modified:
    branches/gcc-4_3-branch/gcc/ChangeLog
    branches/gcc-4_3-branch/gcc/ifcvt.c

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