#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
-#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
bool PreRegAlloc;
bool MadeChange;
int FnNum;
+ std::function<bool(const Function &)> PredicateFtor;
+
public:
static char ID;
- IfConverter() : MachineFunctionPass(ID), FnNum(-1) {
+ IfConverter(std::function<bool(const Function &)> Ftor = nullptr)
+ : MachineFunctionPass(ID), FnNum(-1), PredicateFtor(Ftor) {
initializeIfConverterPass(*PassRegistry::getPassRegistry());
}
bool ValidDiamond(BBInfo &TrueBBI, BBInfo &FalseBBI,
unsigned &Dups1, unsigned &Dups2) const;
void ScanInstructions(BBInfo &BBI);
- BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
- std::vector<IfcvtToken*> &Tokens);
+ void AnalyzeBlock(MachineBasicBlock *MBB, std::vector<IfcvtToken*> &Tokens);
bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
bool isTriangle = false, bool RevBranch = false);
void AnalyzeBlocks(MachineFunction &MF, std::vector<IfcvtToken*> &Tokens);
INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false)
bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
+ if (PredicateFtor && !PredicateFtor(*MF.getFunction()))
+ return false;
+
const TargetSubtargetInfo &ST = MF.getSubtarget();
TLI = ST.getTargetLowering();
TII = ST.getInstrInfo();
/// AnalyzeBlock - Analyze the structure of the sub-CFG starting from
/// the specified block. Record its successors and whether it looks like an
/// if-conversion candidate.
-IfConverter::BBInfo &IfConverter::AnalyzeBlock(MachineBasicBlock *BB,
- std::vector<IfcvtToken*> &Tokens) {
- BBInfo &BBI = BBAnalysis[BB->getNumber()];
+void IfConverter::AnalyzeBlock(MachineBasicBlock *MBB,
+ std::vector<IfcvtToken*> &Tokens) {
+ struct BBState {
+ BBState(MachineBasicBlock *BB) : MBB(BB), SuccsAnalyzed(false) {}
+ MachineBasicBlock *MBB;
+
+ /// This flag is true if MBB's successors have been analyzed.
+ bool SuccsAnalyzed;
+ };
- if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed)
- return BBI;
+ // Push MBB to the stack.
+ SmallVector<BBState, 16> BBStack(1, MBB);
- BBI.BB = BB;
- BBI.IsBeingAnalyzed = true;
+ while (!BBStack.empty()) {
+ BBState &State = BBStack.back();
+ MachineBasicBlock *BB = State.MBB;
+ BBInfo &BBI = BBAnalysis[BB->getNumber()];
- ScanInstructions(BBI);
+ if (!State.SuccsAnalyzed) {
+ if (BBI.IsAnalyzed || BBI.IsBeingAnalyzed) {
+ BBStack.pop_back();
+ continue;
+ }
- // Unanalyzable or ends with fallthrough or unconditional branch, or if is not
- // considered for ifcvt anymore.
- if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
- BBI.IsBeingAnalyzed = false;
- BBI.IsAnalyzed = true;
- return BBI;
- }
+ BBI.BB = BB;
+ BBI.IsBeingAnalyzed = true;
- // Do not ifcvt if either path is a back edge to the entry block.
- if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
- BBI.IsBeingAnalyzed = false;
- BBI.IsAnalyzed = true;
- return BBI;
- }
+ ScanInstructions(BBI);
- // Do not ifcvt if true and false fallthrough blocks are the same.
- if (!BBI.FalseBB) {
- BBI.IsBeingAnalyzed = false;
- BBI.IsAnalyzed = true;
- return BBI;
- }
+ // Unanalyzable or ends with fallthrough or unconditional branch, or if is
+ // not considered for ifcvt anymore.
+ if (!BBI.IsBrAnalyzable || BBI.BrCond.empty() || BBI.IsDone) {
+ BBI.IsBeingAnalyzed = false;
+ BBI.IsAnalyzed = true;
+ BBStack.pop_back();
+ continue;
+ }
- BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens);
- BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
+ // Do not ifcvt if either path is a back edge to the entry block.
+ if (BBI.TrueBB == BB || BBI.FalseBB == BB) {
+ BBI.IsBeingAnalyzed = false;
+ BBI.IsAnalyzed = true;
+ BBStack.pop_back();
+ continue;
+ }
- if (TrueBBI.IsDone && FalseBBI.IsDone) {
- BBI.IsBeingAnalyzed = false;
- BBI.IsAnalyzed = true;
- return BBI;
- }
+ // Do not ifcvt if true and false fallthrough blocks are the same.
+ if (!BBI.FalseBB) {
+ BBI.IsBeingAnalyzed = false;
+ BBI.IsAnalyzed = true;
+ BBStack.pop_back();
+ continue;
+ }
- SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
- bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
+ // Push the False and True blocks to the stack.
+ State.SuccsAnalyzed = true;
+ BBStack.push_back(BBI.FalseBB);
+ BBStack.push_back(BBI.TrueBB);
+ continue;
+ }
- unsigned Dups = 0;
- unsigned Dups2 = 0;
- bool TNeedSub = !TrueBBI.Predicate.empty();
- bool FNeedSub = !FalseBBI.Predicate.empty();
- bool Enqueued = false;
+ BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
+ BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
- BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
+ if (TrueBBI.IsDone && FalseBBI.IsDone) {
+ BBI.IsBeingAnalyzed = false;
+ BBI.IsAnalyzed = true;
+ BBStack.pop_back();
+ continue;
+ }
- if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
- MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) +
- TrueBBI.ExtraCost), TrueBBI.ExtraCost2,
- *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) +
- FalseBBI.ExtraCost),FalseBBI.ExtraCost2,
- Prediction) &&
- FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
- FeasibilityAnalysis(FalseBBI, RevCond)) {
- // Diamond:
- // EBB
- // / \_
- // | |
- // TBB FBB
- // \ /
- // TailBB
- // Note TailBB can be empty.
- Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
- Dups2));
- Enqueued = true;
- }
+ SmallVector<MachineOperand, 4>
+ RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
+ bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
- if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
- MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
- TrueBBI.ExtraCost2, Prediction) &&
- FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
- // Triangle:
- // EBB
- // | \_
- // | |
- // | TBB
- // | /
- // FBB
- Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
- Enqueued = true;
- }
+ unsigned Dups = 0;
+ unsigned Dups2 = 0;
+ bool TNeedSub = !TrueBBI.Predicate.empty();
+ bool FNeedSub = !FalseBBI.Predicate.empty();
+ bool Enqueued = false;
- if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
- MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
- TrueBBI.ExtraCost2, Prediction) &&
- FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
- Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
- Enqueued = true;
- }
+ BranchProbability Prediction = MBPI->getEdgeProbability(BB, TrueBBI.BB);
- if (ValidSimple(TrueBBI, Dups, Prediction) &&
- MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
- TrueBBI.ExtraCost2, Prediction) &&
- FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
- // Simple (split, no rejoin):
- // EBB
- // | \_
- // | |
- // | TBB---> exit
- // |
- // FBB
- Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
- Enqueued = true;
- }
+ if (CanRevCond && ValidDiamond(TrueBBI, FalseBBI, Dups, Dups2) &&
+ MeetIfcvtSizeLimit(*TrueBBI.BB, (TrueBBI.NonPredSize - (Dups + Dups2) +
+ TrueBBI.ExtraCost), TrueBBI.ExtraCost2,
+ *FalseBBI.BB, (FalseBBI.NonPredSize - (Dups + Dups2) +
+ FalseBBI.ExtraCost),FalseBBI.ExtraCost2,
+ Prediction) &&
+ FeasibilityAnalysis(TrueBBI, BBI.BrCond) &&
+ FeasibilityAnalysis(FalseBBI, RevCond)) {
+ // Diamond:
+ // EBB
+ // / \_
+ // | |
+ // TBB FBB
+ // \ /
+ // TailBB
+ // Note TailBB can be empty.
+ Tokens.push_back(new IfcvtToken(BBI, ICDiamond, TNeedSub|FNeedSub, Dups,
+ Dups2));
+ Enqueued = true;
+ }
- if (CanRevCond) {
- // Try the other path...
- if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
- Prediction.getCompl()) &&
- MeetIfcvtSizeLimit(*FalseBBI.BB,
- FalseBBI.NonPredSize + FalseBBI.ExtraCost,
- FalseBBI.ExtraCost2, Prediction.getCompl()) &&
- FeasibilityAnalysis(FalseBBI, RevCond, true)) {
- Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
+ if (ValidTriangle(TrueBBI, FalseBBI, false, Dups, Prediction) &&
+ MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
+ TrueBBI.ExtraCost2, Prediction) &&
+ FeasibilityAnalysis(TrueBBI, BBI.BrCond, true)) {
+ // Triangle:
+ // EBB
+ // | \_
+ // | |
+ // | TBB
+ // | /
+ // FBB
+ Tokens.push_back(new IfcvtToken(BBI, ICTriangle, TNeedSub, Dups));
Enqueued = true;
}
- if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
- Prediction.getCompl()) &&
- MeetIfcvtSizeLimit(*FalseBBI.BB,
- FalseBBI.NonPredSize + FalseBBI.ExtraCost,
- FalseBBI.ExtraCost2, Prediction.getCompl()) &&
- FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
- Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
+ if (ValidTriangle(TrueBBI, FalseBBI, true, Dups, Prediction) &&
+ MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
+ TrueBBI.ExtraCost2, Prediction) &&
+ FeasibilityAnalysis(TrueBBI, BBI.BrCond, true, true)) {
+ Tokens.push_back(new IfcvtToken(BBI, ICTriangleRev, TNeedSub, Dups));
Enqueued = true;
}
- if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
- MeetIfcvtSizeLimit(*FalseBBI.BB,
- FalseBBI.NonPredSize + FalseBBI.ExtraCost,
- FalseBBI.ExtraCost2, Prediction.getCompl()) &&
- FeasibilityAnalysis(FalseBBI, RevCond)) {
- Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
+ if (ValidSimple(TrueBBI, Dups, Prediction) &&
+ MeetIfcvtSizeLimit(*TrueBBI.BB, TrueBBI.NonPredSize + TrueBBI.ExtraCost,
+ TrueBBI.ExtraCost2, Prediction) &&
+ FeasibilityAnalysis(TrueBBI, BBI.BrCond)) {
+ // Simple (split, no rejoin):
+ // EBB
+ // | \_
+ // | |
+ // | TBB---> exit
+ // |
+ // FBB
+ Tokens.push_back(new IfcvtToken(BBI, ICSimple, TNeedSub, Dups));
Enqueued = true;
}
- }
- BBI.IsEnqueued = Enqueued;
- BBI.IsBeingAnalyzed = false;
- BBI.IsAnalyzed = true;
- return BBI;
+ if (CanRevCond) {
+ // Try the other path...
+ if (ValidTriangle(FalseBBI, TrueBBI, false, Dups,
+ Prediction.getCompl()) &&
+ MeetIfcvtSizeLimit(*FalseBBI.BB,
+ FalseBBI.NonPredSize + FalseBBI.ExtraCost,
+ FalseBBI.ExtraCost2, Prediction.getCompl()) &&
+ FeasibilityAnalysis(FalseBBI, RevCond, true)) {
+ Tokens.push_back(new IfcvtToken(BBI, ICTriangleFalse, FNeedSub, Dups));
+ Enqueued = true;
+ }
+
+ if (ValidTriangle(FalseBBI, TrueBBI, true, Dups,
+ Prediction.getCompl()) &&
+ MeetIfcvtSizeLimit(*FalseBBI.BB,
+ FalseBBI.NonPredSize + FalseBBI.ExtraCost,
+ FalseBBI.ExtraCost2, Prediction.getCompl()) &&
+ FeasibilityAnalysis(FalseBBI, RevCond, true, true)) {
+ Tokens.push_back(new IfcvtToken(BBI, ICTriangleFRev, FNeedSub, Dups));
+ Enqueued = true;
+ }
+
+ if (ValidSimple(FalseBBI, Dups, Prediction.getCompl()) &&
+ MeetIfcvtSizeLimit(*FalseBBI.BB,
+ FalseBBI.NonPredSize + FalseBBI.ExtraCost,
+ FalseBBI.ExtraCost2, Prediction.getCompl()) &&
+ FeasibilityAnalysis(FalseBBI, RevCond)) {
+ Tokens.push_back(new IfcvtToken(BBI, ICSimpleFalse, FNeedSub, Dups));
+ Enqueued = true;
+ }
+ }
+
+ BBI.IsEnqueued = Enqueued;
+ BBI.IsBeingAnalyzed = false;
+ BBI.IsAnalyzed = true;
+ BBStack.pop_back();
+ }
}
/// AnalyzeBlocks - Analyze all blocks and find entries for all if-conversion
// Now add the implicit uses for each of the clobbered values.
for (auto Reg : Clobbers) {
- const MachineOperand &Op = *Reg.second;
// FIXME: Const cast here is nasty, but better than making StepForward
// take a mutable instruction instead of const.
- MachineInstr *OpMI = const_cast<MachineInstr*>(Op.getParent());
+ MachineOperand &Op = const_cast<MachineOperand&>(*Reg.second);
+ MachineInstr *OpMI = Op.getParent();
MachineInstrBuilder MIB(*OpMI->getParent()->getParent(), OpMI);
-
if (Op.isRegMask()) {
// First handle regmasks. They clobber any entries in the mask which
// means that we need a def for those registers.
continue;
}
assert(Op.isReg() && "Register operand required");
+ if (Op.isDead()) {
+ // If we found a dead def, but it needs to be live, then remove the dead
+ // flag.
+ if (Redefs.contains(Op.getReg()))
+ Op.setIsDead(false);
+ }
MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
}
}
bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
uint64_t CvtNext = 0, CvtFalse = 0, BBNext = 0, BBCvt = 0, SumWeight = 0;
- uint32_t WeightScale = 0;
if (HasEarlyExit) {
// Get weights before modifying CvtBBI->BB and BBI.BB.
+ // Explictly normalize the weights of all edges from CvtBBI->BB so that we
+ // are aware that the edge weights obtained below are normalized.
+ CvtBBI->BB->normalizeSuccWeights();
CvtNext = MBPI->getEdgeWeight(CvtBBI->BB, NextBBI->BB);
CvtFalse = MBPI->getEdgeWeight(CvtBBI->BB, CvtBBI->FalseBB);
BBNext = MBPI->getEdgeWeight(BBI.BB, NextBBI->BB);
BBCvt = MBPI->getEdgeWeight(BBI.BB, CvtBBI->BB);
- SumWeight = MBPI->getSumForBlock(CvtBBI->BB, WeightScale);
+ SumWeight = MBPI->getSumForBlock(CvtBBI->BB);
}
if (CvtBBI->BB->pred_size() > 1) {
// New_Weight(BBI.BB, CvtBBI->FalseBB) =
// Weight(BBI.BB, CvtBBI->BB) * Weight(CvtBBI->BB, CvtBBI->FalseBB)
- uint64_t NewNext = BBNext * SumWeight + (BBCvt * CvtNext) / WeightScale;
- uint64_t NewFalse = (BBCvt * CvtFalse) / WeightScale;
+ uint64_t NewNext = BBNext * SumWeight + BBCvt * CvtNext;
+ uint64_t NewFalse = BBCvt * CvtFalse;
// We need to scale down all weights of BBI.BB to fit uint32_t.
// Here BBI.BB is connected to CvtBBI->FalseBB and will fall through to
// the next block.
Redefs.addLiveIns(BBI1->BB);
// Remove the duplicated instructions at the beginnings of both paths.
- MachineBasicBlock::iterator DI1 = BBI1->BB->begin();
- MachineBasicBlock::iterator DI2 = BBI2->BB->begin();
- MachineBasicBlock::iterator DIE1 = BBI1->BB->end();
- MachineBasicBlock::iterator DIE2 = BBI2->BB->end();
// Skip dbg_value instructions
- while (DI1 != DIE1 && DI1->isDebugValue())
- ++DI1;
- while (DI2 != DIE2 && DI2->isDebugValue())
- ++DI2;
+ MachineBasicBlock::iterator DI1 = BBI1->BB->getFirstNonDebugInstr();
+ MachineBasicBlock::iterator DI2 = BBI2->BB->getFirstNonDebugInstr();
BBI1->NonPredSize -= NumDups1;
BBI2->NonPredSize -= NumDups1;
}
static bool MaySpeculate(const MachineInstr *MI,
- SmallSet<unsigned, 4> &LaterRedefs,
- const TargetInstrInfo *TII) {
+ SmallSet<unsigned, 4> &LaterRedefs) {
bool SawStore = true;
- if (!MI->isSafeToMove(TII, nullptr, SawStore))
+ if (!MI->isSafeToMove(nullptr, SawStore))
return false;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
// It may be possible not to predicate an instruction if it's the 'true'
// side of a diamond and the 'false' side may re-define the instruction's
// defs.
- if (MaySpec && MaySpeculate(I, *LaterRedefs, TII)) {
+ if (MaySpec && MaySpeculate(I, *LaterRedefs)) {
AnyUnpred = true;
continue;
}
ToBBI.IsAnalyzed = false;
FromBBI.IsAnalyzed = false;
}
+
+FunctionPass *
+llvm::createIfConverter(std::function<bool(const Function &)> Ftor) {
+ return new IfConverter(Ftor);
+}
projects / oota-llvm.git / blobdiff