57 #define DEBUG_TYPE "x86-condbr-folding" 59 STATISTIC(NumFixedCondBrs,
"Number of x86 condbr folded");
67 StringRef getPassName()
const override {
return "X86 CondBr Folding"; }
82 INITIALIZE_PASS(X86CondBrFoldingPass,
"X86CondBrFolding",
"X86CondBrFolding",
false,
false)
85 return new X86CondBrFoldingPass();
90 struct TargetMBBInfo {
103 class X86CondBrFolding {
108 :
TII(TII), MBPI(MBPI), MF(MF) {}
115 std::vector<std::unique_ptr<TargetMBBInfo>> MBBInfos;
126 static bool analyzeCompare(
const MachineInstr &
MI,
unsigned &SrcReg,
141 bool X86CondBrFolding::findPath(
143 TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
144 assert(MBBInfo &&
"Expecting a candidate MBB");
145 int CmpValue = MBBInfo->CmpValue;
150 TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
151 if (!PredMBBInfo || PredMBBInfo->SrcReg != MBBInfo->SrcReg)
154 assert(SaveMBB == PredMBBInfo->TBB || SaveMBB == PredMBBInfo->FBB);
155 bool IsFalseBranch = (SaveMBB == PredMBBInfo->FBB);
159 int PredCmpValue = PredMBBInfo->CmpValue;
160 bool ValueCmpTrue = ((CmpValue < PredCmpValue && CC ==
X86::COND_L) ||
164 if (!(ValueCmpTrue ^ IsFalseBranch)) {
171 if ((CmpValue == PredCmpValue) ||
172 (CmpValue == PredCmpValue - 1 && CC ==
X86::COND_L) ||
173 (CmpValue == PredCmpValue + 1 && CC ==
X86::COND_G))
177 if (PredMBB->
pred_size() != 1 || !PredMBBInfo->CmpBrOnly)
189 if (NewMBB == OldMBB)
192 MI != ME &&
MI->isPHI(); ++
MI)
193 for (
unsigned i = 2, e =
MI->getNumOperands() + 1; i != e; i += 2) {
195 if (MO.
getMBB() == OldMBB)
215 return MI.getOpcode() == X86::JMP_1;
224 TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
226 if (MBBInfo->TBB == OrigDest) {
227 BrMI = MBBInfo->BrInstr;
232 MBBInfo->TBB = NewDest;
238 MBBInfo->FBB = NewDest;
244 setBranchProb(MBB, NewDest, MBPI->getEdgeProbability(MBB, OrigDest));
250 TargetMBBInfo *MBBInfo = getMBBInfo(MBB);
251 if (!MBBInfo->Modified)
258 .addMBB(MBBInfo->TBB);
264 .addMBB(MBBInfo->FBB);
265 MBB->
erase(UncondBrI);
266 MBBInfo->Modified =
false;
283 void X86CondBrFolding::optimizeCondBr(
287 TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
288 assert(MBBInfo &&
"Expecting a candidate MBB");
294 TargetMBBInfo *PredMBBInfo = getMBBInfo(PredMBB);
295 assert(PredMBBInfo &&
"Expecting a candidate MBB");
296 if (PredMBBInfo->Modified)
297 fixupModifiedCond(PredMBB);
298 CC = PredMBBInfo->BranchCode;
302 replaceBrDest(PredMBB, &MBB, MBBInfo->FBB);
305 TargetMBBInfo *RootMBBInfo = getMBBInfo(RootMBB);
306 assert(RootMBBInfo &&
"Expecting a candidate MBB");
307 if (RootMBBInfo->Modified)
308 fixupModifiedCond(RootMBB);
309 CC = RootMBBInfo->BranchCode;
327 .addMBB(RootMBBInfo->FBB);
331 TII->get(X86::JMP_1))
335 RootMBB->
erase(UncondBrI);
337 replaceBrDest(RootMBB, RootMBBInfo->TBB, TargetMBB);
342 if (RootMBBInfo->CmpValue != MBBInfo->CmpValue) {
345 RootMBB->
insert(RootMBBInfo->CmpInstr, NewCmp);
346 RootMBBInfo->CmpInstr->eraseFromParent();
352 for (
auto &
I : BranchPath) {
357 Prob = MBPI->getEdgeProbability(ThisMBB, NextMBB);
360 TargetProb = Prob * TargetProb;
361 Prob = Prob - TargetProb;
363 if (ThisMBB == RootMBB) {
367 if (ThisMBB == RootMBB)
374 fixBranchProb(MBBInfo->FBB);
381 MBBInfos[RootMBB->
getNumber()] =
nullptr;
383 LLVM_DEBUG(
dbgs() <<
"After optimization:\nRootMBB is: " << *RootMBB <<
"\n");
384 if (BranchPath.
size() > 1)
390 bool X86CondBrFolding::optimize() {
391 bool Changed =
false;
392 LLVM_DEBUG(
dbgs() <<
"***** X86CondBr Folding on Function: " << MF.getName()
395 MBBInfos.resize(MF.getNumBlockIDs());
397 MBBInfos[MBB.
getNumber()] = analyzeMBB(MBB);
399 for (
auto &MBB : MF) {
400 TargetMBBInfo *MBBInfo = getMBBInfo(&MBB);
401 if (!MBBInfo || !MBBInfo->CmpBrOnly)
406 <<
" CmpValue: " << MBBInfo->CmpValue <<
"\n");
408 if (!findPath(&MBB, BranchPath))
412 LLVM_DEBUG(
dbgs() <<
"Found one path (len=" << BranchPath.size() <<
"):\n");
415 for (
auto I = BranchPath.rbegin();
I != BranchPath.rend(); ++
I, ++
Index) {
417 TargetMBBInfo *PMBBInfo = getMBBInfo(PMBB);
418 LLVM_DEBUG(
dbgs() <<
"Path MBB (" << Index <<
" of " << BranchPath.size()
419 <<
") is " << *PMBB);
421 <<
" Val=" << PMBBInfo->CmpValue
422 <<
" CmpBrOnly=" << PMBBInfo->CmpBrOnly <<
"\n\n");
425 optimizeCondBr(MBB, BranchPath);
428 NumFixedCondBrs += RemoveList.size();
429 for (
auto MBBI : RemoveList) {
430 while (!MBBI->succ_empty())
431 MBBI->removeSuccessor(MBBI->succ_end() - 1);
433 MBBI->eraseFromParent();
440 bool X86CondBrFolding::analyzeCompare(
const MachineInstr &
MI,
unsigned &SrcReg,
442 unsigned SrcRegIndex = 0;
443 unsigned ValueIndex = 0;
483 std::unique_ptr<TargetMBBInfo>
502 while (I != MBB.
begin()) {
504 if (I->isDebugValue())
506 if (I->getOpcode() == X86::JMP_1) {
509 FBB = I->getOperand(0).getMBB();
527 TBB = I->getOperand(0).getMBB();
531 if (analyzeCompare(*I, SrcReg, CmpValue)) {
541 if (!TBB || !FBB || !CmpInstr)
553 if (CmpValue == INT_MAX)
560 if (CmpValue == INT_MIN)
570 return llvm::make_unique<TargetMBBInfo>(TargetMBBInfo{
571 TBB, FBB, BrInstr, CmpInstr, CC, SrcReg, CmpValue, Modified, CmpBrOnly});
580 &getAnalysis<MachineBranchProbabilityInfo>();
582 X86CondBrFolding CondBr(TII, MBPI, MF);
583 return CondBr.optimize();
bool hasSuccessorProbabilities() const
Return true if any of the successors have probabilities attached to them.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
instr_iterator instr_begin()
instr_iterator instr_end()
MachineBasicBlock * getMBB() const
This class represents lattice values for constants.
static bool setBranchProb(MachineBasicBlock *MBB, MachineBasicBlock *SuccMBB, BranchProbability Prob)
const X86InstrInfo * getInstrInfo() const override
void push_back(const T &Elt)
unsigned getReg() const
getReg - Returns the register number.
STATISTIC(NumFunctions, "Total number of functions")
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
AnalysisUsage & addRequired()
instr_iterator erase(instr_iterator I)
Remove an instruction from the instruction list and delete it.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
const HexagonInstrInfo * TII
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
CondCode getCondFromBranchOpc(unsigned Opc)
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
void initializeX86CondBrFoldingPassPass(PassRegistry &)
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
void setSuccProbability(succ_iterator I, BranchProbability Prob)
Set successor probability of a given iterator.
instr_iterator insert(instr_iterator I, MachineInstr *M)
Insert MI into the instruction list before I, possibly inside a bundle.
void normalizeSuccProbs()
Normalize probabilities of all successors so that the sum of them becomes one.
MachineInstrBuilder BuildMI(MachineFunction &MF, const DebugLoc &DL, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
DebugLoc findDebugLoc(instr_iterator MBBI)
Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE and DBG_LABEL instructions...
void setMBB(MachineBasicBlock *MBB)
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
auto find_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly...
static unsigned GetCondBranchFromCond(XCore::CondCode CC)
GetCondBranchFromCond - Return the Branch instruction opcode that matches the cc. ...
succ_iterator succ_begin()
pred_iterator pred_begin()
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
bool threewayBranchProfitable() const
void addSuccessor(MachineBasicBlock *Succ, BranchProbability Prob=BranchProbability::getUnknown())
Add Succ as a successor of this MachineBasicBlock.
MachineOperand class - Representation of each machine instruction operand.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small...
MachineInstr * getInstr() const
If conversion operators fail, use this method to get the MachineInstr explicitly. ...
unsigned pred_size() const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
static MachineBasicBlock::iterator findUncondBrI(MachineBasicBlock *MBB)
unsigned succ_size() const
Representation of each machine instruction.
static void fixPHIsInSucc(MachineBasicBlock *MBB, MachineBasicBlock *OldMBB, MachineBasicBlock *NewMBB)
void push_back(MachineInstr *MI)
bool isSuccessor(const MachineBasicBlock *MBB) const
Return true if the specified MBB is a successor of this block.
FunctionPass * createX86CondBrFolding()
Return a pass that folds conditional branch jumps.
MachineInstr * removeFromParent()
Unlink 'this' from the containing basic block, and return it without deleting it. ...
void removeSuccessor(MachineBasicBlock *Succ, bool NormalizeSuccProbs=false)
Remove successor from the successors list of this MachineBasicBlock.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StringRef - Represent a constant reference to a string, i.e.
const MachineOperand & getOperand(unsigned i) const