Remove all MMOs from memory operations when tail merging.

[apazos]

Summary

All,
When tail merging MBBs it's necessary to remove all MMOs from memory operations to ensures later passes conservatively compute dependencies.

A more robust solution would be to add multiple MMOs from the duplicate MIs to the new MI. Currently ScheduleDAGInstrs.cpp ignores all MMOs on instructions with multiple MMOs, so the attached patch is equivalent for the time being. If this patch is approved, I'll file a new PR suggesting the potential enhancement.

Just a few questions:

1. Does the new clearMemRefs() API need to free any memory?
2. I couldn't derive a simple test case. Does anyone have a suggestion?

Initial discussion here:
http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/082525.html
http://lists.cs.uiuc.edu/pipermail/llvmdev/2015-February/082526.html

[hfinkel]

Does the new clearMemRefs() API need to free any memory?

No. The memory for memrefs is owned by the machine function (it is allocated by MF.allocateMemRefsArray()).

lib/CodeGen/BranchFolding.cpp

735

We can do better than this. Don't remove the MMOs if we're tail merging two instructions that have identical MMOs.

[apazos]

lib/CodeGen/BranchFolding.cpp

735

Thanks for the suggestion Hal. Chad is OOO, I will uplload a new patch so we can continue the discussion.

[apazos]

Hal let me know if you think we need to check each field in the MMO, I am just checking for the gep instruction, and not going down the underlying objects nor the flags, AA metadatat fields etc.

[hfinkel]

lib/CodeGen/BranchFolding.cpp

744

Yes, please check all of the fields (they can have control dependencies). Also, You can just do V1 != V2, both being null is fine.

[apazos]

Hi Hal,
I added all possible fields so we can agree on what we really need to check.
I think some of the fields we do need to check, like alignment, address space, flags.
Others like AAInfo, Ranges, I just checked the first entry, I did not go down the lists to check each metadata node. Probably we need to do that.
Let me know what you think.

[hfinkel]

In D7769#128094, @apazos wrote:

Hi Hal,
I added all possible fields so we can agree on what we really need to check.
I think some of the fields we do need to check, like alignment, address space, flags.
Others like AAInfo, Ranges, I just checked the first entry, I did not go down the lists to check each metadata node. Probably we need to do that.
Let me know what you think.

