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 |
47static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge", 48 cl::init(cl::BOU_UNSET), cl::Hidden); |
49 |
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 |
200 bool MadeChangeThisIteration = true; 201 while (MadeChangeThisIteration) { 202 MadeChangeThisIteration = false; 203 MadeChangeThisIteration |= TailMergeBlocks(MF); 204 MadeChangeThisIteration |= OptimizeBranches(MF); 205 MadeChange |= MadeChangeThisIteration; 206 } 207 |
208 // Do tail duplication after tail merging is done. Otherwise it is |
209 // tough to avoid situations where tail duplication and tail merging undo 210 // each other's transformations ad infinitum. |
211 MadeChangeThisIteration = true; 212 while (MadeChangeThisIteration) { 213 MadeChangeThisIteration = false; 214 MadeChangeThisIteration |= TailDuplicateBlocks(MF); 215 MadeChange |= MadeChangeThisIteration; 216 } |
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 |
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(); |
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 |
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; |
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 --- |