| BranchFolding.cpp (199481) | BranchFolding.cpp (199511) |
|---|---|
| 1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 27 unchanged lines hidden (view full) --- 36#include "llvm/ADT/Statistic.h" 37#include "llvm/ADT/STLExtras.h" 38#include <algorithm> 39using namespace llvm; 40 41STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 42STATISTIC(NumBranchOpts, "Number of branches optimized"); 43STATISTIC(NumTailMerge , "Number of block tails merged"); | 1//===-- BranchFolding.cpp - Fold machine code branch instructions ---------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// --- 27 unchanged lines hidden (view full) --- 36#include "llvm/ADT/Statistic.h" 37#include "llvm/ADT/STLExtras.h" 38#include <algorithm> 39using namespace llvm; 40 41STATISTIC(NumDeadBlocks, "Number of dead blocks removed"); 42STATISTIC(NumBranchOpts, "Number of branches optimized"); 43STATISTIC(NumTailMerge , "Number of block tails merged"); |
| 44STATISTIC(NumTailDups , "Number of tail duplicated blocks"); 45STATISTIC(NumInstrDups , "Additional instructions due to tail duplication"); 46 |
|
| 44static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 45 cl::init(cl::BOU_UNSET), cl::Hidden); | 47static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 48 cl::init(cl::BOU_UNSET), cl::Hidden); |
| 49 |
|
| 46// Throttle for huge numbers of predecessors (compile speed problems) 47static cl::opt<unsigned> 48TailMergeThreshold("tail-merge-threshold", 49 cl::desc("Max number of predecessors to consider tail merging"), 50 cl::init(150), cl::Hidden); 51 52// Heuristic for tail merging (and, inversely, tail duplication). 53// TODO: This should be replaced with a target query. --- 134 unchanged lines hidden (view full) --- 188 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 189 MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 190 SmallVector<MachineOperand, 4> Cond; 191 if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) 192 MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 193 MadeChange |= OptimizeImpDefsBlock(MBB); 194 } 195 | 50// Throttle for huge numbers of predecessors (compile speed problems) 51static cl::opt<unsigned> 52TailMergeThreshold("tail-merge-threshold", 53 cl::desc("Max number of predecessors to consider tail merging"), 54 cl::init(150), cl::Hidden); 55 56// Heuristic for tail merging (and, inversely, tail duplication). 57// TODO: This should be replaced with a target query. --- 134 unchanged lines hidden (view full) --- 192 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; I++) { 193 MachineBasicBlock *MBB = I, *TBB = 0, *FBB = 0; 194 SmallVector<MachineOperand, 4> Cond; 195 if (!TII->AnalyzeBranch(*MBB, TBB, FBB, Cond, true)) 196 MadeChange |= MBB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty()); 197 MadeChange |= OptimizeImpDefsBlock(MBB); 198 } 199 |
| 196 | |
| 197 bool MadeChangeThisIteration = true; 198 while (MadeChangeThisIteration) { 199 MadeChangeThisIteration = false; 200 MadeChangeThisIteration |= TailMergeBlocks(MF); 201 MadeChangeThisIteration |= OptimizeBranches(MF); 202 MadeChange |= MadeChangeThisIteration; 203 } 204 | 200 bool MadeChangeThisIteration = true; 201 while (MadeChangeThisIteration) { 202 MadeChangeThisIteration = false; 203 MadeChangeThisIteration |= TailMergeBlocks(MF); 204 MadeChangeThisIteration |= OptimizeBranches(MF); 205 MadeChange |= MadeChangeThisIteration; 206 } 207 |
| 205 // Do tail duplication once after tail merging is done. Otherwise it is | 208 // Do tail duplication after tail merging is done. Otherwise it is |
| 206 // tough to avoid situations where tail duplication and tail merging undo 207 // each other's transformations ad infinitum. | 209 // tough to avoid situations where tail duplication and tail merging undo 210 // each other's transformations ad infinitum. |
| 208 MadeChange |= TailDuplicateBlocks(MF); | 211 MadeChangeThisIteration = true; 212 while (MadeChangeThisIteration) { 213 MadeChangeThisIteration = false; 214 MadeChangeThisIteration |= TailDuplicateBlocks(MF); 215 MadeChange |= MadeChangeThisIteration; 216 } |
| 209 210 // See if any jump tables have become mergable or dead as the code generator 211 // did its thing. 212 MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 213 const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 214 if (!JTs.empty()) { 215 // Figure out how these jump tables should be merged. 216 std::vector<unsigned> JTMapping; --- 781 unchanged lines hidden (view full) --- 998} 999 1000/// TailDuplicateBlocks - Look for small blocks that are unconditionally 1001/// branched to and do not fall through. Tail-duplicate their instructions 1002/// into their predecessors to eliminate (dynamic) branches. 1003bool BranchFolder::TailDuplicateBlocks(MachineFunction &MF) { 1004 bool MadeChange = false; 1005 | 217 218 // See if any jump tables have become mergable or dead as the code generator 219 // did its thing. 220 MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); 221 const std::vector<MachineJumpTableEntry> &JTs = JTI->getJumpTables(); 222 if (!JTs.empty()) { 223 // Figure out how these jump tables should be merged. 224 std::vector<unsigned> JTMapping; --- 781 unchanged lines hidden (view full) --- 1006} 1007 1008/// TailDuplicateBlocks - Look for small blocks that are unconditionally 1009/// branched to and do not fall through. Tail-duplicate their instructions 1010/// into their predecessors to eliminate (dynamic) branches. 1011bool BranchFolder::TailDuplicateBlocks(MachineFunction &MF) { 1012 bool MadeChange = false; 1013 |
| 1006 // Make sure blocks are numbered in order 1007 MF.RenumberBlocks(); 1008 | |
| 1009 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 1010 MachineBasicBlock *MBB = I++; 1011 1012 // Only duplicate blocks that end with unconditional branches. 1013 if (CanFallThrough(MBB)) 1014 continue; 1015 1016 MadeChange |= TailDuplicate(MBB, MF); 1017 1018 // If it is dead, remove it. 1019 if (MBB->pred_empty()) { | 1014 for (MachineFunction::iterator I = ++MF.begin(), E = MF.end(); I != E; ) { 1015 MachineBasicBlock *MBB = I++; 1016 1017 // Only duplicate blocks that end with unconditional branches. 1018 if (CanFallThrough(MBB)) 1019 continue; 1020 1021 MadeChange |= TailDuplicate(MBB, MF); 1022 1023 // If it is dead, remove it. 1024 if (MBB->pred_empty()) { |
| 1025 NumInstrDups -= MBB->size(); |
|
| 1020 RemoveDeadBlock(MBB); 1021 MadeChange = true; 1022 ++NumDeadBlocks; 1023 } 1024 } 1025 return MadeChange; 1026} 1027 --- 64 unchanged lines hidden (view full) --- 1092 // Remove PredBB's unconditional branch. 1093 TII->RemoveBranch(*PredBB); 1094 // Clone the contents of TailBB into PredBB. 1095 for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end(); 1096 I != E; ++I) { 1097 MachineInstr *NewMI = MF.CloneMachineInstr(I); 1098 PredBB->insert(PredBB->end(), NewMI); 1099 } | 1026 RemoveDeadBlock(MBB); 1027 MadeChange = true; 1028 ++NumDeadBlocks; 1029 } 1030 } 1031 return MadeChange; 1032} 1033 --- 64 unchanged lines hidden (view full) --- 1098 // Remove PredBB's unconditional branch. 1099 TII->RemoveBranch(*PredBB); 1100 // Clone the contents of TailBB into PredBB. 1101 for (MachineBasicBlock::iterator I = TailBB->begin(), E = TailBB->end(); 1102 I != E; ++I) { 1103 MachineInstr *NewMI = MF.CloneMachineInstr(I); 1104 PredBB->insert(PredBB->end(), NewMI); 1105 } |
| 1106 NumInstrDups += TailBB->size() - 1; // subtract one for removed branch |
|
| 1100 1101 // Update the CFG. 1102 PredBB->removeSuccessor(PredBB->succ_begin()); 1103 assert(PredBB->succ_empty() && 1104 "TailDuplicate called on block with multiple successors!"); 1105 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 1106 E = TailBB->succ_end(); I != E; ++I) 1107 PredBB->addSuccessor(*I); 1108 1109 Changed = true; | 1107 1108 // Update the CFG. 1109 PredBB->removeSuccessor(PredBB->succ_begin()); 1110 assert(PredBB->succ_empty() && 1111 "TailDuplicate called on block with multiple successors!"); 1112 for (MachineBasicBlock::succ_iterator I = TailBB->succ_begin(), 1113 E = TailBB->succ_end(); I != E; ++I) 1114 PredBB->addSuccessor(*I); 1115 1116 Changed = true; |
| 1117 ++NumTailDups; |
|
| 1110 } 1111 1112 // If TailBB was duplicated into all its predecessors except for the prior 1113 // block, which falls through unconditionally, move the contents of this 1114 // block into the prior block. 1115 MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(TailBB)); 1116 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 1117 SmallVector<MachineOperand, 4> PriorCond; --- 381 unchanged lines hidden --- | 1118 } 1119 1120 // If TailBB was duplicated into all its predecessors except for the prior 1121 // block, which falls through unconditionally, move the contents of this 1122 // block into the prior block. 1123 MachineBasicBlock &PrevBB = *prior(MachineFunction::iterator(TailBB)); 1124 MachineBasicBlock *PriorTBB = 0, *PriorFBB = 0; 1125 SmallVector<MachineOperand, 4> PriorCond; --- 381 unchanged lines hidden --- |