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 ---