#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;
}
OS << " Successors according to CFG:";
for (const_succ_iterator SI = succ_begin(), E = succ_end(); SI != E; ++SI) {
OS << " BB#" << (*SI)->getNumber();
- if (!Weights.empty())
- OS << '(' << *getWeightIterator(SI) << ')';
+ if (!Probs.empty())
+ OS << '(' << *getProbabilityIterator(SI) << ')';
}
OS << '\n';
}
}
}
-void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) {
- // Weight list is either empty (if successor list isn't empty, this means
- // disabled optimization) or has the same size as successor list.
- if (!(Weights.empty() && !Successors.empty()))
- Weights.push_back(Weight);
- Successors.push_back(Succ);
- Succ->addPredecessor(this);
-}
-
-void MachineBasicBlock::addSuccessorWithoutWeight(MachineBasicBlock *Succ) {
- // We need to make sure weight list is either empty or has the same size of
- // successor list. When this function is called, we can safely delete all
- // weight in the list.
- Weights.clear();
- Successors.push_back(Succ);
- Succ->addPredecessor(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,
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 Weight list is empty it means we don't use it (disabled optimization).
- if (!Weights.empty()) {
- weight_iterator WI = getWeightIterator(I);
- Weights.erase(WI);
- }
-
// If probability list is empty it means we don't use it (disabled
// optimization).
if (!Probs.empty()) {
probability_iterator WI = getProbabilityIterator(I);
Probs.erase(WI);
+ if (NormalizeSuccProbs)
+ normalizeSuccProbs();
}
(*I)->removePredecessor(this);
}
// New is already a successor.
- // Update its weight instead of adding a duplicate edge.
- if (!Weights.empty())
- *getWeightIterator(NewI) += *getWeightIterator(OldI);
// Update its probability instead of adding a duplicate edge.
- if (!Probs.empty())
- *getProbabilityIterator(NewI) += *getProbabilityIterator(OldI);
-
+ if (!Probs.empty()) {
+ auto ProbIter = getProbabilityIterator(NewI);
+ if (!ProbIter->isUnknown())
+ *ProbIter += *getProbabilityIterator(OldI);
+ }
removeSuccessor(OldI);
}
while (!FromMBB->succ_empty()) {
MachineBasicBlock *Succ = *FromMBB->succ_begin();
- uint32_t Weight = 0;
- // If Weight list is empty it means we don't use it (disabled optimization).
- if (!FromMBB->Weights.empty())
- Weight = *FromMBB->Weights.begin();
+ // If probability list is empty it means we don't use it (disabled optimization).
+ if (!FromMBB->Probs.empty()) {
+ auto Prob = *FromMBB->Probs.begin();
+ addSuccessor(Succ, Prob);
+ } else
+ addSuccessorWithoutProb(Succ);
- addSuccessor(Succ, Weight);
FromMBB->removeSuccessor(Succ);
}
}
while (!FromMBB->succ_empty()) {
MachineBasicBlock *Succ = *FromMBB->succ_begin();
- uint32_t Weight = 0;
- if (!FromMBB->Weights.empty())
- Weight = *FromMBB->Weights.begin();
- addSuccessor(Succ, Weight);
+ if (!FromMBB->Probs.empty()) {
+ auto Prob = *FromMBB->Probs.begin();
+ addSuccessor(Succ, Prob);
+ } else
+ addSuccessorWithoutProb(Succ);
FromMBB->removeSuccessor(Succ);
// Fix up any PHI nodes in the successor.
MO.setMBB(this);
}
}
+ normalizeSuccProbs();
}
bool MachineBasicBlock::isPredecessor(const MachineBasicBlock *MBB) const {
}
}
+ if (Changed)
+ normalizeSuccProbs();
return Changed;
}
return DL;
}
-/// Return weight of the edge from this block to MBB.
-uint32_t MachineBasicBlock::getSuccWeight(const_succ_iterator Succ) const {
- if (Weights.empty())
- return 0;
-
- return *getWeightIterator(Succ);
-}
-
-/// Return probability of the edge from this block to MBB. If probability list
-/// is empty, return a default probability which is 1/N, where N is the number
-/// of successors. If the probability of the given successor is unknown, then
-/// sum up all known probabilities and return the complement of the sum divided
-/// by the number of unknown probabilities.
+/// Return probability of the edge from this block to MBB.
BranchProbability
MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
if (Probs.empty())
return BranchProbability(1, succ_size());
- auto Prob = *getProbabilityIterator(Succ);
- assert(!Prob.isUnknown());
- return Prob;
-}
-
-/// Set successor weight of a given iterator.
-void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) {
- if (Weights.empty())
- return;
- *getWeightIterator(I) = Weight;
+ 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.
*getProbabilityIterator(I) = Prob;
}
-/// Return wight iterator corresonding to the I successor iterator.
-MachineBasicBlock::weight_iterator MachineBasicBlock::
-getWeightIterator(MachineBasicBlock::succ_iterator I) {
- assert(Weights.size() == Successors.size() && "Async weight list!");
- size_t index = std::distance(Successors.begin(), I);
- assert(index < Weights.size() && "Not a current successor!");
- return Weights.begin() + index;
-}
-
-/// Return wight iterator corresonding to the I successor iterator.
-MachineBasicBlock::const_weight_iterator MachineBasicBlock::
-getWeightIterator(MachineBasicBlock::const_succ_iterator I) const {
- assert(Weights.size() == Successors.size() && "Async weight list!");
- const size_t index = std::distance(Successors.begin(), I);
- assert(index < Weights.size() && "Not a current successor!");
- return Weights.begin() + index;
-}
-
-/// Return probability iterator corresonding to the I successor iterator.
-MachineBasicBlock::probability_iterator
-MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
+/// Return probability iterator corresonding to the I successor iterator
+MachineBasicBlock::const_probability_iterator
+MachineBasicBlock::getProbabilityIterator(
+ MachineBasicBlock::const_succ_iterator I) const {
assert(Probs.size() == Successors.size() && "Async probability list!");
const size_t index = std::distance(Successors.begin(), I);
assert(index < Probs.size() && "Not a current successor!");
return Probs.begin() + index;
}
-/// Return probability iterator corresonding to the I successor iterator
-MachineBasicBlock::const_probability_iterator
-MachineBasicBlock::getProbabilityIterator(
- MachineBasicBlock::const_succ_iterator I) const {
+/// Return probability iterator corresonding to the I successor iterator.
+MachineBasicBlock::probability_iterator
+MachineBasicBlock::getProbabilityIterator(MachineBasicBlock::succ_iterator I) {
assert(Probs.size() == Successors.size() && "Async probability list!");
const size_t index = std::distance(Successors.begin(), I);
assert(index < Probs.size() && "Not a current successor!");
/// 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