<div dir="ltr">Hello,<br><br>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.<br><br>The IR produced at the end of the pass seems to be malformed..<br>Looking at transformed IR, it is clear that use of <font face="monospace">%0</font> precedes the definition of <font face="monospace">%0</font>. 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.<div><br></div><div>Also, please help me understand on what basis the pointer to be replaced is picked? In other words, why is <font face="monospace">%tmp</font> is preferred over <font face="monospace">%ref.tmp?</font></div><div>If they allocate the same number of bytes, why is <font face="monospace">%ref.tmp</font> not given preference as it comes first in the order?</div><div><br></div><div><b>Malformed IR at the end of Stack Coloring pass:<br></b><font face="monospace">entry:<br>    %a = alloca %struct.e, align 1<br>    %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8           <br>    <span style="background-color:rgb(255,255,0)">%tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to %class.d*</span><br>    ...<br>    %tmp = alloca %"struct.e::f", align 8                             <br>    <span style="background-color:rgb(255,255,0)">%0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x float> }*</span><br>    ...<br>    ret void<br></font><br><b>Steps to reproduce:</b><br><br>For debugging purposes, I have modified last few lines of <font face="monospace">runOnMachineFunction(..)</font> method present in the StackColoring.cpp file. The original source can be found here: <a href="https://llvm.org/doxygen/StackColoring_8cpp_source.html" target="_blank">https://llvm.org/doxygen/StackColoring_8cpp_source.html</a><br><br>    <font face="monospace">bool StackColoring::runOnMachineFunction(MachineFunction &Func) {<br>    ...<br>    ...<br>    remapInstructions(SlotRemap);<br>+   bool markerCount = removeAllMarkers();<br>+   DenseMap<int, int>::iterator itr = SlotRemap.begin();             </font><div><font face="monospace">+   const AllocaInst *dInst = MFI->getObjectAllocation(itr->first);</font></div><div><font face="monospace">+   LLVM_DEBUG(dbgs() << "Set break point here to inspect dInst\n");<br>+   return markerCount;<br>  }</font><br><br>I'm using the following test-case to reproduce the issue:<br><br><b>testcase.cpp</b><br><br><font face="monospace">class d {<br>  float b[4];<br>};<br><br>d operator-(d);<br>struct e {<br>  struct f {<br>    int *c[4];<br>  };<br>  void h(const d &);<br>};<br><br>struct j {<br>  int temp;<br>  e::f k();<br>};<br>d i;<br><br>void g() {<br>  e a;<br>  a.h(-i);<br>  j b;<br>  b.k();<br>}</font><br><br>Use the following flag set to debug:<br><br><font face="monospace">$ gdb --args llvm/build/bin/clang++ -c -w -O2 testcase.cpp</font><br><br>Inside gdb: (set break point at the end of the pass to inspect the basic block)<br><br><font face="monospace">(gdb) set follow-fork-mode child<br>(gdb) b StackColoring.cpp:1301<br>(gdb) r<br>(gdb) p dInst->getParent()->dump()</font><br><br><b>My findings</b><br><br>1. Definition of <font face="monospace">%0</font> register and use of it are found to be in the same basic block and the use is preceded by the def.</div><div>2. I believe the IR produced is malformed after a call to <font face="monospace">remapInstructions(..)</font> method is made. The method <font face="monospace">removeAllMarkers()</font> 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 <font face="monospace">remapInstructions(..) </font><font face="arial, sans-serif">is made.</font><br>3. While executing <font face="monospace">remapInstructions(..)</font>, the uses of <font face="monospace">%ref.tmp</font> are replaced with <font face="monospace">%0</font> in %tmpcast definition when <font face="monospace">From-AI->replacesAllUsesWith(Inst)</font> call is made. This is triggering the bug. It basically grabs the UseList (one of them being the definition of <font face="monospace">%tmpcast</font>) and renames all the <font face="monospace">%ref.tmp</font> uses to <font face="monospace">%0</font>.<br><br><i>Basic Block IR before replaceAllUsesWith method is executed</i>:<br><br><font face="monospace">entry:                                                                      <br>  %a = alloca %struct.e, align 1  <br>  %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8      <br>  <span style="background-color:rgb(255,255,0)">%tmpcast = bitcast { <2 x float>, <2 x float> }* %ref.tmp to %class.d*</span><br>  %b = alloca %struct.j, align 4                        <br>  %tmp = alloca %"struct.e::f", align 8<br>  <span style="background-color:rgb(255,255,0)">%0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x float>}*</span><br>  ...<br>  ret void</font><br><br><i>Basic Block IR after replaceAllUsesWith method is executed:</i><br><br><font face="monospace">entry:                                                                    <br> %a = alloca %struct.e, align 1<br> %ref.tmp = alloca { <2 x float>, <2 x float> }, align 8<br> <span style="background-color:rgb(255,255,0)">%tmpcast = bitcast { <2 x float>, <2 x float> }* %0 to %class.d*</span><br> %b = alloca %struct.j, align 4<br> %tmp = alloca %"struct.e::f", align 8<br> <span style="background-color:rgb(255,255,0)">%0 = bitcast %"struct.e::f"* %tmp to { <2 x float>, <2 x float> }*</span><br> ...<br> ret void</font><br><br>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.</div></div></div>