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.

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.

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.

Hi Craig,

This patch makes everything right. Thanks, Craig, for your time :slight_smile:

Let me know how to proceed further - do I submit a problem report (PR) or would you be fixing it formally? So as to make sure this unusual behavior is taken care of in the LLVM project.

Kind regards,
Uzair