What you're doing with the Metadata right now is correct; you're comparing the pointers to the metadata, and those should be unique by contents (you won't have two different metadata pointers that have the same contents).

[hfinkel]

lib/CodeGen/BranchFolding.cpp

750

I think function is good, except for this part. Comparing the value's underlying objects won't be sufficient if AA is being used (I think its probably fine otherwise, but I don't really want use-of-AA-dependent behavior here). I think we, realistically, have two options (which as I explained earlier, are more-or-less the same in effect currently):

1. If V1 != V2, strip the MMOs.
2. If V1 != V2, add multiple MMOs.

I think that doing (1) is fine for now, but I'd actually like to see us add multiple MMOs (option 2), and let the scheduler deal with that (which it does not currently).

[apazos]

Hi Hal,

Yes, for now we can have the V1 != V2 solution to resolve the benchmark miscompares resulting from BranchFolding.

I have updated the patch with a few new fixes:
(1) I was potentially removing MMOs from all LD/ST instructions inside the common tail.
I should have been more conservative and remove MMOs from the corresponding LD/ST instructions between a block and the common tail.
(2) The "CommonTailLen" includes matching instructions between a block and the common tail, but it can also include additional debug instructions.
I have to discount these debug instructions.

[hfinkel]

lib/CodeGen/BranchFolding.cpp

740

Can you please add an == operator to the class; this logic needs to be maintained with the MMO class, and should not live here.

[apazos]

I have added operator == and != to MachineMemOperrand.h.

[mcrosier]

In addition to adding the == and != operators to MachineMemOperrand.h, this patch set
address a few issues from the previous patch:

1. When comparing MMO Values, both being null is considered identical, per Hal's review.

2. When iterating over the MBB, only compare instructions in the common block against the equivalent instruction in the non-common block. Previously, we were comparing all instruction in the common block against all instructions in the non-common block which can remove MMOs that are not necessary.

3. The "SameTails" can have CommonTailLen of different values relating to the same common block, and might have different number of matching instructions and some extra debug instructions that have to be discounted.

Ana, please feel free to add additional comments.

include/llvm/CodeGen/MachineMemOperand.h

204

What about something like:
return LHS.getValue() == RHS.getValue() &&

LHS.getPseudoValue() == RHS.getPseudoValue() &&
LHS.getSize() != RHS.getSize() &&
LHS.getOffset() != RHS.getOffset() &&
...
...;

lib/CodeGen/BranchFolding.cpp

764

Directly use MBB->rend(), rather than MBBIE? This would remove the need for the void cast.

[apazos]

Hi Chad, thanks for the suggestions. I incorporated what I agreed with.

The patch you commented on had only the operator change. But the previous patch to that one had the other changes you listed (refer o previous patch commit message):

(1) I was potentially removing MMOs from all LD/ST instructions inside the common tail.
I should have been more conservative and remove MMOs from the corresponding LD/ST instructions between a block and the common tail.
(2) The "CommonTailLen" includes matching instructions between a block and the common tail, but it can also include additional debug instructions.
I have to discount these debug instructions.

Thanks!

[hfinkel]

include/llvm/CodeGen/MachineMemOperand.h

203

Line too long?

215

Line too long?

lib/CodeGen/BranchFolding.cpp

737

I think this loop is just:

return std::equal(I1, E1, I2);

[apazos]

Hi Hal,
I fixed the line format.
As for using std:equal, I do not think it works because it will compare *I1 != *I2 instead of I1 != I2 which we need to compare MemoryOperand references.

[hfinkel]

LGTM. Make sure you mention in the commit message that no reduced test case is available.

As for using std:equal, I do not think it works because it will compare *I1 != *I2 instead of I1 != I2 which we need to compare MemoryOperand references.

Ah, yes, you're right (you could write a custom predicate, but that does not seem worthwhile).

[mcrosier]

Committed in r231799.

include/llvm/CodeGen/MachineInstr.h

   /// setMemRefs - Assign this MachineInstr's memory reference descriptor
   /// list. This does not transfer ownership.
   void setMemRefs(mmo_iterator NewMemRefs, mmo_iterator NewMemRefsEnd) {
     MemRefs = NewMemRefs;
     NumMemRefs = uint8_t(NewMemRefsEnd - NewMemRefs);
     assert(NumMemRefs == NewMemRefsEnd - NewMemRefs && "Too many memrefs");
   }
 
+  /// clearMemRefs - Clear this MachineInstr's memory reference descriptor list.
+  void clearMemRefs() {
+    MemRefs = nullptr;
+    NumMemRefs = 0;
+  }
+
 private:
   /// getRegInfo - If this instruction is embedded into a MachineFunction,
   /// return the MachineRegisterInfo object for the current function, otherwise
   /// return null.
   MachineRegisterInfo *getRegInfo();
 
   /// untieRegOperand - Break any tie involving OpIdx.
   void untieRegOperand(unsigned OpIdx) {

include/llvm/CodeGen/MachineMemOperand.h

public:
   /// to it are being updated.
   void setValue(const Value *NewSV) { PtrInfo.V = NewSV; }
   void setValue(const PseudoSourceValue *NewSV) { PtrInfo.V = NewSV; }
   void setOffset(int64_t NewOffset) { PtrInfo.Offset = NewOffset; }
 
   /// Profile - Gather unique data for the object.
   ///
   void Profile(FoldingSetNodeID &ID) const;
+
+  friend bool operator== (const MachineMemOperand &LHS,
+    const MachineMemOperand &RHS) {
+    return LHS.getValue() == RHS.getValue() &&
+      LHS.getPseudoValue() == RHS.getPseudoValue() &&
+      LHS.getSize() == RHS.getSize() &&
+      LHS.getOffset() == RHS.getOffset() &&
+      LHS.getFlags() == RHS.getFlags() &&
+      LHS.getAAInfo() == RHS.getAAInfo() &&
+      LHS.getRanges() == RHS.getRanges() &&
+      LHS.getAlignment() == RHS.getAlignment() &&
+      LHS.getAddrSpace() == RHS.getAddrSpace();
+  }
+
+  friend bool operator!= (const MachineMemOperand &LHS,
+    const MachineMemOperand &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const MachineMemOperand &MRO);
 
 } // End llvm namespace
 
 #endif

lib/CodeGen/BranchFolding.cpp

 #include "BranchFolding.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
+#include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
 #include "llvm/CodeGen/RegisterScavenging.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
bool BranchFolder::CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 
   // If we split PredBB, newMBB is the new predecessor.
   if (PredBB == MBB)
     PredBB = newMBB;
 
   return true;
 }
 
+static bool hasIdenticalMMOs(const MachineInstr *MI1,
+                             const MachineInstr *MI2) {
+  auto I1 = MI1->memoperands_begin(), E1 = MI1->memoperands_end();
+  auto I2 = MI2->memoperands_begin(), E2 = MI2->memoperands_end();
+  if ((E1 - I1) != (E2 - I2))
+    return false;
+  for (; I1 != E1; ++I1, ++I2) {
+    if (**I1 != **I2)
+      return false;
+  }
+  return true;
+}
+
+static void removeMMOsFromMemoryOperations(
+ MachineBasicBlock::iterator MBBIStartPos,
+ MachineBasicBlock &MBBCommon) {
+  // Remove MMOs from memory operations in the common block
+  // when they do not match the ones from the block being tail-merged.
+  // This ensures later passes conservatively compute dependencies.
+  MachineBasicBlock *MBB = MBBIStartPos->getParent();
+  // Note CommonTailLen does not necessarily matches the size of
+  // the common BB nor all its instructions because of debug
+  // instructions differences.
+  unsigned CommonTailLen = 0;
+  for (auto E = MBB->end(); MBBIStartPos != E; ++MBBIStartPos)
+    ++CommonTailLen;
+
+  MachineBasicBlock::reverse_iterator MBBI = MBB->rbegin();
+  MachineBasicBlock::reverse_iterator MBBICommon = MBBCommon.rbegin();
+  MachineBasicBlock::reverse_iterator MBBIE = MBB->rend();
+  MachineBasicBlock::reverse_iterator MBBIECommon = MBBCommon.rend();
+
+  while (CommonTailLen--) {
+    assert(MBBI != MBBIE && "Reached BB end within common tail length!");
+    (void)MBBIE;
+
+    if (MBBI->isDebugValue()) {
+      ++MBBI;
+      continue;
+    }
+
+    while ((MBBICommon != MBBIECommon) && MBBICommon->isDebugValue())
+      ++MBBICommon;
+
+    assert(MBBICommon != MBBIECommon &&
+      "Reached BB end within common tail length!");
+
+    assert(MBBICommon->isIdenticalTo(&*MBBI) && "Expected matching MIIs!");
+
+    if (MBBICommon->mayLoad() || MBBICommon->mayStore())
+      if (!hasIdenticalMMOs(&*MBBI, &*MBBICommon))
+        MBBICommon->clearMemRefs();
+
+    ++MBBI;
+    ++MBBICommon;
+  }
+}
+
 // See if any of the blocks in MergePotentials (which all have a common single
 // successor, or all have no successor) can be tail-merged.  If there is a
 // successor, any blocks in MergePotentials that are not tail-merged and
 // are not immediately before Succ must have an unconditional branch to
 // Succ added (but the predecessor/successor lists need no adjustment).
 // The lone predecessor of Succ that falls through into Succ,
 // if any, is given in PredBB.
 
while (MergePotentials.size() > 1) {
     // Traversal must be forwards so erases work.
     DEBUG(dbgs() << "\nUsing common tail in BB#" << MBB->getNumber()
                  << " for ");
     for (unsigned int i=0, e = SameTails.size(); i != e; ++i) {
       if (commonTailIndex == i)
         continue;
       DEBUG(dbgs() << "BB#" << SameTails[i].getBlock()->getNumber()
                    << (i == e-1 ? "" : ", "));
+      // Remove MMOs from memory operations as needed.
+      removeMMOsFromMemoryOperations(SameTails[i].getTailStartPos(), *MBB);
       // Hack the end off BB i, making it jump to BB commonTailIndex instead.
       ReplaceTailWithBranchTo(SameTails[i].getTailStartPos(), MBB);
       // BB i is no longer a predecessor of SuccBB; remove it from the worklist.
       MergePotentials.erase(SameTails[i].getMPIter());
     }
     DEBUG(dbgs() << "\n");
     // We leave commonTailIndex in the worklist in case there are other blocks
     // that match it with a smaller number of instructions.