#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"
const MachineFunction *MF = getParent();
MCContext &Ctx = MF->getContext();
const char *Prefix = Ctx.getAsmInfo()->getPrivateLabelPrefix();
+ assert(getNumber() >= 0 && "cannot get label for unreachable MBB");
CachedMCSymbol = Ctx.getOrCreateSymbol(Twine(Prefix) + "BB" +
Twine(MF->getFunctionNumber()) +
"_" + Twine(getNumber()));
for (const_instr_iterator I = instr_begin(); I != instr_end(); ++I) {
if (Indexes) {
- if (Indexes->hasIndex(I))
- OS << Indexes->getInstructionIndex(I);
+ if (Indexes->hasIndex(&*I))
+ OS << Indexes->getInstructionIndex(&*I);
OS << '\t';
}
OS << '\t';
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::moveBefore(MachineBasicBlock *NewAfter) {
- getParent()->splice(NewAfter, this);
+ getParent()->splice(NewAfter->getIterator(), getIterator());
}
void MachineBasicBlock::moveAfter(MachineBasicBlock *NewBefore) {
- MachineFunction::iterator BBI = NewBefore;
- getParent()->splice(++BBI, this);
+ getParent()->splice(++NewBefore->getIterator(), getIterator());
}
void MachineBasicBlock::updateTerminator() {
}
}
-void MachineBasicBlock::addSuccessor(MachineBasicBlock *Succ, uint32_t Weight) {
-
- // If we see non-zero value for the first time it means we actually use Weight
- // list, so we fill all Weights with 0's.
- if (Weight != 0 && Weights.empty())
- Weights.resize(Successors.size());
+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
+}
- if (Weight != 0 || !Weights.empty())
- Weights.push_back(Weight);
+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()))
+ Probs.push_back(Prob);
+ Successors.push_back(Succ);
+ Succ->addPredecessor(this);
+}
+void MachineBasicBlock::addSuccessorWithoutProb(MachineBasicBlock *Succ) {
+ // We need to make sure probability list is either empty or has the same size
+ // of successor list. When this function is called, we can safely delete all
+ // probability in the list.
+ Probs.clear();
Successors.push_back(Succ);
Succ->addPredecessor(this);
}
-void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ) {
- Succ->removePredecessor(this);
+void MachineBasicBlock::removeSuccessor(MachineBasicBlock *Succ,
+ bool NormalizeSuccProbs) {
succ_iterator I = std::find(Successors.begin(), Successors.end(), Succ);
- 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);
- }
-
- Successors.erase(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);
}
}
assert(OldI != E && "Old is not a successor of this block");
- Old->removePredecessor(this);
// If New isn't already a successor, let it take Old's place.
if (NewI == E) {
+ Old->removePredecessor(this);
New->addPredecessor(this);
*OldI = New;
return;
}
// New is already a successor.
- // Update its weight instead of adding a duplicate edge.
- if (!Weights.empty()) {
- weight_iterator OldWI = getWeightIterator(OldI);
- *getWeightIterator(NewI) += *OldWI;
- Weights.erase(OldWI);
+ // Update its probability instead of adding a duplicate edge.
+ if (!Probs.empty()) {
+ auto ProbIter = getProbabilityIterator(NewI);
+ if (!ProbIter->isUnknown())
+ *ProbIter += *getProbabilityIterator(OldI);
}
- Successors.erase(OldI);
+ removeSuccessor(OldI);
}
void MachineBasicBlock::addPredecessor(MachineBasicBlock *Pred) {
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 {
}
bool MachineBasicBlock::canFallThrough() {
- MachineFunction::iterator Fallthrough = this;
+ MachineFunction::iterator Fallthrough = getIterator();
++Fallthrough;
// If FallthroughBlock is off the end of the function, it can't fall through.
if (Fallthrough == getParent()->end())
return false;
// If FallthroughBlock isn't a successor, no fallthrough is possible.
- if (!isSuccessor(Fallthrough))
+ if (!isSuccessor(&*Fallthrough))
return false;
// Analyze the branches, if any, at the end of the block.
if (LV)
for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
I != E; ++I) {
- MachineInstr *MI = I;
+ MachineInstr *MI = &*I;
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
if (!OI->isReg() || OI->getReg() == 0 ||
if (LIS) {
for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
I != E; ++I) {
- MachineInstr *MI = I;
+ MachineInstr *MI = &*I;
for (MachineInstr::mop_iterator OI = MI->operands_begin(),
OE = MI->operands_end(); OI != OE; ++OI) {
if (Indexes) {
for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
I != E; ++I)
- Terminators.push_back(I);
+ Terminators.push_back(&*I);
}
updateTerminator();
SmallVector<MachineInstr*, 4> NewTerminators;
for (instr_iterator I = getFirstInstrTerminator(), E = instr_end();
I != E; ++I)
- NewTerminators.push_back(I);
+ NewTerminators.push_back(&*I);
for (SmallVectorImpl<MachineInstr*>::iterator I = Terminators.begin(),
E = Terminators.end(); I != E; ++I) {
I != E; ++I) {
// Some instructions may have been moved to NMBB by updateTerminator(),
// so we first remove any instruction that already has an index.
- if (Indexes->hasIndex(I))
- Indexes->removeMachineInstrFromMaps(I);
- Indexes->insertMachineInstrInMaps(I);
+ if (Indexes->hasIndex(&*I))
+ Indexes->removeMachineInstrFromMaps(&*I);
+ Indexes->insertMachineInstrInMaps(&*I);
}
}
}
if (!(--I)->addRegisterKilled(Reg, TRI, /* addIfNotFound= */ false))
continue;
if (TargetRegisterInfo::isVirtualRegister(Reg))
- LV->getVarInfo(Reg).Kills.push_back(I);
+ LV->getVarInfo(Reg).Kills.push_back(&*I);
DEBUG(dbgs() << "Restored terminator kill: " << *I);
break;
}
MachineBasicBlock::instr_iterator
MachineBasicBlock::erase(MachineBasicBlock::instr_iterator I) {
- unbundleSingleMI(I);
+ unbundleSingleMI(&*I);
return Insts.erase(I);
}
bool Changed = false;
- MachineFunction::iterator FallThru =
- std::next(MachineFunction::iterator(this));
+ MachineFunction::iterator FallThru = std::next(getIterator());
if (!DestA && !DestB) {
// Block falls through to successor.
- DestA = FallThru;
- DestB = FallThru;
+ DestA = &*FallThru;
+ DestB = &*FallThru;
} else if (DestA && !DestB) {
if (IsCond)
// Block ends in conditional jump that falls through to successor.
- DestB = FallThru;
+ DestB = &*FallThru;
} else {
assert(DestA && DestB && IsCond &&
"CFG in a bad state. Cannot correct CFG edges");
}
}
+ 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.
+BranchProbability
+MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
+ if (Probs.empty())
+ return BranchProbability(1, succ_size());
+
+ 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 weight of a given iterator.
-void MachineBasicBlock::setSuccWeight(succ_iterator I, uint32_t Weight) {
- if (Weights.empty())
+/// Set successor probability of a given iterator.
+void MachineBasicBlock::setSuccProbability(succ_iterator I,
+ BranchProbability Prob) {
+ assert(!Prob.isUnknown());
+ if (Probs.empty())
return;
- *getWeightIterator(I) = Weight;
+ *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 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 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!");
+/// 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 < Weights.size() && "Not a current successor!");
- return Weights.begin() + index;
+ assert(index < Probs.size() && "Not a current successor!");
+ return Probs.begin() + index;
}
/// Return whether (physical) register "Reg" has been <def>ined and not <kill>ed
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;
}
}
// At this point we have no idea of the liveness of the register.
return LQR_Unknown;
}
+
+const uint32_t *
+MachineBasicBlock::getBeginClobberMask(const TargetRegisterInfo *TRI) const {
+ // EH funclet entry does not preserve any registers.
+ return isEHFuncletEntry() ? TRI->getNoPreservedMask() : nullptr;
+}
+
+const uint32_t *
+MachineBasicBlock::getEndClobberMask(const TargetRegisterInfo *TRI) const {
+ // If we see a return block with successors, this must be a funclet return,
+ // which does not preserve any registers. If there are no successors, we don't
+ // care what kind of return it is, putting a mask after it is a no-op.
+ return isReturnBlock() && !succ_empty() ? TRI->getNoPreservedMask() : nullptr;
+}
projects / oota-llvm.git / blobdiff