llvm dev - May 2020 - Unexpected behavior found in Stack Coloring pass, need clarification

Hello,

I have come across an unusual behavior where instruction domination rule is
violated "Instruction does not dominate all its uses." It concerns
with
StackColoring pass present at llvm/lib/CodeGen/StackColoring.cpp. I am
reaching out to the LLVM community to help me understand the cause of this
issue and the working of the pass.

The IR produced at the end of the pass seems to be malformed..
Looking at transformed IR, it is clear that use of %0 precedes the
definition of %0. This is why I feel it is a bug. I would like to confirm
with the community if this is an unexpected behavior and if so, what could
be the possible way of fixing this issue. I shall be happy to submit a
patch.

Also, please help me understand on what basis the pointer to be replaced is
picked? In other words, why is %tmp is preferred over %ref.tmp?
If they allocate the same number of bytes, why is %ref.tmp not given
preference as it comes first in the order?


*Malformed IR at the end of Stack Coloring pass:*entry:
    %a = alloca %struct.e, align 1
    %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
    %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to %class.d*
    ...
    %tmp = alloca %"struct.e::f", align 8
    %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x
float> }*
    ...
    ret void

*Steps to reproduce:*

For debugging purposes, I have modified last few lines of
runOnMachineFunction(..) method present in the StackColoring.cpp file. The
original source can be found here:
https://llvm.org/doxygen/StackColoring_8cpp_source.html

    bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
    ...
    ...
    remapInstructions(SlotRemap);
+   bool markerCount = removeAllMarkers();
+   DenseMap<int, int>::iterator itr = SlotRemap.begin();
+   const AllocaInst *dInst = MFI->getObjectAllocation(itr->first);
+   LLVM_DEBUG(dbgs() << "Set break point here to inspect
dInst\n");
+   return markerCount;
  }

I'm using the following test-case to reproduce the issue:

*testcase.cpp*

class d {
  float b[4];
};

d operator-(d);
struct e {
  struct f {
    int *c[4];
  };
  void h(const d &);
};

struct j {
  int temp;
  e::f k();
};
d i;

void g() {
  e a;
  a.h(-i);
  j b;
  b.k();
}

Use the following flag set to debug:

$ gdb --args llvm/build/bin/clang++ -c -w -O2 testcase.cpp

Inside gdb: (set break point at the end of the pass to inspect the basic
block)

(gdb) set follow-fork-mode child
(gdb) b StackColoring.cpp:1301
(gdb) r
(gdb) p dInst->getParent()->dump()

*My findings*

1. Definition of %0 register and use of it are found to be in the same
basic block and the use is preceded by the def.
2. I believe the IR produced is malformed after a call to
remapInstructions(..) method is made. The method removeAllMarkers() does
not modify IR in my knowledge. So it is safe to assume that LLVM IR
produced at the end of the pass is same as the IR after the call to
remapInstructions(..) is made.
3. While executing remapInstructions(..), the uses of %ref.tmp are replaced
with %0 in %tmpcast definition when From-AI->replacesAllUsesWith(Inst) call
is made. This is triggering the bug. It basically grabs the UseList (one of
them being the definition of %tmpcast) and renames all the %ref.tmp uses to
%0.

*Basic Block IR before replaceAllUsesWith method is executed*:

entry:
  %a = alloca %struct.e, align 1
  %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
  %tmpcast = bitcast { <2 x float>, <2 x float> }* %ref.tmp to
%class.d*
  %b = alloca %struct.j, align 4
  %tmp = alloca %"struct.e::f", align 8
  %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x
float>}*
  ...
  ret void

*Basic Block IR after replaceAllUsesWith method is executed:*

entry:
 %a = alloca %struct.e, align 1
 %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
 %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to %class.d*
 %b = alloca %struct.j, align 4
 %tmp = alloca %"struct.e::f", align 8
 %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x
float> }*
 ...
 ret void

I would like to hear what the community has to say about this. Apologies if
formatting is messy. Let me know if something is not clear, I'm happy to
explain and elaborate. Thanks in advance.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200506/e5e6b20e/attachment.html>

Its very unusual that there is a bitcast in the middle of the allocas going
into the StackColoring pass. While not explicitly illegal IR, its unusual.
Allocas are usually grouped together. I suspect the stack coloring pass
isn't handling this well.

It looks like InstCombine created the bitcast and may have made a bad
decision about where to place it.

~Craig


