#include "llvm/Target/TargetSelectionDAGInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
#include <algorithm>
+#include <utility>
using namespace llvm;
#define DEBUG_TYPE "isel"
if (PartEVT == ValueVT)
return Val;
+ if (PartEVT.isInteger() && ValueVT.isFloatingPoint() &&
+ ValueVT.bitsLT(PartEVT)) {
+ // For an FP value in an integer part, we need to truncate to the right
+ // width first.
+ PartEVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
+ Val = DAG.getNode(ISD::TRUNCATE, DL, PartEVT, Val);
+ }
+
if (PartEVT.isInteger() && ValueVT.isInteger()) {
if (ValueVT.bitsLT(PartEVT)) {
// For a truncate, see if we have any information to
assert(NumParts == 1 && "Do not know what to promote to!");
Val = DAG.getNode(ISD::FP_EXTEND, DL, PartVT, Val);
} else {
+ if (ValueVT.isFloatingPoint()) {
+ // FP values need to be bitcast, then extended if they are being put
+ // into a larger container.
+ ValueVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits());
+ Val = DAG.getNode(ISD::BITCAST, DL, ValueVT, Val);
+ }
assert((PartVT.isInteger() || PartVT == MVT::x86mmx) &&
ValueVT.isInteger() &&
"Unknown mismatch!");
visit(I.getOpcode(), I);
- if (!isa<TerminatorInst>(&I) && !HasTailCall)
+ if (!isa<TerminatorInst>(&I) && !HasTailCall &&
+ !isStatepoint(&I)) // statepoints handle their exports internally
CopyToExportRegsIfNeeded(&I);
CurInst = nullptr;
}
void SelectionDAGBuilder::visitCatchPad(const CatchPadInst &I) {
- llvm_unreachable("should never codegen catchpads");
+ auto Pers = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
+ bool IsMSVCCXX = Pers == EHPersonality::MSVC_CXX;
+ bool IsCoreCLR = Pers == EHPersonality::CoreCLR;
+ MachineBasicBlock *CatchPadMBB = FuncInfo.MBB;
+ // In MSVC C++ and CoreCLR, catchblocks are funclets and need prologues.
+ if (IsMSVCCXX || IsCoreCLR)
+ CatchPadMBB->setIsEHFuncletEntry();
+
+ MachineBasicBlock *NormalDestMBB = FuncInfo.MBBMap[I.getNormalDest()];
+
+ // Update machine-CFG edge.
+ FuncInfo.MBB->addSuccessor(NormalDestMBB);
+
+ SDValue Chain =
+ DAG.getNode(ISD::CATCHPAD, getCurSDLoc(), MVT::Other, getControlRoot());
+
+ // If this is not a fall-through branch or optimizations are switched off,
+ // emit the branch.
+ if (NormalDestMBB != NextBlock(CatchPadMBB) ||
+ TM.getOptLevel() == CodeGenOpt::None)
+ Chain = DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other, Chain,
+ DAG.getBasicBlock(NormalDestMBB));
+ DAG.setRoot(Chain);
}
void SelectionDAGBuilder::visitCatchRet(const CatchReturnInst &I) {
MachineBasicBlock *TargetMBB = FuncInfo.MBBMap[I.getSuccessor()];
FuncInfo.MBB->addSuccessor(TargetMBB);
+ auto Pers = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
+ bool IsSEH = isAsynchronousEHPersonality(Pers);
+ if (IsSEH) {
+ // If this is not a fall-through branch or optimizations are switched off,
+ // emit the branch.
+ if (TargetMBB != NextBlock(FuncInfo.MBB) ||
+ TM.getOptLevel() == CodeGenOpt::None)
+ DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(), MVT::Other,
+ getControlRoot(), DAG.getBasicBlock(TargetMBB)));
+ return;
+ }
+
+ // Figure out the funclet membership for the catchret's successor.
+ // This will be used by the FuncletLayout pass to determine how to order the
+ // BB's.
+ WinEHFuncInfo *EHInfo = DAG.getMachineFunction().getWinEHFuncInfo();
+ const BasicBlock *SuccessorColor = EHInfo->CatchRetSuccessorColorMap[&I];
+ assert(SuccessorColor && "No parent funclet for catchret!");
+ MachineBasicBlock *SuccessorColorMBB = FuncInfo.MBBMap[SuccessorColor];
+ assert(SuccessorColorMBB && "No MBB for SuccessorColor!");
+
// Create the terminator node.
SDValue Ret = DAG.getNode(ISD::CATCHRET, getCurSDLoc(), MVT::Other,
- getControlRoot(), DAG.getBasicBlock(TargetMBB));
+ getControlRoot(), DAG.getBasicBlock(TargetMBB),
+ DAG.getBasicBlock(SuccessorColorMBB));
DAG.setRoot(Ret);
}
// Don't emit any special code for the cleanuppad instruction. It just marks
// the start of a funclet.
FuncInfo.MBB->setIsEHFuncletEntry();
+ FuncInfo.MBB->setIsCleanupFuncletEntry();
}
/// When an invoke or a cleanupret unwinds to the next EH pad, there are
/// destination, but in the machine CFG, we enumerate all the possible blocks.
/// This function skips over imaginary basic blocks that hold catchpad,
/// terminatepad, or catchendpad instructions, and finds all the "real" machine
-/// basic block destinations.
-static void
-findUnwindDestinations(FunctionLoweringInfo &FuncInfo,
- const BasicBlock *EHPadBB,
- SmallVectorImpl<MachineBasicBlock *> &UnwindDests) {
- bool IsMSVCCXX = classifyEHPersonality(FuncInfo.Fn->getPersonalityFn()) ==
- EHPersonality::MSVC_CXX;
+/// basic block destinations. As those destinations may not be successors of
+/// EHPadBB, here we also calculate the edge probability to those destinations.
+/// The passed-in Prob is the edge probability to EHPadBB.
+static void findUnwindDestinations(
+ FunctionLoweringInfo &FuncInfo, const BasicBlock *EHPadBB,
+ BranchProbability Prob,
+ SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
+ &UnwindDests) {
+ EHPersonality Personality =
+ classifyEHPersonality(FuncInfo.Fn->getPersonalityFn());
+ bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX;
+ bool IsCoreCLR = Personality == EHPersonality::CoreCLR;
+
while (EHPadBB) {
const Instruction *Pad = EHPadBB->getFirstNonPHI();
+ BasicBlock *NewEHPadBB = nullptr;
if (isa<LandingPadInst>(Pad)) {
// Stop on landingpads. They are not funclets.
- UnwindDests.push_back(FuncInfo.MBBMap[EHPadBB]);
+ UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
break;
- } else if (isa<CleanupPadInst>(Pad) || isa<LandingPadInst>(Pad)) {
+ } else if (isa<CleanupPadInst>(Pad)) {
// Stop on cleanup pads. Cleanups are always funclet entries for all known
// personalities.
- UnwindDests.push_back(FuncInfo.MBBMap[EHPadBB]);
- UnwindDests.back()->setIsEHFuncletEntry();
+ UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
+ UnwindDests.back().first->setIsEHFuncletEntry();
break;
} else if (const auto *CPI = dyn_cast<CatchPadInst>(Pad)) {
// Add the catchpad handler to the possible destinations.
- UnwindDests.push_back(FuncInfo.MBBMap[CPI->getNormalDest()]);
+ UnwindDests.emplace_back(FuncInfo.MBBMap[EHPadBB], Prob);
// In MSVC C++, catchblocks are funclets and need prologues.
- if (IsMSVCCXX)
- UnwindDests.back()->setIsEHFuncletEntry();
- EHPadBB = CPI->getUnwindDest();
- } else if (const auto *CEPI = dyn_cast<CatchEndPadInst>(Pad)) {
- EHPadBB = CEPI->getUnwindDest();
- } else if (const auto *CEPI = dyn_cast<CleanupEndPadInst>(Pad)) {
- EHPadBB = CEPI->getUnwindDest();
- }
+ if (IsMSVCCXX || IsCoreCLR)
+ UnwindDests.back().first->setIsEHFuncletEntry();
+ NewEHPadBB = CPI->getUnwindDest();
+ } else if (const auto *CEPI = dyn_cast<CatchEndPadInst>(Pad))
+ NewEHPadBB = CEPI->getUnwindDest();
+ else if (const auto *CEPI = dyn_cast<CleanupEndPadInst>(Pad))
+ NewEHPadBB = CEPI->getUnwindDest();
+ else
+ continue;
+
+ BranchProbabilityInfo *BPI = FuncInfo.BPI;
+ if (BPI && NewEHPadBB)
+ Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB);
+ EHPadBB = NewEHPadBB;
}
}
void SelectionDAGBuilder::visitCleanupRet(const CleanupReturnInst &I) {
// Update successor info.
- // FIXME: The weights for catchpads will be wrong.
- SmallVector<MachineBasicBlock *, 1> UnwindDests;
- findUnwindDestinations(FuncInfo, I.getUnwindDest(), UnwindDests);
- for (MachineBasicBlock *UnwindDest : UnwindDests) {
- UnwindDest->setIsEHPad();
- addSuccessorWithWeight(FuncInfo.MBB, UnwindDest);
+ SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 1> UnwindDests;
+ auto UnwindDest = I.getUnwindDest();
+ BranchProbabilityInfo *BPI = FuncInfo.BPI;
+ BranchProbability UnwindDestProb =
+ (BPI && UnwindDest)
+ ? BPI->getEdgeProbability(FuncInfo.MBB->getBasicBlock(), UnwindDest)
+ : BranchProbability::getZero();
+ findUnwindDestinations(FuncInfo, UnwindDest, UnwindDestProb, UnwindDests);
+ for (auto &UnwindDest : UnwindDests) {
+ UnwindDest.first->setIsEHPad();
+ addSuccessorWithProb(FuncInfo.MBB, UnwindDest.first, UnwindDest.second);
}
+ FuncInfo.MBB->normalizeSuccProbs();
// Create the terminator node.
SDValue Ret =
ComputeValueVTs(TLI, DL, PointerType::getUnqual(F->getReturnType()),
PtrValueVTs);
- SDValue RetPtr = DAG.getRegister(DemoteReg, PtrValueVTs[0]);
+ SDValue RetPtr = DAG.getCopyFromReg(DAG.getEntryNode(), getCurSDLoc(),
+ DemoteReg, PtrValueVTs[0]);
SDValue RetOp = getValue(I.getOperand(0));
SmallVector<EVT, 4> ValueVTs;
}
/// Return branch probability calculated by BranchProbabilityInfo for IR blocks.
-uint32_t SelectionDAGBuilder::getEdgeWeight(const MachineBasicBlock *Src,
- const MachineBasicBlock *Dst) const {
+BranchProbability
+SelectionDAGBuilder::getEdgeProbability(const MachineBasicBlock *Src,
+ const MachineBasicBlock *Dst) const {
BranchProbabilityInfo *BPI = FuncInfo.BPI;
- if (!BPI)
- return 0;
const BasicBlock *SrcBB = Src->getBasicBlock();
const BasicBlock *DstBB = Dst->getBasicBlock();
- return BPI->getEdgeWeight(SrcBB, DstBB);
+ if (!BPI) {
+ // If BPI is not available, set the default probability as 1 / N, where N is
+ // the number of successors.
+ auto SuccSize = std::max<uint32_t>(
+ std::distance(succ_begin(SrcBB), succ_end(SrcBB)), 1);
+ return BranchProbability(1, SuccSize);
+ }
+ return BPI->getEdgeProbability(SrcBB, DstBB);
}
-void SelectionDAGBuilder::
-addSuccessorWithWeight(MachineBasicBlock *Src, MachineBasicBlock *Dst,
- uint32_t Weight /* = 0 */) {
- if (!Weight)
- Weight = getEdgeWeight(Src, Dst);
- Src->addSuccessor(Dst, Weight);
+void SelectionDAGBuilder::addSuccessorWithProb(MachineBasicBlock *Src,
+ MachineBasicBlock *Dst,
+ BranchProbability Prob) {
+ if (!FuncInfo.BPI)
+ Src->addSuccessorWithoutProb(Dst);
+ else {
+ if (Prob.isUnknown())
+ Prob = getEdgeProbability(Src, Dst);
+ Src->addSuccessor(Dst, Prob);
+ }
}
-
static bool InBlock(const Value *V, const BasicBlock *BB) {
if (const Instruction *I = dyn_cast<Instruction>(V))
return I->getParent() == BB;
MachineBasicBlock *FBB,
MachineBasicBlock *CurBB,
MachineBasicBlock *SwitchBB,
- uint32_t TWeight,
- uint32_t FWeight) {
+ BranchProbability TProb,
+ BranchProbability FProb) {
const BasicBlock *BB = CurBB->getBasicBlock();
// If the leaf of the tree is a comparison, merge the condition into
}
CaseBlock CB(Condition, BOp->getOperand(0), BOp->getOperand(1), nullptr,
- TBB, FBB, CurBB, TWeight, FWeight);
+ TBB, FBB, CurBB, TProb, FProb);
SwitchCases.push_back(CB);
return;
}
// Create a CaseBlock record representing this branch.
CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()),
- nullptr, TBB, FBB, CurBB, TWeight, FWeight);
+ nullptr, TBB, FBB, CurBB, TProb, FProb);
SwitchCases.push_back(CB);
}
-/// Scale down both weights to fit into uint32_t.
-static void ScaleWeights(uint64_t &NewTrue, uint64_t &NewFalse) {
- uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
- uint32_t Scale = (NewMax / UINT32_MAX) + 1;
- NewTrue = NewTrue / Scale;
- NewFalse = NewFalse / Scale;
-}
-
/// FindMergedConditions - If Cond is an expression like
void SelectionDAGBuilder::FindMergedConditions(const Value *Cond,
MachineBasicBlock *TBB,
MachineBasicBlock *CurBB,
MachineBasicBlock *SwitchBB,
Instruction::BinaryOps Opc,
- uint32_t TWeight,
- uint32_t FWeight) {
+ BranchProbability TProb,
+ BranchProbability FProb) {
// If this node is not part of the or/and tree, emit it as a branch.
const Instruction *BOp = dyn_cast<Instruction>(Cond);
if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) ||
!InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) ||
!InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) {
EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB,
- TWeight, FWeight);
+ TProb, FProb);
return;
}
// Create TmpBB after CurBB.
- MachineFunction::iterator BBI = CurBB;
+ MachineFunction::iterator BBI(CurBB);
MachineFunction &MF = DAG.getMachineFunction();
MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock());
CurBB->getParent()->insert(++BBI, TmpBB);
// The requirement is that
// TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
// = TrueProb for original BB.
- // Assuming the original weights are A and B, one choice is to set BB1's
- // weights to A and A+2B, and set TmpBB's weights to A and 2B. This choice
- // assumes that
+ // Assuming the original probabilities are A and B, one choice is to set
+ // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to
+ // A/(1+B) and 2B/(1+B). This choice assumes that
// TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
// Another choice is to assume TrueProb for BB1 equals to TrueProb for
// TmpBB, but the math is more complicated.
- uint64_t NewTrueWeight = TWeight;
- uint64_t NewFalseWeight = (uint64_t)TWeight + 2 * (uint64_t)FWeight;
- ScaleWeights(NewTrueWeight, NewFalseWeight);
+ auto NewTrueProb = TProb / 2;
+ auto NewFalseProb = TProb / 2 + FProb;
// Emit the LHS condition.
FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, SwitchBB, Opc,
- NewTrueWeight, NewFalseWeight);
+ NewTrueProb, NewFalseProb);
- NewTrueWeight = TWeight;
- NewFalseWeight = 2 * (uint64_t)FWeight;
- ScaleWeights(NewTrueWeight, NewFalseWeight);
+ // Normalize A/2 and B to get A/(1+B) and 2B/(1+B).
+ SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb};
+ BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
// Emit the RHS condition into TmpBB.
FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
- NewTrueWeight, NewFalseWeight);
+ Probs[0], Probs[1]);
} else {
assert(Opc == Instruction::And && "Unknown merge op!");
// Codegen X & Y as:
// The requirement is that
// FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
// = FalseProb for original BB.
- // Assuming the original weights are A and B, one choice is to set BB1's
- // weights to 2A+B and B, and set TmpBB's weights to 2A and B. This choice
- // assumes that
- // FalseProb for BB1 == TrueProb for BB1 * FalseProb for TmpBB.
-
- uint64_t NewTrueWeight = 2 * (uint64_t)TWeight + (uint64_t)FWeight;
- uint64_t NewFalseWeight = FWeight;
- ScaleWeights(NewTrueWeight, NewFalseWeight);
+ // Assuming the original probabilities are A and B, one choice is to set
+ // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
+ // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
+ // TrueProb for BB1 * FalseProb for TmpBB.
+
+ auto NewTrueProb = TProb + FProb / 2;
+ auto NewFalseProb = FProb / 2;
// Emit the LHS condition.
FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, SwitchBB, Opc,
- NewTrueWeight, NewFalseWeight);
+ NewTrueProb, NewFalseProb);
- NewTrueWeight = 2 * (uint64_t)TWeight;
- NewFalseWeight = FWeight;
- ScaleWeights(NewTrueWeight, NewFalseWeight);
+ // Normalize A and B/2 to get 2A/(1+A) and B/(1+A).
+ SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2};
+ BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
// Emit the RHS condition into TmpBB.
FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, SwitchBB, Opc,
- NewTrueWeight, NewFalseWeight);
+ Probs[0], Probs[1]);
}
}
!I.getMetadata(LLVMContext::MD_unpredictable) &&
(Opcode == Instruction::And || Opcode == Instruction::Or)) {
FindMergedConditions(BOp, Succ0MBB, Succ1MBB, BrMBB, BrMBB,
- Opcode, getEdgeWeight(BrMBB, Succ0MBB),
- getEdgeWeight(BrMBB, Succ1MBB));
+ Opcode,
+ getEdgeProbability(BrMBB, Succ0MBB),
+ getEdgeProbability(BrMBB, Succ1MBB));
// If the compares in later blocks need to use values not currently
// exported from this block, export them now. This block should always
// be the first entry.
}
// Update successor info
- addSuccessorWithWeight(SwitchBB, CB.TrueBB, CB.TrueWeight);
+ addSuccessorWithProb(SwitchBB, CB.TrueBB, CB.TrueProb);
// TrueBB and FalseBB are always different unless the incoming IR is
// degenerate. This only happens when running llc on weird IR.
if (CB.TrueBB != CB.FalseBB)
- addSuccessorWithWeight(SwitchBB, CB.FalseBB, CB.FalseWeight);
+ addSuccessorWithProb(SwitchBB, CB.FalseBB, CB.FalseProb);
+ SwitchBB->normalizeSuccProbs();
// If the lhs block is the next block, invert the condition so that we can
// fall through to the lhs instead of the rhs block.
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
SDValue Chain =
TLI.makeLibCall(DAG, RTLIB::STACKPROTECTOR_CHECK_FAIL, MVT::isVoid,
- nullptr, 0, false, getCurSDLoc(), false, false).second;
+ None, false, getCurSDLoc(), false, false).second;
DAG.setRoot(Chain);
}
MachineBasicBlock* MBB = B.Cases[0].ThisBB;
- addSuccessorWithWeight(SwitchBB, B.Default, B.DefaultWeight);
- addSuccessorWithWeight(SwitchBB, MBB, B.Weight);
+ addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb);
+ addSuccessorWithProb(SwitchBB, MBB, B.Prob);
+ SwitchBB->normalizeSuccProbs();
SDValue BrRange = DAG.getNode(ISD::BRCOND, dl,
MVT::Other, CopyTo, RangeCmp,
/// visitBitTestCase - this function produces one "bit test"
void SelectionDAGBuilder::visitBitTestCase(BitTestBlock &BB,
MachineBasicBlock* NextMBB,
- uint32_t BranchWeightToNext,
+ BranchProbability BranchProbToNext,
unsigned Reg,
BitTestCase &B,
MachineBasicBlock *SwitchBB) {
AndOp, DAG.getConstant(0, dl, VT), ISD::SETNE);
}
- // The branch weight from SwitchBB to B.TargetBB is B.ExtraWeight.
- addSuccessorWithWeight(SwitchBB, B.TargetBB, B.ExtraWeight);
- // The branch weight from SwitchBB to NextMBB is BranchWeightToNext.
- addSuccessorWithWeight(SwitchBB, NextMBB, BranchWeightToNext);
+ // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb.
+ addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb);
+ // The branch probability from SwitchBB to NextMBB is BranchProbToNext.
+ addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
+ // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is
+ // one as they are relative probabilities (and thus work more like weights),
+ // and hence we need to normalize them to let the sum of them become one.
+ SwitchBB->normalizeSuccProbs();
SDValue BrAnd = DAG.getNode(ISD::BRCOND, dl,
MVT::Other, getControlRoot(),
CopyToExportRegsIfNeeded(&I);
}
- SmallVector<MachineBasicBlock *, 1> UnwindDests;
- findUnwindDestinations(FuncInfo, EHPadBB, UnwindDests);
+ SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 1> UnwindDests;
+ BranchProbabilityInfo *BPI = FuncInfo.BPI;
+ BranchProbability EHPadBBProb =
+ BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB)
+ : BranchProbability::getZero();
+ findUnwindDestinations(FuncInfo, EHPadBB, EHPadBBProb, UnwindDests);
// Update successor info.
- // FIXME: The weights for catchpads will be wrong.
- addSuccessorWithWeight(InvokeMBB, Return);
- for (MachineBasicBlock *UnwindDest : UnwindDests) {
- UnwindDest->setIsEHPad();
- addSuccessorWithWeight(InvokeMBB, UnwindDest);
+ addSuccessorWithProb(InvokeMBB, Return);
+ for (auto &UnwindDest : UnwindDests) {
+ UnwindDest.first->setIsEHPad();
+ addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second);
}
+ InvokeMBB->normalizeSuccProbs();
// Drop into normal successor.
DAG.setRoot(DAG.getNode(ISD::BR, getCurSDLoc(),
// If there aren't registers to copy the values into (e.g., during SjLj
// exceptions), then don't bother to create these DAG nodes.
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
- if (TLI.getExceptionPointerRegister() == 0 &&
- TLI.getExceptionSelectorRegister() == 0)
+ const Constant *PersonalityFn = FuncInfo.Fn->getPersonalityFn();
+ if (TLI.getExceptionPointerRegister(PersonalityFn) == 0 &&
+ TLI.getExceptionSelectorRegister(PersonalityFn) == 0)
return;
SmallVector<EVT, 2> ValueVTs;
// If this case has the same successor and is a neighbour, merge it into
// the previous cluster.
Clusters[DstIndex - 1].High = CaseVal;
- Clusters[DstIndex - 1].Weight += CC.Weight;
- assert(Clusters[DstIndex - 1].Weight >= CC.Weight && "Weight overflow!");
+ Clusters[DstIndex - 1].Prob += CC.Prob;
} else {
std::memmove(&Clusters[DstIndex++], &Clusters[SrcIndex],
sizeof(Clusters[SrcIndex]));
continue;
MachineBasicBlock *Succ = FuncInfo.MBBMap[BB];
- addSuccessorWithWeight(IndirectBrMBB, Succ);
+ addSuccessorWithProb(IndirectBrMBB, Succ);
}
DAG.setRoot(DAG.getNode(ISD::BRIND, getCurSDLoc(),
void SelectionDAGBuilder::visitUnreachable(const UnreachableInst &I) {
if (DAG.getTarget().Options.TrapUnreachable)
- DAG.setRoot(DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, DAG.getRoot()));
+ DAG.setRoot(
+ DAG.getNode(ISD::TRAP, getCurSDLoc(), MVT::Other, DAG.getRoot()));
}
void SelectionDAGBuilder::visitFSub(const User &I) {
return DAG.getNode(ISD::FPOWI, DL, LHS.getValueType(), LHS, RHS);
}
-// getTruncatedArgReg - Find underlying register used for an truncated
-// argument.
-static unsigned getTruncatedArgReg(const SDValue &N) {
- if (N.getOpcode() != ISD::TRUNCATE)
+// getUnderlyingArgReg - Find underlying register used for a truncated or
+// bitcasted argument.
+static unsigned getUnderlyingArgReg(const SDValue &N) {
+ switch (N.getOpcode()) {
+ case ISD::CopyFromReg:
+ return cast<RegisterSDNode>(N.getOperand(1))->getReg();
+ case ISD::BITCAST:
+ case ISD::AssertZext:
+ case ISD::AssertSext:
+ case ISD::TRUNCATE:
+ return getUnderlyingArgReg(N.getOperand(0));
+ default:
return 0;
-
- const SDValue &Ext = N.getOperand(0);
- if (Ext.getOpcode() == ISD::AssertZext ||
- Ext.getOpcode() == ISD::AssertSext) {
- const SDValue &CFR = Ext.getOperand(0);
- if (CFR.getOpcode() == ISD::CopyFromReg)
- return cast<RegisterSDNode>(CFR.getOperand(1))->getReg();
- if (CFR.getOpcode() == ISD::TRUNCATE)
- return getTruncatedArgReg(CFR);
}
- return 0;
}
/// EmitFuncArgumentDbgValue - If the DbgValueInst is a dbg_value of a function
Op = MachineOperand::CreateFI(FI);
if (!Op && N.getNode()) {
- unsigned Reg;
- if (N.getOpcode() == ISD::CopyFromReg)
- Reg = cast<RegisterSDNode>(N.getOperand(1))->getReg();
- else
- Reg = getTruncatedArgReg(N);
+ unsigned Reg = getUnderlyingArgReg(N);
if (Reg && TargetRegisterInfo::isVirtualRegister(Reg)) {
MachineRegisterInfo &RegInfo = MF.getRegInfo();
unsigned PR = RegInfo.getLiveInPhysReg(Reg);
N);
return nullptr;
}
- } else if (AI)
+ } else {
SDV = DAG.getDbgValue(Variable, Expression, N.getNode(), N.getResNo(),
true, 0, dl, SDNodeOrder);
- else {
- // Can't do anything with other non-AI cases yet.
- DEBUG(dbgs() << "Dropping debug info for " << DI << "\n");
- DEBUG(dbgs() << "non-AllocaInst issue for Address: \n\t");
- DEBUG(Address->dump());
- return nullptr;
}
DAG.AddDbgValue(SDV, N.getNode(), isParameter);
} else {
DAG.setRoot(Res.getValue(1));
return nullptr;
}
+ case Intrinsic::bitreverse:
+ setValue(&I, DAG.getNode(ISD::BITREVERSE, sdl,
+ getValue(I.getArgOperand(0)).getValueType(),
+ getValue(I.getArgOperand(0))));
+ return nullptr;
case Intrinsic::bswap:
setValue(&I, DAG.getNode(ISD::BSWAP, sdl,
getValue(I.getArgOperand(0)).getValueType(),
}
case Intrinsic::clear_cache:
return TLI.getClearCacheBuiltinName();
- case Intrinsic::eh_actions:
- setValue(&I, DAG.getUNDEF(TLI.getPointerTy(DAG.getDataLayout())));
- return nullptr;
case Intrinsic::donothing:
// ignore
return nullptr;
}
case Intrinsic::instrprof_increment:
llvm_unreachable("instrprof failed to lower an increment");
-
+ case Intrinsic::instrprof_value_profile:
+ llvm_unreachable("instrprof failed to lower a value profiling call");
case Intrinsic::localescape: {
MachineFunction &MF = DAG.getMachineFunction();
const TargetInstrInfo *TII = DAG.getSubtarget().getInstrInfo();
return nullptr;
}
- case Intrinsic::eh_begincatch:
- case Intrinsic::eh_endcatch:
- llvm_unreachable("begin/end catch intrinsics not lowered in codegen");
+
+ case Intrinsic::eh_exceptionpointer:
case Intrinsic::eh_exceptioncode: {
- unsigned Reg = TLI.getExceptionPointerRegister();
- assert(Reg && "cannot get exception code on this platform");
+ // Get the exception pointer vreg, copy from it, and resize it to fit.
+ const auto *CPI = cast<CatchPadInst>(I.getArgOperand(0));
MVT PtrVT = TLI.getPointerTy(DAG.getDataLayout());
const TargetRegisterClass *PtrRC = TLI.getRegClassFor(PtrVT);
- assert(FuncInfo.MBB->isEHPad() && "eh.exceptioncode in non-lpad");
- unsigned VReg = FuncInfo.MBB->addLiveIn(Reg, PtrRC);
+ unsigned VReg = FuncInfo.getCatchPadExceptionPointerVReg(CPI, PtrRC);
SDValue N =
DAG.getCopyFromReg(DAG.getEntryNode(), getCurSDLoc(), VReg, PtrVT);
- N = DAG.getZExtOrTrunc(N, getCurSDLoc(), MVT::i32);
+ if (Intrinsic == Intrinsic::eh_exceptioncode)
+ N = DAG.getZExtOrTrunc(N, getCurSDLoc(), MVT::i32);
setValue(&I, N);
return nullptr;
}
DAG.setRoot(DAG.getEHLabel(getCurSDLoc(), getRoot(), EndLabel));
// Inform MachineModuleInfo of range.
- MMI.addInvoke(FuncInfo.MBBMap[EHPadBB], BeginLabel, EndLabel);
+ if (MMI.hasEHFunclets()) {
+ WinEHFuncInfo *EHInfo = DAG.getMachineFunction().getWinEHFuncInfo();
+ EHInfo->addIPToStateRange(EHPadBB, BeginLabel, EndLabel);
+ } else {
+ MMI.addInvoke(FuncInfo.MBBMap[EHPadBB], BeginLabel, EndLabel);
+ }
}
return Result;
if (FastISel)
return A->use_empty();
- const BasicBlock *Entry = A->getParent()->begin();
+ const BasicBlock &Entry = A->getParent()->front();
for (const User *U : A->users())
- if (cast<Instruction>(U)->getParent() != Entry || isa<SwitchInst>(U))
+ if (cast<Instruction>(U)->getParent() != &Entry || isa<SwitchInst>(U))
return false; // Use not in entry block.
return true;
// If this argument is unused then remember its value. It is used to generate
// debugging information.
if (I->use_empty() && NumValues) {
- SDB->setUnusedArgValue(I, InVals[i]);
+ SDB->setUnusedArgValue(&*I, InVals[i]);
// Also remember any frame index for use in FastISel.
if (FrameIndexSDNode *FI =
dyn_cast<FrameIndexSDNode>(InVals[i].getNode()))
- FuncInfo->setArgumentFrameIndex(I, FI->getIndex());
+ FuncInfo->setArgumentFrameIndex(&*I, FI->getIndex());
}
for (unsigned Val = 0; Val != NumValues; ++Val) {
// Note down frame index.
if (FrameIndexSDNode *FI =
dyn_cast<FrameIndexSDNode>(ArgValues[0].getNode()))
- FuncInfo->setArgumentFrameIndex(I, FI->getIndex());
+ FuncInfo->setArgumentFrameIndex(&*I, FI->getIndex());
SDValue Res = DAG.getMergeValues(makeArrayRef(ArgValues.data(), NumValues),
SDB->getCurSDLoc());
- SDB->setValue(I, Res);
+ SDB->setValue(&*I, Res);
if (!TM.Options.EnableFastISel && Res.getOpcode() == ISD::BUILD_PAIR) {
if (LoadSDNode *LNode =
dyn_cast<LoadSDNode>(Res.getOperand(0).getNode()))
if (FrameIndexSDNode *FI =
dyn_cast<FrameIndexSDNode>(LNode->getBasePtr().getNode()))
- FuncInfo->setArgumentFrameIndex(I, FI->getIndex());
+ FuncInfo->setArgumentFrameIndex(&*I, FI->getIndex());
}
// If this argument is live outside of the entry block, insert a copy from
// uses with vregs.
unsigned Reg = cast<RegisterSDNode>(Res.getOperand(1))->getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
- FuncInfo->ValueMap[I] = Reg;
+ FuncInfo->ValueMap[&*I] = Reg;
continue;
}
}
- if (!isOnlyUsedInEntryBlock(I, TM.Options.EnableFastISel)) {
- FuncInfo->InitializeRegForValue(I);
- SDB->CopyToExportRegsIfNeeded(I);
+ if (!isOnlyUsedInEntryBlock(&*I, TM.Options.EnableFastISel)) {
+ FuncInfo->InitializeRegForValue(&*I);
+ SDB->CopyToExportRegsIfNeeded(&*I);
}
}
// If SuccBB has not been created yet, create it.
if (!SuccMBB) {
MachineFunction *MF = ParentMBB->getParent();
- MachineFunction::iterator BBI = ParentMBB;
+ MachineFunction::iterator BBI(ParentMBB);
SuccMBB = MF->CreateMachineBasicBlock(BB);
MF->insert(++BBI, SuccMBB);
}
// Add it as a successor of ParentMBB.
ParentMBB->addSuccessor(
- SuccMBB, BranchProbabilityInfo::getBranchWeightStackProtector(IsLikely));
+ SuccMBB, BranchProbabilityInfo::getBranchProbStackProtector(IsLikely));
return SuccMBB;
}
MachineBasicBlock *SelectionDAGBuilder::NextBlock(MachineBasicBlock *MBB) {
- MachineFunction::iterator I = MBB;
+ MachineFunction::iterator I(MBB);
if (++I == FuncInfo.MF->end())
return nullptr;
- return I;
+ return &*I;
}
/// During lowering new call nodes can be created (such as memset, etc.).
CaseCluster &JTCluster) {
assert(First <= Last);
- uint32_t Weight = 0;
+ auto Prob = BranchProbability::getZero();
unsigned NumCmps = 0;
std::vector<MachineBasicBlock*> Table;
- DenseMap<MachineBasicBlock*, uint32_t> JTWeights;
+ DenseMap<MachineBasicBlock*, BranchProbability> JTProbs;
+
+ // Initialize probabilities in JTProbs.
+ for (unsigned I = First; I <= Last; ++I)
+ JTProbs[Clusters[I].MBB] = BranchProbability::getZero();
+
for (unsigned I = First; I <= Last; ++I) {
assert(Clusters[I].Kind == CC_Range);
- Weight += Clusters[I].Weight;
- assert(Weight >= Clusters[I].Weight && "Weight overflow!");
+ Prob += Clusters[I].Prob;
APInt Low = Clusters[I].Low->getValue();
APInt High = Clusters[I].High->getValue();
NumCmps += (Low == High) ? 1 : 2;
uint64_t ClusterSize = (High - Low).getLimitedValue() + 1;
for (uint64_t J = 0; J < ClusterSize; ++J)
Table.push_back(Clusters[I].MBB);
- JTWeights[Clusters[I].MBB] += Clusters[I].Weight;
+ JTProbs[Clusters[I].MBB] += Clusters[I].Prob;
}
- unsigned NumDests = JTWeights.size();
+ unsigned NumDests = JTProbs.size();
if (isSuitableForBitTests(NumDests, NumCmps,
Clusters[First].Low->getValue(),
Clusters[Last].High->getValue())) {
for (MachineBasicBlock *Succ : Table) {
if (Done.count(Succ))
continue;
- addSuccessorWithWeight(JumpTableMBB, Succ, JTWeights[Succ]);
+ addSuccessorWithProb(JumpTableMBB, Succ, JTProbs[Succ]);
Done.insert(Succ);
}
+ JumpTableMBB->normalizeSuccProbs();
const TargetLowering &TLI = DAG.getTargetLoweringInfo();
unsigned JTI = CurMF->getOrCreateJumpTableInfo(TLI.getJumpTableEncoding())
JTCases.emplace_back(std::move(JTH), std::move(JT));
JTCluster = CaseCluster::jumpTable(Clusters[First].Low, Clusters[Last].High,
- JTCases.size() - 1, Weight);
+ JTCases.size() - 1, Prob);
return true;
}
}
CaseBitsVector CBV;
- uint32_t TotalWeight = 0;
+ auto TotalProb = BranchProbability::getZero();
for (unsigned i = First; i <= Last; ++i) {
// Find the CaseBits for this destination.
unsigned j;
if (CBV[j].BB == Clusters[i].MBB)
break;
if (j == CBV.size())
- CBV.push_back(CaseBits(0, Clusters[i].MBB, 0, 0));
+ CBV.push_back(
+ CaseBits(0, Clusters[i].MBB, 0, BranchProbability::getZero()));
CaseBits *CB = &CBV[j];
- // Update Mask, Bits and ExtraWeight.
+ // Update Mask, Bits and ExtraProb.
uint64_t Lo = (Clusters[i].Low->getValue() - LowBound).getZExtValue();
uint64_t Hi = (Clusters[i].High->getValue() - LowBound).getZExtValue();
assert(Hi >= Lo && Hi < 64 && "Invalid bit case!");
CB->Mask |= (-1ULL >> (63 - (Hi - Lo))) << Lo;
CB->Bits += Hi - Lo + 1;
- CB->ExtraWeight += Clusters[i].Weight;
- TotalWeight += Clusters[i].Weight;
- assert(TotalWeight >= Clusters[i].Weight && "Weight overflow!");
+ CB->ExtraProb += Clusters[i].Prob;
+ TotalProb += Clusters[i].Prob;
}
BitTestInfo BTI;
std::sort(CBV.begin(), CBV.end(), [](const CaseBits &a, const CaseBits &b) {
- // Sort by weight first, number of bits second.
- if (a.ExtraWeight != b.ExtraWeight)
- return a.ExtraWeight > b.ExtraWeight;
+ // Sort by probability first, number of bits second.
+ if (a.ExtraProb != b.ExtraProb)
+ return a.ExtraProb > b.ExtraProb;
return a.Bits > b.Bits;
});
for (auto &CB : CBV) {
MachineBasicBlock *BitTestBB =
FuncInfo.MF->CreateMachineBasicBlock(SI->getParent());
- BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraWeight));
+ BTI.push_back(BitTestCase(CB.Mask, BitTestBB, CB.BB, CB.ExtraProb));
}
BitTestCases.emplace_back(std::move(LowBound), std::move(CmpRange),
SI->getCondition(), -1U, MVT::Other, false,
ContiguousRange, nullptr, nullptr, std::move(BTI),
- TotalWeight);
+ TotalProb);
BTCluster = CaseCluster::bitTests(Clusters[First].Low, Clusters[Last].High,
- BitTestCases.size() - 1, TotalWeight);
+ BitTestCases.size() - 1, TotalProb);
return true;
}
MachineBasicBlock *DefaultMBB) {
MachineFunction *CurMF = FuncInfo.MF;
MachineBasicBlock *NextMBB = nullptr;
- MachineFunction::iterator BBI = W.MBB;
+ MachineFunction::iterator BBI(W.MBB);
if (++BBI != FuncInfo.MF->end())
- NextMBB = BBI;
+ NextMBB = &*BBI;
unsigned Size = W.LastCluster - W.FirstCluster + 1;
ISD::SETEQ);
// Update successor info.
- // Both Small and Big will jump to Small.BB, so we sum up the weights.
- addSuccessorWithWeight(SwitchMBB, Small.MBB, Small.Weight + Big.Weight);
- addSuccessorWithWeight(
- SwitchMBB, DefaultMBB,
- // The default destination is the first successor in IR.
- BPI ? BPI->getEdgeWeight(SwitchMBB->getBasicBlock(), (unsigned)0)
- : 0);
+ // Both Small and Big will jump to Small.BB, so we sum up the
+ // probabilities.
+ addSuccessorWithProb(SwitchMBB, Small.MBB, Small.Prob + Big.Prob);
+ if (BPI)
+ addSuccessorWithProb(
+ SwitchMBB, DefaultMBB,
+ // The default destination is the first successor in IR.
+ BPI->getEdgeProbability(SwitchMBB->getBasicBlock(), (unsigned)0));
+ else
+ addSuccessorWithProb(SwitchMBB, DefaultMBB);
// Insert the true branch.
SDValue BrCond =
}
if (TM.getOptLevel() != CodeGenOpt::None) {
- // Order cases by weight so the most likely case will be checked first.
+ // Order cases by probability so the most likely case will be checked first.
std::sort(W.FirstCluster, W.LastCluster + 1,
[](const CaseCluster &a, const CaseCluster &b) {
- return a.Weight > b.Weight;
+ return a.Prob > b.Prob;
});
// Rearrange the case blocks so that the last one falls through if possible
- // without without changing the order of weights.
+ // without without changing the order of probabilities.
for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster; ) {
--I;
- if (I->Weight > W.LastCluster->Weight)
+ if (I->Prob > W.LastCluster->Prob)
break;
if (I->Kind == CC_Range && I->MBB == NextMBB) {
std::swap(*I, *W.LastCluster);
}
}
- // Compute total weight.
- uint32_t DefaultWeight = W.DefaultWeight;
- uint32_t UnhandledWeights = DefaultWeight;
- for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I) {
- UnhandledWeights += I->Weight;
- assert(UnhandledWeights >= I->Weight && "Weight overflow!");
- }
+ // Compute total probability.
+ BranchProbability DefaultProb = W.DefaultProb;
+ BranchProbability UnhandledProbs = DefaultProb;
+ for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I)
+ UnhandledProbs += I->Prob;
MachineBasicBlock *CurMBB = W.MBB;
for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
// Put Cond in a virtual register to make it available from the new blocks.
ExportFromCurrentBlock(Cond);
}
- UnhandledWeights -= I->Weight;
+ UnhandledProbs -= I->Prob;
switch (I->Kind) {
case CC_JumpTable: {
MachineBasicBlock *JumpMBB = JT->MBB;
CurMF->insert(BBI, JumpMBB);
- uint32_t JumpWeight = I->Weight;
- uint32_t FallthroughWeight = UnhandledWeights;
+ auto JumpProb = I->Prob;
+ auto FallthroughProb = UnhandledProbs;
- // If Fallthrough is a target of the jump table, we evenly distribute
- // the weight on the edge to Fallthrough to successors of CurMBB.
- // Also update the weight on the edge from JumpMBB to Fallthrough.
+ // If the default statement is a target of the jump table, we evenly
+ // distribute the default probability to successors of CurMBB. Also
+ // update the probability on the edge from JumpMBB to Fallthrough.
for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(),
SE = JumpMBB->succ_end();
SI != SE; ++SI) {
- if (*SI == Fallthrough) {
- JumpWeight += DefaultWeight / 2;
- FallthroughWeight -= DefaultWeight / 2;
- JumpMBB->setSuccWeight(SI, DefaultWeight / 2);
+ if (*SI == DefaultMBB) {
+ JumpProb += DefaultProb / 2;
+ FallthroughProb -= DefaultProb / 2;
+ JumpMBB->setSuccProbability(SI, DefaultProb / 2);
break;
}
}
- addSuccessorWithWeight(CurMBB, Fallthrough, FallthroughWeight);
- addSuccessorWithWeight(CurMBB, JumpMBB, JumpWeight);
+ addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb);
+ addSuccessorWithProb(CurMBB, JumpMBB, JumpProb);
// The jump table header will be inserted in our current block, do the
// range check, and fall through to our fallthrough block.
BTB->Parent = CurMBB;
BTB->Default = Fallthrough;
- BTB->DefaultWeight = UnhandledWeights;
+ BTB->DefaultProb = UnhandledProbs;
// If the cases in bit test don't form a contiguous range, we evenly
- // distribute the weight on the edge to Fallthrough to two successors
- // of CurMBB.
+ // distribute the probability on the edge to Fallthrough to two
+ // successors of CurMBB.
if (!BTB->ContiguousRange) {
- BTB->Weight += DefaultWeight / 2;
- BTB->DefaultWeight -= DefaultWeight / 2;
+ BTB->Prob += DefaultProb / 2;
+ BTB->DefaultProb -= DefaultProb / 2;
}
// If we're in the right place, emit the bit test header right now.
RHS = I->High;
}
- // The false weight is the sum of all unhandled cases.
- CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Weight,
- UnhandledWeights);
+ // The false probability is the sum of all unhandled cases.
+ CaseBlock CB(CC, LHS, RHS, MHS, I->MBB, Fallthrough, CurMBB, I->Prob,
+ UnhandledProbs);
if (CurMBB == SwitchMBB)
visitSwitchCase(CB, SwitchMBB);
CaseClusterIt First,
CaseClusterIt Last) {
return std::count_if(First, Last + 1, [&](const CaseCluster &X) {
- if (X.Weight != CC.Weight)
- return X.Weight > CC.Weight;
+ if (X.Prob != CC.Prob)
+ return X.Prob > CC.Prob;
// Ties are broken by comparing the case value.
return X.Low->getValue().slt(CC.Low->getValue());
assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!");
- // Balance the tree based on branch weights to create a near-optimal (in terms
- // of search time given key frequency) binary search tree. See e.g. Kurt
+ // Balance the tree based on branch probabilities to create a near-optimal (in
+ // terms of search time given key frequency) binary search tree. See e.g. Kurt
// Mehlhorn "Nearly Optimal Binary Search Trees" (1975).
CaseClusterIt LastLeft = W.FirstCluster;
CaseClusterIt FirstRight = W.LastCluster;
- uint32_t LeftWeight = LastLeft->Weight + W.DefaultWeight / 2;
- uint32_t RightWeight = FirstRight->Weight + W.DefaultWeight / 2;
+ auto LeftProb = LastLeft->Prob + W.DefaultProb / 2;
+ auto RightProb = FirstRight->Prob + W.DefaultProb / 2;
// Move LastLeft and FirstRight towards each other from opposite directions to
- // find a partitioning of the clusters which balances the weight on both
- // sides. If LeftWeight and RightWeight are equal, alternate which side is
- // taken to ensure 0-weight nodes are distributed evenly.
+ // find a partitioning of the clusters which balances the probability on both
+ // sides. If LeftProb and RightProb are equal, alternate which side is
+ // taken to ensure 0-probability nodes are distributed evenly.
unsigned I = 0;
while (LastLeft + 1 < FirstRight) {
- if (LeftWeight < RightWeight || (LeftWeight == RightWeight && (I & 1)))
- LeftWeight += (++LastLeft)->Weight;
+ if (LeftProb < RightProb || (LeftProb == RightProb && (I & 1)))
+ LeftProb += (++LastLeft)->Prob;
else
- RightWeight += (--FirstRight)->Weight;
+ RightProb += (--FirstRight)->Prob;
I++;
}
const ConstantInt *Pivot = PivotCluster->Low;
// New blocks will be inserted immediately after the current one.
- MachineFunction::iterator BBI = W.MBB;
+ MachineFunction::iterator BBI(W.MBB);
++BBI;
// We will branch to the LHS if Value < Pivot. If LHS is a single cluster,
LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
FuncInfo.MF->insert(BBI, LeftMBB);
WorkList.push_back(
- {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultWeight / 2});
+ {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultProb / 2});
// Put Cond in a virtual register to make it available from the new blocks.
ExportFromCurrentBlock(Cond);
}
RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
FuncInfo.MF->insert(BBI, RightMBB);
WorkList.push_back(
- {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultWeight / 2});
+ {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultProb / 2});
// Put Cond in a virtual register to make it available from the new blocks.
ExportFromCurrentBlock(Cond);
}
// Create the CaseBlock record that will be used to lower the branch.
CaseBlock CB(ISD::SETLT, Cond, Pivot, nullptr, LeftMBB, RightMBB, W.MBB,
- LeftWeight, RightWeight);
+ LeftProb, RightProb);
if (W.MBB == SwitchMBB)
visitSwitchCase(CB, SwitchMBB);
for (auto I : SI.cases()) {
MachineBasicBlock *Succ = FuncInfo.MBBMap[I.getCaseSuccessor()];
const ConstantInt *CaseVal = I.getCaseValue();
- uint32_t Weight =
- BPI ? BPI->getEdgeWeight(SI.getParent(), I.getSuccessorIndex()) : 0;
- Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Weight));
+ BranchProbability Prob =
+ BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex())
+ : BranchProbability(1, SI.getNumCases() + 1);
+ Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob));
}
MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[SI.getDefaultDest()];
SwitchWorkList WorkList;
CaseClusterIt First = Clusters.begin();
CaseClusterIt Last = Clusters.end() - 1;
- uint32_t DefaultWeight = getEdgeWeight(SwitchMBB, DefaultMBB);
- WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultWeight});
+ auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB);
+ WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb});
while (!WorkList.empty()) {
SwitchWorkListItem W = WorkList.back();