//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "ifcvt"
+#include "BranchFolding.h"
#include "llvm/Function.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/CodeGen/MachineModuleInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
+#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/STLExtras.h"
STATISTIC(NumDupBBs, "Number of duplicated blocks");
namespace {
- class VISIBILITY_HIDDEN IfConverter : public MachineFunctionPass {
+ class IfConverter : public MachineFunctionPass {
enum IfcvtKind {
ICNotClassfied, // BB data valid, but not classified.
ICSimpleFalse, // Same as ICSimple, but on the false path.
/// 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
const TargetLowering *TLI;
const TargetInstrInfo *TII;
bool MadeChange;
+ int FnNum;
public:
static char ID;
- IfConverter() : MachineFunctionPass(&ID) {}
+ IfConverter() : MachineFunctionPass(&ID), FnNum(-1) {}
virtual bool runOnMachineFunction(MachineFunction &MF);
virtual const char *getPassName() const { return "If Converter"; }
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;
TII = MF.getTarget().getInstrInfo();
if (!TII) return false;
- static int FnNum = -1;
- DOUT << "\nIfcvt: function (" << ++FnNum << ") \'"
- << MF.getFunction()->getName() << "\'";
+ DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'"
+ << MF.getFunction()->getName() << "\'");
if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {
- DOUT << " skipped\n";
+ DEBUG(dbgs() << " skipped\n");
return false;
}
- DOUT << "\n";
+ DEBUG(dbgs() << "\n");
MF.RenumberBlocks();
BBAnalysis.resize(MF.getNumBlockIDs());
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.
case ICSimpleFalse: {
bool isFalse = Kind == ICSimpleFalse;
if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;
- DOUT << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"")
- << "): BB#" << BBI.BB->getNumber() << " ("
- << ((Kind == ICSimpleFalse)
- ? BBI.FalseBB->getNumber()
- : BBI.TrueBB->getNumber()) << ") ";
+ DEBUG(dbgs() << "Ifcvt (Simple" << (Kind == ICSimpleFalse ? " false" :"")
+ << "): BB#" << BBI.BB->getNumber() << " ("
+ << ((Kind == ICSimpleFalse)
+ ? BBI.FalseBB->getNumber()
+ : BBI.TrueBB->getNumber()) << ") ");
RetVal = IfConvertSimple(BBI, Kind);
- DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
+ DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
if (RetVal) {
if (isFalse) NumSimpleFalse++;
else NumSimple++;
if (DisableTriangleR && !isFalse && isRev) break;
if (DisableTriangleF && isFalse && !isRev) break;
if (DisableTriangleFR && isFalse && isRev) break;
- DOUT << "Ifcvt (Triangle";
+ DEBUG(dbgs() << "Ifcvt (Triangle");
if (isFalse)
- DOUT << " false";
+ DEBUG(dbgs() << " false");
if (isRev)
- DOUT << " rev";
- DOUT << "): BB#" << BBI.BB->getNumber() << " (T:"
- << BBI.TrueBB->getNumber() << ",F:"
- << BBI.FalseBB->getNumber() << ") ";
+ DEBUG(dbgs() << " rev");
+ DEBUG(dbgs() << "): BB#" << BBI.BB->getNumber() << " (T:"
+ << BBI.TrueBB->getNumber() << ",F:"
+ << BBI.FalseBB->getNumber() << ") ");
RetVal = IfConvertTriangle(BBI, Kind);
- DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
+ DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
if (RetVal) {
if (isFalse) {
if (isRev) NumTriangleFRev++;
}
case ICDiamond: {
if (DisableDiamond) break;
- DOUT << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
- << BBI.TrueBB->getNumber() << ",F:"
- << BBI.FalseBB->getNumber() << ") ";
- RetVal = IfConvertDiamond(BBI, Kind, Token->NumDups, Token->NumDups2);
- DOUT << (RetVal ? "succeeded!" : "failed!") << "\n";
+ DEBUG(dbgs() << "Ifcvt (Diamond): BB#" << BBI.BB->getNumber() << " (T:"
+ << BBI.TrueBB->getNumber() << ",F:"
+ << BBI.FalseBB->getNumber() << ") ");
+ RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2);
+ DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");
if (RetVal) NumDiamonds++;
break;
}
Roots.clear();
BBAnalysis.clear();
+ if (MadeChange) {
+ BranchFolder BF(false);
+ BF.OptimizeFunction(MF, TII,
+ MF.getTarget().getRegisterInfo(),
+ getAnalysisIfAvailable<MachineModuleInfo>());
+ }
+
return MadeChange;
}
}
/// 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.empty())
- // End with an unconditional branch. It will be removed.
+ // Ends with an unconditional branch. It will be removed.
--Size;
else {
MachineBasicBlock *FExit = FalseBranch
MachineBasicBlock::iterator TI = TrueBBI.BB->begin();
MachineBasicBlock::iterator FI = FalseBBI.BB->begin();
- while (TI != TrueBBI.BB->end() && FI != FalseBBI.BB->end()) {
+ MachineBasicBlock::iterator TIE = TrueBBI.BB->end();
+ MachineBasicBlock::iterator FIE = FalseBBI.BB->end();
+ // Skip dbg_value instructions
+ while (TI != TIE && TI->isDebugValue())
+ ++TI;
+ while (FI != FIE && FI->isDebugValue())
+ ++FI;
+ while (TI != TIE && FI != FIE) {
if (!TI->isIdenticalTo(FI))
break;
++Dups1;
TI = firstNonBranchInst(TrueBBI.BB, TII);
FI = firstNonBranchInst(FalseBBI.BB, TII);
- while (TI != TrueBBI.BB->begin() && FI != FalseBBI.BB->begin()) {
+ MachineBasicBlock::iterator TIB = TrueBBI.BB->begin();
+ MachineBasicBlock::iterator FIB = FalseBBI.BB->begin();
+ // Skip dbg_value instructions
+ while (TI != TIB && TI->isDebugValue())
+ --TI;
+ while (FI != FIB && FI->isDebugValue())
+ --FI;
+ while (TI != TIB && FI != FIB) {
if (!TI->isIdenticalTo(FI))
break;
++Dups2;
// fallthrough.
if (!BBI.FalseBB)
BBI.FalseBB = findFalseBlock(BBI.BB, BBI.TrueBB);
- assert(BBI.FalseBB && "Expected to find the fallthrough block!");
+ if (!BBI.FalseBB) {
+ // Malformed bcc? True and false blocks are the same?
+ BBI.IsUnpredicable = true;
+ return;
+ }
}
// Then scan all the instructions.
BBI.NonPredSize = 0;
BBI.ClobbersPred = false;
- bool SeenCondBr = false;
for (MachineBasicBlock::iterator I = BBI.BB->begin(), E = BBI.BB->end();
I != E; ++I) {
+ if (I->isDebugValue())
+ continue;
+
const TargetInstrDesc &TID = I->getDesc();
if (TID.isNotDuplicable())
BBI.CannotBeCopied = true;
BBI.IsUnpredicable = true;
return;
}
-
}
if (BBI.ClobbersPred && !isPredicated) {
// Predicate modification instruction should end the block (except for
// already predicated instructions and end of block branches).
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;
}
if (TII->DefinesPredicate(I, PredDefs))
BBI.ClobbersPred = true;
- if (!TID.isPredicable()) {
+ if (!TII->isPredicable(I)) {
BBI.IsUnpredicable = true;
return;
}
if (!isTriangle)
return false;
- // Test predicate subsumsion.
+ // Test predicate subsumption.
SmallVector<MachineOperand, 4> RevPred(Pred.begin(), Pred.end());
SmallVector<MachineOperand, 4> Cond(BBI.BrCond.begin(), BBI.BrCond.end());
if (RevBranch) {
ScanInstructions(BBI);
- // Unanalyable or ends with fallthrough or unconditional branch.
+ // Unanalyzable or ends with fallthrough or unconditional branch.
if (!BBI.IsBrAnalyzable || BBI.BrCond.empty()) {
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;
+ return BBI;
+ }
+
BBInfo &TrueBBI = AnalyzeBlock(BBI.TrueBB, Tokens);
BBInfo &FalseBBI = AnalyzeBlock(BBI.FalseBB, Tokens);
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 {
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 {
// Predicate the 'true' block after removing its branch.
CvtBBI->NonPredSize -= TII->RemoveBranch(*CvtBBI->BB);
PredicateBlock(*CvtBBI, CvtBBI->BB->end(), Cond);
- }
- if (!DupBB) {
// Now merge the entry of the triangle with the true block.
BBI.NonPredSize -= TII->RemoveBranch(*BBI.BB);
MergeBlocks(BBI, *CvtBBI);
}
// 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;
// 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;
BBI1->NonPredSize -= NumDups1;
BBI2->NonPredSize -= NumDups1;
while (NumDups1 != 0) {
// Predicate the 'true' block after removing its branch.
BBI1->NonPredSize -= TII->RemoveBranch(*BBI1->BB);
DI1 = BBI1->BB->end();
- for (unsigned i = 0; i != NumDups2; ++i)
+ for (unsigned i = 0; i != NumDups2; ) {
+ // NumDups2 only counted non-dbg_value instructions, so this won't
+ // run off the head of the list.
+ assert (DI1 != BBI1->BB->begin());
--DI1;
+ // skip dbg_value instructions
+ if (!DI1->isDebugValue())
+ ++i;
+ }
BBI1->BB->erase(DI1, BBI1->BB->end());
PredicateBlock(*BBI1, BBI1->BB->end(), *Cond1);
BBI2->NonPredSize -= TII->RemoveBranch(*BBI2->BB);
DI2 = BBI2->BB->end();
while (NumDups2 != 0) {
+ // NumDups2 only counted non-dbg_value instructions, so this won't
+ // run off the head of the list.
+ assert (DI2 != BBI2->BB->begin());
--DI2;
- --NumDups2;
+ // skip dbg_value instructions
+ if (!DI2->isDebugValue())
+ --NumDups2;
}
PredicateBlock(*BBI2, DI2, *Cond2);
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) {
MachineBasicBlock::iterator E,
SmallVectorImpl<MachineOperand> &Cond) {
for (MachineBasicBlock::iterator I = BBI.BB->begin(); I != E; ++I) {
- if (TII->isPredicated(I))
+ if (I->isDebugValue() || TII->isPredicated(I))
continue;
if (!TII->PredicateInstruction(I, Cond)) {
- cerr << "Unable to predicate " << *I << "!\n";
- abort();
+#ifndef NDEBUG
+ dbgs() << "Unable to predicate " << *I << "!\n";
+#endif
+ llvm_unreachable(0);
}
}
ToBBI.BB->insert(ToBBI.BB->end(), MI);
ToBBI.NonPredSize++;
- if (!isPredicated)
+ if (!isPredicated && !MI->isDebugValue())
if (!TII->PredicateInstruction(MI, Cond)) {
- cerr << "Unable to predicate " << *MI << "!\n";
- abort();
+#ifndef NDEBUG
+ dbgs() << "Unable to predicate " << *I << "!\n";
+#endif
+ llvm_unreachable(0);
}
}
// 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!
+ // Now FromBBI always falls through to the next block!
if (NBB && !FromBBI.BB->isSuccessor(NBB))
FromBBI.BB->addSuccessor(NBB);
projects / oota-llvm.git / blobdiff