On Tue, May 5, 2020 at 11:10 PM Mohammed Abid Uzair via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> Hello,
>
> I have come across an unusual behavior where instruction domination rule
> is violated "Instruction does not dominate all its uses." It
concerns with
> StackColoring pass present at llvm/lib/CodeGen/StackColoring.cpp. I am
> reaching out to the LLVM community to help me understand the cause of this
> issue and the working of the pass.
>
> The IR produced at the end of the pass seems to be malformed..
> Looking at transformed IR, it is clear that use of %0 precedes the
> definition of %0. This is why I feel it is a bug. I would like to confirm
> with the community if this is an unexpected behavior and if so, what could
> be the possible way of fixing this issue. I shall be happy to submit a
> patch.
>
> Also, please help me understand on what basis the pointer to be replaced
> is picked? In other words, why is %tmp is preferred over %ref.tmp?
> If they allocate the same number of bytes, why is %ref.tmp not given
> preference as it comes first in the order?
>
>
> *Malformed IR at the end of Stack Coloring pass:*entry:
>     %a = alloca %struct.e, align 1
>     %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>     %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to
%class.d*
>     ...
>     %tmp = alloca %"struct.e::f", align 8
>     %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>,
<2 x float> }*
>     ...
>     ret void
>
> *Steps to reproduce:*
>
> For debugging purposes, I have modified last few lines of
> runOnMachineFunction(..) method present in the StackColoring.cpp file.
> The original source can be found here:
> https://llvm.org/doxygen/StackColoring_8cpp_source.html
>
>     bool StackColoring::runOnMachineFunction(MachineFunction &Func) {
>     ...
>     ...
>     remapInstructions(SlotRemap);
> +   bool markerCount = removeAllMarkers();
> +   DenseMap<int, int>::iterator itr = SlotRemap.begin();
> +   const AllocaInst *dInst = MFI->getObjectAllocation(itr->first);
> +   LLVM_DEBUG(dbgs() << "Set break point here to inspect
dInst\n");
> +   return markerCount;
>   }
>
> I'm using the following test-case to reproduce the issue:
>
> *testcase.cpp*
>
> class d {
>   float b[4];
> };
>
> d operator-(d);
> struct e {
>   struct f {
>     int *c[4];
>   };
>   void h(const d &);
> };
>
> struct j {
>   int temp;
>   e::f k();
> };
> d i;
>
> void g() {
>   e a;
>   a.h(-i);
>   j b;
>   b.k();
> }
>
> Use the following flag set to debug:
>
> $ gdb --args llvm/build/bin/clang++ -c -w -O2 testcase.cpp
>
> Inside gdb: (set break point at the end of the pass to inspect the basic
> block)
>
> (gdb) set follow-fork-mode child
> (gdb) b StackColoring.cpp:1301
> (gdb) r
> (gdb) p dInst->getParent()->dump()
>
> *My findings*
>
> 1. Definition of %0 register and use of it are found to be in the same
> basic block and the use is preceded by the def.
> 2. I believe the IR produced is malformed after a call to
> remapInstructions(..) method is made. The method removeAllMarkers() does
> not modify IR in my knowledge. So it is safe to assume that LLVM IR
> produced at the end of the pass is same as the IR after the call to
> remapInstructions(..) is made.
> 3. While executing remapInstructions(..), the uses of %ref.tmp are
> replaced with %0 in %tmpcast definition when
> From-AI->replacesAllUsesWith(Inst) call is made. This is triggering the
> bug. It basically grabs the UseList (one of them being the definition of
> %tmpcast) and renames all the %ref.tmp uses to %0.
>
> *Basic Block IR before replaceAllUsesWith method is executed*:
>
> entry:
>
>   %a = alloca %struct.e, align 1
>   %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>   %tmpcast = bitcast { <2 x float>, <2 x float> }* %ref.tmp to
%class.d*
>   %b = alloca %struct.j, align 4
>   %tmp = alloca %"struct.e::f", align 8
>   %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2
x float>}*
>   ...
>   ret void
>
> *Basic Block IR after replaceAllUsesWith method is executed:*
>
> entry:
>  %a = alloca %struct.e, align 1
>  %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>  %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to
%class.d*
>  %b = alloca %struct.j, align 4
>  %tmp = alloca %"struct.e::f", align 8
>  %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2
x float> }*
>  ...
>  ret void
>
> I would like to hear what the community has to say about this. Apologies
> if formatting is messy. Let me know if something is not clear, I'm
happy to
> explain and elaborate. Thanks in advance.
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200505/8500ba07/attachment.html>

Here's a patch for InstCombine. Does this help with the issue?

*--- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp*

*+++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp*

