llvm dev - May 2013 - [LLVMdev] [PATCH] Minor fix to StackColoring to avoid needlessly clearing mem operands.

The following code snippet taken from StackColoring::remapInstructions
clears a mem operand if it can't guarantee whether the memoperand's
underlying value aliases with the merged allocas:

// Update the MachineMemOperand to use the new alloca.
 522       for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
....
         // Climb up and find the original alloca.
 532         V = GetUnderlyingObject(V);
 533         // If we did not find one, or if the one that we found is not
in our
 534         // map, then move on.
 535         if (!V || !isa<AllocaInst>(V)) {
 536           // Clear mem operand since we don't know for sure that it
doesn't
 537           // alias a merged alloca.
 538           MMO->setValue(0);
 539           continue;
 540         }

The attached patch makes the code above less conservative. It avoids
clearing a mem operand if its underlying value is a PseudoSourceValue and
PseudoSourceValue::isConstant returns true. This enables MachineLICM to
hoist loads from GOT out of a loop (see test case in
stackcoloring-test.patch).

Please review.

Question: Why does it need to clear a mem operand if the underlying object
is not an AllocaInst? I am not sure if I understand the reason for this.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130508/1321c612/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stackcoloring.patch
Type: application/octet-stream
Size: 917 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130508/1321c612/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stackcoloring-test.patch
Type: application/octet-stream
Size: 1427 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130508/1321c612/attachment-0001.obj>

Hi Akira, did anything happen with this patch?

Ciao, Duncan.

On 09/05/13 04:04, Akira Hatanaka wrote:
> The following code snippet taken from StackColoring::remapInstructions
clears a
> mem operand if it can't guarantee whether the memoperand's
underlying value
> aliases with the merged allocas:
>
> // Update the MachineMemOperand to use the new alloca.
>   522       for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
> ....
>           // Climb up and find the original alloca.
>   532         V = GetUnderlyingObject(V);
>   533         // If we did not find one, or if the one that we found is not
in our
>   534         // map, then move on.
>   535         if (!V || !isa<AllocaInst>(V)) {
>   536           // Clear mem operand since we don't know for sure that
it doesn't
>   537           // alias a merged alloca.
>   538           MMO->setValue(0);
>   539           continue;
>   540         }
>
> The attached patch makes the code above less conservative. It avoids
clearing a
> mem operand if its underlying value is a PseudoSourceValue and
> PseudoSourceValue::isConstant returns true. This enables MachineLICM to
hoist
> loads from GOT out of a loop (see test case in stackcoloring-test.patch).
>
> Please review.
>
> Question: Why does it need to clear a mem operand if the underlying object
is
> not an AllocaInst? I am not sure if I understand the reason for this.
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

Hi Duncan,

No, it hasn't been reviewed yet.


