//
//===----------------------------------------------------------------------===//
-#define DEBUG_TYPE "early-ifcvt"
-#include "MachineTraceMetrics.h"
-#include "llvm/Function.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseSet.h"
+#include "llvm/ADT/Statistic.h"
#include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/MachineTraceMetrics.h"
#include "llvm/CodeGen/Passes.h"
-#include "llvm/MC/MCInstrItineraries.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/Target/TargetRegisterInfo.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+#include "llvm/Target/TargetSubtargetInfo.h"
using namespace llvm;
+#define DEBUG_TYPE "early-ifcvt"
+
// Absolute maximum number of instructions allowed per speculated block.
// This bypasses all other heuristics, so it should be set fairly high.
static cl::opt<unsigned>
static cl::opt<bool> Stress("stress-early-ifcvt", cl::Hidden,
cl::desc("Turn all knobs to 11"));
-typedef SmallSetVector<MachineBasicBlock*, 8> BlockSetVector;
+STATISTIC(NumDiamondsSeen, "Number of diamonds");
+STATISTIC(NumDiamondsConv, "Number of diamonds converted");
+STATISTIC(NumTrianglesSeen, "Number of triangles");
+STATISTIC(NumTrianglesConv, "Number of triangles converted");
//===----------------------------------------------------------------------===//
// SSAIfConv
/// Find a valid insertion point in Head.
bool findInsertionPoint();
+ /// Replace PHI instructions in Tail with selects.
+ void replacePHIInstrs();
+
+ /// Insert selects and rewrite PHI operands to use them.
+ void rewritePHIOperands();
+
public:
/// runOnMachineFunction - Initialize per-function data structures.
void runOnMachineFunction(MachineFunction &MF) {
// We never speculate stores, so an AA pointer isn't necessary.
bool DontMoveAcrossStore = true;
- if (!I->isSafeToMove(TII, 0, DontMoveAcrossStore)) {
+ if (!I->isSafeToMove(TII, nullptr, DontMoveAcrossStore)) {
DEBUG(dbgs() << "Can't speculate: " << *I);
return false;
}
///
bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) {
Head = MBB;
- TBB = FBB = Tail = 0;
+ TBB = FBB = Tail = nullptr;
if (Head->succ_size() != 2)
return false;
if (Succ0->pred_size() != 1 || Succ0->succ_size() != 1)
return false;
- // We could support additional Tail predecessors by updating phis instead of
- // eliminating them. Let's see an example where it matters first.
Tail = Succ0->succ_begin()[0];
- if (Tail->pred_size() != 2)
- return false;
// This is not a triangle.
if (Tail != Succ1) {
if (!findInsertionPoint())
return false;
+ if (isTriangle())
+ ++NumTrianglesSeen;
+ else
+ ++NumDiamondsSeen;
return true;
}
+/// replacePHIInstrs - Completely replace PHI instructions with selects.
+/// This is possible when the only Tail predecessors are the if-converted
+/// blocks.
+void SSAIfConv::replacePHIInstrs() {
+ assert(Tail->pred_size() == 2 && "Cannot replace PHIs");
+ MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
+ assert(FirstTerm != Head->end() && "No terminators");
+ DebugLoc HeadDL = FirstTerm->getDebugLoc();
+
+ // Convert all PHIs to select instructions inserted before FirstTerm.
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
+ PHIInfo &PI = PHIs[i];
+ DEBUG(dbgs() << "If-converting " << *PI.PHI);
+ unsigned DstReg = PI.PHI->getOperand(0).getReg();
+ TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
+ DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
+ PI.PHI->eraseFromParent();
+ PI.PHI = nullptr;
+ }
+}
+
+/// rewritePHIOperands - When there are additional Tail predecessors, insert
+/// select instructions in Head and rewrite PHI operands to use the selects.
+/// Keep the PHI instructions in Tail to handle the other predecessors.
+void SSAIfConv::rewritePHIOperands() {
+ MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
+ assert(FirstTerm != Head->end() && "No terminators");
+ DebugLoc HeadDL = FirstTerm->getDebugLoc();
+
+ // Convert all PHIs to select instructions inserted before FirstTerm.
+ for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
+ PHIInfo &PI = PHIs[i];
+ DEBUG(dbgs() << "If-converting " << *PI.PHI);
+ unsigned PHIDst = PI.PHI->getOperand(0).getReg();
+ unsigned DstReg = MRI->createVirtualRegister(MRI->getRegClass(PHIDst));
+ TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
+ DEBUG(dbgs() << " --> " << *std::prev(FirstTerm));
+
+ // Rewrite PHI operands TPred -> (DstReg, Head), remove FPred.
+ for (unsigned i = PI.PHI->getNumOperands(); i != 1; i -= 2) {
+ MachineBasicBlock *MBB = PI.PHI->getOperand(i-1).getMBB();
+ if (MBB == getTPred()) {
+ PI.PHI->getOperand(i-1).setMBB(Head);
+ PI.PHI->getOperand(i-2).setReg(DstReg);
+ } else if (MBB == getFPred()) {
+ PI.PHI->RemoveOperand(i-1);
+ PI.PHI->RemoveOperand(i-2);
+ }
+ }
+ DEBUG(dbgs() << " --> " << *PI.PHI);
+ }
+}
/// convertIf - Execute the if conversion after canConvertIf has determined the
/// feasibility.
void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
+ // Update statistics.
+ if (isTriangle())
+ ++NumTrianglesConv;
+ else
+ ++NumDiamondsConv;
+
// Move all instructions into Head, except for the terminators.
if (TBB != Tail)
Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
if (FBB != Tail)
Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
- MachineBasicBlock::iterator FirstTerm = Head->getFirstTerminator();
- assert(FirstTerm != Head->end() && "No terminators");
- DebugLoc HeadDL = FirstTerm->getDebugLoc();
-
- // Convert all PHIs to select instructions inserted before FirstTerm.
- for (unsigned i = 0, e = PHIs.size(); i != e; ++i) {
- PHIInfo &PI = PHIs[i];
- DEBUG(dbgs() << "If-converting " << *PI.PHI);
- assert(PI.PHI->getNumOperands() == 5 && "Unexpected PHI operands.");
- unsigned DstReg = PI.PHI->getOperand(0).getReg();
- TII->insertSelect(*Head, FirstTerm, HeadDL, DstReg, Cond, PI.TReg, PI.FReg);
- DEBUG(dbgs() << " --> " << *llvm::prior(FirstTerm));
- PI.PHI->eraseFromParent();
- PI.PHI = 0;
- }
+ // Are there extra Tail predecessors?
+ bool ExtraPreds = Tail->pred_size() != 2;
+ if (ExtraPreds)
+ rewritePHIOperands();
+ else
+ replacePHIInstrs();
// Fix up the CFG, temporarily leave Head without any successors.
Head->removeSuccessor(TBB);
// Fix up Head's terminators.
// It should become a single branch or a fallthrough.
+ DebugLoc HeadDL = Head->getFirstTerminator()->getDebugLoc();
TII->RemoveBranch(*Head);
// Erase the now empty conditional blocks. It is likely that Head can fall
}
assert(Head->succ_empty() && "Additional head successors?");
- if (Head->isLayoutSuccessor(Tail)) {
+ if (!ExtraPreds && Head->isLayoutSuccessor(Tail)) {
// Splice Tail onto the end of Head.
DEBUG(dbgs() << "Joining tail BB#" << Tail->getNumber()
<< " into head BB#" << Head->getNumber() << '\n');
// We need a branch to Tail, let code placement work it out later.
DEBUG(dbgs() << "Converting to unconditional branch.\n");
SmallVector<MachineOperand, 0> EmptyCond;
- TII->InsertBranch(*Head, Tail, 0, EmptyCond, HeadDL);
+ TII->InsertBranch(*Head, Tail, nullptr, EmptyCond, HeadDL);
Head->addSuccessor(Tail);
}
DEBUG(dbgs() << *Head);
public:
static char ID;
EarlyIfConverter() : MachineFunctionPass(ID) {}
- void getAnalysisUsage(AnalysisUsage &AU) const;
- bool runOnMachineFunction(MachineFunction &MF);
+ void getAnalysisUsage(AnalysisUsage &AU) const override;
+ bool runOnMachineFunction(MachineFunction &MF) override;
+ const char *getPassName() const override { return "Early If-Conversion"; }
private:
bool tryConvertIf(MachineBasicBlock*);
bool EarlyIfConverter::runOnMachineFunction(MachineFunction &MF) {
DEBUG(dbgs() << "********** EARLY IF-CONVERSION **********\n"
- << "********** Function: "
- << ((Value*)MF.getFunction())->getName() << '\n');
+ << "********** Function: " << MF.getName() << '\n');
+ // Only run if conversion if the target wants it.
+ if (!MF.getTarget()
+ .getSubtarget<TargetSubtargetInfo>()
+ .enableEarlyIfConversion())
+ return false;
+
TII = MF.getTarget().getInstrInfo();
TRI = MF.getTarget().getRegisterInfo();
- SchedModel = MF.getTarget().getInstrItineraryData()->SchedModel;
+ SchedModel =
+ MF.getTarget().getSubtarget<TargetSubtargetInfo>().getSchedModel();
MRI = &MF.getRegInfo();
DomTree = &getAnalysis<MachineDominatorTree>();
Loops = getAnalysisIfAvailable<MachineLoopInfo>();
Traces = &getAnalysis<MachineTraceMetrics>();
- MinInstr = 0;
+ MinInstr = nullptr;
bool Changed = false;
IfConv.runOnMachineFunction(MF);
if (tryConvertIf(I->getBlock()))
Changed = true;
- MF.verify(this, "After early if-conversion");
return Changed;
}
projects / oota-llvm.git / blobdiff