[BranchFolding] Merge MMOs during tail merge

[flyingforyou]

Summary

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.

[gberry]

Hi Junmo,

Instead of adding a field to every MachineInstr, it might be better to concatenate the two memref lists in the case that they are unequal when being merged.
You could try to do something more complex like sorting the merged list and removing duplicates, but that might be overkill depending on how large these memref lists can get.

[flyingforyou]

Thanks Geoff.

Is that safe for other optimization passes? Actually, I am not sure that merging memref lists is safe.
If you think it is safe, I will do that. please let me know.

[mcrosier]

In D14797#292428, @flyingforyou wrote:

Thanks Geoff.

Is that safe for other optimization passes? Actually, I am not sure that merging memref lists is safe.
If you think it is safe, I will do that. please let me know.

Checkout the commit message for r231799.

Merging multiple MMO's onto a single MI should not cause any correctness issues. However, the MI scheduler doesn't know how to handle multiple MMOs, so it makes conservative assumptions in this case (see the FIXME comment in ScheduleDAGInstrs.cpp:MIsNeedChainEdge()).

In r231799, Ana and I added the == operator for MMOs. When merging the MMO into the MI you could check for redundant MMOs and not merge them. I don't know if this is necessary for your use case, however.

HTH, Chad

[flyingforyou]

I addressed Chad, Geoff comments.

Thanks Chad. Your comment really helpful for me.

Junmo.

[gberry]

lib/CodeGen/BranchFolding.cpp

747 ↗

(On Diff #40743)

Maybe you should mention the fact that you are removing duplicates.

751 ↗

(On Diff #40743)

This check seems unnecessary to me. You will just skip the below for loop if this is true.

754 ↗

(On Diff #40743)

You should consider using a SmallSet here to look for duplicates instead of the N^2 search that you are currently doing.

756 ↗

(On Diff #40743)

I think you need to set I2 = MI2->memoperands_begin() and E2 = MI2->memoperands_end() here. Otherwise, whenever you find an MMO is equal, when you start looking for a matching MMO on the next iteration you will start where you left off, instead of at the beginning of MI2's MMO list.

763 ↗

(On Diff #40743)

This can be hoisted out of the loop.

[flyingforyou]

Thanks Geoff.

I accept several changes according to your opinion.
And I added several comments about your sugesstions.

[flyingforyou]

lib/CodeGen/BranchFolding.cpp

756 ↗

(On Diff #40859)

When I wrote the code with N^2 search, there is a reason that most of cases, MI only has a one or zero MMO.
So, This routine is faster than using SmallSet.

In order to support that most of MI has one or zero MMO, I tested some benchmarks app and got a data.

When I investigated 12354 MI which is used by mergeMMOs function,
MI(MMO is 0) == 1595, MI(MMO is 1) == 10514. Sum of two cases is 12109 and it's 98%.

So, I don't think Smallset is useful in this case.
But there is no explain why I use N^2 search, so I added the comment.

I want you agree with this, please.

758 ↗

(On Diff #40859)

Thanks.
You're right. I2 = MI2->memoperands_begin() need to be set. But E2 = MI2->memoperands_end() is only needed when MI2's MMO is changed.

[gberry]

Do you have any information on the impact of this change on final code generation/performance?

lib/CodeGen/BranchFolding.cpp

756 ↗

(On Diff #40859)

I believe a SmallSet will have almost exactly the same performance as the code you have written here when N is small, since it just uses a SmallVector and does a linear search. If N ever gets large though it will switch to using a std::set which should have log(N) lookup. I'd like to hear from another reviewer on whether this is warranted in this case.

[flyingforyou]

Hi Geoff, thanks for comment.

This optimization helps LDR/STR optimizations likes making load-pair or store-piar on AArch64.

When I ran Single/Multi Source Benchmarks in LLVM test-suite, Geomean value of positive effect is 0.06%, negative effect is 0.04%.

Especially, below benchmarks shows 0~1% improvement.

MultiSource/Benchmarks/TSVC/GlobalDataFlow-flt/GlobalDataFlow-flt
MultiSource/Benchmarks/Prolangs-C++/life/life
MultiSource/Benchmarks/mafft/pairlocalalign

[flyingforyou]

Hi Chad, Could you review this commit, please?

[mcrosier]

lib/CodeGen/BranchFolding.cpp

747 ↗

(On Diff #40859)

How about:

// 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.

756 ↗

(On Diff #40859)

I believe the number of MMO's on a MI is target-dependent. For AArch64 it tends to be 1, but for x86 it can be more, IIRC. Therefore, I tend to agree with Geoff; we should consider using a SmallSet. @gberry, do you have a suggestion on how the compare function could be written?

[mcrosier]

Another suggestion.

lib/CodeGen/BranchFolding.cpp

756 ↗

(On Diff #40859)

As an alternative you might consider adding logic to handle the common cases and then use std::unique for the other cases.

Something like:

static void mergeMMOs(MachineInstr *MI1, MachineInstr *MI2) {

// Nothing to merge.
if (MI2->getNumMemOperands() == 0)
  return;

if (MI1->getNumMemOperands() == 0) {
  // Copy MMOs from MI2 to MI1.
}

if (MI1->getNumMemOperands() == 1 && MI1->getNumMemOperands() == 1) {
  if (MMO1 == MMO2)
    return;
  // Copy MMO2 to MI1.
  return;
}

// Copy all MMOs from MI2 to MI1.
// std::unique MI1's MMOs.

}

[flyingforyou]

lib/CodeGen/BranchFolding.cpp

747 ↗

(On Diff #40859)

Thanks.

756 ↗

(On Diff #40859)

Thanks Chad.
Actually, I didn't think about other target. But, I think memory operand information is common thing. It is about array reference, pointer information, etc..
For clarity, I tested samething on x86 target. It also shows same percentage (MMO is 0 or 1 == 98%).

MMO Num	MI Count
0	1971
1	11714
2	178
3	24
4	5
5	5
6	3
7	3
8	0
9	0
>=10	1
Total MI Count	13904

Can we just use this code at this time?

For using smallset or unique, we have to develop compare function. I don't think that it's easy.

[flyingforyou]

Addressed Chad's comment.

[mcrosier]

Given your experimental results I think the code is fine as is.

[gberry]

Regarding an MMO compare function, I don't think this would be that much different from the existing MachineMemOperand::operator==.
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]

In D14797#301681, @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.

This sounds very reasonable, IMO.

[flyingforyou]

Thanks, Geoff, Chad.

I will make an another patch.
We can discuss about threshold value.

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) {
+// 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.
+  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,
-                               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.
+mergeMMOsFromMemoryOperations(MachineBasicBlock::iterator MBBIStartPos,
+  // Merge MMOs from memory operations in the common block
   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))
-        MBBICommon->clearMemRefs();
+      mergeMMOs(&*MBBI, &*MBBICommon);
 
     ++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);
+      // Merge MMOs from memory operations as needed.
+      mergeMMOsFromMemoryOperations(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.