thr3ads.net - llvm dev - [LLVMdev] DAGCombiner::MergeConsecutiveStores [Feb 2015]

If this information is useful, please help other people find it:
Share via:

Mikael Holmén

2015-Feb-13 13:50 UTC

[LLVMdev] DAGCombiner::MergeConsecutiveStores

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 at 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

Mehdi Amini

2015-Feb-13 15:54 UTC

head link

[LLVMdev] DAGCombiner::MergeConsecutiveStores

> On Feb 13, 2015, at 5:50 AM, Mikael Holmén <mikael.holmen at
ericsson.com> wrote:
> 
> 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


>  }
> 
> 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 at 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

Mikael Holmén

2015-Feb-16 10:21 UTC

head link

[LLVMdev] DAGCombiner::MergeConsecutiveStores

Hi Mehdi,

Thanks for your answer!

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

On 02/13/2015 04:54 PM, Mehdi Amini wrote:>
>> On Feb 13, 2015, at 5:50 AM, Mikael Holmén <mikael.holmen at
ericsson.com> wrote:
>>
>> 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.
>
> 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
>
>
>
>>   }
>>
>> 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 at 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
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>

Possibly Parallel Threads

Search for more possibly parallel threads

llvm dev - Feb 2015 - [LLVMdev] DAGCombiner::MergeConsecutiveStores

[LLVMdev] DAGCombiner::MergeConsecutiveStores

[LLVMdev] DAGCombiner::MergeConsecutiveStores

[LLVMdev] DAGCombiner::MergeConsecutiveStores

Possibly Parallel Threads