diff options
author | Rafael Espindola <rafael.espindola@gmail.com> | 2011-06-14 15:31:54 +0000 |
---|---|---|
committer | Rafael Espindola <rafael.espindola@gmail.com> | 2011-06-14 15:31:54 +0000 |
commit | f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4 (patch) | |
tree | e578b0374273e11275f5ed1cbdb39fba289afa51 | |
parent | ebf69c34c480ba0c3fd3aa8f5521ef730db4a20a (diff) | |
download | llvm-f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4.tar.gz llvm-f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4.tar.bz2 llvm-f924dea8ddb74df8d591f8fdc409fc5b8b5e10d4.tar.xz |
Add 132986 back, but avoid non-determinism if a bb address gets reused.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@132995 91177308-0d34-0410-b5e6-96231b3b80d8
-rw-r--r-- | lib/CodeGen/BranchFolding.cpp | 29 | ||||
-rw-r--r-- | lib/CodeGen/BranchFolding.h | 2 | ||||
-rw-r--r-- | test/CodeGen/X86/tail-threshold.ll | 41 |
3 files changed, 67 insertions, 5 deletions
diff --git a/lib/CodeGen/BranchFolding.cpp b/lib/CodeGen/BranchFolding.cpp index 719cd264f6..d95f77e90a 100644 --- a/lib/CodeGen/BranchFolding.cpp +++ b/lib/CodeGen/BranchFolding.cpp @@ -108,6 +108,9 @@ void BranchFolder::RemoveDeadBlock(MachineBasicBlock *MBB) { while (!MBB->succ_empty()) MBB->removeSuccessor(MBB->succ_end()-1); + // Avoid matching if this pointer gets reused. + TriedMerging.erase(MBB); + // Remove the block. MF->erase(MBB); } @@ -171,6 +174,8 @@ bool BranchFolder::OptimizeFunction(MachineFunction &MF, MachineModuleInfo *mmi) { if (!tii) return false; + TriedMerging.clear(); + TII = tii; TRI = tri; MMI = mmi; @@ -799,14 +804,21 @@ 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 +842,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 +905,11 @@ 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 4daf4ecfe5..4ed42c0346 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 0000000000..9541c01a4f --- /dev/null +++ b/test/CodeGen/X86/tail-threshold.ll @@ -0,0 +1,41 @@ +; RUN: llc -march=x86-64 %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 +} |