Index: include/llvm/CodeGen/GlobalISel/InstructionSelectTestgen.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/GlobalISel/InstructionSelectTestgen.h @@ -0,0 +1,30 @@ +//===-- GlobalISel/InstructionSelectTestgen.cpp -----------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file This file describes the interface of the ModulePass responsible +/// for auto-generating regression tests for the InstructionSelect pass of +/// GlobalISel. +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H +#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H + +#include "llvm/Pass.h" + +namespace llvm { +class InstructionSelectTestgen : public ModulePass { +public: + static char ID; + InstructionSelectTestgen() : ModulePass(ID) {} + StringRef getPassName() const override { return "InstructionSelectTestgen"; } + void getAnalysisUsage(AnalysisUsage &AU) const override; + bool runOnModule(Module &M) override; +}; +} // End namespace llvm. + +#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECT_TESTGEN_H Index: include/llvm/CodeGen/GlobalISel/InstructionSelector.h =================================================================== --- include/llvm/CodeGen/GlobalISel/InstructionSelector.h +++ include/llvm/CodeGen/GlobalISel/InstructionSelector.h @@ -19,6 +19,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/Optional.h" #include "llvm/ADT/SmallVector.h" +#include "llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h" #include "llvm/Support/CodeGenCoverage.h" #include #include @@ -221,6 +222,7 @@ /// Add a temporary register to the specified instruction /// - InsnID - Instruction ID to modify /// - TempRegID - The temporary register ID to add + /// - TempRegFlags - The register flags to set GIR_AddTempRegister, /// Add an immediate to the specified instruction /// - InsnID - Instruction ID to modify @@ -276,6 +278,8 @@ /// Increment the rule coverage counter. /// - RuleID - The ID of the rule that was covered. GIR_Coverage, + + GIU_NumberOfOpcodes, }; enum { @@ -341,6 +345,10 @@ const RegisterBankInfo &RBI, const PredicateBitset &AvailableFeatures, CodeGenCoverage &CoverageInfo) const; + virtual const int64_t *getMatchTable() const { + llvm_unreachable("Should have been overridden by tablegen if used"); + } + virtual bool testImmPredicate_I64(unsigned, int64_t) const { llvm_unreachable("Subclasses must override this to use tablegen"); } @@ -374,6 +382,12 @@ /// MI and IntoMI do not need to be in the same basic blocks, but MI must /// preceed IntoMI. bool isObviouslySafeToFold(MachineInstr &MI, MachineInstr &IntoMI) const; + +public: + virtual std::unique_ptr getTestgen() const { + llvm_unreachable("Subclasses must use tablegen'erated GlobalISel " + "implementation to auto-generate test cases"); + } }; } // end namespace llvm Index: include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h =================================================================== --- include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h +++ include/llvm/CodeGen/GlobalISel/InstructionSelectorImpl.h @@ -106,6 +106,7 @@ } MachineInstr *NewMI = MRI.getVRegDef(MO.getReg()); + assert(NewMI && "Expected a vreg definition"); if ((size_t)NewInsnID < State.MIs.size()) State.MIs[NewInsnID] = NewMI; else { Index: include/llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h =================================================================== --- /dev/null +++ include/llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h @@ -0,0 +1,69 @@ +//===- llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.h -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file This file declares the API for the instruction selector testgen. +/// The class is responsible for auto-generating regression tests for the +/// InstructionSelect pass of GlobalISel on rule by rule basis. +/// The basic and fully functional implementation is TableGen'erated, the +/// class is used by the InstructionSelectTestgen pass. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H +#define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H + +#include "llvm/ADT/StringRef.h" +#include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/Support/CommandLine.h" + +namespace { +class LiveInRA; +} // end anonymous namespace + +namespace llvm { + +extern cl::opt TestgenFromRule; +extern cl::opt TestgenUntilRule; +extern cl::list TestgenExcludeRules; +extern cl::list TestgenIncludeOnly; +extern cl::opt TestgenSetAllFeatures; +extern cl::opt TestgenNoABI; + +class InstructionSelectorTestgen { +public: + virtual ~InstructionSelectorTestgen() = default; + + virtual void generateTestCases(Module &M, MachineModuleInfo &MMI) const = 0; + + virtual bool checkFeatures(unsigned FeatureBitsetID) const = 0; + virtual LLT getTypeObject(unsigned TypeObjectID) const = 0; + virtual const TargetInstrInfo &getTII() const = 0; + virtual const TargetRegisterInfo &getTRI() const = 0; + virtual const RegisterBankInfo &getRBI() const = 0; + virtual const int64_t *getMatchTable() const = 0; + + static MachineIRBuilder createEmptyTestCase(StringRef Name, Module &M, + MachineModuleInfo &MMI); + static void emitReturnIntoTestCase(MachineIRBuilder &MIRBuilder); + static Type *deduceIRType(LLT LLTy, LLVMContext &Context); + +protected: + InstructionSelectorTestgen() = default; + + void generateTestCasesImpl(Module &M, MachineModuleInfo &MMI) const; + +private: + void generateTestCase(uint64_t CurrentIdx, LiveInRA &RA, + MachineIRBuilder &MIRBuilder) const; +}; + +} // end namespace llvm + +#endif // LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_TESTGEN_H Index: include/llvm/InitializePasses.h =================================================================== --- include/llvm/InitializePasses.h +++ include/llvm/InitializePasses.h @@ -176,6 +176,7 @@ void initializeInstrProfilingLegacyPassPass(PassRegistry&); void initializeInstructionCombiningPassPass(PassRegistry&); void initializeInstructionSelectPass(PassRegistry&); +void initializeInstructionSelectTestgenPass(PassRegistry&); void initializeInterleavedAccessPass(PassRegistry&); void initializeInternalizeLegacyPassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); Index: include/llvm/Support/CodeGenCoverage.h =================================================================== --- include/llvm/Support/CodeGenCoverage.h +++ include/llvm/Support/CodeGenCoverage.h @@ -23,10 +23,13 @@ BitVector RuleCoverage; public: + using covered_iterator = BitVector::const_set_bits_iterator; + CodeGenCoverage(); void setCovered(uint64_t RuleID); - bool isCovered(uint64_t RuleID); + bool isCovered(uint64_t RuleID) const; + iterator_range covered() const; bool parse(MemoryBuffer &Buffer, StringRef BackendName); bool emit(StringRef FilePrefix, StringRef BackendName) const; Index: lib/CodeGen/GlobalISel/CMakeLists.txt =================================================================== --- lib/CodeGen/GlobalISel/CMakeLists.txt +++ lib/CodeGen/GlobalISel/CMakeLists.txt @@ -6,6 +6,8 @@ IRTranslator.cpp InstructionSelect.cpp InstructionSelector.cpp + InstructionSelectTestgen.cpp + InstructionSelectorTestgen.cpp LegalityPredicates.cpp LegalizeMutations.cpp Legalizer.cpp Index: lib/CodeGen/GlobalISel/GlobalISel.cpp =================================================================== --- lib/CodeGen/GlobalISel/GlobalISel.cpp +++ lib/CodeGen/GlobalISel/GlobalISel.cpp @@ -22,4 +22,5 @@ initializeLocalizerPass(Registry); initializeRegBankSelectPass(Registry); initializeInstructionSelectPass(Registry); + initializeInstructionSelectTestgenPass(Registry); } Index: lib/CodeGen/GlobalISel/InstructionSelect.cpp =================================================================== --- lib/CodeGen/GlobalISel/InstructionSelect.cpp +++ lib/CodeGen/GlobalISel/InstructionSelect.cpp @@ -218,6 +218,12 @@ auto &TLI = *MF.getSubtarget().getTargetLowering(); TLI.finalizeLowering(MF); + DEBUG({ + dbgs() << "Rules covered by selecting function: " << MF.getName() << ":"; + for (auto RuleID : CoverageInfo.covered()) + dbgs() << " id" << RuleID; + dbgs() << "\n\n"; + }); CoverageInfo.emit(CoveragePrefix, MF.getSubtarget() .getTargetLowering() Index: lib/CodeGen/GlobalISel/InstructionSelectTestgen.cpp =================================================================== --- /dev/null +++ lib/CodeGen/GlobalISel/InstructionSelectTestgen.cpp @@ -0,0 +1,66 @@ +//===- llvm/CodeGen/GlobalISel/InstructionSelectTestgen.cpp ---------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This file implements the InstructionSelectTestgen class. +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/InstructionSelectTestgen.h" +#include "llvm/CodeGen/GlobalISel/InstructionSelector.h" +#include "llvm/IR/Verifier.h" + +#define DEBUG_TYPE "instruction-select-testgen" + +using namespace llvm; + +char InstructionSelectTestgen::ID = 0; +INITIALIZE_PASS(InstructionSelectTestgen, DEBUG_TYPE, + "Generate instruction selection test cases", false, false) + +void InstructionSelectTestgen::getAnalysisUsage(AnalysisUsage &AU) const { + AU.addRequired(); +} + +static const MachineFunction &createReturnOnlyTestCase(Module &M, + MachineModuleInfo &MMI) { + MachineIRBuilder MIRBuilder = + InstructionSelectorTestgen::createEmptyTestCase("test_return", M, MMI); + InstructionSelectorTestgen::emitReturnIntoTestCase(MIRBuilder); + MachineFunction &MF = MIRBuilder.getMF(); + MF.getProperties().set(MachineFunctionProperties::Property::Legalized); + MF.getProperties().set(MachineFunctionProperties::Property::RegBankSelected); + return MF; +} + +bool InstructionSelectTestgen::runOnModule(Module &M) { + assert(!verifyModule(M, &dbgs()) && "Input module is not valid"); + + MachineModuleInfo &MMI = getAnalysis(); + + for (const Function &F : M.functions()) + if (const MachineFunction *MF = MMI.getMachineFunction(F)) + MF->verify(this, "Pre-existing function", /*AbortOnErrors*/ true); + + const MachineFunction &MF = createReturnOnlyTestCase(M, MMI); + MF.verify(this, "Return only test function", /*AbortOnErrors*/ true); + + const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector(); + assert(ISel && "Can not work without InstructionSelector"); + + std::unique_ptr Testgen = + ISel->getTestgen(); + assert(Testgen && "Can not work without InstructionSelectorTestgen"); + Testgen->generateTestCases(M, MMI); + + for (const Function &F : M.functions()) + if (const MachineFunction *MF = MMI.getMachineFunction(F)) + MF->verify(this, "Output machine function", /*AbortOnErrors*/ true); + + assert(!verifyModule(M, &dbgs()) && "Output module is not valid"); + return true; +} Index: lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp =================================================================== --- /dev/null +++ lib/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp @@ -0,0 +1,907 @@ +//===- llvm/CodeGen/GlobalISel/InstructionSelectorTestgen.cpp -------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +/// \file +/// This file implements the InstructionSelectorTestgen class. +// +//===----------------------------------------------------------------------===// + +#include "llvm/CodeGen/GlobalISel/InstructionSelector.h" +#include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h" +#include "llvm/IR/Verifier.h" + +#define DEBUG_TYPE "instructionselector-testgen" + +using namespace llvm; + +cl::opt llvm::TestgenFromRule( + "testgen-from-rule", + cl::desc("Generate test cases for instruction selector rules from the one " + "specified (by index, inclusive)"), + cl::init(std::numeric_limits::min()), cl::Hidden); + +cl::opt llvm::TestgenUntilRule( + "testgen-until-rule", + cl::desc("Generate test cases for instruction selector rules until the one " + "specified (by index, inclusive)"), + cl::init(std::numeric_limits::max()), cl::Hidden); + +cl::list llvm::TestgenExcludeRules( + "testgen-exclude-rules", + cl::desc("Don't try to generate test cases for the instruction selector " + "rules listed (by index)"), + cl::CommaSeparated, cl::Hidden); + +cl::list llvm::TestgenIncludeOnly( + "testgen-include-only", + cl::desc("Don't try to generate test cases for any instruction selector " + "rules but the ones listed (by index, every other testgen- option " + "is ignored)"), + cl::CommaSeparated, cl::Hidden); + +cl::opt llvm::TestgenSetAllFeatures( + "testgen-set-all-features", + cl::desc("Force all target features to be available"), cl::Hidden); + +cl::opt + llvm::TestgenNoABI("testgen-no-abi", + cl::desc("Don't try to imitate proper ABI boundaries"), + cl::Hidden); + +MachineIRBuilder +InstructionSelectorTestgen::createEmptyTestCase(StringRef Name, Module &M, + MachineModuleInfo &MMI) { + LLVMContext &Context = M.getContext(); + + Function &F = *cast(M.getOrInsertFunction( + Name, FunctionType::get(Type::getVoidTy(Context), false))); + BasicBlock *BB = BasicBlock::Create(Context, "entry", &F); + new UnreachableInst(Context, BB); + assert(!verifyFunction(F, &dbgs()) && "Empty test IR is broken"); + + MachineFunction &MF = MMI.getOrCreateMachineFunction(F); + MachineBasicBlock *MBB = MF.CreateMachineBasicBlock(BB); + MF.push_back(MBB); + MF.verify(/*Pass*/ nullptr, "Empty test function", /*AbortOnErrors*/ true); + + MachineIRBuilder MIRBuilder(MF); + MIRBuilder.setMBB(*MBB); + return MIRBuilder; +} + +void InstructionSelectorTestgen::emitReturnIntoTestCase( + MachineIRBuilder &MIRBuilder) { + MachineBasicBlock &MBB = MIRBuilder.getMBB(); + unsigned RetVReg = 0; + if (!MBB.empty()) { + const MachineInstr &RootInstr = MBB.back(); + if (RootInstr.getNumOperands()) { + const MachineOperand &MO = RootInstr.getOperand(0); + if (MO.isReg() && MO.isDef()) + RetVReg = MO.getReg(); + } + } + auto InsnB = MIRBuilder.buildInstr(TargetOpcode::PATCHABLE_RET).addDef(0); + if (RetVReg) + InsnB.addUse(RetVReg); +} + +Type *InstructionSelectorTestgen::deduceIRType(LLT LLTy, LLVMContext &Context) { + assert(LLTy.isValid() && "Didn't expect an invalid LLT as input"); + if (LLTy.isVector()) + return VectorType::get(deduceIRType(LLTy.getElementType(), Context), + LLTy.getNumElements()); + if (LLTy.isPointer()) + return PointerType::get(Type::getInt32Ty(Context), LLTy.getAddressSpace()); + return Type::getIntNTy(Context, LLTy.getSizeInBits()); +} + +// RegisterBankInfo's getRegBankFromRegClass is only required to be defined on +// user-defined register classes. It could be unable to map TableGen'erated +// register classes (instersections, for instance) to their reg banks +static const RegisterBank * +getRegBankFromRegClass(const RegisterBankInfo &RBI, + const TargetRegisterClass *RC) { + const RegisterBank *Result = nullptr; + for (unsigned i = 0; i < RBI.getNumRegBanks(); ++i) { + const RegisterBank &RB = RBI.getRegBank(i); + if (RB.covers(*RC)) { + assert(!Result && "Register banks should not intersect"); + Result = &RB; + } + } + return Result; +} + +namespace { +class LiveInRA { +public: + LiveInRA(const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI, + const MachineFunction &MF) { + // Classes processed first have the largest impact on the resulting order as + // we only append non-visited registers. Therefore, it's better to process + // the largest classes first: + SmallVector RegClasses(TRI.regclasses()); + std::stable_sort( + RegClasses.begin(), RegClasses.end(), + [](const TargetRegisterClass *RC1, const TargetRegisterClass *RC2) { + // For the reg classes of the same size, it's better to start with + // more concrete ones so we don't overuse weird stuff like register + // tuples (see AArch64) and whatnot, so stable sort this way here, + // reverse later: + return RC1->getNumRegs() < RC2->getNumRegs(); + }); + std::reverse(RegClasses.begin(), RegClasses.end()); + + // Every physical register belongs to a unique register bank, but it may + // belong to register classes of different sizes. Therefore, "visited" + // property needs to be per size: + SmallDenseMap Size2VisitedPhysRegs; + for (const TargetRegisterClass *RC : RegClasses) + if (const RegisterBank *RB = getRegBankFromRegClass(RBI, RC)) { + const unsigned Size = TRI.getRegSizeInBits(*RC); + // RegisterClassInfo::getOrder is not available as the reserved + // registers set is not freezed yet: + for (MCPhysReg PhysReg : RC->getRawAllocationOrder(MF)) + if (!setVisited(Size2VisitedPhysRegs[Size], PhysReg)) + SizeRegBank2Regs[std::make_pair(Size, RB)].first.push_back(PhysReg); + } + // Initializing TrueSizeRegBank2Regs and Reg2TrueSize + SmallVector Keys; + for (const auto &Item : SizeRegBank2Regs) + Keys.push_back(Item.first); + std::sort(Keys.begin(), Keys.end(), std::greater()); + BitVector VisitedPhysRegs; + for (const auto Key : Keys) + for (const MCPhysReg PhysReg : SizeRegBank2Regs[Key].first) + if (!setVisited(VisitedPhysRegs, PhysReg)) { + Reg2TrueSize[PhysReg] = Key.first; + TrueSizeRegBank2Regs[Key].first.push_back(PhysReg); + } + } + + // Returns an inferred actual size of the physical register: true size. + // As a physical register can belong to multiple register classes + // with different register sizes (in bits), the actual size of the + // register could only be guessed as the maximum of all sizes: + unsigned getTrueRegSize(MCPhysReg PhysReg) const { + return Reg2TrueSize.find(PhysReg)->second; + } + + bool hasNext(unsigned SizeInBits, const RegisterBank &RB, + bool ByTrueSize = false) const { + const auto &Map = ByTrueSize ? TrueSizeRegBank2Regs : SizeRegBank2Regs; + return Map.count(std::make_pair(SizeInBits, &RB)); + } + + MCPhysReg next(unsigned SizeInBits, const RegisterBank &RB, + bool ByTrueSize = false) { + assert(hasNext(SizeInBits, RB, ByTrueSize) && "Didn't find an allocatable " + "physical register for the " + "register bank and size"); + auto &Map = ByTrueSize ? TrueSizeRegBank2Regs : SizeRegBank2Regs; + auto &Pool = Map[std::make_pair(SizeInBits, &RB)]; + MCPhysReg AllocatedPhysReg = Pool.first[Pool.second]; + Pool.second = (Pool.second + 1) % Pool.first.size(); + return AllocatedPhysReg; + } + + LiveInRA &reset() { + for (auto &Item : SizeRegBank2Regs) + Item.second.second = 0; + for (auto &Item : TrueSizeRegBank2Regs) + Item.second.second = 0; + return *this; + } + + using Size2RegBanksTy = + DenseMap>; + + const Size2RegBanksTy &getSize2RegBanks() const { + if (Size2RegBanks.empty()) + for (const auto &Item : SizeRegBank2Regs) + Size2RegBanks[Item.first.first].insert(Item.first.second); + return Size2RegBanks; + } + + void dump(const TargetRegisterInfo &TRI) const { + for (const auto &Item : SizeRegBank2Regs) { + dbgs() << "Phys regs of size " << Item.first.first + << " bits from reg bank " << Item.first.second->getName() << ":"; + for (const MCPhysReg PhysReg : Item.second.first) + dbgs() << " " << TRI.getRegAsmName(PhysReg); + dbgs() << "\n"; + } + } + +private: + using SizeRegBank2RegsTy = + DenseMap, + std::pair, unsigned>>; + + // All the physical registers available per bank and size in the preferred + // allocation order with an "allocated so far" index attached: + SizeRegBank2RegsTy SizeRegBank2Regs; + + // getTrueRegSize's cache + DenseMap Reg2TrueSize; + + // All the physical registers available per bank and true size in the + // preferred allocation order with an "allocated so far" index attached: + SizeRegBank2RegsTy TrueSizeRegBank2Regs; + + // getSize2RegBanks' cache + mutable Size2RegBanksTy Size2RegBanks; + + static bool setVisited(BitVector &VisitedPhysRegs, MCPhysReg PhysReg) { + if (PhysReg >= VisitedPhysRegs.size()) + VisitedPhysRegs.resize(PhysReg + 1); + if (!VisitedPhysRegs[PhysReg]) { + VisitedPhysRegs[PhysReg] = true; + return false; + } + return true; + } +}; +} // end anonymous namespace + +static void +selectUnconstrainedRegBanks(const LiveInRA::Size2RegBanksTy &Size2RegBanks, + MachineFunction &MF) { + MachineRegisterInfo &MRI = MF.getRegInfo(); + SmallDenseMap Hist; + for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) { + const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + // Overall in & out vregs of the entire instruction sequence affect the + // selection, the internal vregs and their reg banks don't usually matter, + // but if the selector went into trouble of checking them, they probably do + // so better take them into account as well as the external ones: + if (!MRI.def_empty(Reg) || !MRI.use_empty(Reg)) + // See in which bank the instruction sequence mostly lies in: + ++Hist[MRI.getRegBankOrNull(Reg)]; + } + SmallVector Sizes; + for (const auto &item : Size2RegBanks) + Sizes.push_back(item.first); + std::sort(Sizes.begin(), Sizes.end()); + auto selectRegBank = [&MF, &Sizes, &Size2RegBanks, &Hist](unsigned Reg) { + MachineRegisterInfo &MRI = MF.getRegInfo(); + if (MRI.getRegBankOrNull(Reg)) + return; + const LLT LLTy = MRI.getType(Reg); + unsigned Size = LLTy.getSizeInBits(); + const auto SizeI = std::lower_bound(Sizes.begin(), Sizes.end(), Size); + if (SizeI == Sizes.end()) { + dbgs() << "- Didn't find a register bank containing allocatable\n" + " registers of the required by LLT " << LLTy << " size of\n" + " " << Size << " bits or larger for an unconstrained vreg %" + << TargetRegisterInfo::virtReg2Index(Reg) << "\n"; + // This test will definitely fail during the actual select due to + // register banks not being fully defined yet, but we don't want to + // create too much noise on targets early in GlobalISel migration: + MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); + return; + } + const auto &Banks = Size2RegBanks.find(*SizeI)->second; + assert(!Banks.empty() && "Size2RegBanks is broken: contains empty sets"); + // Out of the banks that have physical registers of an appropriate size + // pick the one that is most common already: + const RegisterBank *RB = *std::max_element( + Banks.begin(), Banks.end(), + [&Hist](const RegisterBank *RB1, const RegisterBank *RB2) { + // Add the unique ID as a tiebreaker for determinism + return std::make_pair(Hist[RB1], RB1->getID()) < + std::make_pair(Hist[RB2], RB2->getID()); + }); + assert(RB && "Size2RegBanks is broken: contains null pointers"); + MRI.setRegBank(Reg, *RB); + // As we might have not picked the most common bank at the previous step + // out of all banks, but only out of a subset of them, update the stats so + // we could greadily select the locally best result for the next vreg: + ++Hist[RB]; + }; + // Process in & out "external" vregs first so our choices on internal ones + // don't affect our choices on the external ones: + for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) { + const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI.def_empty(Reg) ^ MRI.use_empty(Reg)) + selectRegBank(Reg); + } + for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) { + const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + // The internal vregs don't really matter, but we still need to pick + // something for them. Technically, out-of-place banks, banks with no + // registers big enough or no registers at all are fine here, but just in + // case we don't really want to stress selector too much with malicious + // input: + if (!MRI.def_empty(Reg) && !MRI.use_empty(Reg)) + selectRegBank(Reg); + } +} + +static void defineUndefinedVRegs(const TargetInstrInfo &TII, + const TargetRegisterInfo &TRI, + const RegisterBankInfo &RBI, LiveInRA &RA, + MachineIRBuilder &MIRBuilder) { + MachineFunction &MF = MIRBuilder.getMF(); + MachineRegisterInfo &MRI = MF.getRegInfo(); + const auto OrigInsertPt = MIRBuilder.getInsertPt(); + MIRBuilder.setInsertPt(MIRBuilder.getMBB(), MIRBuilder.getMBB().begin()); + for (unsigned i = 0; i < MRI.getNumVirtRegs(); ++i) { + const unsigned Reg = TargetRegisterInfo::index2VirtReg(i); + if (MRI.def_empty(Reg) && !MRI.use_empty(Reg)) { + LLT LLTy = MRI.getType(Reg); + assert(LLTy.isValid() && "Undefined virtual reg doesn't have a type"); + const RegisterBank *RB = MRI.getRegBankOrNull(Reg); + if (!RB) { + dbgs() << "- Undefined virtual register %" + << TargetRegisterInfo::virtReg2Index(Reg) + << " doesn't have a reg bank\n"; + MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg); + } else if (!RA.hasNext(LLTy.getSizeInBits(), *RB, true)) { + dbgs() << "- Didn't find an allocatable physical register for the\n" + " register bank " << RB->getName() << " of the required by" + " LLT " << LLTy << "\n size of " << LLTy.getSizeInBits() + << " bits for an undefined virtual register %" + << TargetRegisterInfo::virtReg2Index(Reg) << "\n"; + MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg); + } else if (TestgenNoABI) + MIRBuilder.buildInstr(TargetOpcode::IMPLICIT_DEF).addDef(Reg); + else + MRI.addLiveIn(RA.next(LLTy.getSizeInBits(), *RB, true), Reg); + } + } + MIRBuilder.setInsertPt(MIRBuilder.getMBB(), OrigInsertPt); + MRI.EmitLiveInCopies(&MF.front(), TRI, TII); +} + +static uint64_t nextGIOpcodeIdx(const int64_t *MatchTable, + uint64_t CurrentIdx) { + static constexpr unsigned NumberOfOperands[GIU_NumberOfOpcodes] = { + 1 /*GIM_Try*/, + 3 /*GIM_RecordInsn*/, + 1 /*GIM_CheckFeatures*/, + 2 /*GIM_CheckOpcode*/, + 2 /*GIM_CheckNumOperands*/, + 2 /*GIM_CheckI64ImmPredicate*/, + 2 /*GIM_CheckAPIntImmPredicate*/, + 2 /*GIM_CheckAPFloatImmPredicate*/, + 2 /*GIM_CheckAtomicOrdering*/, + 2 /*GIM_CheckAtomicOrderingOrStronger*/, + 2 /*GIM_CheckAtomicOrderingWeakerThan*/, + 3 /*GIM_CheckType*/, + 3 /*GIM_CheckPointerToAny*/, + 3 /*GIM_CheckRegBankForClass*/, + 4 /*GIM_CheckComplexPattern*/, + 3 /*GIM_CheckConstantInt*/, + 3 /*GIM_CheckLiteralInt*/, + 3 /*GIM_CheckIntrinsicID*/, + 2 /*GIM_CheckIsMBB*/, + 1 /*GIM_CheckIsSafeToFold*/, + 4 /*GIM_CheckIsSameOperand*/, + 0 /*GIM_Reject*/, + + 3 /*GIR_MutateOpcode*/, + 2 /*GIR_BuildMI*/, + 3 /*GIR_Copy*/, + 4 /*GIR_CopyOrAddZeroReg*/, + 4 /*GIR_CopySubReg*/, + 2 /*GIR_AddImplicitDef*/, + 2 /*GIR_AddImplicitUse*/, + 2 /*GIR_AddRegister*/, + 3 /*GIR_AddTempRegister*/, + 2 /*GIR_AddImm*/, + 2 /*GIR_ComplexRenderer*/, + 3 /*GIR_ComplexSubOperandRenderer*/, + 3 /*GIR_CustomRenderer*/, + 2 /*GIR_CopyConstantAsSImm*/, + 3 /*GIR_ConstrainOperandRC*/, + 1 /*GIR_ConstrainSelectedInstOperands*/, + 3 /*GIR_MergeMemOperands*/, + 1 /*GIR_EraseFromParent*/, + 2 /*GIR_MakeTempReg*/, + 0 /*GIR_Done*/, + 1 /*GIR_Coverage*/, + }; + if (MatchTable[CurrentIdx] == GIR_MergeMemOperands) + do { + ++CurrentIdx; + } while (MatchTable[CurrentIdx] != GIU_MergeMemOperands_EndOfList); + else + CurrentIdx += NumberOfOperands[MatchTable[CurrentIdx]]; + return CurrentIdx + 1; +} + +static MachineInstrBuilder &ensureNumOperands(MachineInstrBuilder &InsnB, + int64_t NumOperands, + int64_t NumDefs = -1) { + if (NumDefs == -1) + NumDefs = InsnB->getDesc().NumDefs; + + while (InsnB->getNumOperands() < NumOperands) + if (InsnB->getNumOperands() < NumDefs) + InsnB.addDef(0); + else + InsnB.addReg(0); + + for (int I = 0; I < NumDefs; ++I) + InsnB->getOperand(I).setIsDef(); + + return InsnB; +} + +static void setType(MachineInstrBuilder &InsnB, unsigned OpIdx, + LLT ExpectedType, MachineRegisterInfo &MRI) { + SmallVector OpIdxs{OpIdx}; + const MCInstrDesc &MCID = InsnB->getDesc(); + if (OpIdx < MCID.getNumOperands() && MCID.OpInfo[OpIdx].isGenericType()) { + const unsigned TypeIdx = MCID.OpInfo[OpIdx].getGenericTypeIndex(); + for (unsigned I = 0; + I < std::min(MCID.getNumOperands(), InsnB->getNumOperands()); ++I) { + if (I == OpIdx || !MCID.OpInfo[I].isGenericType()) + continue; + if (MCID.OpInfo[I].getGenericTypeIndex() == TypeIdx) + OpIdxs.push_back(I); + } + } + ensureNumOperands(InsnB, *std::max_element(OpIdxs.begin(), OpIdxs.end()) + 1); + for (auto Idx : OpIdxs) { + MachineOperand &MO = InsnB->getOperand(Idx); + if (!MO.getReg()) + MO.setReg(MRI.createGenericVirtualRegister(ExpectedType)); + else + MRI.setType(MO.getReg(), ExpectedType); + } +} + +static MachineInstrBuilder & +setOperand(MachineInstrBuilder &InsnB, int64_t OpIdx, + std::function OperandAdder) { + ensureNumOperands(InsnB, OpIdx); + + if (InsnB->getNumOperands() == OpIdx) + OperandAdder(InsnB); + else { + SmallVector Uses; + for (int64_t I = InsnB->getNumOperands() - 1; I > OpIdx; --I) { + Uses.push_back(InsnB->getOperand(I)); + InsnB->RemoveOperand(I); + } + InsnB->RemoveOperand(OpIdx); + OperandAdder(InsnB); + while (!Uses.empty()) + InsnB.add(Uses.pop_back_val()); + } + return InsnB; +} + +static const LLT DummyLLT = LLT::scalar(32); +// Assuming that all the parts of the MatchTable that don't affect the selection +// process but only identify a rule, like GIR_Coverage opcodes, come within a +// rule as a single continuous block, so the meaningful parts of the rule could +// be represented as some prefix and suffix: +using RuleBodyTy = std::pair, ArrayRef>; + +static std::tuple +getDoneIdxRuleIDAndBody(const int64_t *MatchTable, uint64_t CurrentIdx) { + const uint64_t BodyIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx); + uint64_t CoverageFirst = BodyIdx; + uint64_t CoverageLast = CoverageFirst; + int64_t FirstRuleID = -1; + bool CoverageBlockPassed = false; + unsigned NestingLevel = 0; + do { + switch (MatchTable[CurrentIdx++]) { + case GIM_Try: { + CurrentIdx++; + if (++NestingLevel > 1) { +#ifdef NDEBUG + dbgs() + << "Testgen doesn't support non-linear or optimized Match Tables\n"; + exit(1); +#endif + assert(NestingLevel == 1 && + "Testgen doesn't support non-linear or optimized Match Tables"); + } + break; + } + case GIR_Coverage: { + int64_t RuleID = MatchTable[CurrentIdx++]; + assert(RuleID >= 0 && "Expected a non-negative RuleID"); + if (FirstRuleID < 0) { + FirstRuleID = RuleID; + CoverageFirst = CurrentIdx - 2; + } + CoverageLast = CurrentIdx; + if (CoverageBlockPassed) + CoverageFirst = CoverageLast; + break; + } + default: + CoverageBlockPassed = FirstRuleID >= 0; + CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1); + } + } while (MatchTable[CurrentIdx] != GIR_Done); + assert(BodyIdx <= CoverageFirst && + (CoverageFirst < CoverageLast && FirstRuleID >= 0 || + CoverageFirst == CoverageLast) && + CoverageLast <= CurrentIdx && "Broken Coverage Block"); + const auto &RuleBody = RuleBodyTy( + ArrayRef(&MatchTable[BodyIdx], &MatchTable[CoverageFirst]), + ArrayRef(&MatchTable[CoverageLast], &MatchTable[CurrentIdx])); + return std::make_tuple(CurrentIdx, FirstRuleID, RuleBody); +} + +static void +initInsnBuilders(const int64_t *MatchTable, uint64_t CurrentIdx, + MachineIRBuilder &MIRBuilder, + SmallVectorImpl &InsnBuilders) { + do { + switch (MatchTable[CurrentIdx++]) { + case GIM_CheckOpcode: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t Expected = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckOpcode " << InsnID << ", " << Expected << "\n"; + if (static_cast(InsnID) >= InsnBuilders.size()) + InsnBuilders.resize(InsnID + 1); + InsnBuilders[InsnID] = MIRBuilder.buildInstrNoInsert(Expected); + + // G_CONSTANT's and G_FCONSTANT's are assumed to be well-formed by the + // selector w/o actually checking it. + if (Expected == TargetOpcode::G_CONSTANT) { + ensureNumOperands(InsnBuilders[InsnID], 2); + InsnBuilders[InsnID]->getOperand(1).ChangeToImmediate(1); + } else if (Expected == TargetOpcode::G_FCONSTANT) { + ensureNumOperands(InsnBuilders[InsnID], 2); + InsnBuilders[InsnID]->getOperand(1).ChangeToFPImmediate(ConstantFP::get( + MIRBuilder.getMF().getFunction().getContext(), APFloat(0.0))); + } + break; + } + default: + CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1); + } + } while (MatchTable[CurrentIdx] != GIR_Done); +} + +static void mainPass(const InstructionSelectorTestgen &Testgen, + uint64_t CurrentIdx, MachineIRBuilder &MIRBuilder, + SmallVectorImpl &InsnBuilders, + SmallVectorImpl &InsnOrder) { + MachineFunction &MF = MIRBuilder.getMF(); + MachineRegisterInfo &MRI = MF.getRegInfo(); + const TargetRegisterInfo &TRI = Testgen.getTRI(); + const RegisterBankInfo &RBI = Testgen.getRBI(); + const int64_t *MatchTable = Testgen.getMatchTable(); + InsnOrder.push_back(0); + do { + switch (MatchTable[CurrentIdx++]) { + case GIM_RecordInsn: { + int64_t NewInsnID = MatchTable[CurrentIdx++]; + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + dbgs() << "GIM_RecordInsn " << NewInsnID << ", " << InsnID << ", " + << OpIdx << "\n"; + InsnOrder.push_back(NewInsnID); + MachineOperand &Def = + ensureNumOperands(InsnBuilders[NewInsnID], 1, 1)->getOperand(0); + MachineOperand &Use = + ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1)->getOperand(OpIdx); + unsigned Reg = Use.isReg() && Use.getReg() ? Use.getReg() : Def.getReg(); + Reg = Reg ? Reg : MRI.createGenericVirtualRegister(DummyLLT); + Def.setReg(Reg); + Use.ChangeToRegister(Reg, /*isDef*/ false); + break; + } + case GIM_CheckNumOperands: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t Expected = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckNumOperands " << InsnID << ", " << Expected << "\n"; + ensureNumOperands(InsnBuilders[InsnID], Expected); + break; + } + case GIM_CheckIntrinsicID: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t Value = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckIntrinsicID " << InsnID << ", " << OpIdx << ", " + << Value << "\n"; + auto &InsnB = ensureNumOperands(InsnBuilders[InsnID], OpIdx, OpIdx); + setOperand(InsnB, OpIdx, [Value](MachineInstrBuilder &InsnB) { + InsnB.addIntrinsicID(static_cast(Value)); + }); + break; + } + case GIM_CheckIsMBB: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckIsMBB " << InsnID << ", " << OpIdx << "\n"; + setOperand( + InsnBuilders[InsnID], OpIdx, + [&MF](MachineInstrBuilder &InsnB) { InsnB.addMBB(&MF.back()); }); + break; + } + case GIM_CheckType: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t TypeID = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckType " << InsnID << ", " << OpIdx << ", " << TypeID + << "\n"; + setType(InsnBuilders[InsnID], OpIdx, Testgen.getTypeObject(TypeID), MRI); + break; + } + case GIM_CheckPointerToAny: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t SizeInBits = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckPointerToAny " << InsnID << ", " << OpIdx << ", " + << SizeInBits << "\n"; + if (!SizeInBits) + SizeInBits = MF.getDataLayout().getPointerSizeInBits(0); + setType(InsnBuilders[InsnID], OpIdx, LLT::pointer(0, SizeInBits), MRI); + break; + } + case GIM_CheckRegBankForClass: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t RCEnum = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckRegBankForClass " << InsnID << ", " << OpIdx << ", " + << RCEnum << "\n"; + const TargetRegisterClass *RC = TRI.getRegClass(RCEnum); + const RegisterBank *ExpectedRegBank = getRegBankFromRegClass(RBI, RC); + MachineOperand &MO = + ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1)->getOperand(OpIdx); + if (!MO.getReg()) + MO.setReg(MRI.createGenericVirtualRegister(DummyLLT)); + if (ExpectedRegBank) + MRI.setRegBank(MO.getReg(), *ExpectedRegBank); + else { + dbgs() << "- Didn't find a register bank covering class " + << TRI.getRegClassName(RC) << " for operand #" << OpIdx + << " (" << MO << ")" << " of\n" + << " " << *InsnBuilders[InsnID].getInstr() << "\n"; + // This test will definitely fail during the actual select due to + // register banks not being fully defined yet, but we don't want to + // create too much noise on targets early in GlobalISel migration: + MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); + } + break; + } + case GIM_CheckFeatures: { + int64_t ExpectedBitsetID = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckFeatures " << ExpectedBitsetID << "\n"; + if (!Testgen.checkFeatures(ExpectedBitsetID)) { + dbgs() << "! Testgen deficiency: Don't know how to satisfy\n" + << " Module & Function Target Features yet!\n"; + // This test definitely won't match the rule being tested and might not + // even select at all, so mark it to be skipped: + MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); + } + break; + } + case GIM_CheckConstantInt: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t Value = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckConstantInt " << InsnID << ", " << OpIdx << ", " + << Value << "\n"; + MachineOperand &MO = + ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1)->getOperand(OpIdx); + if (MO.isReg() && MO.isUse() && MRI.def_empty(MO.getReg())) { + if (!MO.getReg()) + MO.ChangeToRegister(MRI.createGenericVirtualRegister(DummyLLT), + /*isDef*/ false); + InsnOrder.push_back(InsnBuilders.size()); + InsnBuilders.push_back( + MIRBuilder.buildInstrNoInsert(TargetOpcode::G_CONSTANT) + .addDef(MO.getReg()) + .addImm(Value)); + } + break; + } + case GIM_CheckI64ImmPredicate: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t Predicate = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckI64ImmPredicate " << InsnID << ", " << Predicate + << "\n"; + setOperand(InsnBuilders[InsnID], 1, + [](MachineInstrBuilder &InsnB) { InsnB.addImm(1); }); + break; + } + default: + CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1); + } + } while (MatchTable[CurrentIdx] != GIR_Done); +} + +static void latePass(const int64_t *MatchTable, uint64_t CurrentIdx, + MachineFunction &MF, + SmallVectorImpl &InsnBuilders) { + MachineRegisterInfo &MRI = MF.getRegInfo(); + do { + switch (MatchTable[CurrentIdx++]) { + case GIM_CheckAtomicOrdering: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OrderingVal = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckAtomicOrdering " << InsnID << ", " << OrderingVal + << "\n"; + MachineInstrBuilder &InsnB = InsnBuilders[InsnID]; + auto PtrInfo = MachinePointerInfo::getUnknownStack(MF); + auto Flags = (InsnB->mayLoad() ? MachineMemOperand::MOLoad + : MachineMemOperand::MONone) | + (InsnB->mayStore() ? MachineMemOperand::MOStore + : MachineMemOperand::MOLoad); + LLT LLTy = DummyLLT; + for (const MachineOperand &MO : InsnB->operands()) + if (MO.isReg() && MO.getReg() && MRI.getType(MO.getReg()).isValid()) { + LLTy = MRI.getType(MO.getReg()); + break; + } + Type *ValTy = InstructionSelectorTestgen::deduceIRType( + LLTy, MF.getFunction().getContext()); + auto Size = MF.getDataLayout().getTypeStoreSize(ValTy); + auto Alignment = MF.getDataLayout().getABITypeAlignment(ValTy); + auto Ordering = static_cast(OrderingVal); + MachineMemOperand *MMO = + MF.getMachineMemOperand(PtrInfo, Flags, Size, Alignment, AAMDNodes(), + nullptr, SyncScope::System, Ordering); + if (InsnB->memoperands_empty()) + InsnB.addMemOperand(MMO); + else + *InsnB->memoperands_begin() = MMO; + break; + } + case GIM_CheckIsSameOperand: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t OpIdx = MatchTable[CurrentIdx++]; + int64_t OtherInsnID = MatchTable[CurrentIdx++]; + int64_t OtherOpIdx = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckIsSameOperand " << InsnID << ", " << OpIdx << ", " + << ", " << OtherInsnID << ", " << OtherOpIdx << "\n"; + auto &InsnB = ensureNumOperands(InsnBuilders[InsnID], OpIdx + 1); + auto &OtherInsnB = + ensureNumOperands(InsnBuilders[OtherInsnID], OtherOpIdx + 1); + const auto &MO = InsnB->getOperand(OpIdx); + const auto &OtherMO = OtherInsnB->getOperand(OtherOpIdx); + assert(MO.isReg() && OtherMO.isReg() && "Expected regs as same operands"); + if (MRI.def_empty(OtherMO.getReg()) && MO.getReg()) + setOperand(OtherInsnB, OtherOpIdx, + [&MO](MachineInstrBuilder &OtherInsnB) { + OtherInsnB.addReg(MO.getReg()); + }); + else + setOperand(InsnB, OpIdx, [&OtherMO](MachineInstrBuilder &InsnB) { + InsnB.addReg(OtherMO.getReg()); + }); + break; + } + case GIM_CheckAPIntImmPredicate: { + int64_t InsnID = MatchTable[CurrentIdx++]; + int64_t Predicate = MatchTable[CurrentIdx++]; + dbgs() << "GIM_CheckAPIntImmPredicate " << InsnID << ", " << Predicate + << "\n"; + setOperand( + InsnBuilders[InsnID], 1, [&MF, &MRI](MachineInstrBuilder &InsnB) { + const MachineOperand &Def = InsnB->getOperand(0); + LLT LLTy = Def.isReg() ? MRI.getType(Def.getReg()) : LLT{}; + LLTy = LLTy.isValid() ? LLTy : DummyLLT; + InsnB.addCImm(ConstantInt::get(MF.getFunction().getContext(), + APInt(LLTy.getSizeInBits(), 1))); + }); + break; + } + default: + CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentIdx - 1); + } + } while (MatchTable[CurrentIdx] != GIR_Done); +} + +static std::string buildName(unsigned RuleNum, uint64_t RuleIdx, + int64_t RuleID = -1) { + const auto &ID = RuleID < 0 ? Twine{} : "_id" + Twine(RuleID); + return ("test_rule" + Twine(RuleNum) + ID + "_at_idx" + Twine(RuleIdx)).str(); +} + +static bool skipRule(unsigned RuleNum, uint64_t CurrentIdx, + int64_t RuleID = -1) { + static DenseSet ExplicitlyListedRules; + if (ExplicitlyListedRules.empty()) + for (unsigned Idx : TestgenIncludeOnly) + ExplicitlyListedRules.insert(Idx); + + if (!ExplicitlyListedRules.empty()) + return !ExplicitlyListedRules.count(RuleNum); + + if (RuleNum < TestgenFromRule || RuleNum > TestgenUntilRule) + return true; + + static SmallDenseSet ExcludedRules; + if (ExcludedRules.empty()) + for (unsigned Idx : TestgenExcludeRules) + ExcludedRules.insert(Idx); + return ExcludedRules.count(RuleNum); +} + +void InstructionSelectorTestgen::generateTestCase( + uint64_t CurrentIdx, LiveInRA &RA, MachineIRBuilder &MIRBuilder) const { + + SmallVector InsnBuilders; + initInsnBuilders(getMatchTable(), CurrentIdx, MIRBuilder, InsnBuilders); + + SmallVector InsnOrder; + mainPass(*this, CurrentIdx, MIRBuilder, InsnBuilders, InsnOrder); + + MachineFunction &MF = MIRBuilder.getMF(); + latePass(getMatchTable(), CurrentIdx, MF, InsnBuilders); + + for (auto I = InsnOrder.rbegin(), E = InsnOrder.rend(); I != E; ++I) + MIRBuilder.insertInstr(InsnBuilders[*I]); + + // We need all the banks in place so we could speculate on ABI better: + dbgs() << "** Selecting RegBanks for VRegs unconstrained by the rule\n"; + selectUnconstrainedRegBanks(RA.getSize2RegBanks(), MF); + // selectUnconstrainedRegBanks relies on the input vregs being undefined, + // so run defineUndefinedVRegs later, not before: + dbgs() << "** Defining VRegs undefined by the rule\n"; + defineUndefinedVRegs(getTII(), getTRI(), getRBI(), RA, MIRBuilder); + // finalize the MBB with a non-generic terminator that uses the root vreg: + InstructionSelectorTestgen::emitReturnIntoTestCase(MIRBuilder); + + MF.getProperties().set(MachineFunctionProperties::Property::Legalized); + MF.getProperties().set(MachineFunctionProperties::Property::RegBankSelected); +} + +void InstructionSelectorTestgen::generateTestCasesImpl( + Module &M, MachineModuleInfo &MMI) const { + + const MachineFunction *MF = MMI.getMachineFunction(*M.begin()); + assert(MF && "Expected the Module / MMI to contain an init Machine Function"); + + const int64_t *MatchTable = getMatchTable(); + unsigned RuleNum = 0; + uint64_t CurrentIdx = 0; + uint64_t CurrentDoneIdx = ~0ULL; + int64_t RuleID = -1; + using RuleSig = std::tuple; + RuleBodyTy RuleBody; + + DenseMap> RuleDuplicates; + LiveInRA RA(getTRI(), getRBI(), *MF); + + while (MatchTable[CurrentIdx] != GIM_Reject) { + std::tie(CurrentDoneIdx, RuleID, RuleBody) = + getDoneIdxRuleIDAndBody(MatchTable, CurrentIdx); + + if (!skipRule(RuleNum, CurrentIdx, RuleID)) { + const auto &Name = buildName(RuleNum, CurrentIdx, RuleID); + SmallVectorImpl &Dups = RuleDuplicates[RuleBody]; + Dups.emplace_back(RuleNum, CurrentIdx, RuleID); + + if (Dups.size() > 1) { + dbgs() << "*** Skipping test case " << Name << " as a duplicate of " + << buildName(std::get<0>(Dups.front()), + std::get<1>(Dups.front()), + std::get<2>(Dups.front())) + << "\n"; + } else { + dbgs() << "\n*** Generating test case " << Name << " ***\n"; + MachineIRBuilder MIRBuilder = + InstructionSelectorTestgen::createEmptyTestCase(Name, M, MMI); + generateTestCase(CurrentIdx, RA.reset(), MIRBuilder); + if (!MIRBuilder.getMF().verify(nullptr, Name.c_str(), false)) { + Function *F = M.getFunction(Name); + MMI.deleteMachineFunctionFor(*F); + F->eraseFromParent(); + } + } + } + ++RuleNum; + CurrentIdx = nextGIOpcodeIdx(MatchTable, CurrentDoneIdx); + } +} Index: lib/Support/CodeGenCoverage.cpp =================================================================== --- lib/Support/CodeGenCoverage.cpp +++ lib/Support/CodeGenCoverage.cpp @@ -38,12 +38,17 @@ RuleCoverage[RuleID] = true; } -bool CodeGenCoverage::isCovered(uint64_t RuleID) { +bool CodeGenCoverage::isCovered(uint64_t RuleID) const { if (RuleCoverage.size() <= RuleID) return false; return RuleCoverage[RuleID]; } +iterator_range +CodeGenCoverage::covered() const { + return RuleCoverage.set_bits(); +} + bool CodeGenCoverage::parse(MemoryBuffer &Buffer, StringRef BackendName) { const char *CurPtr = Buffer.getBufferStart(); Index: test/TableGen/GlobalISelEmitter.td =================================================================== --- test/TableGen/GlobalISelEmitter.td +++ test/TableGen/GlobalISelEmitter.td @@ -78,6 +78,9 @@ // CHECK-NEXT: bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const override; // CHECK-NEXT: bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) const override; // CHECK-NEXT: bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat &Imm) const override; +// CHECK-NEXT: const int64_t *getMatchTable() const override; +// CHECK-NEXT: std::unique_ptr getTestgen() const override; +// CHECK-NEXT: friend class MyTargetInstructionSelectorTestgen; // CHECK-NEXT: #endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL // CHECK-LABEL: #ifdef GET_GLOBALISEL_TEMPORARIES_INIT @@ -221,10 +224,16 @@ // CHECK-NEXT: State.MIs.clear(); // CHECK-NEXT: State.MIs.push_back(&I); +// CHECK: if (executeMatchTable(*this, OutMIs, State, ISelInfo, getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) { +// CHECK-NEXT: return true; +// CHECK-NEXT: } + //===- Test a pattern with multiple ComplexPatterns in multiple instrs ----===// // -// CHECK-LABEL: MatchTable0[] = { +// CHECK: const int64_t * +// CHECK-LABEL: MyTargetInstructionSelector::getMatchTable() const { +// CHECK: MatchTable0[] = { // OPT-NEXT: GIM_Try, /*On fail goto*//*Label [[GRP_LABEL_NUM:[0-9]+]]*/ [[GRP_LABEL:[0-9]+]], // OPT-NEXT: GIM_CheckOpcode, /*MI*/0, TargetOpcode::G_SELECT, // CHECK-NEXT: GIM_Try, /*On fail goto*//*Label [[LABEL_NUM:[0-9]+]]*/ [[LABEL:[0-9]+]], @@ -1100,6 +1109,4 @@ // CHECK-NEXT: GIM_Reject, // CHECK-NEXT: }; -// CHECK-NEXT: if (executeMatchTable(*this, OutMIs, State, ISelInfo, MatchTable0, TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) { -// CHECK-NEXT: return true; -// CHECK-NEXT: } +// CHECK-NEXT: return MatchTable0; Index: utils/TableGen/GlobalISelEmitter.cpp =================================================================== --- utils/TableGen/GlobalISelEmitter.cpp +++ utils/TableGen/GlobalISelEmitter.cpp @@ -407,6 +407,8 @@ unsigned size() const { return NumElements; } }; +class Matcher; + /// Holds the contents of a generated MatchTable to enable formatting and the /// necessary index tracking needed to support GIM_Try. class MatchTable { @@ -419,10 +421,11 @@ /// The currently defined labels. DenseMap LabelMap; /// Tracks the sum of MatchTableRecord::NumElements as the table is built. - unsigned CurrentSize; - + unsigned CurrentSize = 0; /// A unique identifier for a MatchTable label. - static unsigned CurrentLabelID; + unsigned CurrentLabelID = 0; + /// Determines if the table should be instrumented for rule coverage tracking. + bool IsWithCoverage; public: static MatchTableRecord LineBreak; @@ -465,7 +468,12 @@ MatchTableRecord::MTRF_CommaFollows); } - MatchTable(unsigned ID) : ID(ID), CurrentSize(0) {} + static MatchTable buildTable(ArrayRef Rules, bool WithCoverage); + + MatchTable(bool WithCoverage, unsigned ID = 0) + : ID(ID), IsWithCoverage(WithCoverage) {} + + bool isWithCoverage() const { return IsWithCoverage; } void push_back(const MatchTableRecord &Value) { if (Value.Flags & MatchTableRecord::MTRF_Label) @@ -474,7 +482,7 @@ CurrentSize += Value.size(); } - unsigned allocateLabelID() const { return CurrentLabelID++; } + unsigned allocateLabelID() { return CurrentLabelID++; } void defineLabel(unsigned LabelID) { LabelMap.insert(std::make_pair(LabelID, CurrentSize)); @@ -519,8 +527,6 @@ } }; -unsigned MatchTable::CurrentLabelID = 0; - MatchTableRecord MatchTable::LineBreak = { None, "" /* Emit String */, 0 /* Elements */, MatchTableRecord::MTRF_LineBreakFollows}; @@ -577,6 +583,15 @@ virtual std::unique_ptr forgetFirstCondition() = 0; }; +MatchTable MatchTable::buildTable(ArrayRef Rules, + bool WithCoverage) { + MatchTable Table(WithCoverage); + for (Matcher *Rule : Rules) + Rule->emit(Table); + + return Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; +} + class GroupMatcher : public Matcher { SmallVector, 8> Conditions; SmallVector Rules; @@ -2483,7 +2498,7 @@ for (const auto &MA : Actions) MA->emitActionOpcodes(Table, *this); - if (GenerateCoverage) + if (Table.isWithCoverage()) Table << MatchTable::Opcode("GIR_Coverage") << MatchTable::IntValue(RuleID) << MatchTable::LineBreak; @@ -2686,8 +2701,11 @@ /// # predicate C /// \endverbatim std::vector optimizeRules( - const std::vector &Rules, + ArrayRef Rules, std::vector> &StorageGroupMatcher); + + MatchTable buildMatchTable(MutableArrayRef Rules, bool Optimize, + bool WithCoverage); }; void GlobalISelEmitter::gatherNodeEquivs() { @@ -3644,7 +3662,7 @@ } std::vector GlobalISelEmitter::optimizeRules( - const std::vector &Rules, + ArrayRef Rules, std::vector> &StorageGroupMatcher) { std::vector OptRules; // Start with a stupid grouping for now. @@ -3675,6 +3693,23 @@ return OptRules; } +MatchTable +GlobalISelEmitter::buildMatchTable(MutableArrayRef Rules, + bool Optimize, bool WithCoverage) { + std::vector InputRules; + for (Matcher &Rule : Rules) + InputRules.push_back(&Rule); + + if (!Optimize) + return MatchTable::buildTable(InputRules, WithCoverage); + + std::vector> StorageGroupMatcher; + std::vector OptRules = + optimizeRules(InputRules, StorageGroupMatcher); + + return MatchTable::buildTable(OptRules, WithCoverage); +} + void GlobalISelEmitter::run(raw_ostream &OS) { if (!UseCoverageFile.empty()) { RuleCoverage = CodeGenCoverage(); @@ -3767,12 +3802,16 @@ << "InstructionSelector::ComplexMatcherMemFn ComplexPredicateFns[];\n" << " static " << Target.getName() << "InstructionSelector::CustomRendererFn CustomRenderers[];\n" - << "bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const " + << " bool testImmPredicate_I64(unsigned PredicateID, int64_t Imm) const " "override;\n" - << "bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) " + << " bool testImmPredicate_APInt(unsigned PredicateID, const APInt &Imm) " "const override;\n" - << "bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat " + << " bool testImmPredicate_APFloat(unsigned PredicateID, const APFloat " "&Imm) const override;\n" + << " const int64_t *getMatchTable() const override;\n" + << " std::unique_ptr " + "getTestgen() const override;\n" + << " friend class " << Target.getName() << "InstructionSelectorTestgen;\n" << "#endif // ifdef GET_GLOBALISEL_TEMPORARIES_DECL\n\n"; OS << "#ifdef GET_GLOBALISEL_TEMPORARIES_INIT\n" @@ -3924,20 +3963,6 @@ << ", // " << Record->getName() << "\n"; OS << "};\n\n"; - OS << "bool " << Target.getName() - << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage " - "&CoverageInfo) const {\n" - << " MachineFunction &MF = *I.getParent()->getParent();\n" - << " MachineRegisterInfo &MRI = MF.getRegInfo();\n" - << " // FIXME: This should be computed on a per-function basis rather " - "than per-insn.\n" - << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI, " - "&MF);\n" - << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n" - << " NewMIVector OutMIs;\n" - << " State.MIs.clear();\n" - << " State.MIs.push_back(&I);\n\n"; - std::stable_sort(Rules.begin(), Rules.end(), [&](const RuleMatcher &A, const RuleMatcher &B) { int ScoreA = RuleMatcherScores[A.getRuleID()]; @@ -3954,36 +3979,110 @@ } return false; }); - std::vector> StorageGroupMatcher; - - std::vector InputRules; - for (Matcher &Rule : Rules) - InputRules.push_back(&Rule); - - std::vector OptRules = - OptimizeMatchTable ? optimizeRules(InputRules, StorageGroupMatcher) - : InputRules; - - MatchTable Table(0); - for (Matcher *Rule : OptRules) - Rule->emit(Table); - Table << MatchTable::Opcode("GIM_Reject") << MatchTable::LineBreak; + OS << "bool " << Target.getName() + << "InstructionSelector::selectImpl(MachineInstr &I, CodeGenCoverage " + << "&CoverageInfo) const {\n" + << " MachineFunction &MF = *I.getParent()->getParent();\n" + << " MachineRegisterInfo &MRI = MF.getRegInfo();\n" + << " // FIXME: This should be computed on a per-function basis rather " + << "than per-insn.\n" + << " AvailableFunctionFeatures = computeAvailableFunctionFeatures(&STI" + << ", &MF);\n" + << " const PredicateBitset AvailableFeatures = getAvailableFeatures();\n" + << " NewMIVector OutMIs;\n" + << " State.MIs.clear();\n" + << " State.MIs.push_back(&I);\n\n" + << " if (executeMatchTable(*this, OutMIs, State, ISelInfo" + << ", getMatchTable(), TII, MRI, TRI, RBI, AvailableFeatures" + << ", CoverageInfo)) {\n" + << " return true;\n" + << " }\n\n" + << " return false;\n" + << "}\n\n" + + << "namespace {\n" + << "class " << Target.getName() << "InstructionSelectorTestgen\n" + << " : public llvm::InstructionSelectorTestgen {\n" + << "public:\n" + << " " << Target.getName() << "InstructionSelectorTestgen(const " + << Target.getName() << "InstructionSelector &ISel)\n" + << " : ISel(ISel) {}\n" + << " void " + << "generateTestCases(Module &M, MachineModuleInfo &MMI) const override;\n" + << " bool checkFeatures(unsigned FeatureBitsetID) const override;\n" + << " LLT getTypeObject(unsigned TypeObjectID) const override;\n" + << " const TargetInstrInfo &getTII() const override { return ISel.TII;" + << " }\n" + << " const TargetRegisterInfo &getTRI() const override { return ISel.TRI;" + << " }\n" + << " const RegisterBankInfo &getRBI() const override { return ISel.RBI;" + << " }\n" + << " const int64_t *getMatchTable() const override;\n" + << "private:\n" + << " const " << Target.getName() << "InstructionSelector &ISel;\n" + << "};\n" + << "} // end anonymous namespace\n\n" + + << "std::unique_ptr\n" + << Target.getName() << "InstructionSelector::getTestgen() const {\n" + << " return llvm::make_unique(*this);\n" + << "}\n\n" + + << "void " << Target.getName() + << "InstructionSelectorTestgen::generateTestCases(Module &M" + << ", MachineModuleInfo &MMI) const {\n" + << " MachineFunction *MF = MMI.getMachineFunction(*M.rbegin());\n" + << " ISel.AvailableFunctionFeatures = " + << "ISel.computeAvailableFunctionFeatures(&ISel.STI, MF);\n" + << " generateTestCasesImpl(M, MMI);\n" + << "}\n\n" + + << "bool " << Target.getName() + << "InstructionSelectorTestgen::checkFeatures(unsigned FeatureBitsetID) " + << "const {\n" + << " const PredicateBitset &ExpectedFeatures = " + << "ISel.ISelInfo.FeatureBitsets[FeatureBitsetID];\n" + << " const PredicateBitset &AvailableFeatures = " + << "ISel.getAvailableFeatures();\n" + << " return (ExpectedFeatures & AvailableFeatures) == ExpectedFeatures;\n" + << "}\n\n" + + << "LLT " << Target.getName() + << "InstructionSelectorTestgen::getTypeObject(unsigned TypeObjectID) " + << "const {\n" + << " return ISel.ISelInfo.TypeObjects[TypeObjectID];\n" + << "}\n\n"; + + OS << "const int64_t *" << Target.getName() + << "InstructionSelectorTestgen::getMatchTable() const {\n"; + if (OptimizeMatchTable || !GenerateCoverage) { + const MatchTable VanillaTable = buildMatchTable(Rules, false, true); + VanillaTable.emitDeclaration(OS); + OS << " return "; + VanillaTable.emitUse(OS); + } else + OS << " return ISel.getMatchTable()"; + OS << ";\n}\n\n"; + + const MatchTable Table = + buildMatchTable(Rules, OptimizeMatchTable, GenerateCoverage); + OS << "const int64_t *" << Target.getName() + << "InstructionSelector::getMatchTable() const {\n"; Table.emitDeclaration(OS); - OS << " if (executeMatchTable(*this, OutMIs, State, ISelInfo, "; + OS << " return "; Table.emitUse(OS); - OS << ", TII, MRI, TRI, RBI, AvailableFeatures, CoverageInfo)) {\n" - << " return true;\n" - << " }\n\n"; + OS << ";\n}\n"; - OS << " return false;\n" - << "}\n" - << "#endif // ifdef GET_GLOBALISEL_IMPL\n"; + OS << "#endif // ifdef GET_GLOBALISEL_IMPL\n\n"; OS << "#ifdef GET_GLOBALISEL_PREDICATES_DECL\n" << "PredicateBitset AvailableModuleFeatures;\n" << "mutable PredicateBitset AvailableFunctionFeatures;\n" << "PredicateBitset getAvailableFeatures() const {\n" + << " if (TestgenSetAllFeatures)\n" + << " return PredicateBitset().set();\n" << " return AvailableModuleFeatures | AvailableFunctionFeatures;\n" << "}\n" << "PredicateBitset\n" Index: utils/update_instruction_select_testgen_tests.sh =================================================================== --- /dev/null +++ utils/update_instruction_select_testgen_tests.sh @@ -0,0 +1,62 @@ +#!/bin/bash -e + +testgend="$1" +llc="$2" +triple="$3" +testgen_extra_args="${@:4}" + +if [ -z "$testgend" -o -z "$llc" -o -z "$triple" ]; then + echo "usage: $0 [extra llc args]" + exit 1 +fi + +selected="${testgend%-testgend.mir}-selected.mir" + +testgen_command="$llc -x mir -mtriple $triple -testgen-set-all-features \ + -run-pass instruction-select-testgen $testgen_extra_args \ + -verify-machineinstrs -simplify-mir -o -" + +text="$(echo | $testgen_command 2> /dev/null | perl -pe 's/\s+$/\n/')" + +test0_line_number=$(echo "$text" | grep -n 'name:\s*test_' \ + | head -n 1 | cut -d: -f 1) +if [ -z "$test0_line_number" ]; then + echo "Couldn't generate any tests by running the following testgen command:" + echo "echo | $testgen_command" + exit 2 +fi +tests=$(echo "$text" | tail +$((test0_line_number - 1))) + +echo "# NOTE: This test has been autogenerated by utils/$(basename $0)" > "$testgend" +echo "# RUN: llc -mtriple $triple -run-pass instruction-select-testgen \\" >> "$testgend" +if [ -n "$testgen_extra_args" ]; then + echo "# RUN: $testgen_extra_args \\" >> "$testgend" +fi +echo "# RUN: -testgen-set-all-features -verify-machineinstrs -simplify-mir %s \\" >> "$testgend" +echo "# RUN: -o - 2>&1 | FileCheck %s --check-prefix=TESTGEND" >> "$testgend" +echo "#" >> "$testgend" +echo "$tests" \ + | perl -pe 's/(test_rule\d+)(_id\d+)?_at_idx\d+/\1/' \ + | perl -pe 's/^(name:\s*test_rule\d+)/# TESTGEND-LABEL: \1/' \ + | perl -pe 's/^([^#\n])/# TESTGEND: \1/' \ + | perl -pe 's/^\n$/#\n/' >> "$testgend" + +echo "# RUN: llc -mtriple $triple -run-pass instruction-select \\" > "$selected" +echo "# RUN: -testgen-set-all-features -disable-gisel-legality-check \\" >> "$selected" +echo "# RUN: -verify-machineinstrs -simplify-mir %s -o - 2>&1 \\" >> "$selected" +echo "# RUN: | FileCheck %s --check-prefix=SELECTED" >> "$selected" +echo "#" >> "$selected" +echo "# Test if this file is in sync with the current state of the selector:" >> "$selected" +echo "$text" >> "$selected" + +$(dirname $0)/update_mir_test_checks.py --llc-binary="$llc" "$selected" + +sed -i '' -e "/^# Test if this file is in sync with the current state of the selector:$/ a\\ + # RUN: cat %s | FileCheck --check-prefix=TESTGEND \\\\\\ + # RUN: %S/$(basename $testgend) + " "$selected" + +sed -i '' -e "1 i\\ + # NOTE: This test has been autogenerated by utils/$(basename $0)\\ + # + " "$selected"