From 3a42565ccb169ec4acf79698b38d7da880f13364 Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Tue, 14 Jun 2011 04:41:17 +0000
Subject: [PATCH] Make the threshold used by branch folding softer. Before we
 would get a sharp all or nothing transition when one extra predecessor was
 added. Now we still test first ones for merging.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132974 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/BranchFolding.cpp      | 26 +++++++++++++++++++-----
 lib/CodeGen/BranchFolding.h        |  2 ++
 test/CodeGen/X86/tail-threshold.ll | 41 ++++++++++++++++++++++++++++++++++++++
 3 files changed, 64 insertions(+), 5 deletions(-)
 create mode 100644 test/CodeGen/X86/tail-threshold.ll

diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp
index 719cd264f68..b43884ebf2f 100644
--- a/lib/CodeGen/BranchFolding.cpp
+++ b/lib/CodeGen/BranchFolding.cpp
@@ -799,14 +799,22 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 
   // First find blocks with no successors.
   MergePotentials.clear();
-  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end();
+       I != E && MergePotentials.size() < TailMergeThreshold; ++I) {
+    if (TriedMerging.count(I))
+      continue;
     if (I->succ_empty())
       MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(I), I));
   }
 
+  // If this is a large problem, avoid visiting the same basic blocks
+  // multiple times.
+  if (MergePotentials.size() == TailMergeThreshold)
+    for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
+      TriedMerging.insert(MergePotentials[i].getBlock());
+
   // See if we can do any tail merging on those.
-  if (MergePotentials.size() < TailMergeThreshold &&
-      MergePotentials.size() >= 2)
+  if (MergePotentials.size() >= 2)
     MadeChange |= TryTailMergeBlocks(NULL, NULL);
 
   // Look at blocks (IBB) with multiple predecessors (PBB).
@@ -830,15 +838,17 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
 
   for (MachineFunction::iterator I = llvm::next(MF.begin()), E = MF.end();
        I != E; ++I) {
-    if (I->pred_size() >= 2 && I->pred_size() < TailMergeThreshold) {
+    if (I->pred_size() >= 2) {
       SmallPtrSet<MachineBasicBlock *, 8> UniquePreds;
       MachineBasicBlock *IBB = I;
       MachineBasicBlock *PredBB = prior(I);
       MergePotentials.clear();
       for (MachineBasicBlock::pred_iterator P = I->pred_begin(),
                                             E2 = I->pred_end();
-           P != E2; ++P) {
+           P != E2 && MergePotentials.size() < TailMergeThreshold; ++P) {
         MachineBasicBlock *PBB = *P;
+        if (TriedMerging.count(PBB))
+          continue;
         // Skip blocks that loop to themselves, can't tail merge these.
         if (PBB == IBB)
           continue;
@@ -891,6 +901,12 @@ bool BranchFolder::TailMergeBlocks(MachineFunction &MF) {
           MergePotentials.push_back(MergePotentialsElt(HashEndOfMBB(PBB), *P));
         }
       }
+      // If this is a large problem, avoid visiting the same basic blocks
+      // multiple times.
+      if (MergePotentials.size() == TailMergeThreshold)
+        for (unsigned i = 0, e = MergePotentials.size(); i != e; ++i)
+          TriedMerging.insert(MergePotentials[i].getBlock());
+
       if (MergePotentials.size() >= 2)
         MadeChange |= TryTailMergeBlocks(IBB, PredBB);
       // Reinsert an unconditional branch if needed.
diff --git a/lib/CodeGen/BranchFolding.h b/lib/CodeGen/BranchFolding.h
index 4daf4ecfe59..4ed42c03464 100644
--- a/lib/CodeGen/BranchFolding.h
+++ b/lib/CodeGen/BranchFolding.h
@@ -10,6 +10,7 @@
 #ifndef LLVM_CODEGEN_BRANCHFOLDING_HPP
 #define LLVM_CODEGEN_BRANCHFOLDING_HPP
 
+#include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/CodeGen/MachineBasicBlock.h"
 #include <vector>
 
@@ -47,6 +48,7 @@ namespace llvm {
     };
     typedef std::vector<MergePotentialsElt>::iterator MPIterator;
     std::vector<MergePotentialsElt> MergePotentials;
+    SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
 
     class SameTailElt {
       MPIterator MPIter;
diff --git a/test/CodeGen/X86/tail-threshold.ll b/test/CodeGen/X86/tail-threshold.ll
new file mode 100644
index 00000000000..17e22d9dd9e
--- /dev/null
+++ b/test/CodeGen/X86/tail-threshold.ll
@@ -0,0 +1,41 @@
+; RUN: llc %s -stats -tail-merge-threshold 2 -o /dev/null |& FileCheck %s
+
+; Test that we still do some merging if a block has more than
+; tail-merge-threshold predecessors.
+
+; CHECK: 2 branchfolding   - Number of block tails merged
+
+declare void @bar()
+
+define void @foo(i32 %xxx) {
+entry:
+  switch i32 %xxx, label %bb4 [
+    i32 0, label %bb0
+    i32 1, label %bb1
+    i32 2, label %bb2
+    i32 3, label %bb3
+  ]
+
+bb0:
+  call void @bar()
+  br label %bb5
+
+bb1:
+ call void @bar()
+ br label %bb5
+
+bb2:
+  call void @bar()
+  br label %bb5
+
+bb3:
+  call void @bar()
+  br label %bb5
+
+bb4:
+  call void @bar()
+  br label %bb5
+
+bb5:
+  ret void
+}
-- 
2.11.0