[llvm-dev] Unexpected behavior found in Stack Coloring pass, need clarification

[Mohammed Abid Uzair via llvm-dev]

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>