DAGCombiner::MergeConsecutiveStores

Project Infrastructure LLVM Dev List Archives
1

Hi,

I'm quite puzzled by a little bit of code in the DAGCombiner where it merges loads in MergeConsecutiveStores.

Two 16bit loads have been merged to one 32bit load, and two 16bit stores have been combined to one 32bit store.

And then the code goes like this:

   // Replace one of the loads with the new load.
   LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
   DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                 SDValue(NewLoad.getNode(), 1));

   // Remove the rest of the load chains.
   for (unsigned i = 1; i < NumElem ; ++i) {
     // Replace all chain users of the old load nodes with the chain of the new
     // load node.
     LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
     DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1), Ld->getChain());
   }

And here I can't understand why we should replace "the rest" of the load chains with the loads' getChain(). Why should one load be treated in one way, and the rest in some other way?

I.e. if there is a chain dependendy to a load, we replace that with the load's chain. Why not replace dependencies to the old loads with dependencies to the new load, just like we do for the first load in the code above.

This code was rewritten to how it looks today in a commit 2012-10-03:

" Fix a cycle in the DAG. In this code we replace multiple loads
      with a single load and
      multiple stores with a single load. We create the wide loads and
      stores (and their chains)
      before we remove the scalar loads and stores and fix the DAG chain.
      We attempted to merge loads with a different chain. When that
      happened, the assumption that it is safe to RAUW
      broke and a cycle was introduced.

     git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@165148 91177308-0d34-0410-b5e6-96231b3b80d8
"

The testcase in that commit works even if I treat all loads the same and replace them all with SDValue(NewLoad.getNode(), 1)

Anyone knows this code and why it looks the way it does?

Regards,
Mikael

2

Hi,

I'm quite puzzled by a little bit of code in the DAGCombiner where it merges loads in MergeConsecutiveStores.

Two 16bit loads have been merged to one 32bit load, and two 16bit stores have been combined to one 32bit store.

And then the code goes like this:

// Replace one of the loads with the new load.
LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                               SDValue(NewLoad.getNode(), 1));

At this point the Chain that the next Load gets has been updated to the new chain, ok?

// Remove the rest of the load chains.
for (unsigned i = 1; i < NumElem ; ++i) {
   // Replace all chain users of the old load nodes with the chain of the new
   // load node.
   LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
   DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1), Ld->getChain());

Ld->getChain() return the Chain that is passed as an input to the Load, it has been replaced earlier.

Let say your original loads are chained this way A->B->C. The new load is A’. Before the loop, A has been replaced with A’:

A’->B->C

Then the first iteration of the loop process B and replace its users with the chain it has as an input:

A’->C

And so on.

I hope it makes sense.

Mehdi

3

Hi Mehdi,

Thanks for your answer!

My case is slightly different from the one you described though, see below.

Hi,

I'm quite puzzled by a little bit of code in the DAGCombiner where it merges loads in MergeConsecutiveStores.

Two 16bit loads have been merged to one 32bit load, and two 16bit stores have been combined to one 32bit store.

And then the code goes like this:

  // Replace one of the loads with the new load.
  LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
  DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
                                SDValue(NewLoad.getNode(), 1));

At this point the Chain that the next Load gets has been updated to the new chain, ok?

  // Remove the rest of the load chains.
  for (unsigned i = 1; i < NumElem ; ++i) {
    // Replace all chain users of the old load nodes with the chain of the new
    // load node.
    LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
    DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1), Ld->getChain());

Ld->getChain() return the Chain that is passed as an input to the Load, it has been replaced earlier.

Let say your original loads are chained this way A->B->C. The new load is A’. Before the loop, A has been replaced with A’:

The original code in my case doesn't have the loads "in sequence" like that, instead they are in parallel, tied together with a TokenFactor, and in addition to that, there is another chain dependency to one of the loads.

I have loads A and B (merged into A'), token factor C (depending on A and B) and a store, D, depending on B:

A B
  \ / \
   \ / \
     C D

The first piece of code replaces the chain in C to the new load A'.

However, the loop then handles B, and when doing that it updates D so it now has a chain dependency to B's chain, which happens to be the entry node. And suddenly one dependency is removed and the code can be rescheduled so the store D is done prior to the load B which it shouldn't.

Regards,
Mikael

A’->B->C

Ok.

4

From: "Mikael Holmén" <mikael.holmen@ericsson.com>
To: "Mehdi Amini" <mehdi.amini@apple.com>
Cc: llvmdev@cs.uiuc.edu
Sent: Monday, February 16, 2015 4:21:12 AM
Subject: Re: [LLVMdev] DAGCombiner::MergeConsecutiveStores

Hi Mehdi,

Thanks for your answer!

My case is slightly different from the one you described though, see
below.

>
>>
>> Hi,
>>
>> I'm quite puzzled by a little bit of code in the DAGCombiner where
>> it merges loads in MergeConsecutiveStores.
>>
>> Two 16bit loads have been merged to one 32bit load, and two 16bit
>> stores have been combined to one 32bit store.
>>
>> And then the code goes like this:
>>
>>
>> // Replace one of the loads with the new load.
>> LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[0].MemNode);
>> DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1),
>> SDValue(NewLoad.getNode(), 1));
>
>
> At this point the Chain that the next Load gets has been updated to
> the new chain, ok?
>
>>
>> // Remove the rest of the load chains.
>> for (unsigned i = 1; i < NumElem ; ++i) {
>> // Replace all chain users of the old load nodes with the
>> chain of the new
>> // load node.
>> LoadSDNode *Ld = cast<LoadSDNode>(LoadNodes[i].MemNode);
>> DAG.ReplaceAllUsesOfValueWith(SDValue(Ld, 1), Ld->getChain());
>
> Ld->getChain() return the Chain that is passed as an input to the
> Load, it has been replaced earlier.
>
> Let say your original loads are chained this way A->B->C. The new
> load is A’. Before the loop, A has been replaced with A’:

The original code in my case doesn't have the loads "in sequence"
like
that, instead they are in parallel, tied together with a TokenFactor,
and in addition to that, there is another chain dependency to one of
the
loads.

I have loads A and B (merged into A'), token factor C (depending on A
and B) and a store, D, depending on B:

A B
  \ / \
   \ / \
     C D

The first piece of code replaces the chain in C to the new load A'.

However, the loop then handles B, and when doing that it updates D so
it
now has a chain dependency to B's chain, which happens to be the
entry
node. And suddenly one dependency is removed and the code can be
rescheduled so the store D is done prior to the load B which it
shouldn't.

Indeed, this seems like a bug.

-Hal