llvm dev - Feb 2010 - [LLVMdev] SelectionDAG legality: isel creating cycles

I've run into a situation in isel where it seems like the selector is 
generating a cycle in the DAG.

I have something like this:

0x215f140: v2f64 = llvm.x86.sse2.min.sd 0x215efd0, 0x21606d0, 0x215eb80
[0] 0x215efd0: i64 = Constant <647>
[0] 0x21606d0: v2f64 = scalar_to_vector 0x213b8f0
  [0] 0x213b8f0: f64,ch = load 0x213b780, 0x213aa90, 0x213b610
<0x2113690:0>
alignment=8
    [0] 0x213b780: ch = Prefetch 0x213aee0:1, 0x213b1c0, 0x213b330, 0x213b4a0
      [1] 0x213aee0: f64,ch = load 0x213a720, 0x213ac00, 0x213b610 
<0x215ace8:0> alignment=8
        [0] 0x213a720: ch = EntryToken 
        [0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
          [0] 0x213a720: ch = EntryToken 
          [0] 0x213ad70: i64 = Register  #1024
        [0] 0x213b610: i64 = undef 
      [0] 0x213b1c0: i64 = add 0x213ac00, 0x213b050
        [0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
          [0] 0x213a720: ch = EntryToken 
          [0] 0x213ad70: i64 = Register  #1024
        [0] 0x213b050: i64 = Constant <136>
      [0] 0x213b330: i32 = Constant <0>
      [0] 0x213b4a0: i32 = Constant <3>
    [0] 0x213aa90: i64 = Constant <0>
    [0] 0x213b610: i64 = undef 
[0] 0x215eb80: v2f64 = scalar_to_vector 0x213aee0
  [0] 0x213aee0: f64,ch = load 0x213a720, 0x213ac00, 0x213b610
<0x215ace8:0>
alignment=8
    [0] 0x213a720: ch = EntryToken 
    [0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
      [0] 0x213a720: ch = EntryToken 
      [0] 0x213ad70: i64 = Register  #1024
    [0] 0x213b610: i64 = undef 

I added the brackets on output to show which result is being linked to, so the 
prefetch takes the chain output from its controlling load.

When  llvm.x86.sse2.min.sd gets selected, the TableGen-generated code
does this:

  SDNode *ResNode = CurDAG->SelectNodeTo(N.getNode(), Opc0, VT0, MVT::Other, 
Ops0, 6);

0x215f140: v2f64,ch = <<Unknown Machine Node>> 0x21606d0, 0x213ac00,
0x215ffa0, 0x215ea10, 0x215ee60, 0x213a720
[0] 0x21606d0: v2f64 = scalar_to_vector 0x213b8f0
  [0] 0x213b8f0: f64,ch = load 0x213b780, 0x213aa90, 0x213b610
<0x2113690:0>
alignment=8
    [0] 0x213b780: ch = Prefetch 0x213aee0:1, 0x213b1c0, 0x213b330, 0x213b4a0
      [1] 0x213aee0: f64,ch = load 0x213a720, 0x213ac00, 0x213b610 
<0x215ace8:0> alignment=8
        [0] 0x213a720: ch = EntryToken 
        [0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
          [0] 0x213a720: ch = EntryToken 
          [0] 0x213ad70: i64 = Register  #1024
        [0] 0x213b610: i64 = undef 
      [0] 0x213b1c0: i64 = add 0x213ac00, 0x213b050
        [0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
          [0] 0x213a720: ch = EntryToken 
          [0] 0x213ad70: i64 = Register  #1024
        [0] 0x213b050: i64 = Constant <136>
      [0] 0x213b330: i32 = Constant <0>
      [0] 0x213b4a0: i32 = Constant <3>
    [0] 0x213aa90: i64 = Constant <0>
    [0] 0x213b610: i64 = undef 
[0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
  [0] 0x213a720: ch = EntryToken 
  [0] 0x213ad70: i64 = Register  #1024
[0] 0x215ffa0: i8 = TargetConstant <1>
[0] 0x215ea10: i64 = Register  #0
[0] 0x215ee60: i32 = TargetConstant <0>
[0] 0x213a720: ch = EntryToken 

Ok, so far so good.

Then it does this:

  ReplaceUses(SDValue(CPInChain2.getNode(), 1), SDValue(ResNode, 1));

CPInChain2 is this:

0x213aee0: f64,ch = load 0x213a720, 0x213ac00, 0x213b610 <0x215ace8:0> 
alignment=8
[0] 0x213a720: ch = EntryToken 
[0] 0x213ac00: i64,ch = CopyFromReg 0x213a720, 0x213ad70
  [0] 0x213a720: ch = EntryToken 
  [0] 0x213ad70: i64 = Register  #1024
[0] 0x213b610: i64 = undef 

So it's replacing the load/memory chain output of the min intrinsic with the
chain output of the min intrinsic.  Ok, that seems right.  But one of the 
users of that chain output is the prefetch.  So now the prefetch will get a
chain input pointing to the chain output of the min intrinsic, creating a 
cycle.

The fundamental issue is that the DAG originally looked like this:

MIN
  LOAD B
    PREFETCH
      Chain from LOAD A
  LOAD A

Now the chain will come from the MIN and we'll have:

MIN
  LOAD B
    PREFETCH
      Chain from MIN
  X86AddressOperands

Is such a thing legal?  I wouldn't expect so since it's cycle. 
Eventually we
blow up in topological sort since it can't find one.

What's the right way to handle this?

                                              -Dave

On Monday 22 February 2010 10:31:24 David Greene wrote:
> The fundamental issue is that the DAG originally looked like this:
>
> MIN
>   LOAD B
>     PREFETCH
>       Chain from LOAD A
>   LOAD A
Actually, it looked like this:

MIN
  LOAD B
    Chain from PREFETCH
      Chain from LOAD A
    NULL
  LOAD A
    Chain from ENTRY
    Some Addressing

LOAD B is from NULL because this is a bugpoint-reduced testcase, so that's
not
an issue.

Just wanted to clarify in case someone was wondering about this.

                                                 -Dave

On Monday 22 February 2010 10:41:04 David Greene wrote:
> Actually, it looked like this:
>
> MIN
>   LOAD B
>     Chain from PREFETCH
>       Chain from LOAD A
>     NULL
>   LOAD A
>     Chain from ENTRY
>     Some Addressing
>
> LOAD B is from NULL because this is a bugpoint-reduced testcase, so
that's
> not an issue.
I suppose one solution would be to not have LOAD B carry the chain from the 
prefetch.  But SelectionDAGBuilder "automatically" gives the node it 
constructs an input from the current root of the DAG.  At some point the 
prefetch is the root and the next thing to be built is LOAD B, so it gets an
operand pointing to the prefetch.

I'll look at this angle some more.  It seems we should be able to break the
cycle here.

Let me know if I'm on the completely wrong track.  :)

                                               -Dave

Hi David,
> I've run into a situation in isel where it seems like the selector is
> generating a cycle in the DAG.
if you build with expensive checks on (configure with --enable-expensive-checks)
then I think some cycle checking stuff kicks in.  This may help find the moment
when it was introduced.

Ciao,

Duncan.

On Feb 22, 2010, at 8:41 AM, David Greene wrote:
> On Monday 22 February 2010 10:31:24 David Greene wrote:
> 
>> The fundamental issue is that the DAG originally looked like this:
>> 
>> MIN
>>  LOAD B
>>    PREFETCH
>>      Chain from LOAD A
>>  LOAD A
> 
> Actually, it looked like this:
> 
> MIN
>  LOAD B
>    Chain from PREFETCH
>      Chain from LOAD A
>    NULL
>  LOAD A
>    Chain from ENTRY
>    Some Addressing
> 
> LOAD B is from NULL because this is a bugpoint-reduced testcase, so
that's not
> an issue.
> 
> Just wanted to clarify in case someone was wondering about this.
I'm currently working in this area.  What pattern is causing the cycle?  Can
I get a testcase?

-Chris