Changes in directory llvm/lib/CodeGen:
BranchFolding.cpp updated: 1.61 -> 1.62
---
Log message:
Implement smarter algorithm for choosing which blocks to tail-merge.
See test/CodeGen/X86/test-pic-jtbl.ll for a case where it works well;
shaves another 10K off our favorite benchmark. I was hesitant about
this because of compile speed, but seems to do OK on a bootstrap.
---
Diffs of the changes: (+45 -30)
BranchFolding.cpp | 75 ++++++++++++++++++++++++++++++++----------------------
1 files changed, 45 insertions(+), 30 deletions(-)
Index: llvm/lib/CodeGen/BranchFolding.cpp
diff -u llvm/lib/CodeGen/BranchFolding.cpp:1.61
llvm/lib/CodeGen/BranchFolding.cpp:1.62
--- llvm/lib/CodeGen/BranchFolding.cpp:1.61 Thu May 31 16:54:00 2007
+++ llvm/lib/CodeGen/BranchFolding.cpp Fri Jun 1 18:02:45 2007
@@ -466,43 +466,58 @@
continue;
}
- // Look through all the blocks that have the same hash as this one, and
- // find the one that has the largest number of instructions in common.
- // Since instructions may get combined later (e.g. single stores into
+ // Look through all the pairs of blocks that have the same hash as this
+ // one, and find the pair that has the largest number of instructions in
+ // common.
+ // Since instructions may get combined later (e.g. single stores into
// store multiple) this measure is not particularly accurate.
- MachineBasicBlock::iterator BBI1, BBI2;
+ MachineBasicBlock::iterator BBI1, BBI2;
- unsigned FoundMatch = ~0U;
+ unsigned FoundI = ~0U, FoundJ = ~0U;
unsigned maxCommonTailLength = 0U;
- for (int i = MergePotentials.size()-2;
+ for (int i = MergePotentials.size()-1;
i != -1 && MergePotentials[i].first == CurHash; --i) {
- MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
- unsigned CommonTailLen = ComputeCommonTailLength(CurMBB,
- MergePotentials[i].second,
- TrialBBI1, TrialBBI2);
- if (CommonTailLen >= minCommonTailLength &&
- CommonTailLen >= maxCommonTailLength) {
- FoundMatch = i;
- maxCommonTailLength = CommonTailLen;
- BBI1 = TrialBBI1;
- BBI2 = TrialBBI2;
- }
- }
-
- // If we didn't find anything that has at least minCommonTailLength
- // instructions matching this one, bail out.
- if (FoundMatch == ~0U) {
- // Put the unconditional branch back, if we need one.
- if (SuccBB && CurMBB != PredBB)
- FixTail(CurMBB, SuccBB, TII);
- MergePotentials.pop_back();
+ for (int j = i-1;
+ j != -1 && MergePotentials[j].first == CurHash; --j) {
+ MachineBasicBlock::iterator TrialBBI1, TrialBBI2;
+ unsigned CommonTailLen = ComputeCommonTailLength(
+ MergePotentials[i].second,
+ MergePotentials[j].second,
+ TrialBBI1, TrialBBI2);
+ if (CommonTailLen >= minCommonTailLength &&
+ CommonTailLen > maxCommonTailLength) {
+ FoundI = i;
+ FoundJ = j;
+ maxCommonTailLength = CommonTailLen;
+ BBI1 = TrialBBI1;
+ BBI2 = TrialBBI2;
+ }
+ }
+ }
+
+ // If we didn't find any pair that has at least minCommonTailLength
+ // instructions in common, bail out. All entries with this
+ // hash code can go away now.
+ if (FoundI == ~0U) {
+ for (int i = MergePotentials.size()-1;
+ i != -1 && MergePotentials[i].first == CurHash; --i) {
+ // Put the unconditional branch back, if we need one.
+ CurMBB = MergePotentials[i].second;
+ if (SuccBB && CurMBB != PredBB)
+ FixTail(CurMBB, SuccBB, TII);
+ MergePotentials.pop_back();
+ }
continue;
}
-
- // Otherwise, move the matching block to the right position.
- if (FoundMatch != MergePotentials.size()-2)
- std::swap(MergePotentials[FoundMatch], *(MergePotentials.end()-2));
+ // Otherwise, move the block(s) to the right position(s). So that
+ // BBI1/2 will be valid, the last must be I and the next-to-last J.
+ if (FoundI != MergePotentials.size()-1)
+ std::swap(MergePotentials[FoundI], *(MergePotentials.end()-1));
+ if (FoundJ != MergePotentials.size()-2)
+ std::swap(MergePotentials[FoundJ], *(MergePotentials.end()-2));
+
+ CurMBB = (MergePotentials.end()-1)->second;
MachineBasicBlock *MBB2 = (MergePotentials.end()-2)->second;
// If neither block is the entire common tail, split the tail of one block
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
