[BranchFolding] Merge MMOs during tail merge

[flyingforyou]

Summary

Recommit r254694, it was reverted in r254700 to investigate a bot failure.

If we remove the MMOs from Load/Store instructions,
they are treated as volatile. This makes other optimization passes unhappy.
eg. Load/Store Optimization

So, it looks better to merge, not remove.
But if the product of two MMOs count is higher than threshold,
we just remove them for preventing any pathological cases from
causing compile time blowups or overflow.

[flyingforyou]

Hi, Chad, Geoff.

In D14797, @gberry wrote:
Alternatively, could you just add a bail out case that clears all memops if M1->getMemOperands().size() * M2->getMemOperands().size() is above a certain threshold? That would > > prevent any pathological cases from causing compile time blowups.
@mcrosier wrote:
This sounds very reasonable, IMO.
@flyingforyou wrote:
I will make an another patch. We can discuss about threshold value.

Your opinion is not optinal. It's essential. So, I added threshold and set it 255. It's maximum value of MMOs count.
After setting threshold, there is no error likes below.
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/21531/steps/annotate/logs/stdio

Could you review this commit again, please?

I am really sorry for hasty decisions.

Junmo.

[mcrosier]

In D15230#302403, @flyingforyou wrote:

Your opinion is not optinal. It's essential. So, I added threshold and set it 255. It's maximum value of MMOs count.
After setting threshold, there is no error likes below.
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux/builds/21531/steps/annotate/logs/stdio

Hi Junmo,
Would you mind explaining what exactly caused the bootstrap to fail? I just want to make sure this is in fact the correct fix. Also, I'm wondering how you arrived at the 255 threshold; I would have probably picked something much smaller (e.g., 16).

Chad

p.s., We should always do the necessary due diligence to prevent breakages, but please don't lose sleep over it. :) We do appreciate your efforts on this patch!

[flyingforyou]

Would you mind explaining what exactly caused the bootstrap to fail?

The error message is below.