@@ -151,6 +151,15 @@ Instruction
*InstCombiner::PromoteCastOfAllocation(BitCastInst &CI,

   if (!AI.hasOneUse()) {

     // New is the allocation instruction, pointer typed. AI is the original

     // allocation instruction, also pointer typed. Thus, cast to use is
BitCast.

+

+    // Scan to the end of the allocation instructions, to skip over a
block of

+    // allocas if possible.

+    //

+    BasicBlock::iterator It(New);

+    while (isa<AllocaInst>(*It))

+      ++It;

+

+    Builder.SetInsertPoint(&*It);

     Value *NewCast = Builder.CreateBitCast(New, AI.getType(),
"tmpcast");

     replaceInstUsesWith(AI, NewCast);

     eraseInstFromFunction(AI);

~Craig


On Tue, May 5, 2020 at 11:30 PM Craig Topper <craig.topper at gmail.com>
wrote:
> Its very unusual that there is a bitcast in the middle of the allocas
> going into the StackColoring pass. While not explicitly illegal IR, its
> unusual. Allocas are usually grouped together. I suspect the stack coloring
> pass isn't handling this well.
>
> It looks like InstCombine created the bitcast and may have made a bad
> decision about where to place it.
>
> ~Craig
>
>
> On Tue, May 5, 2020 at 11:10 PM Mohammed Abid Uzair via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hello,
>>
>> I have come across an unusual behavior where instruction domination
rule
>> is violated "Instruction does not dominate all its uses." It
concerns with
>> StackColoring pass present at llvm/lib/CodeGen/StackColoring.cpp. I am
>> reaching out to the LLVM community to help me understand the cause of
this
>> issue and the working of the pass.
>>
>> The IR produced at the end of the pass seems to be malformed..
>> Looking at transformed IR, it is clear that use of %0 precedes the
>> definition of %0. This is why I feel it is a bug. I would like to
>> confirm with the community if this is an unexpected behavior and if so,
>> what could be the possible way of fixing this issue. I shall be happy
to
>> submit a patch.
>>
>> Also, please help me understand on what basis the pointer to be
replaced
>> is picked? In other words, why is %tmp is preferred over %ref.tmp?
>> If they allocate the same number of bytes, why is %ref.tmp not given
>> preference as it comes first in the order?
>>
>>
>> *Malformed IR at the end of Stack Coloring pass:*entry:
>>     %a = alloca %struct.e, align 1
>>     %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>>     %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to
%class.d*
>>     ...
>>     %tmp = alloca %"struct.e::f", align 8
>>     %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>,
<2 x float> }*
>>     ...
>>     ret void
>>
>> *Steps to reproduce:*
>>
>> For debugging purposes, I have modified last few lines of
>> runOnMachineFunction(..) method present in the StackColoring.cpp file.
>> The original source can be found here:
>> https://llvm.org/doxygen/StackColoring_8cpp_source.html
>>
>>     bool StackColoring::runOnMachineFunction(MachineFunction &Func)
{
>>     ...
>>     ...
>>     remapInstructions(SlotRemap);
>> +   bool markerCount = removeAllMarkers();
>> +   DenseMap<int, int>::iterator itr = SlotRemap.begin();
>> +   const AllocaInst *dInst =
MFI->getObjectAllocation(itr->first);
>> +   LLVM_DEBUG(dbgs() << "Set break point here to inspect
dInst\n");
>> +   return markerCount;
>>   }
>>
>> I'm using the following test-case to reproduce the issue:
>>
>> *testcase.cpp*
>>
>> class d {
>>   float b[4];
>> };
>>
>> d operator-(d);
>> struct e {
>>   struct f {
>>     int *c[4];
>>   };
>>   void h(const d &);
>> };
>>
>> struct j {
>>   int temp;
>>   e::f k();
>> };
>> d i;
>>
>> void g() {
>>   e a;
>>   a.h(-i);
>>   j b;
>>   b.k();
>> }
>>
>> Use the following flag set to debug:
>>
>> $ gdb --args llvm/build/bin/clang++ -c -w -O2 testcase.cpp
>>
>> Inside gdb: (set break point at the end of the pass to inspect the
basic
>> block)
>>
>> (gdb) set follow-fork-mode child
>> (gdb) b StackColoring.cpp:1301
>> (gdb) r
>> (gdb) p dInst->getParent()->dump()
>>
>> *My findings*
>>
>> 1. Definition of %0 register and use of it are found to be in the same
>> basic block and the use is preceded by the def.
>> 2. I believe the IR produced is malformed after a call to
>> remapInstructions(..) method is made. The method removeAllMarkers()
does
>> not modify IR in my knowledge. So it is safe to assume that LLVM IR
>> produced at the end of the pass is same as the IR after the call to
>> remapInstructions(..) is made.
>> 3. While executing remapInstructions(..), the uses of %ref.tmp are
>> replaced with %0 in %tmpcast definition when
>> From-AI->replacesAllUsesWith(Inst) call is made. This is triggering
the
>> bug. It basically grabs the UseList (one of them being the definition
of
>> %tmpcast) and renames all the %ref.tmp uses to %0.
>>
>> *Basic Block IR before replaceAllUsesWith method is executed*:
>>
>> entry:
>>
>>   %a = alloca %struct.e, align 1
>>   %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>>   %tmpcast = bitcast { <2 x float>, <2 x float> }* %ref.tmp
to %class.d*
>>   %b = alloca %struct.j, align 4
>>   %tmp = alloca %"struct.e::f", align 8
>>   %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>,
<2 x float>}*
>>   ...
>>   ret void
>>
>> *Basic Block IR after replaceAllUsesWith method is executed:*
>>
>> entry:
>>  %a = alloca %struct.e, align 1
>>  %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8
>>  %tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to
%class.d*
>>  %b = alloca %struct.j, align 4
>>  %tmp = alloca %"struct.e::f", align 8
>>  %0 = bitcast %"struct.e::f"* %tmp to { <2 x float>,
<2 x float> }*
>>  ...
>>  ret void
>>
>> I would like to hear what the community has to say about this.
Apologies
>> if formatting is messy. Let me know if something is not clear, I'm
happy to
>> explain and elaborate. Thanks in advance.
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200505/252e89da/attachment.html>