Index: include/llvm/CodeGen/GlobalISel/InstructionSelector.h =================================================================== --- include/llvm/CodeGen/GlobalISel/InstructionSelector.h +++ include/llvm/CodeGen/GlobalISel/InstructionSelector.h @@ -16,8 +16,12 @@ #ifndef LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H #define LLVM_CODEGEN_GLOBALISEL_INSTRUCTIONSELECTOR_H +#include + namespace llvm { class MachineInstr; +class MachineOperand; +class MachineRegisterInfo; class RegisterBankInfo; class TargetInstrInfo; class TargetRegisterInfo; @@ -56,6 +60,9 @@ const TargetInstrInfo &TII, const TargetRegisterInfo &TRI, const RegisterBankInfo &RBI) const; + + bool isOperandImmEqual(const MachineOperand &MO, int64_t Value, + const MachineRegisterInfo &MRI) const; }; } // End namespace llvm. Index: lib/CodeGen/GlobalISel/InstructionSelect.cpp =================================================================== --- lib/CodeGen/GlobalISel/InstructionSelect.cpp +++ lib/CodeGen/GlobalISel/InstructionSelect.cpp @@ -176,3 +176,20 @@ // FIXME: Should we accurately track changes? return true; } + +bool InstructionSelector::isOperandImmEqual( + const MachineOperand &MO, int64_t Value, + const MachineRegisterInfo &MRI) const { + // TODO: We should also test isImm() and isCImm() too but this isn't required + // until a DAGCombine equivalent is implemented. + + if (MO.isReg()) { + MachineInstr *Def = MRI.getVRegDef(MO.getReg()); + if (Def->getOpcode() != TargetOpcode::G_CONSTANT) + return false; + assert(Def->getOperand(1).isImm() && "G_CONSTANT values must be constants"); + return Def->getOperand(1).getImm() == Value; + } + + return false; +} Index: lib/Target/AArch64/AArch64InstructionSelector.cpp =================================================================== --- lib/Target/AArch64/AArch64InstructionSelector.cpp +++ lib/Target/AArch64/AArch64InstructionSelector.cpp @@ -634,9 +634,12 @@ // FIXME: Is going through int64_t always correct? ImmOp.ChangeToImmediate( ImmOp.getFPImm()->getValueAPF().bitcastToAPInt().getZExtValue()); - } else { + } else if (I.getOperand(1).isCImm()) { uint64_t Val = I.getOperand(1).getCImm()->getZExtValue(); I.getOperand(1).ChangeToImmediate(Val); + } else if (I.getOperand(1).isImm()) { + uint64_t Val = I.getOperand(1).getImm(); + I.getOperand(1).ChangeToImmediate(Val); } constrainSelectedInstRegOperands(I, TII, TRI, RBI); Index: test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-xor.mir =================================================================== --- /dev/null +++ test/CodeGen/AArch64/GlobalISel/arm64-instructionselect-xor.mir @@ -0,0 +1,166 @@ +# RUN: llc -O0 -mtriple=aarch64-apple-ios -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=IOS +# RUN: llc -O0 -mtriple=aarch64-linux-gnu -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=LINUX-DEFAULT +# RUN: llc -O0 -mtriple=aarch64-linux-gnu -relocation-model=pic -run-pass=instruction-select -verify-machineinstrs -global-isel %s -o - | FileCheck %s -check-prefix=CHECK -check-prefix=LINUX-PIC + +# Test the instruction selector. +# As we support more instructions, we need to split this up. + +--- | + target datalayout = "e-m:o-i64:64-i128:128-n32:64-S128" + + define void @xor_s32_gpr() { ret void } + define void @xor_s64_gpr() { ret void } + define void @xor_constant_n1_s32_gpr() { ret void } + define void @xor_constant_n1_s64_gpr() { ret void } + define void @xor_constant_n1_s32_gpr_2bb() { ret void } + +... + +--- +# Check that we select a 32-bit GPR G_XOR into EORWrr on GPR32. +# Also check that we constrain the register class of the COPY to GPR32. +# CHECK-LABEL: name: xor_s32_gpr +name: xor_s32_gpr +legalized: true +regBankSelected: true + +# CHECK: registers: +# CHECK-NEXT: - { id: 0, class: gpr32 } +# CHECK-NEXT: - { id: 1, class: gpr32 } +# CHECK-NEXT: - { id: 2, class: gpr32 } +registers: + - { id: 0, class: gpr } + - { id: 1, class: gpr } + - { id: 2, class: gpr } + +# CHECK: body: +# CHECK: %0 = COPY %w0 +# CHECK: %1 = COPY %w1 +# CHECK: %2 = EORWrr %0, %1 +body: | + bb.0: + liveins: %w0, %w1 + + %0(s32) = COPY %w0 + %1(s32) = COPY %w1 + %2(s32) = G_XOR %0, %1 +... + +--- +# Same as xor_s64_gpr, for 64-bit operations. +# CHECK-LABEL: name: xor_s64_gpr +name: xor_s64_gpr +legalized: true +regBankSelected: true + +# CHECK: registers: +# CHECK-NEXT: - { id: 0, class: gpr64 } +# CHECK-NEXT: - { id: 1, class: gpr64 } +# CHECK-NEXT: - { id: 2, class: gpr64 } +registers: + - { id: 0, class: gpr } + - { id: 1, class: gpr } + - { id: 2, class: gpr } + +# CHECK: body: +# CHECK: %0 = COPY %x0 +# CHECK: %1 = COPY %x1 +# CHECK: %2 = EORXrr %0, %1 +body: | + bb.0: + liveins: %x0, %x1 + + %0(s64) = COPY %x0 + %1(s64) = COPY %x1 + %2(s64) = G_XOR %0, %1 +... + +--- +# Check that we select a 32-bit GPR G_XOR into EORWrr on GPR32. +# Also check that we constrain the register class of the COPY to GPR32. +# CHECK-LABEL: name: xor_constant_n1_s32_gpr +name: xor_constant_n1_s32_gpr +legalized: true +regBankSelected: true + +# CHECK: registers: +# CHECK-NEXT: - { id: 0, class: gpr32 } +# CHECK-NEXT: - { id: 1, class: gpr32 } +# CHECK-NEXT: - { id: 2, class: gpr32 } +registers: + - { id: 0, class: gpr } + - { id: 1, class: gpr } + - { id: 2, class: gpr } + +# CHECK: body: +# CHECK: %0 = COPY %w0 +# CHECK: %2 = ORNWrr %wzr, %0 +body: | + bb.0: + liveins: %w0 + + %0(s32) = COPY %w0 + %1(s32) = G_CONSTANT -1 + %2(s32) = G_XOR %0, %1 +... + +--- +# Same as xor_constant_n1_s64_gpr, for 64-bit operations. +# CHECK-LABEL: name: xor_constant_n1_s64_gpr +name: xor_constant_n1_s64_gpr +legalized: true +regBankSelected: true + +# CHECK: registers: +# CHECK-NEXT: - { id: 0, class: gpr64 } +# CHECK-NEXT: - { id: 1, class: gpr64 } +# CHECK-NEXT: - { id: 2, class: gpr64 } +registers: + - { id: 0, class: gpr } + - { id: 1, class: gpr } + - { id: 2, class: gpr } + +# CHECK: body: +# CHECK: %0 = COPY %x0 +# CHECK: %2 = ORNXrr %xzr, %0 +body: | + bb.0: + liveins: %x0 + + %0(s64) = COPY %x0 + %1(s64) = G_CONSTANT -1 + %2(s64) = G_XOR %0, %1 +... + +--- +# Check that we can obtain constants from other basic blocks. +# CHECK-LABEL: name: xor_constant_n1_s32_gpr_2bb +name: xor_constant_n1_s32_gpr_2bb +legalized: true +regBankSelected: true + +# CHECK: registers: +# CHECK-NEXT: - { id: 0, class: gpr32 } +# CHECK-NEXT: - { id: 1, class: gpr32 } +# CHECK-NEXT: - { id: 2, class: gpr32 } +registers: + - { id: 0, class: gpr } + - { id: 1, class: gpr } + - { id: 2, class: gpr } + +# CHECK: body: +# CHECK: B %bb.1 +# CHECK: %0 = COPY %w0 +# CHECK: %2 = ORNWrr %wzr, %0 + +body: | + bb.0: + liveins: %w0, %w1 + successors: %bb.1 + %1(s32) = G_CONSTANT -1 + G_BR %bb.1 + bb.1: + %0(s32) = COPY %w0 + %2(s32) = G_XOR %0, %1 +... + Index: test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir =================================================================== --- test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir +++ test/CodeGen/AArch64/GlobalISel/arm64-instructionselect.mir @@ -18,9 +18,6 @@ define void @or_s64_gpr() { ret void } define void @or_v2s32_fpr() { ret void } - define void @xor_s32_gpr() { ret void } - define void @xor_s64_gpr() { ret void } - define void @and_s32_gpr() { ret void } define void @and_s64_gpr() { ret void } @@ -352,64 +349,6 @@ ... --- -# Same as add_s32_gpr, for G_XOR operations. -# CHECK-LABEL: name: xor_s32_gpr -name: xor_s32_gpr -legalized: true -regBankSelected: true - -# CHECK: registers: -# CHECK-NEXT: - { id: 0, class: gpr32 } -# CHECK-NEXT: - { id: 1, class: gpr32 } -# CHECK-NEXT: - { id: 2, class: gpr32 } -registers: - - { id: 0, class: gpr } - - { id: 1, class: gpr } - - { id: 2, class: gpr } - -# CHECK: body: -# CHECK: %0 = COPY %w0 -# CHECK: %1 = COPY %w1 -# CHECK: %2 = EORWrr %0, %1 -body: | - bb.0: - liveins: %w0, %w1 - - %0(s32) = COPY %w0 - %1(s32) = COPY %w1 - %2(s32) = G_XOR %0, %1 -... - ---- -# Same as add_s64_gpr, for G_XOR operations. -# CHECK-LABEL: name: xor_s64_gpr -name: xor_s64_gpr -legalized: true -regBankSelected: true - -# CHECK: registers: -# CHECK-NEXT: - { id: 0, class: gpr64 } -# CHECK-NEXT: - { id: 1, class: gpr64 } -# CHECK-NEXT: - { id: 2, class: gpr64 } -registers: - - { id: 0, class: gpr } - - { id: 1, class: gpr } - - { id: 2, class: gpr } - -# CHECK: body: -# CHECK: %0 = COPY %x0 -# CHECK: %1 = COPY %x1 -# CHECK: %2 = EORXrr %0, %1 -body: | - bb.0: - liveins: %x0, %x1 - - %0(s64) = COPY %x0 - %1(s64) = COPY %x1 - %2(s64) = G_XOR %0, %1 -... - ---- # Same as add_s32_gpr, for G_AND operations. # CHECK-LABEL: name: and_s32_gpr name: and_s32_gpr Index: test/TableGen/GlobalISelEmitter.td =================================================================== --- test/TableGen/GlobalISelEmitter.td +++ test/TableGen/GlobalISelEmitter.td @@ -7,7 +7,7 @@ def MyTargetISA : InstrInfo; def MyTarget : Target { let InstructionSet = MyTargetISA; } -def R0 : Register<"r0">; +def R0 : Register<"r0"> { let Namespace = "MyTarget"; } def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; class I Pat> @@ -23,34 +23,86 @@ // CHECK: bool MyTargetInstructionSelector::selectImpl(MachineInstr &I) const { // CHECK: const MachineRegisterInfo &MRI = I.getParent()->getParent()->getRegInfo(); - //===- Test a simple pattern with regclass operands. ----------------------===// -// CHECK: if ((I.getOpcode() == TargetOpcode::G_ADD) && -// CHECK-NEXT: ((/* Operand 0 */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) && +// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_ADD) && +// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) && // CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) && -// CHECK-NEXT: ((/* Operand 1 */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((/* src1 */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) && // CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) && -// CHECK-NEXT: ((/* Operand 2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((/* src2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) && // CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(2).getReg(), MRI, TRI)))))) { // CHECK-NEXT: // (add:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (ADD:i32 GPR32:i32:$src1, GPR32:i32:$src2) // CHECK-NEXT: I.setDesc(TII.get(MyTarget::ADD)); -// CHECK-NEXT: constrainSelectedInstRegOperands(I, TII, TRI, RBI); +// CHECK-NEXT: MachineInstr &NewI = I; +// CHECK: constrainSelectedInstRegOperands(NewI, TII, TRI, RBI); // CHECK-NEXT: return true; // CHECK-NEXT: } def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), [(set GPR32:$dst, (add GPR32:$src1, GPR32:$src2))]>; +// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_MUL) && +// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) && +// CHECK-NEXT: ((/* src1 */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) && +// CHECK-NEXT: ((/* src2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(2).getReg(), MRI, TRI)))))) { + +// CHECK-NEXT: // (mul:i32 GPR32:i32:$src1, GPR32:i32:$src2) => (MUL:i32 GPR32:i32:$src2, GPR32:i32:$src1) +// CHECK-NEXT: MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::MUL)); +// CHECK-NEXT: MIB.add(I.getOperand(0)/*dst*/); +// CHECK-NEXT: MIB.add(I.getOperand(2)/*src2*/); +// CHECK-NEXT: MIB.add(I.getOperand(1)/*src1*/); +// CHECK-NEXT: MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end()); +// CHECK-NEXT: I.eraseFromParent(); +// CHECK-NEXT: MachineInstr &NewI = *MIB; +// CHECK: constrainSelectedInstRegOperands(NewI, TII, TRI, RBI); +// CHECK-NEXT: return true; +// CHECK-NEXT: } + +def MUL : I<(outs GPR32:$dst), (ins GPR32:$src2, GPR32:$src1), + [(set GPR32:$dst, (mul GPR32:$src1, GPR32:$src2))]>; + +//===- Test a simple pattern with constant immediate operands. ------------===// +// +// This must precede the 3-register variants because constant immediates have +// priority over register banks. + +// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_XOR) && +// CHECK-NEXT: ((/* dst */ (MRI.getType(I.getOperand(0).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(0).getReg(), MRI, TRI))))) && +// CHECK-NEXT: ((/* Wm */ (MRI.getType(I.getOperand(1).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: ((&RBI.getRegBankFromRegClass(MyTarget::GPR32RegClass) == RBI.getRegBank(I.getOperand(1).getReg(), MRI, TRI))))) && +// CHECK-NEXT: ((/* Operand 2 */ (MRI.getType(I.getOperand(2).getReg()) == (LLT::scalar(32))) && +// CHECK-NEXT: (isOperandImmEqual(I.getOperand(2), -1, MRI))))) { + +// CHECK-NEXT: // (xor:i32 GPR32:i32:$Wm, -1:i32) => (ORN:i32 R0:i32, GPR32:i32:$Wm) +// CHECK-NEXT: MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, I.getDebugLoc(), TII.get(MyTarget::ORN)); +// CHECK-NEXT: MIB.add(I.getOperand(0)/*dst*/); +// CHECK-NEXT: MIB.addReg(MyTarget::R0); +// CHECK-NEXT: MIB.add(I.getOperand(1)/*Wm*/); +// CHECK-NEXT: MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end()); +// CHECK-NEXT: I.eraseFromParent(); +// CHECK-NEXT: MachineInstr &NewI = *MIB; +// CHECK: constrainSelectedInstRegOperands(NewI, TII, TRI, RBI); +// CHECK-NEXT: return true; +// CHECK-NEXT: } + +def ORN : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; +def : Pat<(not GPR32:$Wm), (ORN R0, GPR32:$Wm)>; + //===- Test a pattern with an MBB operand. --------------------------------===// -// CHECK: if ((I.getOpcode() == TargetOpcode::G_BR) && -// CHECK-NEXT: ((/* Operand 0 */ (I.getOperand(0).isMBB())))) { +// CHECK-LABEL: if ((I.getOpcode() == TargetOpcode::G_BR) && +// CHECK-NEXT: ((/* target */ (I.getOperand(0).isMBB())))) { // CHECK-NEXT: // (br (bb:Other):$target) => (BR (bb:Other):$target) // CHECK-NEXT: I.setDesc(TII.get(MyTarget::BR)); -// CHECK-NEXT: constrainSelectedInstRegOperands(I, TII, TRI, RBI); +// CHECK-NEXT: MachineInstr &NewI = I; +// CHECK: constrainSelectedInstRegOperands(NewI, TII, TRI, RBI); // CHECK-NEXT: return true; // CHECK-NEXT: } Index: utils/TableGen/GlobalISelEmitter.cpp =================================================================== --- utils/TableGen/GlobalISelEmitter.cpp +++ utils/TableGen/GlobalISelEmitter.cpp @@ -55,8 +55,6 @@ "in the GlobalISel selector"), cl::init(false)); -namespace { - //===- Helper functions ---------------------------------------------------===// /// Convert an MVT to an equivalent LLT if possible, or the invalid LLT() for @@ -134,8 +132,11 @@ /// the predicate when generating the matcher code. Kinds with higher priority /// must be tested first. /// - /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter. + /// The relative priority of OPM_LLT, OPM_RegBank, and OPM_MBB do not matter + /// but OPM_Int must have priority over OPM_RegBank since constant integers + /// are represented by a virtual register defined by a G_CONSTANT instruction. enum PredicateKind { + OPM_Int, OPM_LLT, OPM_RegBank, OPM_MBB, @@ -157,8 +158,8 @@ /// Compare the priority of this object and B. /// /// Returns true if this object is more important than B. - virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) { - return false; + virtual bool isHigherPriorityThan(const OperandPredicateMatcher &B) const { + return Kind < B.Kind; }; }; @@ -217,22 +218,53 @@ } }; +/// Generates code to check that an operand is a particular int. +class IntOperandMatcher : public OperandPredicateMatcher { +protected: + int64_t Value; + +public: + IntOperandMatcher(int64_t Value) + : OperandPredicateMatcher(OPM_Int), Value(Value) {} + + static bool classof(const OperandPredicateMatcher *P) { + return P->getKind() == OPM_Int; + } + + void emitCxxPredicateExpr(raw_ostream &OS, + const StringRef OperandExpr) const override { + OS << "isOperandImmEqual(" << OperandExpr << ", " << Value << ", MRI)"; + } +}; + /// Generates code to check that a set of predicates match for a particular /// operand. class OperandMatcher : public PredicateListMatcher { protected: unsigned OpIdx; + std::string SymbolicName; public: - OperandMatcher(unsigned OpIdx) : OpIdx(OpIdx) {} - std::string getOperandExpr(StringRef InsnVarName) const { + OperandMatcher(unsigned OpIdx, const std::string &SymbolicName) + : OpIdx(OpIdx), SymbolicName(SymbolicName) {} + + bool hasSymbolicName() const { return !SymbolicName.empty(); } + const StringRef getSymbolicName() const { return SymbolicName; } + unsigned getOperandIndex() const { return OpIdx; } + + std::string getOperandExpr(const StringRef InsnVarName) const { return (InsnVarName + ".getOperand(" + std::to_string(OpIdx) + ")").str(); } /// Emit a C++ expression that tests whether the instruction named in /// InsnVarName matches all the predicate and all the operands. - void emitCxxPredicateExpr(raw_ostream &OS, StringRef InsnVarName) const { - OS << "(/* Operand " << OpIdx << " */ "; + void emitCxxPredicateExpr(raw_ostream &OS, const StringRef InsnVarName) const { + OS << "(/* "; + if (SymbolicName.empty()) + OS << "Operand " << OpIdx; + else + OS << SymbolicName; + OS << " */ "; emitCxxPredicateListExpr(OS, getOperandExpr(InsnVarName)); OS << ")"; } @@ -276,6 +308,7 @@ PredicateKind Kind; public: + InstructionPredicateMatcher(PredicateKind Kind) : Kind(Kind) {} virtual ~InstructionPredicateMatcher() {} PredicateKind getKind() const { return Kind; } @@ -288,7 +321,7 @@ /// Compare the priority of this object and B. /// /// Returns true if this object is more important than B. - bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const { + virtual bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const { return Kind < B.Kind; }; }; @@ -299,7 +332,8 @@ const CodeGenInstruction *I; public: - InstructionOpcodeMatcher(const CodeGenInstruction *I) : I(I) {} + InstructionOpcodeMatcher(const CodeGenInstruction *I) + : InstructionPredicateMatcher(IPM_Opcode), I(I) {} static bool classof(const InstructionPredicateMatcher *P) { return P->getKind() == IPM_Opcode; @@ -313,8 +347,8 @@ /// Compare the priority of this object and B. /// - /// Returns true if is more important than B. - bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const { + /// Returns true if this object is more important than B. + bool isHigherPriorityThan(const InstructionPredicateMatcher &B) const override { if (InstructionPredicateMatcher::isHigherPriorityThan(B)) return true; if (B.InstructionPredicateMatcher::isHigherPriorityThan(*this)) @@ -340,15 +374,41 @@ class InstructionMatcher : public PredicateListMatcher { protected: - std::vector Operands; + typedef std::vector OperandVec; + + /// The operands to match. All rendered operands must be present even if the + /// condition is always true. + OperandVec Operands; public: /// Add an operand to the matcher. - OperandMatcher &addOperand(unsigned OpIdx) { - Operands.emplace_back(OpIdx); + OperandMatcher &addOperand(unsigned OpIdx, const std::string &SymbolicName) { + Operands.emplace_back(OpIdx, SymbolicName); return Operands.back(); } + const OperandMatcher &getOperand(const StringRef SymbolicName) const { + assert(!SymbolicName.empty() && "Cannot lookup unnamed operand"); + const auto &I = std::find_if(Operands.begin(), Operands.end(), + [&SymbolicName](const OperandMatcher &X) { + return X.getSymbolicName() == SymbolicName; + }); + if (I != Operands.end()) + return *I; + llvm_unreachable("Failed to lookup operand"); + } + + unsigned getNumOperands() const { return Operands.size(); } + OperandVec::const_iterator operands_begin() const { + return Operands.begin(); + } + OperandVec::const_iterator operands_end() const { + return Operands.end(); + } + iterator_range operands() const { + return make_range(operands_begin(), operands_end()); + } + /// Emit a C++ expression that tests whether the instruction named in /// InsnVarName matches all the predicates and all the operands. void emitCxxPredicateExpr(raw_ostream &OS, StringRef InsnVarName) const { @@ -390,6 +450,75 @@ //===- Actions ------------------------------------------------------------===// +namespace { +class OperandRenderer { +public: + enum RendererKind { OR_Copy, OR_Register }; + +protected: + RendererKind Kind; + +public: + OperandRenderer(RendererKind Kind) : Kind(Kind) {} + virtual ~OperandRenderer() {} + + RendererKind getKind() const { return Kind; } + + virtual void emitCxxRenderStmts(raw_ostream &OS) const = 0; +}; + +/// A CopyRenderer emits code to copy a single operand from an existing +/// instruction to the one being built. +class CopyRenderer : public OperandRenderer { +protected: + /// The matcher for the instruction that this operand is copied from. + /// This provides the facility for looking up an a operand by it's name so + /// that it can be used as a source for the instruction being built. + const InstructionMatcher &Matched; + /// The name of the instruction to copy from. + const StringRef InsnVarName; + /// The name of the operand. + const StringRef SymbolicName; + +public: + CopyRenderer(const InstructionMatcher &Matched, const StringRef InsnVarName, + const StringRef SymbolicName) + : OperandRenderer(OR_Copy), Matched(Matched), InsnVarName(InsnVarName), + SymbolicName(SymbolicName) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Copy; + } + + const StringRef getSymbolicName() const { return SymbolicName; } + + void emitCxxRenderStmts(raw_ostream &OS) const override { + std::string OperandExpr = + Matched.getOperand(SymbolicName).getOperandExpr(InsnVarName); + OS << " MIB.add(" << OperandExpr << "/*" << SymbolicName << "*/);\n"; + } +}; + +/// Adds a specific physical register to the instruction being built. +/// This is typically useful for WZR/XZR on AArch64. +class AddRegisterRenderer : public OperandRenderer { +protected: + const Record *RegisterDef; + +public: + AddRegisterRenderer(const Record *RegisterDef) + : OperandRenderer(OR_Register), RegisterDef(RegisterDef) {} + + static bool classof(const OperandRenderer *R) { + return R->getKind() == OR_Register; + } + + void emitCxxRenderStmts(raw_ostream &OS) const override { + OS << " MIB.addReg(" << RegisterDef->getValueAsString("Namespace") + << "::" << RegisterDef->getName() << ");\n"; + } +}; + /// An action taken when all Matcher predicates succeeded for a parent rule. /// /// Typical actions include: @@ -398,7 +527,14 @@ class MatchAction { public: virtual ~MatchAction() {} - virtual void emitCxxActionStmts(raw_ostream &OS) const = 0; + + /// Emit the C++ statements to implement the action. + /// + /// \param InsnVarName If given, it's an instruction to recycle. The + /// requirements on the instruction vary from action to + /// action. + virtual void emitCxxActionStmts(raw_ostream &OS, + const StringRef InsnVarName) const = 0; }; /// Generates a comment describing the matched rule being acted upon. @@ -409,23 +545,65 @@ public: DebugCommentAction(const PatternToMatch &P) : P(P) {} - virtual void emitCxxActionStmts(raw_ostream &OS) const { + void emitCxxActionStmts(raw_ostream &OS, + const StringRef InsnVarName) const override { OS << "// " << *P.getSrcPattern() << " => " << *P.getDstPattern(); } }; -/// Generates code to set the opcode (really, the MCInstrDesc) of a matched -/// instruction to a given Instruction. -class MutateOpcodeAction : public MatchAction { +/// Generates code to build an instruction or mutate an existing instruction +/// into the desired instruction when this is possible. +class BuildMIAction : public MatchAction { private: const CodeGenInstruction *I; + const InstructionMatcher &Matched; + std::vector> OperandRenderers; + + /// True if the instruction can be built solely by mutating the opcode. + bool canMutate() const { + for (const auto &Renderer : enumerate(OperandRenderers)) { + if (const auto *Copy = dyn_cast(&*Renderer.Value)) { + if (Matched.getOperand(Copy->getSymbolicName()).getOperandIndex() != + Renderer.Index) + return false; + } else + return false; + } + + return true; + } public: - MutateOpcodeAction(const CodeGenInstruction *I) : I(I) {} + BuildMIAction(const CodeGenInstruction *I, const InstructionMatcher &Matched) + : I(I), Matched(Matched) {} + + template + Kind &addRenderer(Args&&... args) { + OperandRenderers.emplace_back( + llvm::make_unique(std::forward(args)...)); + return *static_cast(OperandRenderers.back().get()); + } + + virtual void emitCxxActionStmts(raw_ostream &OS, + const StringRef InsnVarName) const { + if (canMutate()) { + OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName() + << "));\n"; + OS << " MachineInstr &NewI = I;\n"; + return; + } - virtual void emitCxxActionStmts(raw_ostream &OS) const { - OS << "I.setDesc(TII.get(" << I->Namespace << "::" << I->TheDef->getName() - << "));"; + // TODO: Simple permutation looks like it could be almost as common as + // mutation due to commutative operations. + + OS << "MachineInstrBuilder MIB = BuildMI(*I.getParent(), I, " + "I.getDebugLoc(), TII.get(" + << I->Namespace << "::" << I->TheDef->getName() << "));\n"; + for (const auto &Renderer : OperandRenderers) + Renderer->emitCxxRenderStmts(OS); + OS << " MIB.setMemRefs(I.memoperands_begin(), I.memoperands_end());\n"; + OS << " " << InsnVarName << ".eraseFromParent();\n"; + OS << " MachineInstr &NewI = *MIB;\n"; } }; @@ -475,11 +653,11 @@ for (const auto &MA : Actions) { OS << " "; - MA->emitCxxActionStmts(OS); + MA->emitCxxActionStmts(OS, "I"); OS << "\n"; } - OS << " constrainSelectedInstRegOperands(I, TII, TRI, RBI);\n"; + OS << " constrainSelectedInstRegOperands(NewI, TII, TRI, RBI);\n"; OS << " return true;\n"; OS << " }\n\n"; } @@ -588,7 +766,7 @@ // The operators look good: match the opcode and mutate it to the new one. InstructionMatcher &InsnMatcher = M.addInstructionMatcher(); InsnMatcher.addPredicate(&SrcGI); - M.addAction(&DstI); + auto &DstMIBuilder = M.addAction(&DstI, InsnMatcher); // Next, analyze the children, only accepting patterns that don't require // any change to operands. @@ -602,7 +780,8 @@ return failedImport("Src pattern results and dst MI defs are different"); for (const EEVT::TypeSet &Ty : Src->getExtTypes()) { - Record *DstIOpRec = DstI.Operands[OpIdx].Rec; + const auto &DstIOperand = DstI.Operands[OpIdx]; + Record *DstIOpRec = DstIOperand.Rec; if (!DstIOpRec->isSubClassOf("RegisterClass")) return failedImport("Dst MI def isn't a register class"); @@ -610,48 +789,35 @@ if (!OpTyOrNone) return failedImport("Dst operand has an unsupported type"); - OperandMatcher &OM = InsnMatcher.addOperand(OpIdx); + OperandMatcher &OM = InsnMatcher.addOperand(OpIdx, DstIOperand.Name); OM.addPredicate(*OpTyOrNone); OM.addPredicate( Target.getRegisterClass(DstIOpRec)); + DstMIBuilder.addRenderer(InsnMatcher, "I", DstIOperand.Name); ++OpIdx; } // Finally match the used operands (i.e., the children of the root operator). for (unsigned i = 0, e = Src->getNumChildren(); i != e; ++i) { auto *SrcChild = Src->getChild(i); - auto *DstChild = Dst->getChild(i); - // Patterns can reorder operands. Ignore those for now. - if (SrcChild->getName() != DstChild->getName()) - return failedImport("Src/dst pattern children not in same order"); + OperandMatcher &OM = InsnMatcher.addOperand(OpIdx++, SrcChild->getName()); // The only non-leaf child we accept is 'bb': it's an operator because // BasicBlockSDNode isn't inline, but in MI it's just another operand. if (!SrcChild->isLeaf()) { - if (DstChild->isLeaf() || - SrcChild->getOperator() != DstChild->getOperator()) - return failedImport("Src/dst pattern child operator mismatch"); - if (SrcChild->getOperator()->isSubClassOf("SDNode")) { auto &ChildSDNI = CGP.getSDNodeInfo(SrcChild->getOperator()); if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") { - InsnMatcher.addOperand(OpIdx++).addPredicate(); + OM.addPredicate(); continue; } } - return failedImport("Src pattern child isn't a leaf node"); + return failedImport("Src pattern child isn't a leaf node or an MBB"); } - if (SrcChild->getLeafValue() != DstChild->getLeafValue()) - return failedImport("Src/dst pattern child leaf mismatch"); - - // Otherwise, we're looking for a bog-standard RegisterClass operand. if (SrcChild->hasAnyPredicate()) return failedImport("Src pattern child has predicate"); - auto *ChildRec = cast(SrcChild->getLeafValue())->getDef(); - if (!ChildRec->isSubClassOf("RegisterClass")) - return failedImport("Src pattern child isn't a RegisterClass"); ArrayRef ChildTypes = SrcChild->getExtTypes(); if (ChildTypes.size() != 1) @@ -660,12 +826,77 @@ auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete()); if (!OpTyOrNone) return failedImport("Src operand has an unsupported type"); - - OperandMatcher &OM = InsnMatcher.addOperand(OpIdx); OM.addPredicate(*OpTyOrNone); - OM.addPredicate( - Target.getRegisterClass(ChildRec)); - ++OpIdx; + + if (auto *ChildInt = dyn_cast(SrcChild->getLeafValue())) { + OM.addPredicate(ChildInt->getValue()); + continue; + } + + if (auto *ChildDefInit = dyn_cast(SrcChild->getLeafValue())) { + auto *ChildRec = ChildDefInit->getDef(); + + // Otherwise, we're looking for a bog-standard RegisterClass operand. + if (!ChildRec->isSubClassOf("RegisterClass")) + return failedImport("Src pattern child isn't a RegisterClass"); + + OM.addPredicate( + Target.getRegisterClass(ChildRec)); + continue; + } + + return failedImport("Src pattern child is an unsupported kind"); + } + + // Finally render the used operands (i.e., the children of the root operator). + for (unsigned i = 0, e = Dst->getNumChildren(); i != e; ++i) { + auto *DstChild = Dst->getChild(i); + + // The only non-leaf child we accept is 'bb': it's an operator because + // BasicBlockSDNode isn't inline, but in MI it's just another operand. + if (!DstChild->isLeaf()) { + if (DstChild->getOperator()->isSubClassOf("SDNode")) { + auto &ChildSDNI = CGP.getSDNodeInfo(DstChild->getOperator()); + if (ChildSDNI.getSDClassName() == "BasicBlockSDNode") { + DstMIBuilder.addRenderer(InsnMatcher, "I", + DstChild->getName()); + continue; + } + } + return failedImport("Dst pattern child isn't a leaf node or an MBB"); + } + + // Otherwise, we're looking for a bog-standard RegisterClass operand. + if (DstChild->hasAnyPredicate()) + return failedImport("Dst pattern child has predicate"); + + if (auto *ChildDefInit = dyn_cast(DstChild->getLeafValue())) { + auto *ChildRec = ChildDefInit->getDef(); + + ArrayRef ChildTypes = DstChild->getExtTypes(); + if (ChildTypes.size() != 1) + return failedImport("Dst pattern child has multiple results"); + + auto OpTyOrNone = MVTToLLT(ChildTypes.front().getConcrete()); + if (!OpTyOrNone) + return failedImport("Dst operand has an unsupported type"); + + if (ChildRec->isSubClassOf("Register")) { + DstMIBuilder.addRenderer(ChildRec); + continue; + } + + if (ChildRec->isSubClassOf("RegisterClass")) { + DstMIBuilder.addRenderer(InsnMatcher, "I", + DstChild->getName()); + continue; + } + + return failedImport( + "Dst pattern child def is an unsupported tablegen class"); + } + + return failedImport("Src pattern child is an unsupported kind"); } // We're done with this pattern! It's eligible for GISel emission; return it. @@ -706,8 +937,8 @@ Rules.push_back(std::move(MatcherOrErr.get())); } - std::sort(Rules.begin(), Rules.end(), - [](const RuleMatcher &A, const RuleMatcher &B) { + std::stable_sort(Rules.begin(), Rules.end(), + [&](const RuleMatcher &A, const RuleMatcher &B) { if (A.isHigherPriorityThan(B)) { assert(!B.isHigherPriorityThan(A) && "Cannot be more important " "and less important at "