1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===----------- BreakCriticalMachineEdges - Break critical edges ---------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by Fernando Pereira and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===---------------------------------------------------------------------===//
//
// Break all of the critical edges in the CFG by inserting a dummy basic block.
// This pass may be "required" by passes that cannot deal with critical edges.
// Notice that this pass invalidates the CFG, because the same BasicBlock is
// used as parameter for the src MachineBasicBlock and the new dummy
// MachineBasicBlock.
//
//===---------------------------------------------------------------------===//
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineJumpTableInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/Compiler.h"
using namespace llvm;
namespace {
struct VISIBILITY_HIDDEN BreakCriticalMachineEdges :
public MachineFunctionPass {
static char ID; // Pass identification
BreakCriticalMachineEdges() : MachineFunctionPass((intptr_t)&ID) {}
bool runOnMachineFunction(MachineFunction& Fn);
void splitCriticalEdge(MachineBasicBlock* A, MachineBasicBlock* B);
};
char BreakCriticalMachineEdges::ID = 0;
RegisterPass<BreakCriticalMachineEdges> X("critical-machine-edges",
"Break critical machine code edges");
}
const PassInfo *llvm::BreakCriticalMachineEdgesID = X.getPassInfo();
void BreakCriticalMachineEdges::splitCriticalEdge(MachineBasicBlock* src,
MachineBasicBlock* dst) {
const BasicBlock* srcBB = src->getBasicBlock();
MachineBasicBlock* crit_mbb = new MachineBasicBlock(srcBB);
// modify the llvm control flow graph
src->removeSuccessor(dst);
src->addSuccessor(crit_mbb);
crit_mbb->addSuccessor(dst);
// insert the new block into the machine function.
src->getParent()->getBasicBlockList().insert(src->getParent()->end(),
crit_mbb);
// insert a unconditional branch linking the new block to dst
const TargetMachine& TM = src->getParent()->getTarget();
const TargetInstrInfo* TII = TM.getInstrInfo();
std::vector<MachineOperand> emptyConditions;
TII->InsertBranch(*crit_mbb, dst, (MachineBasicBlock*)0, emptyConditions);
// modify every branch in src that points to dst to point to the new
// machine basic block instead:
MachineBasicBlock::iterator mii = src->end();
bool found_branch = false;
while (mii != src->begin()) {
mii--;
// if there are no more branches, finish the loop
if (!TII->isTerminatorInstr(mii->getOpcode())) {
break;
}
// Scan the operands of this branch, replacing any uses of dst with
// crit_mbb.
for (unsigned i = 0, e = mii->getNumOperands(); i != e; ++i) {
MachineOperand & mo = mii->getOperand(i);
if (mo.isMachineBasicBlock() &&
mo.getMachineBasicBlock() == dst) {
found_branch = true;
mo.setMachineBasicBlock(crit_mbb);
}
}
}
// TODO: This is tentative. It may be necessary to fix this code. Maybe
// I am inserting too many gotos, but I am trusting that the asm printer
// will optimize the unnecessary gotos.
if(!found_branch) {
TII->InsertBranch(*src, crit_mbb, (MachineBasicBlock*)0, emptyConditions);
}
/// Change all the phi functions in dst, so that the incoming block be
/// crit_mbb, instead of src
for(mii = dst->begin(); mii != dst->end(); mii++) {
/// the first instructions are always phi functions.
if(mii->getOpcode() != TargetInstrInfo::PHI)
break;
for (unsigned u = 0; u != mii->getNumOperands(); ++u)
if (mii->getOperand(u).isMachineBasicBlock() &&
mii->getOperand(u).getMachineBasicBlock() == src)
mii->getOperand(u).setMachineBasicBlock(crit_mbb);
}
}
bool BreakCriticalMachineEdges::runOnMachineFunction(MachineFunction& F) {
std::vector<MachineBasicBlock *> SourceBlocks;
std::vector<MachineBasicBlock *> DestBlocks;
for(MachineFunction::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) {
for(MachineBasicBlock::succ_iterator SI = FI->succ_begin(),
SE = FI->succ_end(); SI != SE; ++SI) {
// predecessor with multiple successors, successor with multiple
// predecessors.
if (FI->succ_size() > 1 && (*SI)->pred_size() > 1) {
SourceBlocks.push_back(FI);
DestBlocks.push_back(*SI);
}
}
}
for(unsigned u = 0; u < SourceBlocks.size() > 0; u++)
splitCriticalEdge(SourceBlocks[u], DestBlocks[u]);
return false;
}
|
