[StackColoring] When remapping alloca's move the To alloca if the From alloca is before it.

[craig.topper]

Summary

If To is after From its possible that there's a use of From
between them.

I'm not sure if this is the right fix, but wanted to start here
for discussion. Also not sure how to test this since we're in
the Machine IR section of the pipeline, but modifying IR.

Fixes issue reported here http://lists.llvm.org/pipermail/llvm-dev/2020-May/141421.html

[jdoerfert]

Did we have a bug with reproducer that we can run? I hope there is also a way to run only this pass and get the output (IR). Though, I don't know how :)

---

I find the patch fine but I want someone else to say something as well.
Nit: maybe put the first sentence of the commit message as a comment before the conditional.

[craig.topper]

In D80101#2041001, @jdoerfert wrote:

Did we have a bug with reproducer that we can run? I hope there is also a way to run only this pass and get the output (IR). Though, I don't know how :)

---

I find the patch fine but I want someone else to say something as well.
Nit: maybe put the first sentence of the commit message as a comment before the conditional.

We have this C++ test which we can get IR for llc from.

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();
}

[efriedma]

Also not sure how to test this since we're in the Machine IR section of the pipeline, but modifying IR.

If you run a pass with llc -run-pass, it prints both the LLVM IR module, and the MIR for each function after the pass runs.

[craig.topper]

Add test.

[efriedma]

LGTM

llvm/lib/CodeGen/StackColoring.cpp

 //===- StackColoring.cpp --------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
void StackColoring::remapInstructions(DenseMap<int, int> &SlotRemap) {
   // Keep a list of allocas which has been affected by the remap.
   SmallPtrSet<const AllocaInst*, 32> MergedAllocas;
 
   for (const std::pair<int, int> &SI : SlotRemap) {
     const AllocaInst *From = MFI->getObjectAllocation(SI.first);
     const AllocaInst *To = MFI->getObjectAllocation(SI.second);
     assert(To && From && "Invalid allocation object");
     Allocas[From] = To;
+    if (From->comesBefore(To))
+      const_cast<AllocaInst*>(To)->moveBefore(const_cast<AllocaInst*>(From));
 
     // AA might be used later for instruction scheduling, and we need it to be
     // able to deduce the correct aliasing releationships between pointers
     // derived from the alloca being remapped and the target of that remapping.
     // The only safe way, without directly informing AA about the remapping
     // somehow, is to directly update the IR to reflect the change being made
     // here.
     Instruction *Inst = const_cast<AllocaInst *>(To);