//
// The LLVM Compiler Infrastructure
//
-// This file was developed by the Evan Cheng and is distributed under
-// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
#include "llvm/ADT/STLExtras.h"
using namespace llvm;
-namespace {
- // Hidden options for help debugging.
- cl::opt<int> IfCvtFnStart("ifcvt-fn-start", cl::init(-1), cl::Hidden);
- cl::opt<int> IfCvtFnStop("ifcvt-fn-stop", cl::init(-1), cl::Hidden);
- cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
- cl::opt<bool> DisableSimple("disable-ifcvt-simple",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
- cl::init(false), cl::Hidden);
- cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
- cl::init(false), cl::Hidden);
-}
+// 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);
+static cl::opt<int> IfCvtLimit("ifcvt-limit", cl::init(-1), cl::Hidden);
+static cl::opt<bool> DisableSimple("disable-ifcvt-simple",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableSimpleF("disable-ifcvt-simple-false",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableTriangle("disable-ifcvt-triangle",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableTriangleR("disable-ifcvt-triangle-rev",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableTriangleF("disable-ifcvt-triangle-false",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableTriangleFR("disable-ifcvt-triangle-false-rev",
+ cl::init(false), cl::Hidden);
+static cl::opt<bool> DisableDiamond("disable-ifcvt-diamond",
+ cl::init(false), cl::Hidden);
STATISTIC(NumSimple, "Number of simple if-conversions performed");
STATISTIC(NumSimpleFalse, "Number of simple (F) if-conversions performed");
STATISTIC(NumDupBBs, "Number of duplicated blocks");
namespace {
- class IfConverter : public MachineFunctionPass {
+ class VISIBILITY_HIDDEN IfConverter : public MachineFunctionPass {
enum IfcvtKind {
ICNotClassfied, // BB data valid, but not classified.
ICSimpleFalse, // Same as ICSimple, but on the false path.
/// IsBrAnalyzable - True if AnalyzeBranch() returns false.
/// HasFallThrough - True if BB may fallthrough to the following BB.
/// IsUnpredicable - True if BB is known to be unpredicable.
- /// ClobbersPredicate- True if BB would modify the predicate (e.g. has
+ /// ClobbersPred - True if BB could modify predicates (e.g. has
/// cmp, call, etc.)
/// NonPredSize - Number of non-predicated instructions.
/// BB - Corresponding MachineBasicBlock.
MachineBasicBlock *BB;
MachineBasicBlock *TrueBB;
MachineBasicBlock *FalseBB;
- std::vector<MachineOperand> BrCond;
- std::vector<MachineOperand> Predicate;
+ SmallVector<MachineOperand, 4> BrCond;
+ SmallVector<MachineOperand, 4> Predicate;
BBInfo() : IsDone(false), IsBeingAnalyzed(false),
IsAnalyzed(false), IsEnqueued(false), IsBrAnalyzable(false),
HasFallThrough(false), IsUnpredicable(false),
/// IfcvtToken - Record information about pending if-conversions to attemp:
/// BBI - Corresponding BBInfo.
/// Kind - Type of block. See IfcvtKind.
- /// NeedSubsumsion - True if the to be predicated BB has already been
+ /// NeedSubsumption - True if the to-be-predicated BB has already been
/// predicated.
/// NumDups - Number of instructions that would be duplicated due
/// to this if-conversion. (For diamonds, the number of
struct IfcvtToken {
BBInfo &BBI;
IfcvtKind Kind;
- bool NeedSubsumsion;
+ bool NeedSubsumption;
unsigned NumDups;
unsigned NumDups2;
IfcvtToken(BBInfo &b, IfcvtKind k, bool s, unsigned d, unsigned d2 = 0)
- : BBI(b), Kind(k), NeedSubsumsion(s), NumDups(d), NumDups2(d2) {}
+ : BBI(b), Kind(k), NeedSubsumption(s), NumDups(d), NumDups2(d2) {}
};
/// Roots - Basic blocks that do not have successors. These are the starting
bool MadeChange;
public:
static char ID;
- IfConverter() : MachineFunctionPass((intptr_t)&ID) {}
+ IfConverter() : MachineFunctionPass(&ID) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
- virtual const char *getPassName() const { return "If converter"; }
+ virtual const char *getPassName() const { return "If Converter"; }
private:
bool ReverseBranchCondition(BBInfo &BBI);
void ScanInstructions(BBInfo &BBI);
BBInfo &AnalyzeBlock(MachineBasicBlock *BB,
std::vector<IfcvtToken*> &Tokens);
- bool FeasibilityAnalysis(BBInfo &BBI, std::vector<MachineOperand> &Cond,
+ bool FeasibilityAnalysis(BBInfo &BBI, SmallVectorImpl<MachineOperand> &Cond,
bool isTriangle = false, bool RevBranch = false);
bool AnalyzeBlocks(MachineFunction &MF,
std::vector<IfcvtToken*> &Tokens);
unsigned NumDups1, unsigned NumDups2);
void PredicateBlock(BBInfo &BBI,
MachineBasicBlock::iterator E,
- std::vector<MachineOperand> &Cond);
+ SmallVectorImpl<MachineOperand> &Cond);
void CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
- std::vector<MachineOperand> &Cond,
+ SmallVectorImpl<MachineOperand> &Cond,
bool IgnoreBr = false);
void MergeBlocks(BBInfo &ToBBI, BBInfo &FromBBI);
if (Incr1 > Incr2)
return true;
else if (Incr1 == Incr2) {
- // Favors subsumsion.
- if (C1->NeedSubsumsion == false && C2->NeedSubsumsion == true)
+ // Favors subsumption.
+ if (C1->NeedSubsumption == false && C2->NeedSubsumption == true)
return true;
- else if (C1->NeedSubsumsion == C2->NeedSubsumsion) {
+ else if (C1->NeedSubsumption == C2->NeedSubsumption) {
// Favors diamond over triangle, etc.
if ((unsigned)C1->Kind < (unsigned)C2->Kind)
return true;
char IfConverter::ID = 0;
}
+static RegisterPass<IfConverter>
+X("if-converter", "If Converter");
+
FunctionPass *llvm::createIfConverterPass() { return new IfConverter(); }
bool IfConverter::runOnMachineFunction(MachineFunction &MF) {
// Look for root nodes, i.e. blocks without successors.
for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
- if (I->succ_size() == 0)
+ if (I->succ_empty())
Roots.push_back(I);
std::vector<IfcvtToken*> Tokens;
unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +
NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;
while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {
- // Do an intial analysis for each basic block and finding all the potential
- // candidates to perform if-convesion.
+ // Do an initial analysis for each basic block and find all the potential
+ // candidates to perform if-conversion.
bool Change = AnalyzeBlocks(MF, Tokens);
while (!Tokens.empty()) {
IfcvtToken *Token = Tokens.back();
Tokens.pop_back();
BBInfo &BBI = Token->BBI;
IfcvtKind Kind = Token->Kind;
+ unsigned NumDups = Token->NumDups;
+ unsigned NumDups2 = Token->NumDups2;
+
+ delete Token;
// If the block has been evicted out of the queue or it has already been
// marked dead (due to it being predicated), then skip it.
: BBI.TrueBB->getNumber()) << ") ";
RetVal = IfConvertSimple(BBI, Kind);
DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
- if (RetVal)
+ if (RetVal) {
if (isFalse) NumSimpleFalse++;
else NumSimple++;
+ }
break;
}
case ICTriangle:
DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
<< BBI.TrueBB->getNumber() << ",F:"
<< BBI.FalseBB->getNumber() << ") ";
- RetVal = IfConvertDiamond(BBI, Kind, Token->NumDups, Token->NumDups2);
+ RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
if (RetVal) NumDiamonds++;
break;
}
/// ReverseBranchCondition - Reverse the condition of the end of the block
-/// branchs. Swap block's 'true' and 'false' successors.
+/// branch. Swap block's 'true' and 'false' successors.
bool IfConverter::ReverseBranchCondition(BBInfo &BBI) {
if (!TII->ReverseBranchCondition(BBI.BrCond)) {
TII->RemoveBranch(*BBI.BB);
unsigned Size = TrueBBI.NonPredSize;
if (TrueBBI.IsBrAnalyzable) {
- if (TrueBBI.TrueBB && TrueBBI.BrCond.size() == 0)
- // End with an unconditional branch. It will be removed.
+ if (TrueBBI.TrueBB && TrueBBI.BrCond.empty())
+ // Ends with an unconditional branch. It will be removed.
--Size;
else {
MachineBasicBlock *FExit = FalseBranch
MachineBasicBlock::iterator I = BB->end();
while (I != BB->begin()) {
--I;
- const TargetInstrDescriptor *TID = I->getInstrDescriptor();
- if ((TID->Flags & M_BRANCH_FLAG) == 0)
+ if (!I->getDesc().isBranch())
break;
}
return I;
/// ScanInstructions - Scan all the instructions in the block to determine if
/// the block is predicable. In most cases, that means all the instructions
-/// in the block has M_PREDICABLE flag. Also checks if the block contains any
+/// in the block are isPredicable(). Also checks if the block contains any
/// instruction which can clobber a predicate (e.g. condition code register).
/// If so, the block is not predicable unless it's the last instruction.
void IfConverter::ScanInstructions(BBInfo &BBI) {
bool SeenCondBr = false;
for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
I != E; ++I) {
- const TargetInstrDescriptor *TID = I->getInstrDescriptor();
- if ((TID->Flags & M_NOT_DUPLICABLE) != 0)
+ const TargetInstrDesc &TID = I->getDesc();
+ if (TID.isNotDuplicable())
BBI.CannotBeCopied = true;
bool isPredicated = TII->isPredicated(I);
- bool isCondBr = BBI.IsBrAnalyzable &&
- (TID->Flags & M_BRANCH_FLAG) != 0 && (TID->Flags & M_BARRIER_FLAG) == 0;
+ bool isCondBr = BBI.IsBrAnalyzable && TID.isConditionalBranch();
if (!isCondBr) {
if (!isPredicated)
BBI.IsUnpredicable = true;
return;
}
-
}
if (BBI.ClobbersPred && !isPredicated) {
if (isCondBr) {
SeenCondBr = true;
- // Conditional branches is not predicable. But it may be eliminated.
+ // A conditional branch is not predicable, but it may be eliminated.
continue;
}
return;
}
- if (TID->Flags & M_CLOBBERS_PRED)
+ // FIXME: Make use of PredDefs? e.g. ADDC, SUBC sets predicates but are
+ // still potentially predicable.
+ std::vector<MachineOperand> PredDefs;
+ if (TII->DefinesPredicate(I, PredDefs))
BBI.ClobbersPred = true;
- if ((TID->Flags & M_PREDICABLE) == 0) {
+ if (!TID.isPredicable()) {
BBI.IsUnpredicable = true;
return;
}
/// FeasibilityAnalysis - Determine if the block is a suitable candidate to be
/// predicated by the specified predicate.
bool IfConverter::FeasibilityAnalysis(BBInfo &BBI,
- std::vector<MachineOperand> &Pred,
+ SmallVectorImpl<MachineOperand> &Pred,
bool isTriangle, bool RevBranch) {
// If the block is dead or unpredicable, then it cannot be predicated.
if (BBI.IsDone || BBI.IsUnpredicable)
if (!isTriangle)
return false;
- // Test predicate subsumsion.
- std::vector<MachineOperand> RevPred(Pred);
- std::vector<MachineOperand> Cond(BBI.BrCond);
+ // Test predicate subsumption.
+ SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
+ SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
if (RevBranch) {
if (TII->ReverseBranchCondition(Cond))
return false;
ScanInstructions(BBI);
- // Unanalyable or ends with fallthrough or unconditional branch.
- if (!BBI.IsBrAnalyzable || BBI.BrCond.size() == 0) {
+ // Unanalyzable or ends with fallthrough or unconditional branch.
+ if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) {
BBI.IsBeingAnalyzed = false;
BBI.IsAnalyzed = true;
return BBI;
return BBI;
}
- std::vector<MachineOperand> RevCond(BBI.BrCond);
+ SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
bool CanRevCond = !TII->ReverseBranchCondition(RevCond);
unsigned Dups = 0;
///
static void InsertUncondBranch(MachineBasicBlock *BB, MachineBasicBlock *ToBB,
const TargetInstrInfo *TII) {
- std::vector<MachineOperand> NoCond;
+ SmallVector<MachineOperand, 0> NoCond;
TII->InsertBranch(*BB, ToBB, NULL, NoCond);
}
/// successors.
void IfConverter::RemoveExtraEdges(BBInfo &BBI) {
MachineBasicBlock *TBB = NULL, *FBB = NULL;
- std::vector<MachineOperand> Cond;
+ SmallVector<MachineOperand, 4> Cond;
if (!TII->AnalyzeBranch(*BBI.BB, TBB, FBB, Cond))
BBI.BB->CorrectExtraCFGEdges(TBB, FBB, !Cond.empty());
}
BBInfo *CvtBBI = &TrueBBI;
BBInfo *NextBBI = &FalseBBI;
- std::vector<MachineOperand> Cond(BBI.BrCond);
+ SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
if (Kind == ICSimpleFalse)
std::swap(CvtBBI, NextBBI);
}
if (Kind == ICSimpleFalse)
- TII->ReverseBranchCondition(Cond);
+ if (TII->ReverseBranchCondition(Cond))
+ assert(false && "Unable to reverse branch condition!");
if (CvtBBI->BB->pred_size() > 1) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
- // Copy instructions in the true block, predicate them add them to
+ // Copy instructions in the true block, predicate them, and add them to
// the entry block.
CopyAndPredicateBlock(BBI, *CvtBBI, Cond);
} else {
BBInfo *CvtBBI = &TrueBBI;
BBInfo *NextBBI = &FalseBBI;
- std::vector<MachineOperand> Cond(BBI.BrCond);
+ SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
std::swap(CvtBBI, NextBBI);
}
if (Kind == ICTriangleFalse || Kind == ICTriangleFRev)
- TII->ReverseBranchCondition(Cond);
+ if (TII->ReverseBranchCondition(Cond))
+ assert(false && "Unable to reverse branch condition!");
if (Kind == ICTriangleRev || Kind == ICTriangleFRev) {
- ReverseBranchCondition(*CvtBBI);
- // BB has been changed, modify its predecessors (except for this
- // one) so they don't get ifcvt'ed based on bad intel.
- for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
- E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
- MachineBasicBlock *PBB = *PI;
- if (PBB == BBI.BB)
- continue;
- BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
- if (PBBI.IsEnqueued) {
- PBBI.IsAnalyzed = false;
- PBBI.IsEnqueued = false;
+ if (ReverseBranchCondition(*CvtBBI)) {
+ // BB has been changed, modify its predecessors (except for this
+ // one) so they don't get ifcvt'ed based on bad intel.
+ for (MachineBasicBlock::pred_iterator PI = CvtBBI->BB->pred_begin(),
+ E = CvtBBI->BB->pred_end(); PI != E; ++PI) {
+ MachineBasicBlock *PBB = *PI;
+ if (PBB == BBI.BB)
+ continue;
+ BBInfo &PBBI = BBAnalysis[PBB->getNumber()];
+ if (PBBI.IsEnqueued) {
+ PBBI.IsAnalyzed = false;
+ PBBI.IsEnqueued = false;
+ }
}
}
}
bool DupBB = CvtBBI->BB->pred_size() > 1;
if (DupBB) {
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
- // Copy instructions in the true block, predicate them add them to
+ // Copy instructions in the true block, predicate them, and add them to
// the entry block.
CopyAndPredicateBlock(BBI, *CvtBBI, Cond, true);
} else {
// If 'true' block has a 'false' successor, add an exit branch to it.
if (HasEarlyExit) {
- std::vector<MachineOperand> RevCond(CvtBBI->BrCond);
+ SmallVector<MachineOperand, 4> RevCond(CvtBBI->BrCond.begin(),
+ CvtBBI->BrCond.end());
if (TII->ReverseBranchCondition(RevCond))
assert(false && "Unable to reverse branch condition!");
TII->InsertBranch(*BBI.BB, CvtBBI->FalseBB, NULL, RevCond);
}
// Merge in the 'false' block if the 'false' block has no other
- // predecessors. Otherwise, add a unconditional branch from to 'false'.
+ // predecessors. Otherwise, add an unconditional branch to 'false'.
bool FalseBBDead = false;
bool IterIfcvt = true;
bool isFallThrough = canFallThroughTo(BBI.BB, NextBBI->BB);
BBInfo &TrueBBI = BBAnalysis[BBI.TrueBB->getNumber()];
BBInfo &FalseBBI = BBAnalysis[BBI.FalseBB->getNumber()];
MachineBasicBlock *TailBB = TrueBBI.TrueBB;
- // True block must fall through or ended with unanalyzable terminator.
+ // True block must fall through or end with an unanalyzable terminator.
if (!TailBB) {
if (blockAlwaysFallThrough(TrueBBI))
TailBB = FalseBBI.TrueBB;
// block would clobber the predicate, in that case, do the opposite.
BBInfo *BBI1 = &TrueBBI;
BBInfo *BBI2 = &FalseBBI;
- std::vector<MachineOperand> RevCond(BBI.BrCond);
- TII->ReverseBranchCondition(RevCond);
- std::vector<MachineOperand> *Cond1 = &BBI.BrCond;
- std::vector<MachineOperand> *Cond2 = &RevCond;
+ SmallVector<MachineOperand, 4> RevCond(BBI.BrCond.begin(), BBI.BrCond.end());
+ if (TII->ReverseBranchCondition(RevCond))
+ assert(false && "Unable to reverse branch condition!");
+ SmallVector<MachineOperand, 4> *Cond1 = &BBI.BrCond;
+ SmallVector<MachineOperand, 4> *Cond2 = &RevCond;
// Figure out the more profitable ordering.
bool DoSwap = false;
MergeBlocks(BBI, *BBI1);
MergeBlocks(BBI, *BBI2);
- // If the if-converted block fallthrough or unconditionally branch into the
- // tail block, and the tail block does not have other predecessors, then
+ // If the if-converted block falls through or unconditionally branches into
+ // the tail block, and the tail block does not have other predecessors, then
// fold the tail block in as well. Otherwise, unless it falls through to the
// tail, add a unconditional branch to it.
if (TailBB) {
/// specified end with the specified condition.
void IfConverter::PredicateBlock(BBInfo &BBI,
MachineBasicBlock::iterator E,
- std::vector<MachineOperand> &Cond) {
+ SmallVectorImpl<MachineOperand> &Cond) {
for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
if (TII->isPredicated(I))
continue;
/// CopyAndPredicateBlock - Copy and predicate instructions from source BB to
/// the destination block. Skip end of block branches if IgnoreBr is true.
void IfConverter::CopyAndPredicateBlock(BBInfo &ToBBI, BBInfo &FromBBI,
- std::vector<MachineOperand> &Cond,
+ SmallVectorImpl<MachineOperand> &Cond,
bool IgnoreBr) {
+ MachineFunction &MF = *ToBBI.BB->getParent();
+
for (MachineBasicBlock::iterator I = FromBBI.BB->begin(),
E = FromBBI.BB->end(); I != E; ++I) {
- const TargetInstrDescriptor *TID = I->getInstrDescriptor();
+ const TargetInstrDesc &TID = I->getDesc();
bool isPredicated = TII->isPredicated(I);
// Do not copy the end of the block branches.
- if (IgnoreBr && !isPredicated && (TID->Flags & M_BRANCH_FLAG) != 0)
+ if (IgnoreBr && !isPredicated && TID.isBranch())
break;
- MachineInstr *MI = I->clone();
+ MachineInstr *MI = MF.CloneMachineInstr(I);
ToBBI.BB->insert(ToBBI.BB->end(), MI);
ToBBI.NonPredSize++;
// Fallthrough edge can't be transferred.
if (Succ == FallThrough)
continue;
- if (!ToBBI.BB->isSuccessor(Succ))
- ToBBI.BB->addSuccessor(Succ);
+ ToBBI.BB->addSuccessor(Succ);
}
std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
if (Succ == FallThrough)
continue;
FromBBI.BB->removeSuccessor(Succ);
- if (!ToBBI.BB->isSuccessor(Succ))
- ToBBI.BB->addSuccessor(Succ);
+ ToBBI.BB->addSuccessor(Succ);
}
- // Now FromBBI always fall through to the next block!
- if (NBB && !FromBBI.BB->isSuccessor(NBB))
+ // Now FromBBI always falls through to the next block!
+ if (NBB)
FromBBI.BB->addSuccessor(NBB);
std::copy(FromBBI.Predicate.begin(), FromBBI.Predicate.end(),
projects / oota-llvm.git / blobdiff