On Mon, May 13, 2013 at 8:50 AM, Duncan Sands <baldrick at free.fr> wrote:
> Hi Akira, did anything happen with this patch?
>
> Ciao, Duncan.
>
>
> On 09/05/13 04:04, Akira Hatanaka wrote:
>
>> The following code snippet taken from
StackColoring::**remapInstructions
>> clears a
>> mem operand if it can't guarantee whether the memoperand's
underlying
>> value
>> aliases with the merged allocas:
>>
>> // Update the MachineMemOperand to use the new alloca.
>>   522       for (MachineInstr::mmo_iterator MM =
I->memoperands_begin(),
>> ....
>>           // Climb up and find the original alloca.
>>   532         V = GetUnderlyingObject(V);
>>   533         // If we did not find one, or if the one that we found is
>> not in our
>>   534         // map, then move on.
>>   535         if (!V || !isa<AllocaInst>(V)) {
>>   536           // Clear mem operand since we don't know for sure
that it
>> doesn't
>>   537           // alias a merged alloca.
>>   538           MMO->setValue(0);
>>   539           continue;
>>   540         }
>>
>> The attached patch makes the code above less conservative. It avoids
>> clearing a
>> mem operand if its underlying value is a PseudoSourceValue and
>> PseudoSourceValue::isConstant returns true. This enables MachineLICM to
>> hoist
>> loads from GOT out of a loop (see test case in
stackcoloring-test.patch).
>>
>> Please review.
>>
>> Question: Why does it need to clear a mem operand if the underlying
>> object is
>> not an AllocaInst? I am not sure if I understand the reason for this.
>>
>>
>>
>> ______________________________**_________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>
http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>>
>>
> ______________________________**_________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>
http://lists.cs.uiuc.edu/**mailman/listinfo/llvmdev<http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/95778804/attachment.html>

This is the email I sent last week.

---------- Forwarded message ----------
From: Akira Hatanaka <ahatanak at gmail.com>
Date: Wed, May 8, 2013 at 7:04 PM
Subject: [PATCH] Minor fix to StackColoring to avoid needlessly clearing
mem operands.
To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>


The following code snippet taken from StackColoring::remapInstructions
clears a mem operand if it can't guarantee whether the memoperand's
underlying value aliases with the merged allocas:

// Update the MachineMemOperand to use the new alloca.
 522       for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
....
         // Climb up and find the original alloca.
 532         V = GetUnderlyingObject(V);
 533         // If we did not find one, or if the one that we found is not
in our
 534         // map, then move on.
 535         if (!V || !isa<AllocaInst>(V)) {
 536           // Clear mem operand since we don't know for sure that it
doesn't
 537           // alias a merged alloca.
 538           MMO->setValue(0);
 539           continue;
 540         }

The attached patch makes the code above less conservative. It avoids
clearing a mem operand if its underlying value is a PseudoSourceValue and
PseudoSourceValue::isConstant returns true. This enables MachineLICM to
hoist loads from GOT out of a loop (see test case in
stackcoloring-test.patch).

Please review.

Question: Why does it need to clear a mem operand if the underlying object
is not an AllocaInst? I am not sure if I understand the reason for this.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/0d4bac7a/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stackcoloring.patch
Type: application/octet-stream
Size: 917 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/0d4bac7a/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: stackcoloring-test.patch
Type: application/octet-stream
Size: 1427 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/0d4bac7a/attachment-0001.obj>

The patch LGTM.  The StackColoring patch is still too conservative and I am
consulting with Jakob and Andy about possible solutions.

On May 13, 2013, at 10:33 AM, Akira Hatanaka <ahatanak at gmail.com>
wrote:
> This is the email I sent last week.
> 
> ---------- Forwarded message ----------
> From: Akira Hatanaka <ahatanak at gmail.com>
> Date: Wed, May 8, 2013 at 7:04 PM
> Subject: [PATCH] Minor fix to StackColoring to avoid needlessly clearing
mem operands.
> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
> 
> 
> The following code snippet taken from StackColoring::remapInstructions
clears a mem operand if it can't guarantee whether the memoperand's
underlying value aliases with the merged allocas:
> 
> // Update the MachineMemOperand to use the new alloca.
>  522       for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
> ....
>          // Climb up and find the original alloca.
>  532         V = GetUnderlyingObject(V);
>  533         // If we did not find one, or if the one that we found is not
in our
>  534         // map, then move on.
>  535         if (!V || !isa<AllocaInst>(V)) {
>  536           // Clear mem operand since we don't know for sure that
it doesn't
>  537           // alias a merged alloca.
>  538           MMO->setValue(0);
>  539           continue;
>  540         }
> 
> The attached patch makes the code above less conservative. It avoids
clearing a mem operand if its underlying value is a PseudoSourceValue and
PseudoSourceValue::isConstant returns true. This enables MachineLICM to hoist
loads from GOT out of a loop (see test case in stackcoloring-test.patch).
> 
> Please review.
> 
> Question: Why does it need to clear a mem operand if the underlying object
is not an AllocaInst? I am not sure if I understand the reason for this.
> 
> 
>
<stackcoloring.patch><stackcoloring-test.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/3d29da54/attachment.html>

On May 13, 2013, at 10:33 AM, Akira Hatanaka <ahatanak at gmail.com>
wrote:
> This is the email I sent last week.
> 
> ---------- Forwarded message ----------
> From: Akira Hatanaka <ahatanak at gmail.com>
> Date: Wed, May 8, 2013 at 7:04 PM
> Subject: [PATCH] Minor fix to StackColoring to avoid needlessly clearing
mem operands.
> To: LLVM Developers Mailing List <llvmdev at cs.uiuc.edu>
> 
> 
> The following code snippet taken from StackColoring::remapInstructions
clears a mem operand if it can't guarantee whether the memoperand's
underlying value aliases with the merged allocas:
> 
> // Update the MachineMemOperand to use the new alloca.
>  522       for (MachineInstr::mmo_iterator MM = I->memoperands_begin(),
> ....
>          // Climb up and find the original alloca.
>  532         V = GetUnderlyingObject(V);
>  533         // If we did not find one, or if the one that we found is not
in our
>  534         // map, then move on.
>  535         if (!V || !isa<AllocaInst>(V)) {
>  536           // Clear mem operand since we don't know for sure that
it doesn't
>  537           // alias a merged alloca.
>  538           MMO->setValue(0);
>  539           continue;
>  540         }
> 
> The attached patch makes the code above less conservative. It avoids
clearing a mem operand if its underlying value is a PseudoSourceValue and
PseudoSourceValue::isConstant returns true. This enables MachineLICM to hoist
loads from GOT out of a loop (see test case in stackcoloring-test.patch).
> 
> Please review.
> 
> Question: Why does it need to clear a mem operand if the underlying object
is not an AllocaInst? I am not sure if I understand the reason for this.

See llvm.org/pr14090 and test/CodeGen/X86/pr14090.ll.

The fix is super-conservative. An optimization would be to guarantee that
StackColoring and ScheduleDAGInstrs use exactly the same API for underlying
objects. Even with that fix though, the alias info could be incorrect because we
remap field accesses to the alloca base, so base-offset disambiguation could
fail.

The only way to make this safe in general for IR-level alias analysis is to
transform the IR, which would naturally be done with an IR pass.

-Andy
> 
> 
>
<stackcoloring.patch><stackcoloring-test.patch>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130513/b52a8e17/attachment.html>