#include "llvm/IR/ModuleSlotTracker.h"
#include "llvm/MC/MCAsmInfo.h"
#include "llvm/MC/MCContext.h"
+#include "llvm/Support/DataTypes.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#define DEBUG_TYPE "codegen"
MachineBasicBlock::MachineBasicBlock(MachineFunction &MF, const BasicBlock *B)
- : BB(B), Number(-1), xParent(&MF) {
+ : BB(B), Number(-1), xParent(&MF), canEliminateMachineBB(true) {
Insts.Parent = this;
}
}
}
+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((uint64_t)std::abs(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
// disabled optimization) or has the same size as successor list.
- if (!(Probs.empty() && !Successors.empty())) {
- assert((Probs.empty() || (Prob.isUnknown() && Probs.back().isUnknown()) ||
- (!Prob.isUnknown() && !Probs.back().isUnknown())) &&
- "Successors with both known and unknwon probabilities are not "
- "allowed.");
+ if (!(Probs.empty() && !Successors.empty()))
Probs.push_back(Prob);
- }
Successors.push_back(Succ);
Succ->addPredecessor(this);
}
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
if (!Probs.empty()) {
probability_iterator WI = getProbabilityIterator(I);
Probs.erase(WI);
+ if (NormalizeSuccProbs)
+ normalizeSuccProbs();
}
(*I)->removePredecessor(this);
MO.setMBB(this);
}
}
+ normalizeSuccProbs();
}
bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
}
}
+ if (Changed)
+ normalizeSuccProbs();
return Changed;
}
/// Return probability of the edge from this block to MBB.
BranchProbability
MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
- if (Probs.empty() || Probs.back().isUnknown())
+ if (Probs.empty())
return BranchProbability(1, succ_size());
- return *getProbabilityIterator(Succ);
+ const auto &Prob = *getProbabilityIterator(Succ);
+ if (Prob.isUnknown()) {
+ // For unknown probabilities, collect the sum of all known ones, and evenly
+ // ditribute the complemental of the sum to each unknown probability.
+ unsigned KnownProbNum = 0;
+ auto Sum = BranchProbability::getZero();
+ for (auto &P : Probs) {
+ if (!P.isUnknown()) {
+ Sum += P;
+ KnownProbNum++;
+ }
+ }
+ return Sum.getCompl() / (Probs.size() - KnownProbNum);
+ } else
+ return Prob;
}
/// Set successor probability of a given iterator.
/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
/// as of just before "MI".
-///
+///
/// Search is localised to a neighborhood of
/// Neighborhood instructions before (searching for defs or kills) and N
/// instructions after (searching just for defs) MI.
do {
--I;
- MachineOperandIteratorBase::PhysRegInfo Analysis =
+ MachineOperandIteratorBase::PhysRegInfo Info =
ConstMIOperands(I).analyzePhysReg(Reg, TRI);
- if (Analysis.Defines)
- // Outputs happen after inputs so they take precedence if both are
- // present.
- return Analysis.DefinesDead ? LQR_Dead : LQR_Live;
+ // Defs happen after uses so they take precedence if both are present.
- if (Analysis.Kills || Analysis.Clobbers)
- // Register killed, so isn't live.
+ // Register is dead after a dead def of the full register.
+ if (Info.DeadDef)
return LQR_Dead;
-
- else if (Analysis.ReadsOverlap)
- // Defined or read without a previous kill - live.
- return Analysis.Reads ? LQR_Live : LQR_OverlappingLive;
-
+ // Register is (at least partially) live after a def.
+ if (Info.Defined)
+ return LQR_Live;
+ // Register is dead after a full kill or clobber and no def.
+ if (Info.Killed || Info.Clobbered)
+ return LQR_Dead;
+ // Register must be live if we read it.
+ if (Info.Read)
+ return LQR_Live;
} while (I != begin() && --N > 0);
}
// Did we get to the start of the block?
if (I == begin()) {
// If so, the register's state is definitely defined by the live-in state.
- for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true);
- RAI.isValid(); ++RAI) {
+ for (MCRegAliasIterator RAI(Reg, TRI, /*IncludeSelf=*/true); RAI.isValid();
+ ++RAI)
if (isLiveIn(*RAI))
- return (*RAI == Reg) ? LQR_Live : LQR_OverlappingLive;
- }
+ return LQR_Live;
return LQR_Dead;
}
// If this is the last insn in the block, don't search forwards.
if (I != end()) {
for (++I; I != end() && N > 0; ++I, --N) {
- MachineOperandIteratorBase::PhysRegInfo Analysis =
+ MachineOperandIteratorBase::PhysRegInfo Info =
ConstMIOperands(I).analyzePhysReg(Reg, TRI);
- if (Analysis.ReadsOverlap)
- // Used, therefore must have been live.
- return (Analysis.Reads) ?
- LQR_Live : LQR_OverlappingLive;
-
- else if (Analysis.Clobbers || Analysis.Defines)
- // Defined (but not read) therefore cannot have been live.
+ // Register is live when we read it here.
+ if (Info.Read)
+ return LQR_Live;
+ // Register is dead if we can fully overwrite or clobber it here.
+ if (Info.FullyDefined || Info.Clobbered)
return LQR_Dead;
}
}
projects / oota-llvm.git / blobdiff