Consolidate MemRefs handling from BranchFolding and correct latent bug

[reames]

Summary

Move the logic from BranchFolding to use the shared infrastructure for merging MMOs introduced in 256909. This has the effect of making BranchFolding more capable.

In the process, fix a latent bug. The existing handling for merging didn't handle the case where one of the instructions being merged had overflowed and dropped MemRefs. This was a latent bug in the places the code was commoned from, but potentially reachable in BranchFolding.

Once this is in, we're left with a single place to consider implementing MMO unique-ing as proposed in http://reviews.llvm.org/D15230.

[atrick]

LGTM

[gberry]

This seems reasonable to me. A couple of minor comments/questions below.

lib/CodeGen/BranchFolding.cpp

796 ↗

(On Diff #44087)

I think dropMemRefs() is dead after this change, so it could also be removed.

lib/CodeGen/MachineInstr.cpp

881 ↗

(On Diff #44087)

Isn't this going to do pointer equality comparisons instead of the MachineMemOperand::operator==() comparisons that hasIdenticalMMOs() was doing? I don't think these are equivalent since as far as I can tell there is no uniqueing of MachineMemOperands done at creation.

887 ↗

(On Diff #44087)

Perhaps NumMemRefs + Other.NumMemRefs would be better?

[reames]

lib/CodeGen/BranchFolding.cpp

796 ↗

(On Diff #44087)

Good catch.

lib/CodeGen/MachineInstr.cpp

881 ↗

(On Diff #44087)

Really good catch. Yep, this was a bug on my part. Will fix.

[reames]

lib/CodeGen/BranchFolding.cpp

796 ↗

(On Diff #44087)

Actually, after further though, I'm going to leave the routine. The semantic operation it performs is useful and not really clear from any of the other accessors.

I may change my mind when I try to actually introduce the poison state, but that can be part of that review.

[gberry]

lib/CodeGen/BranchFolding.cpp

796 ↗

(On Diff #44087)

Yeah, I had a similar thought after I sent the original comment.

llvm/trunk/lib/CodeGen/BranchFolding.cpp

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
while (CommonTailLen--) {
     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->dropMemRefs();
+      MBBICommon->setMemRefs(MBBI->mergeMemRefsWith(*MBBI));
 
     ++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

llvm/trunk/lib/CodeGen/MachineInstr.cpp

void MachineInstr::addMemOperand(MachineFunction &MF,
   unsigned NewNum = NumMemRefs + 1;
   mmo_iterator NewMemRefs = MF.allocateMemRefsArray(NewNum);
 
   std::copy(OldMemRefs, OldMemRefs + OldNumMemRefs, NewMemRefs);
   NewMemRefs[NewNum - 1] = MO;
   setMemRefs(NewMemRefs, NewMemRefs + NewNum);
 }
 
+/// Check to see if the MMOs pointed to by the two MemRefs arrays are
+/// identical. 
+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;
+}
+
 std::pair<MachineInstr::mmo_iterator, unsigned>
 MachineInstr::mergeMemRefsWith(const MachineInstr& Other) {
-  // TODO: If we end up with too many memory operands, return the empty
-  // conservative set rather than failing asserts.
+
+  // If either of the incoming memrefs are empty, we must be conservative and
+  // treat this as if we've exhausted our space for memrefs and dropped them.
+  if (memoperands_empty() || Other.memoperands_empty())
+    return std::make_pair(nullptr, 0);
+
+  // If both instructions have identical memrefs, we don't need to merge them.
+  // Since many instructions have a single memref, and we tend to merge things
+  // like pairs of loads from the same location, this catches a large number of
+  // cases in practice.
+  if (hasIdenticalMMOs(*this, Other))
+    return std::make_pair(MemRefs, NumMemRefs);
+  
   // TODO: consider uniquing elements within the operand lists to reduce
   // space usage and fall back to conservative information less often.
-  size_t CombinedNumMemRefs = (memoperands_end() - memoperands_begin())
-    + (Other.memoperands_end() - Other.memoperands_begin());
+  size_t CombinedNumMemRefs = NumMemRefs + Other.NumMemRefs;
+
+  // If we don't have enough room to store this many memrefs, be conservative
+  // and drop them.  Otherwise, we'd fail asserts when trying to add them to
+  // the new instruction.
+  if (CombinedNumMemRefs != uint8_t(CombinedNumMemRefs))
+    return std::make_pair(nullptr, 0);
 
   MachineFunction *MF = getParent()->getParent();
   mmo_iterator MemBegin = MF->allocateMemRefsArray(CombinedNumMemRefs);
   mmo_iterator MemEnd = std::copy(memoperands_begin(), memoperands_end(),
                                   MemBegin);
   MemEnd = std::copy(Other.memoperands_begin(), Other.memoperands_end(),
                      MemEnd);
   assert(MemEnd - MemBegin == (ptrdiff_t)CombinedNumMemRefs &&