void llvm::MachineInstr::setMemRefs(llvm::MachineInstr::mmo_iterator, llvm::MachineInstr::mmo_iterator): Assertion `NumMemRefs == NewMemRefsEnd - NewMemRefs && "Too many memrefs"' failed.

MachineInstr.h

   uint8_t NumMemRefs;                   // Information on memory references.
   mmo_iterator MemRefs;

NumMemRefs type is uint8_t. So the maximum value is 255. Previous commit doesn't care about the NewMemrefs's count. When modified clang build clang, there are several cases that sum of two MI's MMOs count is over 255.
So, it has a problem. I just set the threshold value maximum. No matter MI1, MI2's count is, it could be safe.
eg. MI1 MMOs count == 1, MI2 MMOs count == 255, it will be occurred overflow. Because Sum of two MMOs count is 256. (Product of two MMOs count is 255. This is the maximum value of NumMemRefs.)

I don't want to set threshold value to 255. 16 is also good choice. (If the threshold value is 16, most of MMOs can be merged.)

p.s., We should always do the necessary due diligence to prevent breakages, but please don't lose sleep over it. :) We do appreciate your efforts on this patch!

I really appreciate your kind words.

Junmo.

[flyingforyou]

Addressed Chad's comments. (Reduce threshold value)

Thanks Chad.

[flyingforyou]

Ping.

[gberry]

A few comments below.

lib/CodeGen/BranchFolding.cpp

760

You might want to change this comment to refer to the threshold check done in the caller.

784

This comment formatting should be cleaned up. Don't capitalize "Merge" on this line and move it up to the above line and re-wrap it.

820

It seems to me that adding MachineInstr::getNumMemOperands() and using it here would be cleaner.

[flyingforyou]

Addressed Geoff's comments.
Thanks.

[gberry]

include/llvm/CodeGen/MachineInstr.h

350

I don't think you want to have the uint8_t implementation detail leak out of the interface here. Perhaps this should be 'unsigned'?
I'd like to hear from @hfinkel on this detail before I can approve it.

[flyingforyou]

include/llvm/CodeGen/MachineInstr.h

350

Thanks Geoff. Before waiting review from @hfinkel, I want to talk something.

We choose the way to check threshold MI1 MMO's count * MI2's MMO's count. If we change uint8_t to unsigned, it seems that can return over 255. This means we may take care overflow. Because the type of merge-mmos-threshold is unsigned. it's not uint64_t.

If @hfinkel also think change the return type to unsigned, we need to add assert before multipication.

And MachineInstr has two more uint8_t variables Flags, AsmPrinterFlags. Their getter & setter also have same return type.
So I think this function may be ok also.

Junmo.

[gberry]

include/llvm/CodeGen/MachineInstr.h

350

Junmo, I agree with your points above, other than a small point that we shouldn't add an assert for overflow, but rather a check that handles it appropriately (i.e. by not doing the merge).

I think all that's left is for @hfinkel to chime in.

[flyingforyou]

Ping: Hal, Could you review this commit, please?

[reames]

Do you have test cases to motivate this change? I ask for two reasons:

1. They'll be absolutely required before submission.
2. I'm trying to understand when the merging is useful in practice.

include/llvm/CodeGen/MachineInstr.h

350

I disagree on using uint8_t. The maximum storage size of the mem operand array is an implementation detail and should not leak outside the owning class.

p.s. I have out of tree changes which change the size of this field. I know of at least one other group that has a similar change. It'd be nice if we abstracted over the storage size. :)

lib/CodeGen/BranchFolding.cpp

69

Given how many bugs we have around treating cleared MMOs correctly, I *strongly* recommend preserving them if at all possible.

764

This is an order N^2 algorithm. Not acceptable particular since a sort/unique based one is clearly feasible.

I'll also comment that the semantics of merging two memoperand lists are unclear at the moment. This code might be semantically correct, but I don't know enough yet to say for sure.

816

And what happens if I set merge threshold to 270? There needs to be an assert/bounds check on the merge threshold.

[reames]

I have a review up (http://reviews.llvm.org/D15757) which cleans up the API this is building on. I suggest that you wait until that patch has landed, then rebase your changes there. It'll simplify the changes needed and remove the need for the interface extensions. Once my change is in, moving the isIdenticalMMO as a special case of the new conservative merge would also be useful.

[flyingforyou]

Thanks, Philip.

This commit is bug fix of D14797. Several discussions were already done in D14797.

I will rebase the code soon.

include/llvm/CodeGen/MachineInstr.h

350

OK. If someone use NumMemRefs uint16_t, we could use unsigned for return type.

lib/CodeGen/BranchFolding.cpp

69

Most of cases, I think threshold value(16) is enough. (Also this is Chad's idea.) If you need practical data, I will make it. please let me know.

764

please refer below commit.
http://reviews.llvm.org/D14797

Most of cases(98%), MI1's MMO count is 0 or 1. so It takes less time than we think. If we make the code using Smallset, we should use function call, compare function, using more room for saving MMOs. I don't think this is betther than now.

816

I will add comment that the threshold limit should be 254. Then, we don't need to insert assert check. right?

[flyingforyou]

Addressed Philip's comments.

[reames]

I've landed two changes (r256966 and r256909) which clarify the semantics of MMO merging. This patch should be rebased over the generic merging infrastructure now in place so that other parts of the backend can pick them up.

I still think the merging algorithm used here is unnecessarily inefficient. There's no reason this merge step shouldn't scale to the maximum number of memrefs we allow. I suggested in an offlist email that we use a std::sort idiom. That is slightly complicated by the need to sort the pointers based on the contents of objects reachable through pointers, but that still seems like the right approach. A custom comparator function or lambda would be perfect in this context.

If you'd rather, I'm happy to write up a patch which implements that. The only thing I would need is a couple of test cases which show the need for it so that I can tell if the code is actually correct. (The tests would be mandatory for the rebased version of this change as well.)

[flyingforyou]

Hi Philip.

This patch's main idea is merging MMOs. But you already did that on D15913.
So I think rebasing this commit is not necesaary any more.

Thanks.

[gberry]

I don't think that is correct. If you look at the body of MachineInstr::mergeMemRefsWith() after Philip's change, it is only merging in the case where the MMO lists are the same. I believe his intention was for you to refactor this change by making a similar change in mergeMemRefsWith() instead of in TryTailMergeBlocks()

[flyingforyou]

Hi Geoff.

I checked triple time after seeing your comment. I think I am not wrong with my comment.

In mergeMemRefsWith()

if (hasIdenticalMMOs(*this, Other))
  return std::make_pair(MemRefs, NumMemRefs);
-> If MMO lists are same, just return itself's MMOs.

-> If MMO lists are not same, it starts merging likes below.

// TODO: consider uniquing elements within the operand lists to reduce
// space usage and fall back to conservative information less often.
size_t CombinedNumMemRefs = NumMemRefs + Other.NumMemRefs;

After applying philip's commit, if the MMO lists are not same, we preserve MMOs.

Anyway, what I want to check is below part.

if (MBBICommon->mayLoad() || MBBICommon->mayStore())
  MBBICommon->setMemRefs(MBBI->mergeMemRefsWith(*MBBI));

MBBI->mergeMemRefsWith(*MBBI) might be
MBBICommon->mergeMemRefsWith(*MBBI) or MBBI->mergeMemRefsWith(*MBBICommon).

I will upload new commit for this.

-Junmo.

[gberry]

The other difference from your original change is that duplicates aren't removed from the newly merged list, but I guess we'd need to see a case where that mattered to justify the cost of fixing it.

include/llvm/CodeGen/MachineInstr.h

public:
   iterator_range<const_mop_iterator> uses() const {
     return make_range(operands_begin() + getDesc().getNumDefs(),
                       operands_end());
   }
 
   /// Returns the number of the operand iterator \p I points to.
   unsigned getOperandNo(const_mop_iterator I) const {
     return I - operands_begin();
   }
 
   /// Access to memory operands of the instruction
   mmo_iterator memoperands_begin() const { return MemRefs; }
   mmo_iterator memoperands_end() const { return MemRefs + NumMemRefs; }
   /// Return true if we don't have any memory operands which described the the
   /// memory access done by this instruction.  If this is true, calling code
   /// must be conservative.    
   bool memoperands_empty() const { return NumMemRefs == 0; }
+  unsigned getNumMemOperands() const { return NumMemRefs; }
 
   iterator_range<mmo_iterator>  memoperands() {
     return make_range(memoperands_begin(), memoperands_end());
   }
   iterator_range<mmo_iterator> memoperands() const {
     return make_range(memoperands_begin(), memoperands_end());
   }
 

lib/CodeGen/BranchFolding.cpp

 
 // Heuristic for tail merging (and, inversely, tail duplication).
 // TODO: This should be replaced with a target query.
 static cl::opt<unsigned>
 TailMergeSize("tail-merge-size",
           cl::desc("Min number of instructions to consider tail merging"),
                               cl::init(3), cl::Hidden);
 
+// merge-mmos-threshold's maximum value should be <= 255.
+// Because NumMemRefs's type is uint8_t now.
+static cl::opt<unsigned>
+    MergeMMOsThreshold("merge-mmos-threshold",
+                       cl::desc("Threshold for mergeMMOs function"),
+                       cl::init(16), cl::Hidden);
+
 namespace {
   /// BranchFolderPass - Wrap branch folder in a machine function pass.
   class BranchFolderPass : public MachineFunctionPass {
   public:
     static char ID;
     explicit BranchFolderPass(): MachineFunctionPass(ID) {}
 
     bool runOnMachineFunction(MachineFunction &MF) override;
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) {
+// Add MI1's MMOs to MI2's MMOs while excluding any duplicates. The MI scheduler
+// currently doesn't handle multiple MMOs, so duplicates would likely pessimize
+// the scheduler.
+static void mergeMMOs(MachineInstr *MI1, 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;
+  MachineFunction *MF = MI1->getParent()->getParent();
+
+  // Mostly, MI1's MMO count is 1 or zero. So we don't have to use
+  // SmallSet. The threshold check is done in the caller.
+  for (; I1 != E1; ++I1) {
+    bool IsDupMMO = false;
+    for (I2 = MI2->memoperands_begin(); I2 != E2; ++I2) {
+      if (**I1 == **I2) {
+        IsDupMMO = true;
+        break;
+      }
+    }
+    if (IsDupMMO == false) {
+      MI2->addMemOperand(*MF, *I1);
+      E2 = MI2->memoperands_end();
+    }
   }
-  return true;
 }
 
 static void
-removeMMOsFromMemoryOperations(MachineBasicBlock::iterator MBBIStartPos,
+removeOrMergeMMOsFromMemoryOperations(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.
+
+  unsigned MergeThreshold = MergeMMOsThreshold;
+  // If MBB's MMOs count * MBBCommon's MMOs count is smaller than
+  // MergeThreshold, merge MMOs from memory operations in the
+  // common block. Otherwise, we remove them.
   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;
 
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))
+    if (MBBICommon->mayLoad() || MBBICommon->mayStore()) {
+      if (MBBICommon->getNumMemOperands() * MBBI->getNumMemOperands() <
+          MergeThreshold)
+        mergeMMOs(&*MBBI, &*MBBICommon);
+      else
         MBBICommon->dropMemRefs();
+    }
 
     ++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
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);
+      // Remove or merge MMOs from memory operations as needed.
+      removeOrMergeMMOsFromMemoryOperations(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.