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");
44static cl::opt<cl::boolOrDefault> FlagEnableTailMerge("enable-tail-merge",
45 cl::init(cl::BOU_UNSET), cl::Hidden);
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
196
197 bool MadeChangeThisIteration = true;
198 while (MadeChangeThisIteration) {
199 MadeChangeThisIteration = false;
200 MadeChangeThisIteration |= TailMergeBlocks(MF);
201 MadeChangeThisIteration |= OptimizeBranches(MF);
202 MadeChange |= MadeChangeThisIteration;
203 }
204
205 // Do tail duplication once 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.
208 MadeChange |= TailDuplicateBlocks(MF);
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
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()) {
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 }
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;
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 ---