CodeGen: Tail-duplicate longer blocks that end with indirect branches.

[iteratee]

Summary

Specifically, this is currently done for tail-duplication before
register allocation, and is now done for tail-duplication during layout.

A similar change was necessary for tail-merging during layout to prevent
the two from being in conflict.

[davidxl]

lib/CodeGen/TailDuplicator.cpp

569

I asked the question before: can you use back.isIndirectBranch() && !back.isReturn() ?

[iteratee]

lib/CodeGen/TailDuplicator.cpp

569

Sorry if the reply got lost in splitting this out.
I checked, and no, that's not something that works. There are platforms where lowered returns don't set isReturn()

It's unfortunate, but it's what's there.

[davidxl]

lgtm

[iteratee]

It's been a while, because of dependencies. Are you still fine with this going in?

[davidxl]

Need a test case.

Also do you have any performance data?

lib/CodeGen/BranchFolding.cpp

709

!empty()

713

This basically disabled tailMerging for blocks with indirect branch. Is there a way to override that? If not, why not simply disable TailMerge for such blocks directly?

lib/CodeGen/BranchFolding.cpp

 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineJumpTableInfo.h"
 #include "llvm/CodeGen/MachineMemOperand.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineModuleInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/Passes.h"
+#include "llvm/CodeGen/TailDuplicator.h"
 #include "llvm/CodeGen/TargetPassConfig.h"
 #include "llvm/IR/Function.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Target/TargetInstrInfo.h"
 #include "llvm/Target/TargetRegisterInfo.h"
unsigned BranchFolder::ComputeSameTails(unsigned CurHash,
   SameTails.clear();
   MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
   MPIterator HighestMPIter = std::prev(MergePotentials.end());
   for (MPIterator CurMPIter = std::prev(MergePotentials.end()),
                   B = MergePotentials.begin();
        CurMPIter != B && CurMPIter->getHash() == CurHash; --CurMPIter) {
     for (MPIterator I = std::prev(CurMPIter); I->getHash() == CurHash; --I) {
       unsigned CommonTailLen;
+      unsigned MinCommonTailLengthInside = MinCommonTailLength;
+      // Prefer to leave indirect branches duplicated after placement.
+      if (AfterBlockPlacement) {
+        MachineBasicBlock &Block1 = *CurMPIter->getBlock();
+        if (Block1.empty())
+          // Look for indirect local branches, and try to avoid merging them
+          // when merging during layout. Having multiple copies of these
+          // branches allows for better branch prediction.
+          if (Block1.back().isIndirectBranch() && Block1.succ_size() != 0)
+            MinCommonTailLengthInside = TailDupIndirectBranchSize + 1;
+      }
       if (ProfitableToMerge(CurMPIter->getBlock(), I->getBlock(),
-                            MinCommonTailLength,
+                            MinCommonTailLengthInside,
                             CommonTailLen, TrialBBI1, TrialBBI2,
                             SuccBB, PredBB,
                             FuncletMembership,
                             AfterBlockPlacement)) {
         if (CommonTailLen > maxCommonTailLength) {
           SameTails.clear();
           maxCommonTailLength = CommonTailLen;
           HighestMPIter = CurMPIter;

lib/CodeGen/TailDuplicator.cpp

if (TII->analyzeBranch(TailBB, PredTBB, PredFBB, PredCond, true)
     return false;
 
   // If the target has hardware branch prediction that can handle indirect
   // branches, duplicating them can often make them predictable when there
   // are common paths through the code.  The limit needs to be high enough
   // to allow undoing the effects of tail merging and other optimizations
   // that rearrange the predecessors of the indirect branch.
 
-  bool HasIndirectbr = false;
-  if (!TailBB.empty())
-    HasIndirectbr = TailBB.back().isIndirectBranch();
+  bool HasLocalIndirectbr = false;
+  if (!TailBB.empty()) {
+    MachineInstr &back = TailBB.back();
+    // On some platforms return instructions are marked as indirect branches and
+    // not as return instructions. What we're actually looking for is indirect
+    // branches that occur within a function, so we check for local successors.
+    HasLocalIndirectbr = back.isIndirectBranch() && TailBB.succ_size() != 0;
+  }
 
-  if (HasIndirectbr && PreRegAlloc)
+  if (HasLocalIndirectbr && (PreRegAlloc || LayoutMode))
     MaxDuplicateCount = TailDupIndirectBranchSize;
 
   // Check the instructions in the block to determine whether tail-duplication
   // is invalid or unlikely to be profitable.
   unsigned InstrCount = 0;
   for (MachineInstr &MI : TailBB) {
     // Non-duplicable things shouldn't be tail-duplicated.
     if (MI.isNotDuplicable())
for (auto &I : *SB) {
       unsigned Idx = getPHISrcRegOpIdx(&I, &TailBB);
       assert(Idx != 0);
       MachineOperand &PU = I.getOperand(Idx);
       if (PU.getSubReg() != 0)
         return false;
     }
   }
 
-  if (HasIndirectbr && PreRegAlloc)
+  if (HasLocalIndirectbr && PreRegAlloc)
     return true;
 
   if (IsSimple)
     return true;
 
   if (!PreRegAlloc)
     return true;