//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "ifcvt"
#include "llvm/CodeGen/Passes.h"
#include "BranchFolding.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/Statistic.h"
+#include "llvm/CodeGen/LivePhysRegs.h"
+#include "llvm/CodeGen/MachineBlockFrequencyInfo.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/TargetSchedule.h"
-#include "llvm/CodeGen/LiveRegUnits.h"
-#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetLowering.h"
-#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Target/TargetSubtargetInfo.h"
+#include <algorithm>
using namespace llvm;
+#define DEBUG_TYPE "ifcvt"
+
// Hidden options for help debugging.
static cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
static cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
HasFallThrough(false), IsUnpredicable(false),
CannotBeCopied(false), ClobbersPred(false), NonPredSize(0),
- ExtraCost(0), ExtraCost2(0), BB(0), TrueBB(0), FalseBB(0) {}
+ ExtraCost(0), ExtraCost2(0), BB(nullptr), TrueBB(nullptr),
+ FalseBB(nullptr) {}
};
/// IfcvtToken - Record information about pending if-conversions to attempt:
const TargetLoweringBase *TLI;
const TargetInstrInfo *TII;
const TargetRegisterInfo *TRI;
+ const MachineBlockFrequencyInfo *MBFI;
const MachineBranchProbabilityInfo *MBPI;
MachineRegisterInfo *MRI;
- LiveRegUnits Redefs;
- LiveRegUnits DontKill;
+ LivePhysRegs Redefs;
+ LivePhysRegs DontKill;
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());
}
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ void getAnalysisUsage(AnalysisUsage &AU) const override {
+ AU.addRequired<MachineBlockFrequencyInfo>();
AU.addRequired<MachineBranchProbabilityInfo>();
MachineFunctionPass::getAnalysisUsage(AU);
}
- virtual bool runOnMachineFunction(MachineFunction &MF);
+ bool runOnMachineFunction(MachineFunction &MF) override;
private:
bool ReverseBranchCondition(BBInfo &BBI);
bool ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
- const BranchProbability &Prediction) const;
+ BranchProbability Prediction) const;
bool ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
bool FalseBranch, unsigned &Dups,
- const BranchProbability &Prediction) const;
+ BranchProbability Prediction) const;
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);
void PredicateBlock(BBInfo &BBI,
MachineBasicBlock::iterator E,
SmallVectorImpl<MachineOperand> &Cond,
- SmallSet<unsigned, 4> *LaterRedefs = 0);
+ SmallSet<unsigned, 4> *LaterRedefs = nullptr);
void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
SmallVectorImpl<MachineOperand> &Cond,
bool IgnoreBr = false);
bool MeetIfcvtSizeLimit(MachineBasicBlock &BB,
unsigned Cycle, unsigned Extra,
- const BranchProbability &Prediction) const {
+ BranchProbability Prediction) const {
return Cycle > 0 && TII->isProfitableToIfCvt(BB, Cycle, Extra,
Prediction);
}
unsigned TCycle, unsigned TExtra,
MachineBasicBlock &FBB,
unsigned FCycle, unsigned FExtra,
- const BranchProbability &Prediction) const {
+ BranchProbability Prediction) const {
return TCycle > 0 && FCycle > 0 &&
TII->isProfitableToIfCvt(TBB, TCycle, TExtra, FBB, FCycle, FExtra,
Prediction);
// blockAlwaysFallThrough - Block ends without a terminator.
bool blockAlwaysFallThrough(BBInfo &BBI) const {
- return BBI.IsBrAnalyzable && BBI.TrueBB == NULL;
+ return BBI.IsBrAnalyzable && BBI.TrueBB == nullptr;
}
// IfcvtTokenCmp - Used to sort if-conversion candidates.
return true;
else if (Incr1 == Incr2) {
// Favors subsumption.
- if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
+ if (!C1->NeedSubsumption && C2->NeedSubsumption)
return true;
else if (C1->NeedSubsumption == C2->NeedSubsumption) {
// Favors diamond over triangle, etc.
INITIALIZE_PASS_END(IfConverter, "if-converter", "If Converter", false, false)
bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
- TLI = MF.getTarget().getTargetLowering();
- TII = MF.getTarget().getInstrInfo();
- TRI = MF.getTarget().getRegisterInfo();
+ if (PredicateFtor && !PredicateFtor(*MF.getFunction()))
+ return false;
+
+ const TargetSubtargetInfo &ST = MF.getSubtarget();
+ TLI = ST.getTargetLowering();
+ TII = ST.getInstrInfo();
+ TRI = ST.getRegisterInfo();
+ MBFI = &getAnalysis<MachineBlockFrequencyInfo>();
MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
MRI = &MF.getRegInfo();
-
- const TargetSubtargetInfo &ST =
- MF.getTarget().getSubtarget<TargetSubtargetInfo>();
- SchedModel.init(*ST.getSchedModel(), &ST, TII);
+ SchedModel.init(ST.getSchedModel(), &ST, TII);
if (!TII) return false;
bool BFChange = false;
if (!PreRegAlloc) {
// Tail merge tend to expose more if-conversion opportunities.
- BranchFolder BF(true, false);
- BFChange = BF.OptimizeFunction(MF, TII,
- MF.getTarget().getRegisterInfo(),
+ BranchFolder BF(true, false, *MBFI, *MBPI);
+ BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo(),
getAnalysisIfAvailable<MachineModuleInfo>());
}
BBAnalysis.clear();
if (MadeChange && IfCvtBranchFold) {
- BranchFolder BF(false, false);
- BF.OptimizeFunction(MF, TII,
- MF.getTarget().getRegisterInfo(),
+ BranchFolder BF(false, false, *MBFI, *MBPI);
+ BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo(),
getAnalysisIfAvailable<MachineModuleInfo>());
}
if (SuccBB != TrueBB)
return SuccBB;
}
- return NULL;
+ return nullptr;
}
/// ReverseBranchCondition - Reverse the condition of the end of the block
/// getNextBlock - Returns the next block in the function blocks ordering. If
/// it is the end, returns NULL.
static inline MachineBasicBlock *getNextBlock(MachineBasicBlock *BB) {
- MachineFunction::iterator I = BB;
+ MachineFunction::iterator I = BB->getIterator();
MachineFunction::iterator E = BB->getParent()->end();
if (++I == E)
- return NULL;
- return I;
+ return nullptr;
+ return &*I;
}
/// ValidSimple - Returns true if the 'true' block (along with its
/// number of instructions that the ifcvt would need to duplicate if performed
/// in Dups.
bool IfConverter::ValidSimple(BBInfo &TrueBBI, unsigned &Dups,
- const BranchProbability &Prediction) const {
+ BranchProbability Prediction) const {
Dups = 0;
if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
return false;
/// if performed in 'Dups'.
bool IfConverter::ValidTriangle(BBInfo &TrueBBI, BBInfo &FalseBBI,
bool FalseBranch, unsigned &Dups,
- const BranchProbability &Prediction) const {
+ BranchProbability Prediction) const {
Dups = 0;
if (TrueBBI.IsBeingAnalyzed || TrueBBI.IsDone)
return false;
MachineBasicBlock *TExit = FalseBranch ? TrueBBI.FalseBB : TrueBBI.TrueBB;
if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
- MachineFunction::iterator I = TrueBBI.BB;
+ MachineFunction::iterator I = TrueBBI.BB->getIterator();
if (++I == TrueBBI.BB->getParent()->end())
return false;
- TExit = I;
+ TExit = &*I;
}
return TExit && TExit == FalseBBI.BB;
}
FT = getNextBlock(FalseBBI.BB);
if (TT != FT)
return false;
- if (TT == NULL && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
+ if (!TT && (TrueBBI.IsBrAnalyzable || FalseBBI.IsBrAnalyzable))
return false;
if (TrueBBI.BB->pred_size() > 1 || FalseBBI.BB->pred_size() > 1)
return false;
bool AlreadyPredicated = !BBI.Predicate.empty();
// First analyze the end of BB branches.
- BBI.TrueBB = BBI.FalseBB = NULL;
+ BBI.TrueBB = BBI.FalseBB = nullptr;
BBI.BrCond.clear();
BBI.IsBrAnalyzable =
!TII->AnalyzeBranch(*BBI.BB, BBI.TrueBB, BBI.FalseBB, BBI.BrCond);
- BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == NULL;
+ BBI.HasFallThrough = BBI.IsBrAnalyzable && BBI.FalseBB == nullptr;
if (BBI.BrCond.size()) {
// No false branch. This BB must end with a conditional branch and a
if (BBI.IsDone || BBI.IsUnpredicable)
return false;
+ // If it is already predicated but we couldn't analyze its terminator, the
+ // latter might fallthrough, but we can't determine where to.
+ // Conservatively avoid if-converting again.
+ if (BBI.Predicate.size() && !BBI.IsBrAnalyzable)
+ return false;
+
// If it is already predicated, check if the new predicate subsumes
// its predicate.
if (BBI.Predicate.size() && !TII->SubsumesPredicate(Pred, BBI.Predicate))
/// 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
/// candidates.
void IfConverter::AnalyzeBlocks(MachineFunction &MF,
std::vector<IfcvtToken*> &Tokens) {
- for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) {
- MachineBasicBlock *BB = I;
- AnalyzeBlock(BB, Tokens);
- }
+ for (auto &BB : MF)
+ AnalyzeBlock(&BB, Tokens);
// Sort to favor more complex ifcvt scheme.
std::stable_sort(Tokens.begin(), Tokens.end(), IfcvtTokenCmp);
/// that all the intervening blocks are empty (given BB can fall through to its
/// next block).
static bool canFallThroughTo(MachineBasicBlock *BB, MachineBasicBlock *ToBB) {
- MachineFunction::iterator PI = BB;
- MachineFunction::iterator I = llvm::next(PI);
- MachineFunction::iterator TI = ToBB;
+ MachineFunction::iterator PI = BB->getIterator();
+ MachineFunction::iterator I = std::next(PI);
+ MachineFunction::iterator TI = ToBB->getIterator();
MachineFunction::iterator E = BB->getParent()->end();
while (I != TI) {
// Check isSuccessor to avoid case where the next block is empty, but
// it's not a successor.
- if (I == E || !I->empty() || !PI->isSuccessor(I))
+ if (I == E || !I->empty() || !PI->isSuccessor(&*I))
return false;
PI = I++;
}
/// to determine if it can be if-converted. If predecessor is already enqueued,
/// dequeue it!
void IfConverter::InvalidatePreds(MachineBasicBlock *BB) {
- for (MachineBasicBlock::pred_iterator PI = BB->pred_begin(),
- E = BB->pred_end(); PI != E; ++PI) {
- BBInfo &PBBI = BBAnalysis[(*PI)->getNumber()];
+ for (const auto &Predecessor : BB->predecessors()) {
+ BBInfo &PBBI = BBAnalysis[Predecessor->getNumber()];
if (PBBI.IsDone || PBBI.BB == BB)
continue;
PBBI.IsAnalyzed = false;
const TargetInstrInfo *TII) {
DebugLoc dl; // FIXME: this is nowhere
SmallVector<MachineOperand, 0> NoCond;
- TII->InsertBranch(*BB, ToBB, NULL, NoCond, dl);
+ TII->InsertBranch(*BB, ToBB, nullptr, NoCond, dl);
}
/// RemoveExtraEdges - Remove true / false edges if either / both are no longer
/// successors.
void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
- MachineBasicBlock *TBB = NULL, *FBB = NULL;
+ MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
/// Behaves like LiveRegUnits::StepForward() but also adds implicit uses to all
/// values defined in MI which are not live/used by MI.
-static void UpdatePredRedefs(MachineInstr *MI, LiveRegUnits &Redefs,
- const TargetRegisterInfo *TRI) {
- for (ConstMIBundleOperands Ops(MI); Ops.isValid(); ++Ops) {
- if (!Ops->isReg() || !Ops->isKill())
- continue;
- unsigned Reg = Ops->getReg();
- if (Reg == 0)
+static void UpdatePredRedefs(MachineInstr *MI, LivePhysRegs &Redefs) {
+ SmallVector<std::pair<unsigned, const MachineOperand*>, 4> Clobbers;
+ Redefs.stepForward(*MI, Clobbers);
+
+ // Now add the implicit uses for each of the clobbered values.
+ for (auto Reg : Clobbers) {
+ // FIXME: Const cast here is nasty, but better than making StepForward
+ // take a mutable instruction instead of const.
+ 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.
+ MIB.addReg(Reg.first, RegState::Implicit | RegState::Undef);
+
+ // We also need to add an implicit def of this register for the later
+ // use to read from.
+ // For the register allocator to have allocated a register clobbered
+ // by the call which is used later, it must be the case that
+ // the call doesn't return.
+ MIB.addReg(Reg.first, RegState::Implicit | RegState::Define);
continue;
- Redefs.removeReg(Reg, *TRI);
- }
- for (MIBundleOperands Ops(MI); Ops.isValid(); ++Ops) {
- if (!Ops->isReg() || !Ops->isDef())
- continue;
- unsigned Reg = Ops->getReg();
- if (Reg == 0 || Redefs.contains(Reg, *TRI))
- continue;
- Redefs.addReg(Reg, *TRI);
-
- MachineOperand &Op = *Ops;
- MachineInstr *MI = Op.getParent();
- MachineInstrBuilder MIB(*MI->getParent()->getParent(), MI);
- MIB.addReg(Reg, RegState::Implicit | RegState::Undef);
+ }
+ 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);
}
}
/**
* Remove kill flags from operands with a registers in the @p DontKill set.
*/
-static void RemoveKills(MachineInstr &MI, const LiveRegUnits &DontKill,
- const MCRegisterInfo &MCRI) {
+static void RemoveKills(MachineInstr &MI, const LivePhysRegs &DontKill) {
for (MIBundleOperands O(&MI); O.isValid(); ++O) {
if (!O->isReg() || !O->isKill())
continue;
- if (DontKill.contains(O->getReg(), MCRI))
+ if (DontKill.contains(O->getReg()))
O->setIsKill(false);
}
}
*/
static void RemoveKills(MachineBasicBlock::iterator I,
MachineBasicBlock::iterator E,
- const LiveRegUnits &DontKill,
+ const LivePhysRegs &DontKill,
const MCRegisterInfo &MCRI) {
for ( ; I != E; ++I)
- RemoveKills(*I, DontKill, MCRI);
+ RemoveKills(*I, DontKill);
}
/// IfConvertSimple - If convert a simple (split, no rejoin) sub-CFG.
// Initialize liveins to the first BB. These are potentiall redefined by
// predicated instructions.
Redefs.init(TRI);
- Redefs.addLiveIns(CvtBBI->BB, *TRI);
- Redefs.addLiveIns(NextBBI->BB, *TRI);
+ Redefs.addLiveIns(CvtBBI->BB);
+ Redefs.addLiveIns(NextBBI->BB);
// Compute a set of registers which must not be killed by instructions in
// BB1: This is everything live-in to BB2.
DontKill.init(TRI);
- DontKill.addLiveIns(NextBBI->BB, *TRI);
+ DontKill.addLiveIns(NextBBI->BB);
if (CvtBBI->BB->pred_size() > 1) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
Redefs.init(TRI);
- Redefs.addLiveIns(CvtBBI->BB, *TRI);
- Redefs.addLiveIns(NextBBI->BB, *TRI);
+ Redefs.addLiveIns(CvtBBI->BB);
+ Redefs.addLiveIns(NextBBI->BB);
DontKill.clear();
- bool HasEarlyExit = CvtBBI->FalseBB != NULL;
+ bool HasEarlyExit = CvtBBI->FalseBB != nullptr;
+ BranchProbability CvtNext, CvtFalse, BBNext, BBCvt;
+
+ if (HasEarlyExit) {
+ // Get probabilities before modifying CvtBBI->BB and BBI.BB.
+ CvtNext = MBPI->getEdgeProbability(CvtBBI->BB, NextBBI->BB);
+ CvtFalse = MBPI->getEdgeProbability(CvtBBI->BB, CvtBBI->FalseBB);
+ BBNext = MBPI->getEdgeProbability(BBI.BB, NextBBI->BB);
+ BBCvt = MBPI->getEdgeProbability(BBI.BB, CvtBBI->BB);
+ }
+
if (CvtBBI->BB->pred_size() > 1) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
// Copy instructions in the true block, predicate them, and add them to
CvtBBI->BrCond.end());
if (TII->ReverseBranchCondition(RevCond))
llvm_unreachable("Unable to reverse branch condition!");
- TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond, dl);
- BBI.BB->addSuccessor(CvtBBI->FalseBB);
+
+ // Update the edge probability for both CvtBBI->FalseBB and NextBBI.
+ // NewNext = New_Prob(BBI.BB, NextBBI->BB) =
+ // Prob(BBI.BB, NextBBI->BB) +
+ // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, NextBBI->BB)
+ // NewFalse = New_Prob(BBI.BB, CvtBBI->FalseBB) =
+ // Prob(BBI.BB, CvtBBI->BB) * Prob(CvtBBI->BB, CvtBBI->FalseBB)
+ auto NewTrueBB = getNextBlock(BBI.BB);
+ auto NewNext = BBNext + BBCvt * CvtNext;
+ auto NewTrueBBIter =
+ std::find(BBI.BB->succ_begin(), BBI.BB->succ_end(), NewTrueBB);
+ if (NewTrueBBIter != BBI.BB->succ_end())
+ BBI.BB->setSuccProbability(NewTrueBBIter, NewNext);
+
+ auto NewFalse = BBCvt * CvtFalse;
+ TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, nullptr, RevCond, dl);
+ BBI.BB->addSuccessor(CvtBBI->FalseBB, NewFalse);
}
// Merge in the 'false' block if the 'false' block has no other
// Initialize liveins to the first BB. These are potentially redefined by
// predicated instructions.
Redefs.init(TRI);
- Redefs.addLiveIns(BBI1->BB, *TRI);
+ 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;
DontKill.init(TRI);
for (MachineBasicBlock::reverse_iterator I = BBI2->BB->rbegin(),
E = MachineBasicBlock::reverse_iterator(DI2); I != E; ++I) {
- DontKill.stepBackward(*I, *TRI);
+ DontKill.stepBackward(*I);
}
for (MachineBasicBlock::const_iterator I = BBI1->BB->begin(), E = DI1; I != E;
++I) {
- Redefs.stepForward(*I, *TRI);
+ SmallVector<std::pair<unsigned, const MachineOperand*>, 4> IgnoredClobbers;
+ Redefs.stepForward(*I, IgnoredClobbers);
}
BBI.BB->splice(BBI.BB->end(), BBI1->BB, BBI1->BB->begin(), DI1);
BBI2->BB->erase(BBI2->BB->begin(), DI2);
PredicateBlock(*BBI2, DI2, *Cond2);
// Merge the true block into the entry of the diamond.
- MergeBlocks(BBI, *BBI1, TailBB == 0);
- MergeBlocks(BBI, *BBI2, TailBB == 0);
+ MergeBlocks(BBI, *BBI1, TailBB == nullptr);
+ MergeBlocks(BBI, *BBI2, TailBB == nullptr);
// If the if-converted block falls through or unconditionally branches into
// the tail block, and the tail block does not have other predecessors, then
MergeBlocks(BBI, TailBBI);
TailBBI.IsDone = true;
} else {
- BBI.BB->addSuccessor(TailBB);
+ BBI.BB->addSuccessor(TailBB, BranchProbability::getOne());
InsertUncondBranch(BBI.BB, TailBB, TII);
BBI.HasFallThrough = false;
}
}
static bool MaySpeculate(const MachineInstr *MI,
- SmallSet<unsigned, 4> &LaterRedefs,
- const TargetInstrInfo *TII) {
+ SmallSet<unsigned, 4> &LaterRedefs) {
bool SawStore = true;
- if (!MI->isSafeToMove(TII, 0, SawStore))
+ if (!MI->isSafeToMove(nullptr, SawStore))
return false;
for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
SmallVectorImpl<MachineOperand> &Cond,
SmallSet<unsigned, 4> *LaterRedefs) {
bool AnyUnpred = false;
- bool MaySpec = LaterRedefs != 0;
+ bool MaySpec = LaterRedefs != nullptr;
for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
if (I->isDebugValue() || TII->isPredicated(I))
continue;
// 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;
}
#ifndef NDEBUG
dbgs() << "Unable to predicate " << *I << "!\n";
#endif
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
// If the predicated instruction now redefines a register as the result of
// if-conversion, add an implicit kill.
- UpdatePredRedefs(I, Redefs, TRI);
+ UpdatePredRedefs(I, Redefs);
}
- std::copy(Cond.begin(), Cond.end(), std::back_inserter(BBI.Predicate));
+ BBI.Predicate.append(Cond.begin(), Cond.end());
BBI.IsAnalyzed = false;
BBI.NonPredSize = 0;
#ifndef NDEBUG
dbgs() << "Unable to predicate " << *I << "!\n";
#endif
- llvm_unreachable(0);
+ llvm_unreachable(nullptr);
}
}
// If the predicated instruction now redefines a register as the result of
// if-conversion, add an implicit kill.
- UpdatePredRedefs(MI, Redefs, TRI);
+ UpdatePredRedefs(MI, Redefs);
// Some kill flags may not be correct anymore.
if (!DontKill.empty())
- RemoveKills(*MI, DontKill, *TRI);
+ RemoveKills(*MI, DontKill);
}
if (!IgnoreBr) {
std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
FromBBI.BB->succ_end());
MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
- MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
+ MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
MachineBasicBlock *Succ = Succs[i];
}
}
- std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
- std::back_inserter(ToBBI.Predicate));
- std::copy(Cond.begin(), Cond.end(), std::back_inserter(ToBBI.Predicate));
+ ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
+ ToBBI.Predicate.append(Cond.begin(), Cond.end());
ToBBI.ClobbersPred |= FromBBI.ClobbersPred;
ToBBI.IsAnalyzed = false;
ToBBI.BB->splice(ToBBI.BB->end(),
FromBBI.BB, FromBBI.BB->begin(), FromBBI.BB->end());
- std::vector<MachineBasicBlock *> Succs(FromBBI.BB->succ_begin(),
- FromBBI.BB->succ_end());
+ SmallVector<MachineBasicBlock *, 4> FromSuccs(FromBBI.BB->succ_begin(),
+ FromBBI.BB->succ_end());
MachineBasicBlock *NBB = getNextBlock(FromBBI.BB);
- MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : NULL;
+ MachineBasicBlock *FallThrough = FromBBI.HasFallThrough ? NBB : nullptr;
+ // The edge probability from ToBBI.BB to FromBBI.BB, which is only needed when
+ // AddEdges is true and FromBBI.BB is a successor of ToBBI.BB.
+ auto To2FromProb = BranchProbability::getZero();
+ if (AddEdges && ToBBI.BB->isSuccessor(FromBBI.BB)) {
+ To2FromProb = MBPI->getEdgeProbability(ToBBI.BB, FromBBI.BB);
+ // Set the edge probability from ToBBI.BB to FromBBI.BB to zero to avoid the
+ // edge probability being merged to other edges when this edge is removed
+ // later.
+ ToBBI.BB->setSuccProbability(
+ std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), FromBBI.BB),
+ BranchProbability::getZero());
+ }
- for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
- MachineBasicBlock *Succ = Succs[i];
+ for (unsigned i = 0, e = FromSuccs.size(); i != e; ++i) {
+ MachineBasicBlock *Succ = FromSuccs[i];
// Fallthrough edge can't be transferred.
if (Succ == FallThrough)
continue;
+
+ auto NewProb = BranchProbability::getZero();
+ if (AddEdges) {
+ // Calculate the edge probability for the edge from ToBBI.BB to Succ,
+ // which is a portion of the edge probability from FromBBI.BB to Succ. The
+ // portion ratio is the edge probability from ToBBI.BB to FromBBI.BB (if
+ // FromBBI is a successor of ToBBI.BB. See comment below for excepion).
+ NewProb = MBPI->getEdgeProbability(FromBBI.BB, Succ);
+
+ // To2FromProb is 0 when FromBBI.BB is not a successor of ToBBI.BB. This
+ // only happens when if-converting a diamond CFG and FromBBI.BB is the
+ // tail BB. In this case FromBBI.BB post-dominates ToBBI.BB and hence we
+ // could just use the probabilities on FromBBI.BB's out-edges when adding
+ // new successors.
+ if (!To2FromProb.isZero())
+ NewProb *= To2FromProb;
+ }
+
FromBBI.BB->removeSuccessor(Succ);
- if (AddEdges && !ToBBI.BB->isSuccessor(Succ))
- ToBBI.BB->addSuccessor(Succ);
+
+ if (AddEdges) {
+ // If the edge from ToBBI.BB to Succ already exists, update the
+ // probability of this edge by adding NewWeight to it. An example is shown
+ // below, in which A is ToBBI.BB and B is FromBBI.BB. In this case we
+ // don't have to set C as A's successor as it already is. We only need to
+ // update the edge probability on A->C. Note that B will not be
+ // immediately removed from A's successors. It is possible that B->D is
+ // not removed either if D is a fallthrough of B. Later the edge A->D
+ // (generated here) and B->D will be combined into one edge. To maintain
+ // correct edge probability of this combined edge, we need to set the edge
+ // probability of A->B to zero, which is already done above. The edge
+ // probability on A->D is calculated by scaling the original probability
+ // on A->B by the probability of B->D.
+ //
+ // Before ifcvt: After ifcvt (assume B->D is kept):
+ //
+ // A A
+ // /| /|\
+ // / B / B|
+ // | /| | ||
+ // |/ | | |/
+ // C D C D
+ //
+ if (ToBBI.BB->isSuccessor(Succ))
+ ToBBI.BB->setSuccProbability(
+ std::find(ToBBI.BB->succ_begin(), ToBBI.BB->succ_end(), Succ),
+ MBPI->getEdgeProbability(ToBBI.BB, Succ) + NewProb);
+ else
+ ToBBI.BB->addSuccessor(Succ, NewProb);
+ }
}
// Now FromBBI always falls through to the next block!
if (NBB && !FromBBI.BB->isSuccessor(NBB))
FromBBI.BB->addSuccessor(NBB);
- std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
- std::back_inserter(ToBBI.Predicate));
+ ToBBI.Predicate.append(FromBBI.Predicate.begin(), FromBBI.Predicate.end());
FromBBI.Predicate.clear();
ToBBI.NonPredSize += FromBBI.NonPredSize;
ToBBI.IsAnalyzed = false;
FromBBI.IsAnalyzed = false;
}
+
+FunctionPass *
+llvm::createIfConverter(std::function<bool(const Function &)> Ftor) {
+ return new IfConverter(Ftor);
+}
projects / oota-llvm.git / blobdiff