summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--llvm/include/llvm/CodeGen/MachineBasicBlock.h19
-rw-r--r--llvm/lib/CodeGen/EarlyIfConversion.cpp6
-rw-r--r--llvm/lib/CodeGen/IfConversion.cpp12
-rw-r--r--llvm/lib/CodeGen/MachineBasicBlock.cpp26
-rw-r--r--llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp1
-rw-r--r--llvm/lib/CodeGen/TailDuplication.cpp1
-rw-r--r--llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp4
-rw-r--r--llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp16
-rw-r--r--llvm/lib/Target/ARM/ARMISelLowering.cpp1
-rw-r--r--llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp3
-rw-r--r--llvm/lib/Target/Mips/MipsLongBranch.cpp2
-rw-r--r--llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp4
12 files changed, 68 insertions, 27 deletions
diff --git a/llvm/include/llvm/CodeGen/MachineBasicBlock.h b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
index 16a349fdeb1..3d58c499823 100644
--- a/llvm/include/llvm/CodeGen/MachineBasicBlock.h
+++ b/llvm/include/llvm/CodeGen/MachineBasicBlock.h
@@ -454,19 +454,32 @@ public:
void setSuccProbability(succ_iterator I, BranchProbability Prob);
/// Normalize probabilities of all successors so that the sum of them becomes
- /// one.
+ /// one. This is usually done when the current update on this MBB is done, and
+ /// the sum of its successors' probabilities is not guaranteed to be one. The
+ /// user is responsible for the correct use of this function.
+ /// MBB::removeSuccessor() has an option to do this automatically.
void normalizeSuccProbs() {
BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
}
+ /// Validate successors' probabilities and check if the sum of them is
+ /// approximate one. This only works in DEBUG mode.
+ void validateSuccProbs() const;
+
/// Remove successor from the successors list of this MachineBasicBlock. The
/// Predecessors list of Succ is automatically updated.
- void removeSuccessor(MachineBasicBlock *Succ);
+ /// If NormalizeSuccProbs is true, then normalize successors' probabilities
+ /// after the successor is removed.
+ void removeSuccessor(MachineBasicBlock *Succ,
+ bool NormalizeSuccProbs = false);
/// Remove specified successor from the successors list of this
/// MachineBasicBlock. The Predecessors list of Succ is automatically updated.
+ /// If NormalizeSuccProbs is true, then normalize successors' probabilities
+ /// after the successor is removed.
/// Return the iterator to the element after the one removed.
- succ_iterator removeSuccessor(succ_iterator I);
+ succ_iterator removeSuccessor(succ_iterator I,
+ bool NormalizeSuccProbs = false);
/// Replace successor OLD with NEW and update probability info.
void replaceSuccessor(MachineBasicBlock *Old, MachineBasicBlock *New);
diff --git a/llvm/lib/CodeGen/EarlyIfConversion.cpp b/llvm/lib/CodeGen/EarlyIfConversion.cpp
index fbc4d97c498..f3536d74111 100644
--- a/llvm/lib/CodeGen/EarlyIfConversion.cpp
+++ b/llvm/lib/CodeGen/EarlyIfConversion.cpp
@@ -538,11 +538,11 @@ void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
// Fix up the CFG, temporarily leave Head without any successors.
Head->removeSuccessor(TBB);
- Head->removeSuccessor(FBB);
+ Head->removeSuccessor(FBB, true);
if (TBB != Tail)
- TBB->removeSuccessor(Tail);
+ TBB->removeSuccessor(Tail, true);
if (FBB != Tail)
- FBB->removeSuccessor(Tail);
+ FBB->removeSuccessor(Tail, true);
// Fix up Head's terminators.
// It should become a single branch or a fallthrough.
diff --git a/llvm/lib/CodeGen/IfConversion.cpp b/llvm/lib/CodeGen/IfConversion.cpp
index 71bd61a15cb..a1835fa3297 100644
--- a/llvm/lib/CodeGen/IfConversion.cpp
+++ b/llvm/lib/CodeGen/IfConversion.cpp
@@ -1113,7 +1113,7 @@ bool IfConverter::IfConvertSimple(BBInfo &BBI, IfcvtKind Kind) {
// RemoveExtraEdges won't work if the block has an unanalyzable branch, so
// explicitly remove CvtBBI as a successor.
- BBI.BB->removeSuccessor(CvtBBI->BB);
+ BBI.BB->removeSuccessor(CvtBBI->BB, true);
} else {
RemoveKills(CvtBBI->BB->begin(), CvtBBI->BB->end(), DontKill, *TRI);
PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
@@ -1226,7 +1226,7 @@ bool IfConverter::IfConvertTriangle(BBInfo &BBI, IfcvtKind Kind) {
// RemoveExtraEdges won't work if the block has an unanalyzable branch, so
// explicitly remove CvtBBI as a successor.
- BBI.BB->removeSuccessor(CvtBBI->BB);
+ BBI.BB->removeSuccessor(CvtBBI->BB, true);
} else {
// Predicate the 'true' block after removing its branch.
CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
@@ -1512,7 +1512,7 @@ bool IfConverter::IfConvertDiamond(BBInfo &BBI, IfcvtKind Kind,
// which can happen here if TailBB is unanalyzable and is merged, so
// explicitly remove BBI1 and BBI2 as successors.
BBI.BB->removeSuccessor(BBI1->BB);
- BBI.BB->removeSuccessor(BBI2->BB);
+ BBI.BB->removeSuccessor(BBI2->BB, true);
RemoveExtraEdges(BBI);
// Update block info.
@@ -1706,7 +1706,7 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
if (AddEdges) {
// If the edge from ToBBI.BB to Succ already exists, update the
- // probability of this edge by adding NewWeight to it. An example is shown
+ // probability of this edge by adding NewProb to it. An example is shown
// below, in which A is ToBBI.BB and B is FromBBI.BB. In this case we
// don't have to set C as A's successor as it already is. We only need to
// update the edge probability on A->C. Note that B will not be
@@ -1740,6 +1740,10 @@ void IfConverter::MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI, bool AddEdges) {
if (NBB && !FromBBI.BB->isSuccessor(NBB))
FromBBI.BB->addSuccessor(NBB);
+ // Normalize the probabilities of ToBBI.BB's successors with all adjustment
+ // we've done above.
+ ToBBI.BB->normalizeSuccProbs();
+
ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
FromBBI.Predicate.clear();
diff --git a/llvm/lib/CodeGen/MachineBasicBlock.cpp b/llvm/lib/CodeGen/MachineBasicBlock.cpp
index c8a5030e8d8..f2876ab265b 100644
--- a/llvm/lib/CodeGen/MachineBasicBlock.cpp
+++ b/llvm/lib/CodeGen/MachineBasicBlock.cpp
@@ -506,6 +506,20 @@ void MachineBasicBlock::updateTerminator() {
}
}
+void MachineBasicBlock::validateSuccProbs() const {
+#ifndef NDEBUG
+ int64_t Sum = 0;
+ for (auto Prob : Probs)
+ Sum += Prob.getNumerator();
+ // Due to precision issue, we assume that the sum of probabilities is one if
+ // the difference between the sum of their numerators and the denominator is
+ // no greater than the number of successors.
+ assert(std::abs<uint64_t>(Sum - BranchProbability::getDenominator()) <=
+ Probs.size() &&
+ "The sum of successors's probabilities exceeds one.");
+#endif // NDEBUG
+}
+
void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ,
BranchProbability Prob) {
// Probability list is either empty (if successor list isn't empty, this means
@@ -525,13 +539,14 @@ void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
Succ->addPredecessor(this);
}
-void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) {
+void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
+ bool NormalizeSuccProbs) {
succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
- removeSuccessor(I);
+ removeSuccessor(I, NormalizeSuccProbs);
}
MachineBasicBlock::succ_iterator
-MachineBasicBlock::removeSuccessor(succ_iterator I) {
+MachineBasicBlock::removeSuccessor(succ_iterator I, bool NormalizeSuccProbs) {
assert(I != Successors.end() && "Not a current successor!");
// If probability list is empty it means we don't use it (disabled
@@ -539,6 +554,8 @@ MachineBasicBlock::removeSuccessor(succ_iterator I) {
if (!Probs.empty()) {
probability_iterator WI = getProbabilityIterator(I);
Probs.erase(WI);
+ if (NormalizeSuccProbs)
+ normalizeSuccProbs();
}
(*I)->removePredecessor(this);
@@ -636,6 +653,7 @@ MachineBasicBlock::transferSuccessorsAndUpdatePHIs(MachineBasicBlock *FromMBB) {
MO.setMBB(this);
}
}
+ normalizeSuccProbs();
}
bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
@@ -1088,6 +1106,8 @@ bool MachineBasicBlock::CorrectExtraCFGEdges(MachineBasicBlock *DestA,
}
}
+ if (Changed)
+ normalizeSuccProbs();
return Changed;
}
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 77b52c0f2e3..3b09f258952 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -2270,6 +2270,7 @@ void SelectionDAGBuilder::visitIndirectBr(const IndirectBrInst &I) {
MachineBasicBlock *Succ = FuncInfo.MBBMap[BB];
addSuccessorWithProb(IndirectBrMBB, Succ);
}
+ IndirectBrMBB->normalizeSuccProbs();
DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(),
MVT::Other, getControlRoot(),
diff --git a/llvm/lib/CodeGen/TailDuplication.cpp b/llvm/lib/CodeGen/TailDuplication.cpp
index 1f5b54866ac..9bd15dd6ec7 100644
--- a/llvm/lib/CodeGen/TailDuplication.cpp
+++ b/llvm/lib/CodeGen/TailDuplication.cpp
@@ -751,6 +751,7 @@ TailDuplicatePass::duplicateSimpleBB(MachineBasicBlock *TailBB,
assert(NumSuccessors <= 1);
if (NumSuccessors == 0 || *PredBB->succ_begin() != NewTarget)
PredBB->addSuccessor(NewTarget, Prob);
+ PredBB->normalizeSuccProbs();
TDBBs.push_back(PredBB);
}
diff --git a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp
index 920f4094a45..df1320fbd4c 100644
--- a/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp
+++ b/llvm/lib/Target/AArch64/AArch64ConditionalCompares.cpp
@@ -567,8 +567,8 @@ void SSACCmpConv::convert(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks) {
// All CmpBB instructions are moved into Head, and CmpBB is deleted.
// Update the CFG first.
updateTailPHIs();
- Head->removeSuccessor(CmpBB);
- CmpBB->removeSuccessor(Tail);
+ Head->removeSuccessor(CmpBB, true);
+ CmpBB->removeSuccessor(Tail, true);
Head->transferSuccessorsAndUpdatePHIs(CmpBB);
DebugLoc TermDL = Head->getFirstTerminator()->getDebugLoc();
TII->RemoveBranch(*Head);
diff --git a/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp b/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
index cdbd1209215..917efd149e0 100644
--- a/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
+++ b/llvm/lib/Target/AMDGPU/AMDILCFGStructurizer.cpp
@@ -1164,7 +1164,7 @@ int AMDGPUCFGStructurizer::loopcontPatternMatch(MachineLoop *LoopRep,
for (SmallVectorImpl<MachineBasicBlock *>::iterator It = ContMBB.begin(),
E = ContMBB.end(); It != E; ++It) {
- (*It)->removeSuccessor(LoopHeader);
+ (*It)->removeSuccessor(LoopHeader, true);
}
numLoopcontPatternMatch += NumCont;
@@ -1487,7 +1487,7 @@ void AMDGPUCFGStructurizer::mergeSerialBlock(MachineBasicBlock *DstMBB,
);
DstMBB->splice(DstMBB->end(), SrcMBB, SrcMBB->begin(), SrcMBB->end());
- DstMBB->removeSuccessor(SrcMBB);
+ DstMBB->removeSuccessor(SrcMBB, true);
cloneSuccessorList(DstMBB, SrcMBB);
removeSuccessor(SrcMBB);
@@ -1537,9 +1537,9 @@ void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
if (TrueMBB) {
MBB->splice(I, TrueMBB, TrueMBB->begin(), TrueMBB->end());
- MBB->removeSuccessor(TrueMBB);
+ MBB->removeSuccessor(TrueMBB, true);
if (LandMBB && TrueMBB->succ_size()!=0)
- TrueMBB->removeSuccessor(LandMBB);
+ TrueMBB->removeSuccessor(LandMBB, true);
retireBlock(TrueMBB);
MLI->removeBlock(TrueMBB);
}
@@ -1548,9 +1548,9 @@ void AMDGPUCFGStructurizer::mergeIfthenelseBlock(MachineInstr *BranchMI,
insertInstrBefore(I, AMDGPU::ELSE);
MBB->splice(I, FalseMBB, FalseMBB->begin(),
FalseMBB->end());
- MBB->removeSuccessor(FalseMBB);
+ MBB->removeSuccessor(FalseMBB, true);
if (LandMBB && FalseMBB->succ_size() != 0)
- FalseMBB->removeSuccessor(LandMBB);
+ FalseMBB->removeSuccessor(LandMBB, true);
retireBlock(FalseMBB);
MLI->removeBlock(FalseMBB);
}
@@ -1591,7 +1591,7 @@ void AMDGPUCFGStructurizer::mergeLoopbreakBlock(MachineBasicBlock *ExitingMBB,
//now branchInst can be erase safely
BranchMI->eraseFromParent();
//now take care of successors, retire blocks
- ExitingMBB->removeSuccessor(LandMBB);
+ ExitingMBB->removeSuccessor(LandMBB, true);
}
void AMDGPUCFGStructurizer::settleLoopcontBlock(MachineBasicBlock *ContingMBB,
@@ -1757,7 +1757,7 @@ void AMDGPUCFGStructurizer::removeRedundantConditionalBranch(
DEBUG(dbgs() << "Removing unneeded cond branch instr: " << *BranchMI);
BranchMI->eraseFromParent();
SHOWNEWBLK(MBB1, "Removing redundant successor");
- MBB->removeSuccessor(MBB1);
+ MBB->removeSuccessor(MBB1, true);
}
void AMDGPUCFGStructurizer::addDummyExitBlock(
diff --git a/llvm/lib/Target/ARM/ARMISelLowering.cpp b/llvm/lib/Target/ARM/ARMISelLowering.cpp
index fc32cf2ce4e..29c072a6cc9 100644
--- a/llvm/lib/Target/ARM/ARMISelLowering.cpp
+++ b/llvm/lib/Target/ARM/ARMISelLowering.cpp
@@ -7397,6 +7397,7 @@ void ARMTargetLowering::EmitSjLjDispatchBlock(MachineInstr *MI,
}
BB->addSuccessor(DispatchBB, BranchProbability::getZero());
+ BB->normalizeSuccProbs();
// Find the invoke call and mark all of the callee-saved registers as
// 'implicit defined' so that they're spilled. This prevents code from
diff --git a/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp b/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
index 89f098f0ff6..ee0c318ffb5 100644
--- a/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonEarlyIfConv.cpp
@@ -939,7 +939,7 @@ void HexagonEarlyIfConversion::removeBlock(MachineBasicBlock *B) {
B->removeSuccessor(B->succ_begin());
for (auto I = B->pred_begin(), E = B->pred_end(); I != E; ++I)
- (*I)->removeSuccessor(B);
+ (*I)->removeSuccessor(B, true);
Deleted.insert(B);
MDT->eraseNode(B);
@@ -1001,6 +1001,7 @@ void HexagonEarlyIfConversion::mergeBlocks(MachineBasicBlock *PredB,
MachineBasicBlock::succ_iterator I, E = SuccB->succ_end();
for (I = SuccB->succ_begin(); I != E; ++I)
PredB->addSuccessor(*I);
+ PredB->normalizeSuccProbs();
replacePhiEdges(SuccB, PredB);
removeBlock(SuccB);
if (!TermOk)
diff --git a/llvm/lib/Target/Mips/MipsLongBranch.cpp b/llvm/lib/Target/Mips/MipsLongBranch.cpp
index e75858a181e..49fb99a8ec4 100644
--- a/llvm/lib/Target/Mips/MipsLongBranch.cpp
+++ b/llvm/lib/Target/Mips/MipsLongBranch.cpp
@@ -148,7 +148,7 @@ void MipsLongBranch::splitMBB(MachineBasicBlock *MBB) {
// Insert NewMBB and fix control flow.
MachineBasicBlock *Tgt = getTargetMBB(*FirstBr);
NewMBB->transferSuccessors(MBB);
- NewMBB->removeSuccessor(Tgt);
+ NewMBB->removeSuccessor(Tgt, true);
MBB->addSuccessor(NewMBB);
MBB->addSuccessor(Tgt);
MF->insert(std::next(MachineFunction::iterator(MBB)), NewMBB);
diff --git a/llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp b/llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp
index cbc8d8fdb09..b455aa9ea04 100644
--- a/llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp
+++ b/llvm/lib/Target/PowerPC/PPCEarlyReturn.cpp
@@ -153,7 +153,7 @@ protected:
}
for (unsigned i = 0, ie = PredToRemove.size(); i != ie; ++i)
- PredToRemove[i]->removeSuccessor(&ReturnMBB);
+ PredToRemove[i]->removeSuccessor(&ReturnMBB, true);
if (Changed && !ReturnMBB.hasAddressTaken()) {
// We now might be able to merge this blr-only block into its
@@ -163,7 +163,7 @@ protected:
if (PrevMBB.isLayoutSuccessor(&ReturnMBB) && PrevMBB.canFallThrough()) {
// Move the blr into the preceding block.
PrevMBB.splice(PrevMBB.end(), &ReturnMBB, I);
- PrevMBB.removeSuccessor(&ReturnMBB);
+ PrevMBB.removeSuccessor(&ReturnMBB, true);
}
}
OpenPOWER on IntegriCloud