[LLVMdev] Possible SelectionDAG Bug

[Dan Gohman]

On Mar 3, 2010, at 7:25 AM, David Greene wrote:

> On Tuesday 02 March 2010 18:24:42 David Greene wrote:
>> On Tuesday 02 March 2010 17:58:57 David Greene wrote:
>>>> way to confirm this right now. Does it fix the bug you're seeing?
>>> 
>>> Yep, it fixed it.
>> 
>> Hmm...curiously, not all.  More tomorrow.
> 
> Ah, missed a spot in 2.5, which has a few more RAUW implementations.
> I think we're good.

Ok. Are you able to produce a testcase?  Does it depend on custom changes?
Where does the failure happen (legalize, dagcombine, selection, etc.)?

The interesting case happens when the "++UI;" code in the patch gets
executed, so you could put a breakpoint there and look at the graph at
that point, or insert an abort and use bugpoint.

Anyway, here's the theoretical situation I imagined:

A is a user of T. B, C, and D are all users of F. C is also a user of B,
and D is also a user of A. A and B have the same opcode. C and D have the
same opcode.

  F   T
// \  |
|| |  |
|| B  A
|\ / /
\ C /
 \  |
  \ |
   \|
    D

RAUW(F, T) is called. B is first on F's use list. C is the next use,
so the use iterator is incremented to point to C. B's use is updated.

  F   T
//   /|
||  / |
|| B  A
|\ / /
\ C /
 \  |
  \ |
   \|
    D

B would now be identical to A, so RAUW(B, A) gets called and B is
deleted. C was a user of B so it now becomes a user of A.

  F   T
//    |
||    |
||  __A
|\ / /
\ C /
 \  |
  \ |
   \|
    D

That would make C identical to D, so RAUW(C, D) gets called and C is
deleted.

  F   T
/     |
|     |
|     A
|    /
\   /
 \  |
  \ |
   \|
    D

CSE and recursive RAUW are now done, so control transfers back to
the original RAUW call. C was where the the first RAUW call's
iterator was pointing, and it's now deleted, so that iterator is
now invalid.

Dan