// the verifier errors.
//===----------------------------------------------------------------------===//
-#include "llvm/Instructions.h"
-#include "llvm/Function.h"
+#include "llvm/CodeGen/Passes.h"
+#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DepthFirstIterator.h"
+#include "llvm/ADT/SetOperations.h"
+#include "llvm/ADT/SmallVector.h"
#include "llvm/CodeGen/LiveIntervalAnalysis.h"
-#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/LiveStackAnalysis.h"
-#include "llvm/CodeGen/MachineInstrBundle.h"
-#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/LiveVariables.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstrBundle.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
-#include "llvm/CodeGen/Passes.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/InlineAsm.h"
+#include "llvm/IR/Instructions.h"
#include "llvm/MC/MCAsmInfo.h"
-#include "llvm/Target/TargetMachine.h"
-#include "llvm/Target/TargetRegisterInfo.h"
-#include "llvm/Target/TargetInstrInfo.h"
-#include "llvm/ADT/DenseSet.h"
-#include "llvm/ADT/SetOperations.h"
-#include "llvm/ADT/SmallVector.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/TargetMachine.h"
+#include "llvm/Target/TargetRegisterInfo.h"
using namespace llvm;
namespace {
typedef SmallVector<const uint32_t*, 4> RegMaskVector;
typedef DenseSet<unsigned> RegSet;
typedef DenseMap<unsigned, const MachineInstr*> RegMap;
+ typedef SmallPtrSet<const MachineBasicBlock*, 8> BlockSet;
const MachineInstr *FirstTerminator;
+ BlockSet FunctionBlocks;
BitVector regsReserved;
- BitVector regsAllocatable;
RegSet regsLive;
RegVector regsDefined, regsDead, regsKilled;
RegMaskVector regMasks;
// block. This set is disjoint from regsLiveOut.
RegSet vregsRequired;
+ // Set versions of block's predecessor and successor lists.
+ BlockSet Preds, Succs;
+
BBInfo() : reachable(false) {}
// Add register to vregsPassed if it belongs there. Return true if
}
bool isAllocatable(unsigned Reg) {
- return Reg < regsAllocatable.size() && regsAllocatable.test(Reg);
+ return Reg < TRI->getNumRegs() && MRI->isAllocatable(Reg);
}
// Analysis information if available
void report(const char *msg, const MachineBasicBlock *MBB,
const LiveInterval &LI);
+ void verifyInlineAsm(const MachineInstr *MI);
+
void checkLiveness(const MachineOperand *MO, unsigned MONum);
void markReachable(const MachineBasicBlock *MBB);
void calcRegsPassed();
void verifyLiveIntervalValue(const LiveInterval&, VNInfo*);
void verifyLiveIntervalSegment(const LiveInterval&,
LiveInterval::const_iterator);
+
+ void verifyStackFrame();
};
struct MachineVerifierPass : public MachineFunctionPass {
raw_ostream *OutFile = 0;
if (OutFileName) {
std::string ErrorInfo;
- OutFile = new raw_fd_ostream(OutFileName, ErrorInfo,
- raw_fd_ostream::F_Append);
+ OutFile = new raw_fd_ostream(OutFileName, ErrorInfo, sys::fs::F_Append);
if (!ErrorInfo.empty()) {
errs() << "Error opening '" << OutFileName << "': " << ErrorInfo << '\n';
exit(1);
visitMachineBasicBlockBefore(MFI);
// Keep track of the current bundle header.
const MachineInstr *CurBundle = 0;
+ // Do we expect the next instruction to be part of the same bundle?
+ bool InBundle = false;
+
for (MachineBasicBlock::const_instr_iterator MBBI = MFI->instr_begin(),
MBBE = MFI->instr_end(); MBBI != MBBE; ++MBBI) {
if (MBBI->getParent() != MFI) {
*OS << "Instruction: " << *MBBI;
continue;
}
+
+ // Check for consistent bundle flags.
+ if (InBundle && !MBBI->isBundledWithPred())
+ report("Missing BundledPred flag, "
+ "BundledSucc was set on predecessor", MBBI);
+ if (!InBundle && MBBI->isBundledWithPred())
+ report("BundledPred flag is set, "
+ "but BundledSucc not set on predecessor", MBBI);
+
// Is this a bundle header?
if (!MBBI->isInsideBundle()) {
if (CurBundle)
for (unsigned I = 0, E = MBBI->getNumOperands(); I != E; ++I)
visitMachineOperand(&MBBI->getOperand(I), I);
visitMachineInstrAfter(MBBI);
+
+ // Was this the last bundled instruction?
+ InBundle = MBBI->isBundledWithSucc();
}
if (CurBundle)
visitMachineBundleAfter(CurBundle);
+ if (InBundle)
+ report("BundledSucc flag set on last instruction in block", &MFI->back());
visitMachineBasicBlockAfter(MFI);
}
visitMachineFunctionAfter();
MF->print(*OS, Indexes);
}
*OS << "*** Bad machine code: " << msg << " ***\n"
- << "- function: " << MF->getFunction()->getName() << "\n";
+ << "- function: " << MF->getName() << "\n";
}
void MachineVerifier::report(const char *msg, const MachineBasicBlock *MBB) {
report(msg, MBB->getParent());
*OS << "- basic block: BB#" << MBB->getNumber()
<< ' ' << MBB->getName()
- << " (" << (void*)MBB << ')';
+ << " (" << (const void*)MBB << ')';
if (Indexes)
*OS << " [" << Indexes->getMBBStartIdx(MBB)
<< ';' << Indexes->getMBBEndIdx(MBB) << ')';
void MachineVerifier::visitMachineFunctionBefore() {
lastIndex = SlotIndex();
- regsReserved = TRI->getReservedRegs(*MF);
+ regsReserved = MRI->getReservedRegs();
// A sub-register of a reserved register is also reserved
for (int Reg = regsReserved.find_first(); Reg>=0;
}
}
- regsAllocatable = TRI->getAllocatableSet(*MF);
-
markReachable(&MF->front());
+
+ // Build a set of the basic blocks in the function.
+ FunctionBlocks.clear();
+ for (MachineFunction::const_iterator
+ I = MF->begin(), E = MF->end(); I != E; ++I) {
+ FunctionBlocks.insert(I);
+ BBInfo &MInfo = MBBInfoMap[I];
+
+ MInfo.Preds.insert(I->pred_begin(), I->pred_end());
+ if (MInfo.Preds.size() != I->pred_size())
+ report("MBB has duplicate entries in its predecessor list.", I);
+
+ MInfo.Succs.insert(I->succ_begin(), I->succ_end());
+ if (MInfo.Succs.size() != I->succ_size())
+ report("MBB has duplicate entries in its successor list.", I);
+ }
+
+ // Check that the register use lists are sane.
+ MRI->verifyUseLists();
+
+ verifyStackFrame();
}
// Does iterator point to a and b as the first two elements?
E = MBB->succ_end(); I != E; ++I) {
if ((*I)->isLandingPad())
LandingPadSuccs.insert(*I);
+ if (!FunctionBlocks.count(*I))
+ report("MBB has successor that isn't part of the function.", MBB);
+ if (!MBBInfoMap[*I].Preds.count(MBB)) {
+ report("Inconsistent CFG", MBB);
+ *OS << "MBB is not in the predecessor list of the successor BB#"
+ << (*I)->getNumber() << ".\n";
+ }
+ }
+
+ // Check the predecessor list.
+ for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
+ E = MBB->pred_end(); I != E; ++I) {
+ if (!FunctionBlocks.count(*I))
+ report("MBB has predecessor that isn't part of the function.", MBB);
+ if (!MBBInfoMap[*I].Succs.count(MBB)) {
+ report("Inconsistent CFG", MBB);
+ *OS << "MBB is not in the successor list of the predecessor BB#"
+ << (*I)->getNumber() << ".\n";
+ }
}
const MCAsmInfo *AsmInfo = TM->getMCAsmInfo();
++MBBI;
if (MBBI == MF->end()) {
report("MBB conditionally falls through out of function!", MBB);
- } if (MBB->succ_size() != 2) {
+ } else if (MBB->succ_size() == 1) {
+ // A conditional branch with only one successor is weird, but allowed.
+ if (&*MBBI != TBB)
+ report("MBB exits via conditional branch/fall-through but only has "
+ "one CFG successor!", MBB);
+ else if (TBB != *MBB->succ_begin())
+ report("MBB exits via conditional branch/fall-through but the CFG "
+ "successor don't match the actual successor!", MBB);
+ } else if (MBB->succ_size() != 2) {
report("MBB exits via conditional branch/fall-through but doesn't have "
"exactly two CFG successors!", MBB);
} else if (!matchPair(MBB->succ_begin(), TBB, MBBI)) {
} else if (TBB && FBB) {
// Block conditionally branches somewhere, otherwise branches
// somewhere else.
- if (MBB->succ_size() != 2) {
+ if (MBB->succ_size() == 1) {
+ // A conditional branch with only one successor is weird, but allowed.
+ if (FBB != TBB)
+ report("MBB exits via conditional branch/branch through but only has "
+ "one CFG successor!", MBB);
+ else if (TBB != *MBB->succ_begin())
+ report("MBB exits via conditional branch/branch through but the CFG "
+ "successor don't match the actual successor!", MBB);
+ } else if (MBB->succ_size() != 2) {
report("MBB exits via conditional branch/branch but doesn't have "
"exactly two CFG successors!", MBB);
} else if (!matchPair(MBB->succ_begin(), TBB, FBB)) {
report("MBB live-in list contains non-physical register", MBB);
continue;
}
- regsLive.insert(*I);
- for (MCSubRegIterator SubRegs(*I, TRI); SubRegs.isValid(); ++SubRegs)
+ for (MCSubRegIterator SubRegs(*I, TRI, /*IncludeSelf=*/true);
+ SubRegs.isValid(); ++SubRegs)
regsLive.insert(*SubRegs);
}
regsLiveInButUnused = regsLive;
assert(MFI && "Function has no frame info");
BitVector PR = MFI->getPristineRegs(MBB);
for (int I = PR.find_first(); I>0; I = PR.find_next(I)) {
- regsLive.insert(I);
- for (MCSubRegIterator SubRegs(I, TRI); SubRegs.isValid(); ++SubRegs)
+ for (MCSubRegIterator SubRegs(I, TRI, /*IncludeSelf=*/true);
+ SubRegs.isValid(); ++SubRegs)
regsLive.insert(*SubRegs);
}
}
}
+// The operands on an INLINEASM instruction must follow a template.
+// Verify that the flag operands make sense.
+void MachineVerifier::verifyInlineAsm(const MachineInstr *MI) {
+ // The first two operands on INLINEASM are the asm string and global flags.
+ if (MI->getNumOperands() < 2) {
+ report("Too few operands on inline asm", MI);
+ return;
+ }
+ if (!MI->getOperand(0).isSymbol())
+ report("Asm string must be an external symbol", MI);
+ if (!MI->getOperand(1).isImm())
+ report("Asm flags must be an immediate", MI);
+ // Allowed flags are Extra_HasSideEffects = 1, Extra_IsAlignStack = 2,
+ // Extra_AsmDialect = 4, Extra_MayLoad = 8, and Extra_MayStore = 16.
+ if (!isUInt<5>(MI->getOperand(1).getImm()))
+ report("Unknown asm flags", &MI->getOperand(1), 1);
+
+ assert(InlineAsm::MIOp_FirstOperand == 2 && "Asm format changed");
+
+ unsigned OpNo = InlineAsm::MIOp_FirstOperand;
+ unsigned NumOps;
+ for (unsigned e = MI->getNumOperands(); OpNo < e; OpNo += NumOps) {
+ const MachineOperand &MO = MI->getOperand(OpNo);
+ // There may be implicit ops after the fixed operands.
+ if (!MO.isImm())
+ break;
+ NumOps = 1 + InlineAsm::getNumOperandRegisters(MO.getImm());
+ }
+
+ if (OpNo > MI->getNumOperands())
+ report("Missing operands in last group", MI);
+
+ // An optional MDNode follows the groups.
+ if (OpNo < MI->getNumOperands() && MI->getOperand(OpNo).isMetadata())
+ ++OpNo;
+
+ // All trailing operands must be implicit registers.
+ for (unsigned e = MI->getNumOperands(); OpNo < e; ++OpNo) {
+ const MachineOperand &MO = MI->getOperand(OpNo);
+ if (!MO.isReg() || !MO.isImplicit())
+ report("Expected implicit register after groups", &MO, OpNo);
+ }
+}
+
void MachineVerifier::visitMachineInstrBefore(const MachineInstr *MI) {
const MCInstrDesc &MCID = MI->getDesc();
if (MI->getNumOperands() < MCID.getNumOperands()) {
<< MI->getNumExplicitOperands() << " given.\n";
}
+ // Check the tied operands.
+ if (MI->isInlineAsm())
+ verifyInlineAsm(MI);
+
// Check the MachineMemOperands for basic consistency.
for (MachineInstr::mmo_iterator I = MI->memoperands_begin(),
E = MI->memoperands_end(); I != E; ++I) {
MachineVerifier::visitMachineOperand(const MachineOperand *MO, unsigned MONum) {
const MachineInstr *MI = MO->getParent();
const MCInstrDesc &MCID = MI->getDesc();
- const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
// The first MCID.NumDefs operands must be explicit register defines
if (MONum < MCID.getNumDefs()) {
+ const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
if (!MO->isReg())
report("Explicit definition must be a register", MO, MONum);
else if (!MO->isDef() && !MCOI.isOptionalDef())
else if (MO->isImplicit())
report("Explicit definition marked as implicit", MO, MONum);
} else if (MONum < MCID.getNumOperands()) {
+ const MCOperandInfo &MCOI = MCID.OpInfo[MONum];
// Don't check if it's the last operand in a variadic instruction. See,
// e.g., LDM_RET in the arm back end.
if (MO->isReg() &&
if (MO->isImplicit())
report("Explicit operand marked as implicit", MO, MONum);
}
+
+ int TiedTo = MCID.getOperandConstraint(MONum, MCOI::TIED_TO);
+ if (TiedTo != -1) {
+ if (!MO->isReg())
+ report("Tied use must be a register", MO, MONum);
+ else if (!MO->isTied())
+ report("Operand should be tied", MO, MONum);
+ else if (unsigned(TiedTo) != MI->findTiedOperandIdx(MONum))
+ report("Tied def doesn't match MCInstrDesc", MO, MONum);
+ } else if (MO->isReg() && MO->isTied())
+ report("Explicit operand should not be tied", MO, MONum);
} else {
// ARM adds %reg0 operands to indicate predicates. We'll allow that.
if (MO->isReg() && !MO->isImplicit() && !MI->isVariadic() && MO->getReg())
if (MRI->tracksLiveness() && !MI->isDebugValue())
checkLiveness(MO, MONum);
+ // Verify the consistency of tied operands.
+ if (MO->isTied()) {
+ unsigned OtherIdx = MI->findTiedOperandIdx(MONum);
+ const MachineOperand &OtherMO = MI->getOperand(OtherIdx);
+ if (!OtherMO.isReg())
+ report("Must be tied to a register", MO, MONum);
+ if (!OtherMO.isTied())
+ report("Missing tie flags on tied operand", MO, MONum);
+ if (MI->findTiedOperandIdx(OtherIdx) != MONum)
+ report("Inconsistent tie links", MO, MONum);
+ if (MONum < MCID.getNumDefs()) {
+ if (OtherIdx < MCID.getNumOperands()) {
+ if (-1 == MCID.getOperandConstraint(OtherIdx, MCOI::TIED_TO))
+ report("Explicit def tied to explicit use without tie constraint",
+ MO, MONum);
+ } else {
+ if (!OtherMO.isImplicit())
+ report("Explicit def should be tied to implicit use", MO, MONum);
+ }
+ }
+ }
+
// Verify two-address constraints after leaving SSA form.
unsigned DefIdx;
if (!MRI->isSSA() && MO->isUse() &&
}
}
}
+
+namespace {
+ // FrameSetup and FrameDestroy can have zero adjustment, so using a single
+ // integer, we can't tell whether it is a FrameSetup or FrameDestroy if the
+ // value is zero.
+ // We use a bool plus an integer to capture the stack state.
+ struct StackStateOfBB {
+ StackStateOfBB() : EntryValue(0), ExitValue(0), EntryIsSetup(false),
+ ExitIsSetup(false) { }
+ StackStateOfBB(int EntryVal, int ExitVal, bool EntrySetup, bool ExitSetup) :
+ EntryValue(EntryVal), ExitValue(ExitVal), EntryIsSetup(EntrySetup),
+ ExitIsSetup(ExitSetup) { }
+ // Can be negative, which means we are setting up a frame.
+ int EntryValue;
+ int ExitValue;
+ bool EntryIsSetup;
+ bool ExitIsSetup;
+ };
+}
+
+/// Make sure on every path through the CFG, a FrameSetup <n> is always followed
+/// by a FrameDestroy <n>, stack adjustments are identical on all
+/// CFG edges to a merge point, and frame is destroyed at end of a return block.
+void MachineVerifier::verifyStackFrame() {
+ int FrameSetupOpcode = TII->getCallFrameSetupOpcode();
+ int FrameDestroyOpcode = TII->getCallFrameDestroyOpcode();
+
+ SmallVector<StackStateOfBB, 8> SPState;
+ SPState.resize(MF->getNumBlockIDs());
+ SmallPtrSet<const MachineBasicBlock*, 8> Reachable;
+
+ // Visit the MBBs in DFS order.
+ for (df_ext_iterator<const MachineFunction*,
+ SmallPtrSet<const MachineBasicBlock*, 8> >
+ DFI = df_ext_begin(MF, Reachable), DFE = df_ext_end(MF, Reachable);
+ DFI != DFE; ++DFI) {
+ const MachineBasicBlock *MBB = *DFI;
+
+ StackStateOfBB BBState;
+ // Check the exit state of the DFS stack predecessor.
+ if (DFI.getPathLength() >= 2) {
+ const MachineBasicBlock *StackPred = DFI.getPath(DFI.getPathLength() - 2);
+ assert(Reachable.count(StackPred) &&
+ "DFS stack predecessor is already visited.\n");
+ BBState.EntryValue = SPState[StackPred->getNumber()].ExitValue;
+ BBState.EntryIsSetup = SPState[StackPred->getNumber()].ExitIsSetup;
+ BBState.ExitValue = BBState.EntryValue;
+ BBState.ExitIsSetup = BBState.EntryIsSetup;
+ }
+
+ // Update stack state by checking contents of MBB.
+ for (MachineBasicBlock::const_iterator I = MBB->begin(), E = MBB->end();
+ I != E; ++I) {
+ if (I->getOpcode() == FrameSetupOpcode) {
+ // The first operand of a FrameOpcode should be i32.
+ int Size = I->getOperand(0).getImm();
+ assert(Size >= 0 &&
+ "Value should be non-negative in FrameSetup and FrameDestroy.\n");
+
+ if (BBState.ExitIsSetup)
+ report("FrameSetup is after another FrameSetup", I);
+ BBState.ExitValue -= Size;
+ BBState.ExitIsSetup = true;
+ }
+
+ if (I->getOpcode() == FrameDestroyOpcode) {
+ // The first operand of a FrameOpcode should be i32.
+ int Size = I->getOperand(0).getImm();
+ assert(Size >= 0 &&
+ "Value should be non-negative in FrameSetup and FrameDestroy.\n");
+
+ if (!BBState.ExitIsSetup)
+ report("FrameDestroy is not after a FrameSetup", I);
+ int AbsSPAdj = BBState.ExitValue < 0 ? -BBState.ExitValue :
+ BBState.ExitValue;
+ if (BBState.ExitIsSetup && AbsSPAdj != Size) {
+ report("FrameDestroy <n> is after FrameSetup <m>", I);
+ *OS << "FrameDestroy <" << Size << "> is after FrameSetup <"
+ << AbsSPAdj << ">.\n";
+ }
+ BBState.ExitValue += Size;
+ BBState.ExitIsSetup = false;
+ }
+ }
+ SPState[MBB->getNumber()] = BBState;
+
+ // Make sure the exit state of any predecessor is consistent with the entry
+ // state.
+ for (MachineBasicBlock::const_pred_iterator I = MBB->pred_begin(),
+ E = MBB->pred_end(); I != E; ++I) {
+ if (Reachable.count(*I) &&
+ (SPState[(*I)->getNumber()].ExitValue != BBState.EntryValue ||
+ SPState[(*I)->getNumber()].ExitIsSetup != BBState.EntryIsSetup)) {
+ report("The exit stack state of a predecessor is inconsistent.", MBB);
+ *OS << "Predecessor BB#" << (*I)->getNumber() << " has exit state ("
+ << SPState[(*I)->getNumber()].ExitValue << ", "
+ << SPState[(*I)->getNumber()].ExitIsSetup
+ << "), while BB#" << MBB->getNumber() << " has entry state ("
+ << BBState.EntryValue << ", " << BBState.EntryIsSetup << ").\n";
+ }
+ }
+
+ // Make sure the entry state of any successor is consistent with the exit
+ // state.
+ for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
+ E = MBB->succ_end(); I != E; ++I) {
+ if (Reachable.count(*I) &&
+ (SPState[(*I)->getNumber()].EntryValue != BBState.ExitValue ||
+ SPState[(*I)->getNumber()].EntryIsSetup != BBState.ExitIsSetup)) {
+ report("The entry stack state of a successor is inconsistent.", MBB);
+ *OS << "Successor BB#" << (*I)->getNumber() << " has entry state ("
+ << SPState[(*I)->getNumber()].EntryValue << ", "
+ << SPState[(*I)->getNumber()].EntryIsSetup
+ << "), while BB#" << MBB->getNumber() << " has exit state ("
+ << BBState.ExitValue << ", " << BBState.ExitIsSetup << ").\n";
+ }
+ }
+
+ // Make sure a basic block with return ends with zero stack adjustment.
+ if (!MBB->empty() && MBB->back().isReturn()) {
+ if (BBState.ExitIsSetup)
+ report("A return block ends with a FrameSetup.", MBB);
+ if (BBState.ExitValue)
+ report("A return block ends with a nonzero stack adjustment.", MBB);
+ }
+ }
+}
projects / oota-llvm.git / blobdiff