Index: llvm/include/llvm/CodeGen/GlobalISel/CombinerInfo.h =================================================================== --- llvm/include/llvm/CodeGen/GlobalISel/CombinerInfo.h +++ llvm/include/llvm/CodeGen/GlobalISel/CombinerInfo.h @@ -17,6 +17,10 @@ namespace llvm { class GISelChangeObserver; +template +class DenseMap; class LegalizerInfo; class MachineInstr; class MachineIRBuilder; @@ -63,7 +67,8 @@ /// /// However, it is important to report instruction modification and this is /// not automatic. - virtual bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + virtual bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const = 0; }; } // namespace llvm Index: llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h =================================================================== --- llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h +++ llvm/include/llvm/CodeGen/GlobalISel/GISelWorkList.h @@ -111,6 +111,11 @@ WorklistMap.erase(I); return I; } + + bool contains(const MachineInstr *I) { + auto It = WorklistMap.find(I); + return It != WorklistMap.end(); + } }; } // end namespace llvm. Index: llvm/lib/CodeGen/GlobalISel/Combiner.cpp =================================================================== --- llvm/lib/CodeGen/GlobalISel/Combiner.cpp +++ llvm/lib/CodeGen/GlobalISel/Combiner.cpp @@ -51,6 +51,7 @@ class WorkListMaintainer : public GISelChangeObserver { using WorkListTy = GISelWorkList<512>; WorkListTy &WorkList; + SmallVectorImpl &ChangedInstrs; /// The instructions that have been created but we want to report once they /// have their operands. This is only maintained if debug output is requested. #ifndef NDEBUG @@ -58,7 +59,9 @@ #endif public: - WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {} + WorkListMaintainer(WorkListTy &WorkList, + SmallVectorImpl &ChangedInstrs) + : WorkList(WorkList), ChangedInstrs(ChangedInstrs) {} virtual ~WorkListMaintainer() = default; void erasingInstr(MachineInstr &MI) override { @@ -67,16 +70,19 @@ } void createdInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); - WorkList.insert(&MI); + //WorkList.insert(&MI); + ChangedInstrs.push_back(&MI); LLVM_DEBUG(CreatedInstrs.insert(&MI)); } void changingInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); - WorkList.insert(&MI); + //WorkList.insert(&MI); + ChangedInstrs.push_back(&MI); } void changedInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); - WorkList.insert(&MI); + //WorkList.insert(&MI); + ChangedInstrs.push_back(&MI); } void reportFullyCreatedInstrs() { @@ -88,7 +94,41 @@ LLVM_DEBUG(CreatedInstrs.clear()); } }; -} + +// For each changed/created node, the TreeRepairer adds the path from the node +// to the root of the tree by following the use edges. For these nodes, the +// match sets in the underlying combiner may be invalid, and adding them to the +// WorkList ensures that the match sets are recalculated in the correct order. +class TreeRepairer { + MachineRegisterInfo *MRI; + using WorkListTy = GISelWorkList<512>; + WorkListTy &WorkList; + + void add(MachineInstr *MI) { + if (WorkList.contains(MI)) + return; + for (auto Op : MI->operands()) { + if (!Op.isReg() || !Op.isDef()) + continue; + for (auto &UseMI : MRI->use_nodbg_instructions(Op.getReg())) + add(&UseMI); + } + WorkList.insert(MI); + } + +public: + TreeRepairer(MachineRegisterInfo *MRI, WorkListTy &WorkList) + : MRI(MRI), WorkList(WorkList) {} + + void run(SmallVectorImpl &ChangedInstrs) { + for (MachineInstr *MI : ChangedInstrs) { + LLVM_DEBUG(dbgs() << "Adding path for: "; MI->print(dbgs())); + add(MI); + } + ChangedInstrs.clear(); + } +}; +} // namespace Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC) : CInfo(Info), TPC(TPC) { @@ -117,6 +157,7 @@ bool MFChanged = false; bool Changed; MachineIRBuilder &B = *Builder; + DenseMap MatchSets; do { // Collect all instructions. Do a post order traversal for basic blocks and @@ -124,11 +165,13 @@ // down RPOT. Changed = false; GISelWorkList<512> WorkList; - WorkListMaintainer Observer(WorkList); + SmallVector ChangedInstrs; + WorkListMaintainer Observer(WorkList, ChangedInstrs); GISelObserverWrapper WrapperObserver(&Observer); if (CSEInfo) WrapperObserver.addObserver(CSEInfo); RAIIDelegateInstaller DelInstall(MF, &WrapperObserver); + TreeRepairer Repairer(MRI, WorkList); for (MachineBasicBlock *MBB : post_order(&MF)) { for (MachineInstr &CurMI : llvm::make_early_inc_range(llvm::reverse(*MBB))) { @@ -143,12 +186,14 @@ } } WorkList.finalize(); + MatchSets.reserve(WorkList.size()); // Main Loop. Process the instructions here. while (!WorkList.empty()) { MachineInstr *CurrInst = WorkList.pop_back_val(); LLVM_DEBUG(dbgs() << "\nTry combining " << *CurrInst;); - Changed |= CInfo.combine(WrapperObserver, *CurrInst, B); + Changed |= CInfo.combine(MatchSets, WrapperObserver, *CurrInst, B); Observer.reportFullyCreatedInstrs(); + Repairer.run(ChangedInstrs); } MFChanged |= Changed; } while (Changed); Index: llvm/lib/Target/AArch64/GISel/AArch64O0PreLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/AArch64/GISel/AArch64O0PreLegalizerCombiner.cpp +++ llvm/lib/Target/AArch64/GISel/AArch64O0PreLegalizerCombiner.cpp @@ -66,17 +66,19 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AArch64O0PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, - MachineInstr &MI, - MachineIRBuilder &B) const { +bool AArch64O0PreLegalizerCombinerInfo::combine( + DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, + MachineIRBuilder &B) const { CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ true, KB, MDT); AArch64GenO0PreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper); - if (Generated.tryCombineAll(Observer, MI, B)) + if (Generated.tryCombineAll(MatchSets, Observer, MI, B)) return true; unsigned Opc = MI.getOpcode(); Index: llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp +++ llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerCombiner.cpp @@ -355,18 +355,20 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AArch64PostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, - MachineInstr &MI, - MachineIRBuilder &B) const { +bool AArch64PostLegalizerCombinerInfo::combine( + DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, + MachineIRBuilder &B) const { const auto *LI = MI.getParent()->getParent()->getSubtarget().getLegalizerInfo(); CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ false, KB, MDT, LI); AArch64GenPostLegalizerCombinerHelper Generated(GeneratedRuleCfg); - return Generated.tryCombineAll(Observer, MI, B, Helper); + return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper); } #define AARCH64POSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP Index: llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerLowering.cpp =================================================================== --- llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerLowering.cpp +++ llvm/lib/Target/AArch64/GISel/AArch64PostLegalizerLowering.cpp @@ -1069,16 +1069,18 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AArch64PostLegalizerLoweringInfo::combine(GISelChangeObserver &Observer, - MachineInstr &MI, - MachineIRBuilder &B) const { +bool AArch64PostLegalizerLoweringInfo::combine( + DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, + MachineIRBuilder &B) const { CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false); AArch64GenPostLegalizerLoweringHelper Generated(GeneratedRuleCfg); - return Generated.tryCombineAll(Observer, MI, B, Helper); + return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper); } #define AARCH64POSTLEGALIZERLOWERINGHELPER_GENCOMBINERHELPER_CPP Index: llvm/lib/Target/AArch64/GISel/AArch64PreLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/AArch64/GISel/AArch64PreLegalizerCombiner.cpp +++ llvm/lib/Target/AArch64/GISel/AArch64PreLegalizerCombiner.cpp @@ -370,18 +370,20 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AArch64PreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, - MachineInstr &MI, - MachineIRBuilder &B) const { +bool AArch64PreLegalizerCombinerInfo::combine( + DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, + MachineIRBuilder &B) const { const auto *LI = MI.getMF()->getSubtarget().getLegalizerInfo(); CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ true, KB, MDT, LI); AArch64GenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper); - if (Generated.tryCombineAll(Observer, MI, B)) + if (Generated.tryCombineAll(MatchSets, Observer, MI, B)) return true; unsigned Opc = MI.getOpcode(); Index: llvm/lib/Target/AMDGPU/AMDGPUPostLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/AMDGPU/AMDGPUPostLegalizerCombiner.cpp +++ llvm/lib/Target/AMDGPU/AMDGPUPostLegalizerCombiner.cpp @@ -346,11 +346,13 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AMDGPUPostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, +bool AMDGPUPostLegalizerCombinerInfo::combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const { AMDGPUCombinerHelper Helper(Observer, B, /*IsPreLegalize*/ false, KB, MDT, @@ -359,7 +361,7 @@ AMDGPUGenPostLegalizerCombinerHelper Generated( GeneratedRuleCfg, Helper, PostLegalizerHelper, Subtarget); - if (Generated.tryCombineAll(Observer, MI, B)) + if (Generated.tryCombineAll(MatchSets, Observer, MI, B)) return true; switch (MI.getOpcode()) { Index: llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp +++ llvm/lib/Target/AMDGPU/AMDGPUPreLegalizerCombiner.cpp @@ -191,11 +191,13 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AMDGPUPreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, +bool AMDGPUPreLegalizerCombinerInfo::combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const { const auto *LI = MI.getMF()->getSubtarget().getLegalizerInfo(); @@ -204,7 +206,7 @@ AMDGPUGenPreLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper, PreLegalizerHelper); - if (Generated.tryCombineAll(Observer, MI, B)) + if (Generated.tryCombineAll(MatchSets, Observer, MI, B)) return true; switch (MI.getOpcode()) { Index: llvm/lib/Target/AMDGPU/AMDGPURegBankCombiner.cpp =================================================================== --- llvm/lib/Target/AMDGPU/AMDGPURegBankCombiner.cpp +++ llvm/lib/Target/AMDGPU/AMDGPURegBankCombiner.cpp @@ -392,11 +392,13 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool AMDGPURegBankCombinerInfo::combine(GISelChangeObserver &Observer, +bool AMDGPURegBankCombinerInfo::combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const { CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false, KB, MDT); @@ -404,7 +406,7 @@ AMDGPUGenRegBankCombinerHelper Generated(GeneratedRuleCfg, Helper, RegBankHelper); - if (Generated.tryCombineAll(Observer, MI, B)) + if (Generated.tryCombineAll(MatchSets, Observer, MI, B)) return true; return false; Index: llvm/lib/Target/Mips/MipsPostLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/Mips/MipsPostLegalizerCombiner.cpp +++ llvm/lib/Target/Mips/MipsPostLegalizerCombiner.cpp @@ -53,18 +53,20 @@ report_fatal_error("Invalid rule identifier"); } - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool MipsPostLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, +bool MipsPostLegalizerCombinerInfo::combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const { CombinerHelper Helper(Observer, B, /* IsPreLegalize*/ false, KB, /*DominatorTree*/ nullptr, LInfo); MipsGenPostLegalizerCombinerHelper Generated(GeneratedRuleCfg, Helper); - return Generated.tryCombineAll(Observer, MI, B, Helper); + return Generated.tryCombineAll(MatchSets, Observer, MI, B, Helper); } #define MIPSPOSTLEGALIZERCOMBINERHELPER_GENCOMBINERHELPER_CPP Index: llvm/lib/Target/Mips/MipsPreLegalizerCombiner.cpp =================================================================== --- llvm/lib/Target/Mips/MipsPreLegalizerCombiner.cpp +++ llvm/lib/Target/Mips/MipsPreLegalizerCombiner.cpp @@ -31,11 +31,13 @@ : CombinerInfo(/*AllowIllegalOps*/ true, /*ShouldLegalizeIllegal*/ false, /*LegalizerInfo*/ nullptr, /*EnableOpt*/ false, /*EnableOptSize*/ false, /*EnableMinSize*/ false) {} - bool combine(GISelChangeObserver &Observer, MachineInstr &MI, + bool combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const override; }; -bool MipsPreLegalizerCombinerInfo::combine(GISelChangeObserver &Observer, +bool MipsPreLegalizerCombinerInfo::combine(DenseMap &MatchSets, + GISelChangeObserver &Observer, MachineInstr &MI, MachineIRBuilder &B) const { CombinerHelper Helper(Observer, B, /*IsPreLegalize*/ true); Index: llvm/test/TableGen/GICombinerEmitter/match-tree-automaton-1.td =================================================================== --- /dev/null +++ llvm/test/TableGen/GICombinerEmitter/match-tree-automaton-1.td @@ -0,0 +1,105 @@ +// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ +// RUN: -combiners=MyCombinerHelper -gicombiner-stop-after-build %s \ +// RUN: -o %t.inc | FileCheck %s + +// This is the example from the paper of Chase. Please note the values in the +// lookup table are not exactly the same. The encoding of the match sets depends +// on the order of calculation, which is not described. However, it is easy to +// see that the structure is the same, and a bijective function from the values +// in the paper to the values here in the test case can be easily defined. + +include "llvm/Target/Target.td" +include "llvm/Target/GlobalISel/Combine.td" + +def MyTargetISA : InstrInfo; +def MyTarget : Target { let InstructionSet = MyTargetISA; } + +def dummy; + +def R0 : Register<"r0"> { let Namespace = "MyTarget"; } +def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; +class I Pat> + : Instruction { + let Namespace = "MyTarget"; + let OutOperandList = OOps; + let InOperandList = IOps; + let Pattern = Pat; +} +def A : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; +def B : I<(outs GPR32:$dst), (ins), []>; +def C : I<(outs GPR32:$dst), (ins), []>; + +def Rule0 : GICombineRule< + (defs root:$d), + (match (B $t2), + (B $t3), + (A $t1, $t3, $s1), + (A $d, $t1, $t2)), + (apply [{ APPLY }])>; + +def Rule1 : GICombineRule< + (defs root:$d), + (match (C $t2), + (C $t3), + (A $t1, $s1, $t3), + (A $d, $t1, $t2)), + (apply [{ APPLY }])>; + +def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ + Rule0, + Rule1 +]>; + +// CHECK: PatternForest: # PF +// CHECK-DAG: - 1: B [ ] +// CHECK-DAG: - 6: A [ 5, 4 ] +// CHECK-DAG: - 3: A [ 2, 1 ] +// CHECK-DAG: - 4: C [ ] +// CHECK-DAG: - 2: A [ 1, 0 ] +// CHECK-DAG: - 0: * +// CHECK-DAG: - 5: A [ 0, 4 ] +// CHECK-NEXT:MatchSets: # R +// CHECK-NEXT: - 0: [ 0 ] +// CHECK-NEXT: - 1: [ 0, 1 ] +// CHECK-NEXT: - 2: [ 0, 2 ] +// CHECK-NEXT: - 3: [ 0, 3 ] +// CHECK-NEXT: - 4: [ 0, 4 ] +// CHECK-NEXT: - 5: [ 0, 5 ] +// CHECK-NEXT: - 6: [ 0, 2, 5 ] +// CHECK-NEXT: - 7: [ 0, 5, 6 ] +// CHECK-NEXT:ChildPatternSets: # P_A +// CHECK-NEXT: A: +// CHECK-NEXT: - 0: [ 0, 1, 2, 5 ] +// CHECK-NEXT: - 1: [ 0, 1, 4 ] +// CHECK-NEXT: B: +// CHECK-NEXT: C: +// CHECK-NEXT:RepresenterSets: # S_A +// CHECK-NEXT: A: +// CHECK-NEXT: - 0: +// CHECK-NEXT: - 0: [ 0 ] +// CHECK-NEXT: - 1: [ 0, 1 ] +// CHECK-NEXT: - 2: [ 0, 2 ] +// CHECK-NEXT: - 3: [ 0, 5 ] +// CHECK-NEXT: - 4: [ 0, 2, 5 ] +// CHECK-NEXT: - 1: +// CHECK-NEXT: - 0: [ 0 ] +// CHECK-NEXT: - 1: [ 0, 1 ] +// CHECK-NEXT: - 2: [ 0, 4 ] +// CHECK-NEXT: B: +// CHECK-NEXT: C: +// CHECK-NEXT:LeafTables: +// CHECK-NEXT: B: 1 +// CHECK-NEXT: C: 4 +// CHECK-NEXT:Tables: +// CHECK-NEXT: A: +// CHECK-NEXT: C: [ +// CHECK-NEXT: [ 0, 1, 2, 0, 0, 3, 4, 3 ], +// CHECK-NEXT: [ 0, 1, 0, 0, 2, 0, 0, 0 ] +// CHECK-NEXT: ] +// CHECK-NEXT: T: [ +// CHECK-NEXT: [ 0, 0, 5 ], +// CHECK-NEXT: [ 2, 2, 6 ], +// CHECK-NEXT: [ 0, 3, 5 ], +// CHECK-NEXT: [ 0, 0, 7 ], +// CHECK-NEXT: [ 0, 3, 7 ] +// CHECK-NEXT: ] Index: llvm/test/TableGen/GICombinerEmitter/match-tree.td =================================================================== --- llvm/test/TableGen/GICombinerEmitter/match-tree.td +++ /dev/null @@ -1,315 +0,0 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombinerHelper -gicombiner-stop-after-build %s \ -// RUN: -o %t.inc | FileCheck %s -// -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombinerHelper %s | \ -// RUN: FileCheck --check-prefix=CODE %s - -include "llvm/Target/Target.td" -include "llvm/Target/GlobalISel/Combine.td" - -def MyTargetISA : InstrInfo; -def MyTarget : Target { let InstructionSet = MyTargetISA; } - -def dummy; - -def R0 : Register<"r0"> { let Namespace = "MyTarget"; } -def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; -class I Pat> - : Instruction { - let Namespace = "MyTarget"; - let OutOperandList = OOps; - let InOperandList = IOps; - let Pattern = Pat; -} -def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def ADD : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def SUB : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def MUL : I<(outs GPR32:$dst), (ins GPR32:$src1, GPR32:$src2), []>; -def TRUNC : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def SEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def ZEXT : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def ICMP : I<(outs GPR32:$dst), (ins GPR32:$tst, GPR32:$src1, GPR32:$src2), []>; - -def HasFoo : Predicate<"Subtarget->hasFoo()">; -def HasAnswerToEverything : Predicate<"Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42">; - -def Rule0 : GICombineRule< - (defs root:$d), - (match (MUL $t, $s1, $s2), - (SUB $d, $t, $s3)), - (apply [{ APPLY }])>; - -def Rule1 : GICombineRule< - (defs root:$d), - (match (MOV $s1, $s2), - (MOV $d, $s1)), - (apply [{ APPLY }])>; - -def Rule2 : GICombineRule< - (defs root:$d), - (match (MOV $d, $s)), - (apply [{ APPLY }])>; - -def Rule3 : GICombineRule< - (defs root:$d), - (match (MUL $t, $s1, $s2), - (ADD $d, $t, $s3), [{ A }]), - (apply [{ APPLY }])>; - -def Rule4 : GICombineRule< - (defs root:$d), - (match (ADD $d, $s1, $s2)), - (apply [{ APPLY }])>; - -let Predicates = [HasFoo] in -def Rule5 : GICombineRule< - (defs root:$d), - (match (SUB $d, $s1, $s2)), - (apply [{ APPLY }])>; - -let Predicates = [HasFoo, HasAnswerToEverything] in -def Rule6 : GICombineRule< - (defs root:$d), - (match (SEXT $t, $s1), - (TRUNC $d, $t)), - (apply [{ APPLY }])>; - -def Rule7 : GICombineRule< - (defs root:$d), - (match (ZEXT $t, $s1), - (TRUNC $d, $t)), - (apply [{ APPLY }])>; - -// Rules 8&9 check that the partitions are formed correctly if -// - there is an edge different from Operand(1) -> Operand(0) -// - more than one leaf is ignored because the leaf does not -// care about the instruction -// - a single instruction has more operands than all others -// These conditions triggered a crash when emitting the -// resulting source code. -def Rule8 : GICombineRule< - (defs root:$d), - (match (ICMP $ic, $cc, $s2, $s3), - (ZEXT $z, $ic), - (MUL $d, $t, $z), - [{ MATCH }]), - (apply [{ APPLY }])>; - -def Rule9 : GICombineRule< - (defs root:$d), - (match (MUL $d, $t, $z)), - (apply [{ APPLY }])>; - -def MyCombinerHelper: GICombinerHelper<"GenMyCombinerHelper", [ - Rule0, - Rule1, - Rule2, - Rule3, - Rule4, - Rule5, - Rule6, - Rule7, - Rule8, - Rule9 -]>; - -// CHECK-LABEL: digraph "matchtree" { -// CHECK-DAG: Node[[N0:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[0].getOpcode()|5 partitions|Rule0,Rule1,Rule2,Rule3,Rule4,Rule5,Rule6,Rule7,Rule8,Rule9}"] -// CHECK-DAG: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule0,Rule5}"] -// CHECK-DAG: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule0,Rule5}"] -// CHECK-DAG: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule0}"] -// CHECK-DAG: Node[[N4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"] -// CHECK-DAG: Node[[N5:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule5}"] -// CHECK-DAG: Node[[N6:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule1,Rule2}"] -// CHECK-DAG: Node[[N7:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule1,Rule2}"] -// CHECK-DAG: Node[[N8:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule1}"] -// CHECK-DAG: Node[[N9:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"] -// CHECK-DAG: Node[[N10:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule2}"] -// CHECK-DAG: Node[[N11:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|2 partitions|Rule3,Rule4}"] -// CHECK-DAG: Node[[N12:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule3,Rule4}"] -// CHECK-DAG: Node[[N13:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule3,Rule4}",color=red] -// CHECK-DAG: Node[[N14:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"] -// CHECK-DAG: Node[[N15:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule4}"] -// CHECK-DAG: Node[[N16:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(1))|1 partitions|Rule6,Rule7}"] -// CHECK-DAG: Node[[N17:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule6,Rule7}"] -// CHECK-DAG: Node[[N18:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule6}"] -// CHECK-DAG: Node[[N19:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule7}"] -// CHECK-DAG: Node[[N20:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1] = getVRegDef(MI[0].getOperand(2))|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N21:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[1].getOpcode()|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N22:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2] = getVRegDef(MI[1].getOperand(1))|1 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N23:(0x)?[0-9a-fA-F]+]] [shape=record,label="{MI[2].getOpcode()|2 partitions|Rule8,Rule9}"] -// CHECK-DAG: Node[[N24:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule8,Rule9}",color=red] -// CHECK-DAG: Node[[N25:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] -// CHECK-DAG: Node[[N26:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] -// CHECK-DAG: Node[[N27:(0x)?[0-9a-fA-F]+]] [shape=record,label="{No partitioner|Rule9}"] - -// The most important partitioner is on the first opcode: -// CHECK-DAG: Node[[N0]] -> Node[[N1]] [label="#0 MyTarget::SUB"] -// CHECK-DAG: Node[[N0]] -> Node[[N6]] [label="#1 MyTarget::MOV"] -// CHECK-DAG: Node[[N0]] -> Node[[N11]] [label="#2 MyTarget::ADD"] -// CHECK-DAG: Node[[N0]] -> Node[[N16]] [label="#3 MyTarget::TRUNC"] -// CHECK-DAG: Node[[N0]] -> Node[[N20]] [label="#4 MyTarget::MUL"] - -// For, MI[0].getOpcode() == SUB, then has to determine whether it has a reg -// operand and follow that link. If it can't then Rule5 is the only choice as -// that rule is not constrained to a reg. -// CHECK-DAG: Node[[N1]] -> Node[[N2]] [label="#0 true"] -// CHECK-DAG: Node[[N1]] -> Node[[N5]] [label="#1 false"] - -// For, MI[0].getOpcode() == SUB && MI[0].getOperand(1).isReg(), if MI[1] is a -// MUL then it must be either Rule0 or Rule5. Rule0 is fully tested so Rule5 is -// unreachable. If it's not MUL then it must be Rule5. -// CHECK-DAG: Node[[N2]] -> Node[[N3]] [label="#0 MyTarget::MUL"] -// CHECK-DAG: Node[[N2]] -> Node[[N4]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N6]] -> Node[[N7]] [label="#0 true"] -// CHECK-DAG: Node[[N6]] -> Node[[N10]] [label="#1 false"] - -// CHECK-DAG: Node[[N7]] -> Node[[N8]] [label="#0 MyTarget::MOV"] -// CHECK-DAG: Node[[N7]] -> Node[[N9]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N11]] -> Node[[N12]] [label="#0 true"] -// CHECK-DAG: Node[[N11]] -> Node[[N15]] [label="#1 false"] - -// CHECK-DAG: Node[[N12]] -> Node[[N13]] [label="#0 MyTarget::MUL"] -// CHECK-DAG: Node[[N12]] -> Node[[N14]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N16]] -> Node[[N17]] [label="#0 true"] - -// CHECK-DAG: Node[[N17]] -> Node[[N18]] [label="#0 MyTarget::SEXT"] -// CHECK-DAG: Node[[N17]] -> Node[[N19]] [label="#1 MyTarget::ZEXT"] - -// Follow the links for MI[0].getOpcode() == MUL. -// CHECK-DAG: Node[[N20]] -> Node[[N21]] [label="#0 true"] -// CHECK-DAG: Node[[N20]] -> Node[[N27]] [label="#1 false"] - -// CHECK-DAG: Node[[N21]] -> Node[[N22]] [label="#0 MyTarget::ZEXT"] -// CHECK-DAG: Node[[N21]] -> Node[[N26]] [label="#1 * or nullptr"] - -// CHECK-DAG: Node[[N22]] -> Node[[N23]] [label="#0 true"] - -// CHECK-DAG: Node[[N23]] -> Node[[N24]] [label="#0 MyTarget::ICMP"] -// CHECK-DAG: Node[[N23]] -> Node[[N25]] [label="#1 * or nullptr"] - - -// CHECK-LABEL: {{^}$}} - - -// Check the generated source code. - -// CODE-LABEL: GenMyCombinerHelper::tryCombineAll - -// Check the first partition. The numbers correspond to the labels above. -// CODE: switch (MIs[0]->getOpcode()) { -// CODE-NEXT: case MyTarget::SUB: Partition = 0; break; -// CODE-NEXT: case MyTarget::MOV: Partition = 1; break; -// CODE-NEXT: case MyTarget::ADD: Partition = 2; break; -// CODE-NEXT: case MyTarget::TRUNC: Partition = 3; break; -// CODE-NEXT: case MyTarget::MUL: Partition = 4; break; -// CODE-NEXT: } - -// Check that the correct partition is choosen if operand 1 is a register. - -// CODE: if (Partition == 0 /* MyTarget::SUB */) { -// CODE-NEXT: Partition = -1; -// CODE-NEXT: if (MIs.size() <= 1) MIs.resize(2); -// CODE-NEXT: MIs[1] = nullptr; -// CODE-NEXT: if (MIs[0]->getOperand(1).isReg()) -// CODE-NEXT: MIs[1] = MRI.getVRegDef(MIs[0]->getOperand(1).getReg()); -// CODE-NEXT: if (MIs[1] == nullptr) Partition = 1; -// CODE-NEXT: if (MIs[1] != nullptr) Partition = 0; - - -// Check that the MUL opcode is tested. - -// CODE: if (Partition == 0 /* true */) { -// CODE-NEXT: Partition = -1; -// CODE-NEXT: switch (MIs[1]->getOpcode()) { -// CODE-NEXT: case MyTarget::MUL: Partition = 0; break; -// CODE-NEXT: default: Partition = 1; break; -// CODE-NEXT: } - -// Check that action for MUL is executed. - -// CODE: if (Partition == 0 /* MyTarget::MUL */) { -// CODE-NEXT: // Leaf name: Rule0 -// CODE-NEXT: // Rule: Rule0 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(0)) { -// CODE-NEXT: if (1 -// CODE-NEXT:) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule0'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } - -// Check that the other rule involving SUB (Rule5) is run otherwise. - -// CODE-NEXT: if (Partition == 1 /* * or nullptr */) { -// CODE-NEXT: // Leaf name: Rule5 -// CODE-NEXT: // Rule: Rule5 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(5)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT:) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } -// CODE-NEXT: } - -// Check that Rule5 is run if operand 1 is not MUL. - -// CODE-NEXT: if (Partition == 1 /* false */) { -// CODE-NEXT: // Leaf name: Rule5 -// CODE-NEXT: // Rule: Rule5 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(5)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT: ) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule5'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } -// CODE-NEXT: llvm_unreachable("Combine rule elision was incorrect"); -// CODE-NEXT: return false; -// CODE-NEXT: } -// CODE-NEXT: } - - -// Check multiple predicates are correctly emitted - -// CODE: // Leaf name: Rule6 -// CODE-NEXT: // Rule: Rule6 -// CODE-NEXT: if (!RuleConfig->isRuleDisabled(6)) { -// CODE-NEXT: if (1 -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasFoo -// CODE-NEXT: Subtarget->hasFoo() -// CODE-NEXT: ) -// CODE-NEXT: && ( -// CODE-NEXT: // Predicate: HasAnswerToEverything -// CODE-NEXT: Subtarget->getAnswerToUniverse() == 42 && Subtarget->getAnswerToLife() == 42 -// CODE-NEXT: ) -// CODE-NEXT: ) { -// CODE-NEXT: LLVM_DEBUG(dbgs() << "Applying rule 'Rule6'\n"); -// CODE-NEXT: APPLY -// CODE-NEXT: return true; -// CODE-NEXT: } -// CODE-NEXT: } Index: llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td =================================================================== --- llvm/test/TableGen/GICombinerEmitter/parse-match-pattern.td +++ /dev/null @@ -1,215 +0,0 @@ -// RUN: llvm-tblgen -I %p/../../../include -gen-global-isel-combiner \ -// RUN: -combiners=MyCombiner -gicombiner-stop-after-parse %s \ -// RUN: -o /dev/null -debug 2>&1 | FileCheck %s -// REQUIRES: asserts - -include "llvm/Target/Target.td" -include "llvm/Target/GlobalISel/Combine.td" - -def MyTargetISA : InstrInfo; -def MyTarget : Target { let InstructionSet = MyTargetISA; } - -def dummy; - -def R0 : Register<"r0"> { let Namespace = "MyTarget"; } -def GPR32 : RegisterClass<"MyTarget", [i32], 32, (add R0)>; -class I Pat> - : Instruction { - let Namespace = "MyTarget"; - let OutOperandList = OOps; - let InOperandList = IOps; - let Pattern = Pat; -} -def MOV : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; -def MOV2 : I<(outs GPR32:$dst), (ins GPR32:$src1), []>; - -def trivial : GICombineRule< - (defs root:$d), - (match (MOV $d, $s)), - (apply [{ APPLY }])>; - -// CHECK-LABEL: Parsed rule defs/match for 'trivial' - -// The matchdag block is a fairly direct dump of the information that was read. -// It's oriented towards the data structures within tablegen. -// CHECK-NEXT: matchdag { -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon0_0 // $d=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred0_1 -// CHECK-NEXT: __anon0_0 ==> __anonpred0_1[mi] -// CHECK-NEXT: {{^}$}} - -// The digraph block is a human-oriented dump of the information that was read. -// Run it through graphviz to produce a nice DAG showing the matcher behaviour. -// CHECK-NEXT: digraph "trivial" { -// CHECK-NEXT: rankdir="BT" -// CHECK-NEXT: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon0_0|MOV|Match starts here|$d=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred0_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] -// CHECK-NEXT: {{^}$}} - -def simple : GICombineRule< - (defs root:$d), - (match (MOV $t, $s), - (MOV $d, $t)), - (apply [{ APPLY }])>; - -// CHECK-LABEL: Parsed rule defs/match for 'simple' - -// CHECK-NEXT: matchdag { -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon1_0 // $t=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon1_2 // $d=getOperand(0), $t=getOperand(1) -// CHECK-NEXT: __anon1_2[src1] --[t]--> __anon1_0[dst] -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred1_1 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred1_3 -// CHECK-NEXT: __anon1_0 ==> __anonpred1_1[mi] -// CHECK-NEXT: __anon1_2 ==> __anonpred1_3[mi] -// CHECK-NEXT: {{^}$}} - -// CHECK-NEXT: digraph "simple" { -// CHECK-NEXT: rankdir="BT" -// CHECK-NEXT: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_0|MOV|$t=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon1_2|MOV|Match starts here|$d=getOperand(0), $t=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$t"] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred1_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] -// CHECK-NEXT: {{^}$}} - -def multiroot : GICombineRule< - (defs root:$d1, root:$d2), - (match (MOV $s, $s2), - (MOV $d1, $s), - (MOV $d2, $s)), - (apply [{ APPLY }])>; - -// CHECK-LABEL: Parsed rule defs/match for 'multiroot' - -// CHECK-NEXT: matchdag { -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_0 // $s=getOperand(0), $s2=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_2 // $d1=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon2_4 // $d2=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: __anon2_2[src1] --[s]--> __anon2_0[dst] -// CHECK-NEXT: __anon2_4[src1] --[s]--> __anon2_0[dst] -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_1 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_3 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred2_5 -// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred2_6 -// CHECK-NEXT: __anon2_0 ==> __anonpred2_1[mi] -// CHECK-NEXT: __anon2_2 ==> __anonpred2_3[mi] -// CHECK-NEXT: __anon2_4 ==> __anonpred2_5[mi] -// CHECK-NEXT: __anon2_2[src1] ==> __anonpred2_6[mi0] -// CHECK-NEXT: __anon2_4[src1] ==> __anonpred2_6[mi1] -// CHECK-NEXT: {{^}$}} - -// CHECK-NEXT: digraph "multiroot" { -// CHECK-NEXT: rankdir="BT" -// CHECK-NEXT: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_0|MOV|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_2|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon2_4|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s"] -// CHECK-NEXT: Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s"] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred2_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred2_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] -// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted] -// CHECK-NEXT: {{^}$}} - -def nonstandardroot : GICombineRule< - (defs root:$s), - (match (MOV $s, $s2), - (MOV $d1, $s), - (MOV $d2, $s)), - (apply [{ APPLY }])>; - -// CHECK-LABEL: Parsed rule defs/match for 'nonstandardroot' - -// CHECK-NEXT: matchdag { -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_0 // $s=getOperand(0), $s2=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_2 // $d1=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon3_4 // $d2=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: __anon3_0[dst] --[s]--> __anon3_2[src1] -// CHECK-NEXT: __anon3_0[dst] --[s]--> __anon3_4[src1] -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_1 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_3 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred3_5 -// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred3_6 -// CHECK-NEXT: __anon3_0 ==> __anonpred3_1[mi] -// CHECK-NEXT: __anon3_2 ==> __anonpred3_3[mi] -// CHECK-NEXT: __anon3_4 ==> __anonpred3_5[mi] -// CHECK-NEXT: __anon3_2[src1] ==> __anonpred3_6[mi0] -// CHECK-NEXT: __anon3_4[src1] ==> __anonpred3_6[mi1] -// CHECK-NEXT: {{^}$}} - -// CHECK-NEXT: digraph "nonstandardroot" { -// CHECK-NEXT: rankdir="BT" -// CHECK-NEXT: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_0|MOV|Match starts here|$s=getOperand(0), $s2=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_2|MOV|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon3_4|MOV|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}"] -// CHECK-NEXT: Node[[N2]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow] -// CHECK-NEXT: Node[[N3]]:s1:n -> Node[[N1]]:d0:s [label="$s",dir=back,arrowtail=crow] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred3_5|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P4:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred3_6|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] -// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N3]]:e -> Pred[[P3]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P4]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N3]]:s1:n -> Pred[[P4]]:d2:s [style=dotted] -// CHECK-NEXT: {{^}$}} - -def multiref_use : GICombineRule< - (defs root:$d1, root:$d2), - (match (MOV $d1, $s), - (MOV $d2, $s)), - (apply [{ APPLY }])>; - -// CHECK-LABEL: Parsed rule defs/match for 'multiref_use' - -// CHECK-NEXT: matchdag { -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon4_0 // $d1=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: (MOV 0:dst, 1:src1):$__anon4_2 // $d2=getOperand(0), $s=getOperand(1) -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred4_1 -// CHECK-NEXT: <<$mi.getOpcode() == MOV>>:$__anonpred4_3 -// CHECK-NEXT: <<$mi0 == $mi1>>:$__anonpred4_4 -// CHECK-NEXT: __anon4_0 ==> __anonpred4_1[mi] -// CHECK-NEXT: __anon4_2 ==> __anonpred4_3[mi] -// CHECK-NEXT: __anon4_0[src1] ==> __anonpred4_4[mi0] -// CHECK-NEXT: __anon4_2[src1] ==> __anonpred4_4[mi1] -// CHECK-NEXT: {{^}$}} - -// CHECK-NEXT: digraph "multiref_use" { -// CHECK-NEXT: rankdir="BT" -// CHECK-NEXT: Node[[N1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_0|MOV|Match starts here|$d1=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Node[[N2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $dst|#1 $src1}|__anon4_2|MOV|Match starts here|$d2=getOperand(0), $s=getOperand(1)|{{(0x)?[0-9a-fA-F]+}}|{#0 $dst|#1 $src1}}",color=red] -// CHECK-NEXT: Pred[[P1:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_1|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P2:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi}|__anonpred4_3|$mi.getOpcode() == MOV|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi}}",style=dotted] -// CHECK-NEXT: Pred[[P3:(0x)?[0-9a-fA-F]+]] [shape=record,label="{{[{]{}}#0 $$|#1 $mi0|#2 $mi1}|__anonpred4_4|$mi0 == $mi1|{{(0x)?[0-9a-fA-F]+}}|{#0 $$|#1 $mi0|#2 $mi1}}",style=dotted] -// CHECK-NEXT: Node[[N1]]:e -> Pred[[P1]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:e -> Pred[[P2]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N1]]:s1:n -> Pred[[P3]]:d1:s [style=dotted] -// CHECK-NEXT: Node[[N2]]:s1:n -> Pred[[P3]]:d2:s [style=dotted] -// CHECK-NEXT: {{^}$}} - -def MyCombiner: GICombinerHelper<"GenMyCombiner", [ - trivial, - simple, - multiroot, - nonstandardroot, - multiref_use -]>; - -// Verify we're sharing operand lists correctly -// CHECK-LABEL: GIMatchDagOperandListContext { -// CHECK-NEXT: OperandLists { -// CHECK-NEXT: 0:dst, 1:src1{{$}} -// CHECK-NEXT: 0:$, 1:mi{{$}} -// CHECK-NEXT: 0:$, 1:mi0, 2:mi1{{$}} -// CHECK-NEXT: } -// CHECK-NEXT: } Index: llvm/utils/TableGen/GICombinerEmitter.cpp =================================================================== --- llvm/utils/TableGen/GICombinerEmitter.cpp +++ llvm/utils/TableGen/GICombinerEmitter.cpp @@ -17,6 +17,7 @@ #include "GlobalISel/GIMatchDag.h" #include "GlobalISel/GIMatchDagPredicate.h" #include "GlobalISel/GIMatchTree.h" +#include "GlobalISel/GIMatchTreeAutomaton.h" #include "llvm/ADT/SmallSet.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/StringSet.h" @@ -68,22 +69,6 @@ return StrTab.insert(S).first->first(); } -class format_partition_name { - const GIMatchTree &Tree; - unsigned Idx; - -public: - format_partition_name(const GIMatchTree &Tree, unsigned Idx) - : Tree(Tree), Idx(Idx) {} - void print(raw_ostream &OS) const { - Tree.getPartitioner()->emitPartitionName(OS, Idx); - } -}; -raw_ostream &operator<<(raw_ostream &OS, const format_partition_name &Fmt) { - Fmt.print(OS); - return OS; -} - /// Declares data that is passed from the match stage to the apply stage. class MatchDataInfo { /// The symbol used in the tablegen patterns @@ -615,8 +600,9 @@ /// response to the generated cl::opt. void emitNameMatcher(raw_ostream &OS) const; - void generateCodeForTree(raw_ostream &OS, const GIMatchTree &Tree, - StringRef Indent) const; + void generateCodeForTree(raw_ostream &OS, + const GIMatchTreeAutomaton &TreeAutomaton, + unsigned Indent) const; }; GICombinerEmitter::GICombinerEmitter(RecordKeeper &RK, @@ -717,33 +703,70 @@ } } -void GICombinerEmitter::generateCodeForTree(raw_ostream &OS, - const GIMatchTree &Tree, - StringRef Indent) const { - if (Tree.getPartitioner() != nullptr) { - Tree.getPartitioner()->generatePartitionSelectorCode(OS, Indent); - for (const auto &EnumChildren : enumerate(Tree.children())) { - OS << Indent << "if (Partition == " << EnumChildren.index() << " /* " - << format_partition_name(Tree, EnumChildren.index()) << " */) {\n"; - generateCodeForTree(OS, EnumChildren.value(), (Indent + " ").str()); - OS << Indent << "}\n"; - } - return; - } +void GICombinerEmitter::generateCodeForTree( + raw_ostream &OS, const GIMatchTreeAutomaton &TreeAutomaton, + unsigned Indent) const { - bool AnyFullyTested = false; - for (const auto &Leaf : Tree.possible_leaves()) { - OS << Indent << "// Leaf name: " << Leaf.getName() << "\n"; + // Emit code to calculate the resulting match set number. + OS.indent(Indent) << "unsigned MS = 0;\n"; + TreeAutomaton.emitTransitions(OS, Indent); + OS.indent(Indent) << "MatchSets[&MI] = MS;\n"; - const CombineRule *Rule = Leaf.getTargetData(); - const Record &RuleDef = Rule->getDef(); + // Emit code to select matching rules. + TreeAutomaton.emitRuleMapping(OS, Indent); + + // Emit code to execute a rule. + if (TreeAutomaton.getMatchingRuleInfos().empty()) + return; + OS.indent(Indent) << "for (unsigned PatternRuleID : Rules[MSToRule[MS]]) {\n"; + OS.indent(Indent + 2) << "switch (PatternRuleID) {\n"; + for (auto &[Idx, Info] : enumerate(TreeAutomaton.getMatchingRuleInfos())) { + if (Info.isVariant()) + continue; + OS.indent(Indent + 2) << "case " << Idx << ":\n"; + for (unsigned VariantId : Info.getVariants()) { + OS.indent(Indent + 2) << "case " << VariantId << ":\n"; + } - OS << Indent << "// Rule: " << RuleDef.getName() << "\n" - << Indent << "if (!RuleConfig->isRuleDisabled(" << Rule->getID() - << ")) {\n"; + const CombineRule *Rule = Info.getTargetData(); + const Record &RuleDef = Rule->getDef(); + OS.indent(Indent + 4) << "// Rule: " << RuleDef.getName() << "\n"; + OS.indent(Indent + 4) << "if (!RuleConfig->isRuleDisabled(" << Rule->getID() + << ")) {\n"; + + // Emit the MIs[] array. + auto EmitMIs = [&OS](unsigned Indent, const GIMatchPatternInfo &Info) { + for (auto [Index, Value] : enumerate(Info.instr_infos())) { + if (Index) + OS.indent(Indent) << "MIs[" << Index << "] = MRI.getVRegDef(MIs[" + << Value.getBaseInstrID() << "]->getOperand(" + << Value.getFromOpIdx() << ").getReg());\n"; + else + OS.indent(Indent) << "MIs[0] = &MI;\n"; + } + }; + OS.indent(Indent + 6) << "MachineInstr* MIs[" << Info.getNumInstrInfo() + << "];\n"; + if (Info.hasVariants()) { + OS.indent(Indent + 6) << "if (PatternRuleID == " << Idx << ") {\n"; + EmitMIs(Indent + 8, Info); + for (auto I = Info.getVariants().begin(), E = Info.getVariants().end(); + I != E;) { + unsigned VarId = *I; + OS.indent(Indent + 6) << "} else"; + ++I; + if (I != E) + OS << " if (PatternRuleID == " << VarId << ")"; + OS << " {\n"; + EmitMIs(Indent + 8, TreeAutomaton.getMatchingRuleInfos()[VarId]); + } + OS.indent(Indent + 6) << "}\n"; + } else + EmitMIs(Indent + 6, Info); + // Create the set of variable expansions. CodeExpansions Expansions; - for (const auto &VarBinding : Leaf.var_bindings()) { + for (const auto &VarBinding : Info.var_bindings()) { if (VarBinding.isInstr()) Expansions.declare(VarBinding.getName(), "MIs[" + to_string(VarBinding.getInstrID()) + "]"); @@ -755,14 +778,14 @@ } Rule->declareExpansions(Expansions); + // Check that the apply function is defined. DagInit *Applyer = RuleDef.getValueAsDag("Apply"); - if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() != - "apply") { + if (Applyer->getOperatorAsDef(RuleDef.getLoc())->getName() != "apply") { PrintError(RuleDef.getLoc(), "Expected 'apply' operator in Apply DAG"); return; } - OS << Indent << " if (1\n"; + OS.indent(Indent + 6) << "if (1\n"; // Emit code for C++ Predicates. if (RuleDef.getValue("Predicates")) { @@ -779,37 +802,15 @@ if (CondString.empty()) continue; - OS << Indent << " && (\n" - << Indent << " // Predicate: " << Def->getName() << "\n" - << Indent << " " << CondString << "\n" - << Indent << " )\n"; + OS.indent(Indent + 6) << " && (\n"; + OS.indent(Indent + 6) + << " // Predicate: " << Def->getName() << "\n"; + OS.indent(Indent + 6) << " " << CondString << "\n"; + OS.indent(Indent + 6) << " )\n"; } } } - // Attempt to emit code for any untested predicates left over. Note that - // isFullyTested() will remain false even if we succeed here and therefore - // combine rule elision will not be performed. This is because we do not - // know if there's any connection between the predicates for each leaf and - // therefore can't tell if one makes another unreachable. Ideally, the - // partitioner(s) would be sufficiently complete to prevent us from having - // untested predicates left over. - for (const GIMatchDagPredicate *Predicate : Leaf.untested_predicates()) { - if (Predicate->generateCheckCode(OS, (Indent + " ").str(), - Expansions)) - continue; - PrintError(RuleDef.getLoc(), - "Unable to test predicate used in rule"); - PrintNote(SMLoc(), - "This indicates an incomplete implementation in tablegen"); - Predicate->print(errs()); - errs() << "\n"; - OS << Indent - << "llvm_unreachable(\"TableGen did not emit complete code for this " - "path\");\n"; - break; - } - if (Rule->getMatchingFixupCode() && !Rule->getMatchingFixupCode()->getValue().empty()) { // FIXME: Single-use lambda's like this are a serious compile-time @@ -819,49 +820,36 @@ // a big problem for low-mem systems around the 500 rule mark but by the // time we grow that large we should have merged the ISel match table // mechanism with the Combiner. - OS << Indent << " && [&]() {\n" - << Indent << " " - << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions, - RuleDef.getLoc(), ShowExpansions) - << '\n' - << Indent << " return true;\n" - << Indent << " }()"; + OS.indent(Indent + 6) << " && [&]() {\n"; + OS.indent(Indent + 8) + << CodeExpander(Rule->getMatchingFixupCode()->getValue(), Expansions, + RuleDef.getLoc(), ShowExpansions) + << '\n'; + OS.indent(Indent + 8) << "return true;\n"; + OS.indent(Indent + 6) << "}()"; } - OS << Indent << " ) {\n" << Indent << " "; + OS << ") {\n"; if (const StringInit *Code = dyn_cast(Applyer->getArg(0))) { - OS << " LLVM_DEBUG(dbgs() << \"Applying rule '" - << RuleDef.getName() - << "'\\n\");\n" - << CodeExpander(Code->getAsUnquotedString(), Expansions, - RuleDef.getLoc(), ShowExpansions) - << '\n' - << Indent << " return true;\n" - << Indent << " }\n"; + OS.indent(Indent + 8) << "LLVM_DEBUG(dbgs() << \"Applying rule '" + << RuleDef.getName() << "'\\n\");\n"; + OS.indent(Indent + 8) + << CodeExpander(Code->getAsUnquotedString(), Expansions, + RuleDef.getLoc(), ShowExpansions) + << '\n'; + OS.indent(Indent + 8) << "return true;\n"; + OS.indent(Indent + 6) << "}\n"; } else { PrintError(RuleDef.getLoc(), "Expected apply code block"); return; } - OS << Indent << "}\n"; - - assert(Leaf.isFullyTraversed()); - - // If we didn't have any predicates left over and we're not using the - // trap-door we have to support arbitrary C++ code while we're migrating to - // the declarative style then we know that subsequent leaves are - // unreachable. - if (Leaf.isFullyTested() && - (!Rule->getMatchingFixupCode() || - Rule->getMatchingFixupCode()->getValue().empty())) { - AnyFullyTested = true; - OS << Indent - << "llvm_unreachable(\"Combine rule elision was incorrect\");\n" - << Indent << "return false;\n"; - } - } - if (!AnyFullyTested) - OS << Indent << "return false;\n"; + OS.indent(Indent + 4) << "}\n"; + + OS.indent(Indent + 4) << "break;\n"; + } // end of loop over matching rules. + OS.indent(Indent + 2) << "}\n"; + OS.indent(Indent) << "}\n"; } static void emitAdditionalHelperMethodArguments(raw_ostream &OS, @@ -883,25 +871,27 @@ if (ErrorsPrinted) PrintFatalError(Combiner->getLoc(), "Failed to parse one or more rules"); LLVM_DEBUG(dbgs() << "Optimizing tree for " << Rules.size() << " rules\n"); - std::unique_ptr Tree; - Records.startTimer("Optimize combiner"); + std::unique_ptr TreeAutomaton; + Records.startTimer("Create automaton"); { - GIMatchTreeBuilder TreeBuilder(0); + GIMatchTreeAutomatonBuilder TreeBuilder(Records); for (const auto &Rule : Rules) { bool HadARoot = false; for (const auto &Root : enumerate(Rule->getMatchDag().roots())) { - TreeBuilder.addLeaf(Rule->getName(), Root.index(), Rule->getMatchDag(), - Rule.get()); + TreeBuilder.addLeaf(Rule->getName(), Rule->getID(), Root.index(), + Rule->getMatchDag(), Rule.get()); HadARoot = true; } if (!HadARoot) PrintFatalError(Rule->getDef().getLoc(), "All rules must have a root"); } - Tree = TreeBuilder.run(); + TreeAutomaton = TreeBuilder.run(); + if (StopAfterBuild) + TreeBuilder.writeYAML(outs()); } if (StopAfterBuild) { - Tree->writeDOTGraph(outs()); + TreeAutomaton->writeYAML(outs()); PrintNote(Combiner->getLoc(), "Terminating due to -gicombiner-stop-after-build"); return; @@ -941,6 +931,7 @@ OS << "RuleConfig(&RuleConfig) {}\n" << "\n" << " bool tryCombineAll(\n" + << " DenseMap &MatchSets,\n" << " GISelChangeObserver &Observer,\n" << " MachineInstr &MI,\n" << " MachineIRBuilder &B"; @@ -1034,6 +1025,7 @@ << "}\n\n"; OS << "bool " << getClassName() << "::tryCombineAll(\n" + << " DenseMap &MatchSets,\n" << " GISelChangeObserver &Observer,\n" << " MachineInstr &MI,\n" << " MachineIRBuilder &B"; @@ -1051,8 +1043,7 @@ OS << " " << I.getType() << " " << I.getVariableName() << ";\n"; OS << "\n"; - OS << " int Partition = -1;\n"; - generateCodeForTree(OS, *Tree, " "); + generateCodeForTree(OS, *TreeAutomaton, 2); OS << "\n return false;\n" << "}\n" << "#endif // ifdef " << Name.upper() << "_GENCOMBINERHELPER_CPP\n"; Index: llvm/utils/TableGen/GlobalISel/CMakeLists.txt =================================================================== --- llvm/utils/TableGen/GlobalISel/CMakeLists.txt +++ llvm/utils/TableGen/GlobalISel/CMakeLists.txt @@ -12,4 +12,5 @@ GIMatchDagPredicate.cpp GIMatchDagPredicateDependencyEdge.cpp GIMatchTree.cpp + GIMatchTreeAutomaton.cpp ) Index: llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.h =================================================================== --- /dev/null +++ llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.h @@ -0,0 +1,230 @@ +//===- GIMatchTree.h - A decision tree to match GIMatchDag's --------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// The general approach is to generate a bottom-up tree matcher as described by +/// Chase. +/// +/// References: +/// Hoffmann, O'Donnel: Pattern Matching in Trees (1982) +/// https://dl.acm.org/doi/10.1145/322290.322295 +/// +/// Chase: An Improvement to Bottom-up Tree Pattern Matching (1987) +/// https://dl.acm.org/doi/10.1145/41625.41640 +//===----------------------------------------------------------------------===// + +#ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H +#define LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H + +#include "GIMatchDag.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallVector.h" + +#include "../CodeGenTarget.h" // For enumerating instructions. + +namespace llvm { +class raw_ostream; +class CodeGenInstruction; +class PatternForestBuilder; + +/// Describes the binding of a variable to the matched MIR. +class GIMatchPatternVariableBinding { + /// The name of the variable described by this binding. + StringRef Name; + // The matched instruction it is bound to. + unsigned InstrID; + // The matched operand (if appropriate) it is bound to. + Optional OpIdx; + +public: + GIMatchPatternVariableBinding(StringRef Name, unsigned InstrID, + Optional OpIdx = std::nullopt) + : Name(Name), InstrID(InstrID), OpIdx(OpIdx) {} + + bool isInstr() const { return !OpIdx; } + StringRef getName() const { return Name; } + unsigned getInstrID() const { return InstrID; } + unsigned getOpIdx() const { + assert(OpIdx && "Is not an operand binding"); + return *OpIdx; + } +}; + +class GIMatchPatternInstrInfo { + // The ID of the instruction which this instruction refers too. + unsigned BaseInstrID; + // The defining operand. + unsigned FromOpIdx; + +public: + GIMatchPatternInstrInfo(unsigned BaseInstrID, unsigned FromOpIdx) + : BaseInstrID(BaseInstrID), FromOpIdx(FromOpIdx) {} + unsigned getBaseInstrID() const { return BaseInstrID; } + unsigned getFromOpIdx() const { return FromOpIdx; } +}; + +class GIMatchPatternInfo { +public: + using const_instr_infos_iterator = + SmallVector::const_iterator; + using const_var_binding_iterator = + SmallVector::const_iterator; + +private: + /// A name for the pattern. This is primarily for debugging. + StringRef Name; + /// Opaque data the caller of the tree building code understands. + void *Data; + + // List of the instructions used in the pattern. + // The elements of this list form a tree, with the first element being the + // root. + SmallVector InstrInfos; + + // The variable bindings associated with this pattern. + SmallVector VarBindings; + + // Is this info a variant of another info? + bool IsVariant; + + // List of variants. + SmallVector Variants; + +public: + GIMatchPatternInfo(StringRef Name, void *Data, bool IsVariant = false) + : Name(Name), Data(Data), IsVariant(IsVariant) {} + + StringRef getName() const { return Name; } + + template Ty *getTargetData() const { + return static_cast(Data); + } + + unsigned add(const GIMatchDagInstr *Instr, unsigned BaseInstrID, + unsigned FromOpIdx) { + unsigned ID = addInstrInfo(BaseInstrID, FromOpIdx); + + if (Instr) { + if (!Instr->getUserAssignedName().empty()) + bindInstrVariable(Instr->getUserAssignedName(), ID); + for (const auto &VarBinding : Instr->user_assigned_operand_names()) + bindOperandVariable(VarBinding.second, ID, VarBinding.first); + } + + return ID; + }; + + unsigned addInstrInfo(unsigned BaseInstrID, unsigned FromOpIdx) { + unsigned ID = InstrInfos.size(); + InstrInfos.emplace_back(BaseInstrID, FromOpIdx); + return ID; + } + size_t getNumInstrInfo() const { return InstrInfos.size(); } + const_instr_infos_iterator instr_infos_begin() const { + return InstrInfos.begin(); + } + const_instr_infos_iterator instr_infos_end() const { + return InstrInfos.end(); + } + iterator_range instr_infos() const { + return make_range(InstrInfos.begin(), InstrInfos.end()); + } + + void bindInstrVariable(StringRef Name, unsigned InstrID) { + VarBindings.emplace_back(Name, InstrID); + } + void bindOperandVariable(StringRef Name, unsigned InstrID, unsigned OpIdx) { + VarBindings.emplace_back(Name, InstrID, OpIdx); + } + const_var_binding_iterator var_bindings_begin() const { + return VarBindings.begin(); + } + const_var_binding_iterator var_bindings_end() const { + return VarBindings.end(); + } + iterator_range var_bindings() const { + return make_range(VarBindings.begin(), VarBindings.end()); + } + + bool isVariant() const { return IsVariant; } + bool hasVariants() const { return !Variants.empty(); } + void addVariant(unsigned VariantID) { + Variants.push_back(VariantID); + } + const SmallVectorImpl &getVariants() const { return Variants; } +}; + +class GIMatchTreeAutomaton { + friend class PatternForestBuilder; + +public: + struct Table { + // The label. + const CodeGenInstruction *Inst; + // Dimension of the compression table. + unsigned DimC; + // The compression table. Dimension is DimC X DimMatchSets. + OwningArrayRef C; + // Dimension and data of the transition table. + OwningArrayRef DimT; + OwningArrayRef T; + }; + +private: + // Number of match sets. This determines the dimension of the C array. + unsigned DimMatchSets; + + // The compression and transistion tables. + SmallVector Tables; + + // LeafTables. + SmallVector, 0> LeafTables; + + // The matching rules. + DenseMap> MatchingRules; + SmallVector MatchingRuleInfos; + + void emitTable(raw_ostream &OS, const Table &T, unsigned Indent) const; + +public: + GIMatchTreeAutomaton(unsigned DimMatchSets); + const DenseMap> &getMatchingRules() const { + return MatchingRules; + } + const SmallVector &getMatchingRuleInfos() const { + return MatchingRuleInfos; + } + void emitTransitions(raw_ostream &OS, unsigned Indent) const; + void emitRuleMapping(raw_ostream &OS, unsigned Indent) const; + void writeYAML(raw_ostream &OS) const; + void dump() const; +}; + +class GIMatchTreeAutomatonBuilder { + /// For information about target instructions. + const CodeGenTarget Target; + + std::unique_ptr PFBuilder; + +public: + GIMatchTreeAutomatonBuilder(RecordKeeper &Records); + ~GIMatchTreeAutomatonBuilder(); + + void addLeaf(StringRef Name, uint64_t ID, unsigned RootIdx, + const GIMatchDag &MatchDag, void *Data); + + /// Construct the bottom up tree matcher. + std::unique_ptr run(); + + void writeYAML(raw_ostream &OS) const; + void dump() const; +}; + +} // end namespace llvm +#endif // ifndef LLVM_UTILS_TABLEGEN_GIMATCHTREEAUTOMATON_H Index: llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp =================================================================== --- /dev/null +++ llvm/utils/TableGen/GlobalISel/GIMatchTreeAutomaton.cpp @@ -0,0 +1,1212 @@ +//===- GIMatchTree.cpp - A decision tree to match GIMatchDag's ------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// Generate a bottom-up tree matcher as described by Chase (1987). +/// +/// The basic idea of a bottom-up matcher is to associate with each instruction +/// the set of matching patterns, called the match set. For an instruction +/// without use operands (a leaf) the match set is easily determined. For any +/// other instruction, the match set is retrieved with a table lookup, using the +/// use operands as table indices. As a result, all matching patterns can be +/// found in linear time. +/// +/// All patterns to match are known at compile. From these patterns, the match +/// sets and the table lookups are constructed. The algorithm was first +/// described by Hoffmann and O'Donnel. +/// - First enumerate the pattern forest (the set of all subpatterns), and +/// assign a number to each pattern +/// - Then calculate the match sets. First, the match sets of patterns with +/// height 0 are calculated. Based on the result, patterns of height 1 can be +/// calculated, and so on. +/// - Finally, the lookup tables con be constructed. +/// +/// The main disadvantage of this algorithm is that the tables can get very +/// large. This affects the preprocessing time and space requirements in the +/// resulting matcher. Chase modified the algorithm to include compression of +/// the tables. The basic idea is to define an equivalence relation on the set +/// of of patterns, which can appear as subpatterns of a pattern. Using these +/// representer sets, the calculation is speed up, and the tables are much +/// smaller. +/// +/// The modification to the algorithm includes: +/// - The representer sets are calculated along the match sets, and the +/// calculation of the match sets uses the representer sets. +/// - The lookup tables are only computed for the representer sets. +/// - An additional mapping from the match sets to the representer sets is +/// required. +/// +/// Implementation notes +/// The nodes of the pattern tree are labled with the instruction name. These +/// lables are singletons, and implemented using a FoldingSetVector. +/// Each pattern is given a numeric encoding. The set of all subpatterns, +/// called the pattern forest, is implemented as a FoldingSet. +/// A set of patterns is implemented as a BitVector, and also given a numeric +/// encoding. The match sets, which are sets of sets of patterns, are stored in +/// a DenseMap, using the set of patterns as key, and its numerical encoding as +/// value. (The vector versions of the FoldingSet and the DenseMap are used to +/// make the calculation deterministic. Pointers are involved in the calculation +/// of the hash values, which introduces randomness.) +/// The implementation assumes that the placeholder * (v in paper of Chase) is +/// always a member of the pattern forest. It further assumes that the +/// placeholder * and the set only containing the placeholder have the encoding +/// 0. +/// +/// References: +/// Hoffmann, O'Donnel: Pattern Matching in Trees (1982) +/// https://dl.acm.org/doi/10.1145/322290.322295 +/// +/// Chase: An Improvement to Bottom-up Tree Pattern Matching (1987) +/// https://dl.acm.org/doi/10.1145/41625.41640 +//===----------------------------------------------------------------------===// + +#include "GIMatchTreeAutomaton.h" +#include "GIMatchDagPredicate.h" + +#include "../CodeGenInstruction.h" + +#include "llvm/ADT/FoldingSet.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/MapVector.h" +#include "llvm/Support/Debug.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" +#include "llvm/TableGen/Error.h" +#include "llvm/TableGen/Record.h" + +#include + +#define DEBUG_TYPE "gimatchtreeautomaton" + +using namespace llvm; + +/* + Some remarks about performance and memory usage + + (a) + The encoding of newly discovered sets depends on the order of calculation. + Since hashing is used, there is no guaranteed order since hashing of pointers + introduces some randomness. To overcome this problem, the match sets and the + representer sets are assigned an encoding based on an ordering of the sets. + This is a big performance hit! It should be possible to avoid this cost be + rearranging the YAML output. + - The pattern encoding is stable because it depends on the syntactical order + and the tree traversal. + - The match sets can be printed sorted by the set content instead of sorted by + encoding. This order is stable, but the encoding numbers would vary. + - Same can be done for printing the subpattern sets and the representer sets. + - The encoding in the lookup table can be matched by an reg ex. + - Only the compression table is tricky. + - The order of the elements depends on the match set encoding. This could be + overcome by printing (match set, encoding) pairs, sorted by match set. + - The Chase set encoding (and with it the layout of the lookup table) + currently depends on the order of the discovery of new sets, which is + completely arbitrary. That mapping could be reordered, e.g. by the order + of the match sets. However, this would introduce a sorting step while + creating the compressions table. + (partially implemented) + + (b) + If a dimension of the lookup table is 1 then that dimenion, the corresponding + row of the compression table, and the corresponding operand can be omitted. + + (c) + The Label and the Pattern class have 1 or 2 OwningArrayRef members. The size + of the array is known when the objects are allocated. These additional memory + allocations can be avoided by managing that memory together with the object. + E.g. + static Label *create(const CodeGenInstruction *Inst) { + unsigned NumOpnds = Inst->Operands.size() - Inst->Operands.NumDefs; + size_t Ofs = alignTo(sizeof(Label), alignof(BitVector)); + void *Mem = operator new[](Ofs + NumOpnds * sizeof(BitVector)); + BitVector *PAj = reinterpret_cast( + reinterpret_cast(Mem) + Ofs); + for (unsigned I = 0, E = NumOpnds; I < E; ++I) + new (&PAj[I]) BitVector(); + return new (Mem) Label(Inst, MutableArrayRef(PAj, NumOpnds)); + } + The objects could also be made smaller by exploting the facts that the size of + the array only need to be stored once, and that the pointer(s) to the array(s) + are at known offsets from the this pointer. + + (d) + The implementation does not care about memory management. A context object + holding a bump allocator could be introduced to free most of the memory after + the matcher is created. +*/ + +namespace llvm { + +namespace { +// The algorithm requires to enumerate all elements of an n-dimensional set +// product. That is, given sets R_1, ..., R_n, all tuples (r_1, ..., r_n) of +// R_1 x ... x R_n are enumerated. +// For convenience and easy understanding, that enumeration is implemented as a +// C++ range. The template implementation needs to know that type of the set +// (SetT), and the type of the set elements (ElemT). The only other requirement +// is that the set type provides a const_iterator. +// Two specialized version are provided. One uses a BitVector as set type and +// unsigned as element type. This is mainly provided for performance reasons, as +// this range is used in the innermost loop, and the implementeation requires +// less temporary memory. The other version enumerates a set product [0..N_0] x +// ... X [0..N_n] of integer intervals. The rightmost element changes the +// fastest, which is compatible with multi-dimensional C++ arrays. + +// This version uses iterators to loop over elements of the sets R_i. +// TODO The implementation is not completely generic - it assumes that the set +// contains key-value pairs as DenseMap does. +template class EnumSetRangeImpl { + const ArrayRef &Dimension; + SmallVector + Iter; // The iterator for each dimension. + SmallVector Elem; // The current element for each dimension. + bool AtEnd; + +public: + EnumSetRangeImpl(const ArrayRef &Dimension, bool IsAtEnd = false) + : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) { + if (AtEnd) + return; + + const size_t Dim = Dimension.size(); + + // Make room for the iterators and element data. + Iter.resize_for_overwrite(Dim); + Elem.resize_for_overwrite(Dim); + + // Initialize first element. Return if one of the sets is empty. + for (int I = 0, E = Dim; I < E; ++I) { + Iter[I] = Dimension[I].begin(); + if (Iter[I] == Dimension[I].end()) { + AtEnd = true; + break; + } + Elem[I] = Iter[I]->first; + } + } + + EnumSetRangeImpl &operator++() { + assert(!AtEnd && "Incrementing iterator over end"); + for (unsigned I = 0, E = Dimension.size(); I < E; ++I) { + unsigned Idx = E - I - 1; + if (++Iter[Idx] != Dimension[Idx].end()) { + Elem[Idx] = Iter[Idx]->first; + break; + } + + // Overflow in the left most position indicates all elements are + // enumerated. + if (Idx == 0) { + AtEnd = true; + return *this; + } + Iter[Idx] = Dimension[Idx].begin(); + Elem[Idx] = Iter[Idx]->first; + } + return *this; + } + ArrayRef operator*() const { return Elem; } + bool operator!=(const EnumSetRangeImpl &Other) const { + assert(Dimension == Other.Dimension && "Comparing different enumerations"); + if (AtEnd != Other.AtEnd) + return true; + if (AtEnd && Other.AtEnd) + return false; + return Elem != Other.Elem; + } +}; + +// Specialization for sets represented as BitVector. +template <> class EnumSetRangeImpl { + const ArrayRef &Dimension; + SmallVector Elem; + int AtEnd; + +public: + EnumSetRangeImpl(const ArrayRef &Dimension, bool IsAtEnd = false) + : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) { + if (AtEnd) + return; + + const size_t Dim = Dimension.size(); + + // Make room for the element data. + Elem.resize_for_overwrite(Dim); + + // Initialize first element. Return if one of the sets is empty. + for (int I = 0, E = Dim; I < E; ++I) { + int N = Dimension[I].find_first(); + if (N == -1) { + AtEnd = true; + break; + } + Elem[I] = N; + } + } + + EnumSetRangeImpl &operator++() { + assert(!AtEnd && "Incrementing iterator over end"); + for (unsigned I = 0, E = Dimension.size(); I < E; ++I) { + unsigned Idx = E - I - 1; + int N = Dimension[Idx].find_next(Elem[Idx]); + if (N != -1) { + Elem[Idx] = N; + break; + } + + // Overflow in the left most position indicates all elements are + // enumerated. + if (Idx == 0) { + AtEnd = true; + return *this; + } + Elem[Idx] = Dimension[Idx].find_first(); + } + return *this; + } + ArrayRef operator*() const { return Elem; } + bool operator!=(const EnumSetRangeImpl &Other) const { + assert(Dimension == Other.Dimension && "Comparing different enumerations"); + if (AtEnd != Other.AtEnd) + return true; + if (AtEnd && Other.AtEnd) + return false; + return Elem != Other.Elem; + } +}; + +// Specialization for set product of integer intervals. +template <> class EnumSetRangeImpl { + const ArrayRef &Dimension; + SmallVector Elem; + int AtEnd; + +public: + EnumSetRangeImpl(const ArrayRef &Dimension, bool IsAtEnd = false) + : Dimension(Dimension), AtEnd(IsAtEnd || !Dimension.size()) { + if (AtEnd) + return; + + const size_t Dim = Dimension.size(); + + // Make room for the element data. + Elem.resize_for_overwrite(Dim); + + // Initialize first element. Return if one of the sets is empty. + for (int I = 0, E = Dim; I < E; ++I) + Elem[I] = 0; + } + + EnumSetRangeImpl &operator++() { + assert(!AtEnd && "Incrementing iterator over end"); + for (unsigned I = 0, E = Dimension.size(); I < E; ++I) { + unsigned Idx = E - I - 1; + unsigned N = Elem[Idx] + 1; + if (N < Dimension[Idx]) { + Elem[Idx] = N; + break; + } + + // Overflow in the left most position indicates all elements are + // enumerated. + if (Idx == 0) { + AtEnd = true; + return *this; + } + Elem[Idx] = 0; + } + return *this; + } + ArrayRef operator*() const { return Elem; } + bool operator!=(const EnumSetRangeImpl &Other) const { + assert(Dimension == Other.Dimension && "Comparing different enumerations"); + if (AtEnd != Other.AtEnd) + return true; + if (AtEnd && Other.AtEnd) + return false; + return Elem != Other.Elem; + } +}; + +template class EnumSet { + + using iterator = EnumSetRangeImpl; + + const ArrayRef Dimension; + +public: + EnumSet(ArrayRef Dimension) : Dimension(Dimension) {} + iterator begin() { return std::move(iterator(Dimension)); } + iterator end() { return std::move(iterator(Dimension, true)); } +}; + +// Emit a multi-dimensional array. The dimenions are given in array Dim, and the +// data is in array Data. The symbols used for opening and closing parenthesis +// must be provided in Paren. +void emitMultiDimTable(raw_ostream &OS, unsigned Indent, + const ArrayRef Dim, + const ArrayRef Data, StringRef Paren) { + assert(Dim.size() > 0 && "Expected at least one dimension"); + assert(Paren.size() == 2 && "Expected pair of parenthesis"); + const char PO = Paren[0]; + const char PC = Paren[1]; + const unsigned LastDim = Dim[Dim.size() - 1]; + + for (unsigned Idx = 0, End = Data.size(); Idx < End; ++Idx) { + // Emit prefix: either chain of opening parenthesis, or a comma. + if (Idx % LastDim) + OS << ","; + else { + if (Idx) + OS.indent(Indent); + OS << PO; + for (unsigned PrevFac = LastDim, I = 0, E = Dim.size() - 1; I < E; ++I) { + unsigned Fac = PrevFac * Dim[Dim.size() - I - 2]; + if ((Idx % Fac) != 0) + break; + Indent += 2; + OS << "\n"; + OS.indent(Indent) << PO; + PrevFac = Fac; + } + } + + // Emit the data element. + OS << format(" %u", Data[Idx]); + + // Emit chain of closing parenthesis if required. + if ((Idx + 1) % LastDim == 0) { + OS << " " << PC; + for (unsigned PrevFac = LastDim, I = 0, E = Dim.size() - 1; I < E; ++I) { + unsigned Fac = PrevFac * Dim[Dim.size() - I - 2]; + if (((Idx + 1) % Fac) != 0) { + OS << ",\n"; + break; + } + Indent -= 2; + OS << "\n"; + OS.indent(Indent) << PC; + PrevFac = Fac; + } + } + } +} + +// Ouput a BitVector as a sequence of the set bit's number. +raw_ostream &operator<<(raw_ostream &OS, const BitVector &BV) { + int B = BV.find_first(); + if (B != -1) { + OS << B; + while ((B = BV.find_next(B)) != -1) + OS << ", " << B; + } + return OS; +} + +// Compare function to force an order on BitVectors. +bool CmpBitVector(const BitVector *LHS, const BitVector *RHS) { + assert(LHS->size() == RHS->size() && "Comparing BitVectors of different size"); + auto L = LHS->getData(); + auto R = RHS->getData(); + for (unsigned I = 0, E = L.size(); I < E; ++I) { + if (L[I] != R[I]) + return L[I] < R[I]; + } + return false; +} +} // namespace + +class PatternForestBuilder { + // Each bit vector represents a match set (aka a set of patterns). The value + // of the map is the encoding of the match set. + using SetOfSetOfPatterns = DenseMap; + + // Data structure to represent the label and the patterns that appear as the + // j-th child of that label. In Chase's description, a pattern is described as + // A[p_0, ..., p_n]. This structure store A (the instruction), the set of + // patterns appearing as children P_A (for every operand j), and the + // representer set S_A. + struct Label : public FoldingSetNode { + const CodeGenInstruction *Inst; + + // P_A_j is the set of patterns which appears as the j-th child of patterns + // with label A in PF. + OwningArrayRef PA; + + // S_A_j is the set of representer set, basically the intersection of the + // match sets R with P_A_j. + OwningArrayRef SA; + + private: + Label(const CodeGenInstruction *Inst) + : Inst(Inst), PA(Inst->Operands.size() - Inst->Operands.NumDefs), + SA(PA.size()) {} + + public: + static Label *create(const CodeGenInstruction *Inst) { + assert(Inst && "Expected instruction"); + return new Label(Inst); + } + + void Profile(FoldingSetNodeID &ID) const { ID.AddPointer(Inst->TheDef); } + + bool isCommutable() { return Inst->isCommutable; } + + bool isLeaf() { return getNumUseOpnds() == 0; } + + unsigned getNumDefOpnds() const { return Inst->Operands.NumDefs; } + unsigned getNumUseOpnds() const { + return Inst->Operands.size() - Inst->Operands.NumDefs; + } + unsigned getNumOpnds() const { return Inst->Operands.size(); } + + // Update the P_A sets. + void updatePA(ArrayRef Opnds) { + assert(getNumUseOpnds() == Opnds.size() && + "Unexpected number of operands"); + for (unsigned J = 0, E = getNumUseOpnds(); J != E; ++J) { + if (PA[J].size() <= Opnds[J]) + PA[J].resize(Opnds[J] + 1); + PA[J].set(Opnds[J]); + } + } + + // Make sure that the P_A sets all have the same size. + void normalizePA(unsigned NumOfPatterns) { + for (unsigned J = 0, E = PA.size(); J < E; ++J) { + if (PA[J].size() != NumOfPatterns) { + assert(PA[J].size() <= NumOfPatterns && + "P_A_j larger than number of patterns"); + PA[J].resize(NumOfPatterns); + } + } + } + + // Update the representer sets S_A. + // Given a match set MS, calculate MS /\ P_A_j for each operand j, and + // insert the result into S_A_j. Return true if a new element was inserted + // into S_A_j. + bool updateSA(const BitVector &MS) { + bool Changes = false; + for (unsigned J = 0, E = getNumUseOpnds(); J < E; ++J) { + BitVector B(MS); // R + B &= PA[J]; // R /\ P_A_j + if (B.any()) { + if (SA[J].insert(std::pair(B, SA[J].size())).second) + Changes = true; + } + } + return Changes; + } + }; + + // A pattern, consisting of the label and the children (which are also + // patterns). In Chase's paper it is A[p_0, ..., p_n]. Each pattern is encoded + // as an integer. The placeholder * (or v in the paper) is modelled as having + // no label and no children. + struct Pattern : public FoldingSetNode { + const Label *A; + const OwningArrayRef Opnds; + const unsigned Enc; // Numeric encoding of the pattern. + + private: + Pattern(const Label *A, unsigned Enc, ArrayRef Opnds) + : A(A), Opnds(Opnds), Enc(Enc) {} + + public: + static Pattern *create(const Label *A, unsigned Enc, + ArrayRef Opnds) { + return new Pattern(A, Enc, Opnds); + } + + void Profile(FoldingSetNodeID &ID) const { + ID.AddPointer(A); + for (unsigned I = 0, E = Opnds.size(); I < E; ++I) + ID.AddInteger(Opnds[I]); + } + + void dump(); + void writeYAML(raw_ostream &OS, unsigned Indent) const; + }; + + // The labels are singletons. + FoldingSetVector> Labels; + + // Set of all patterns, ordered by encoding. The first slot is the placeholder + // *. + FoldingSet Patterns; + + // Number of patterns. Should always be same as Patterns.size(). + unsigned NumOfPatterns; + + // The set of the calculated match sets R. + SetOfSetOfPatterns MatchSets; + + // Returns the label instance used for the instruction. It ensures that there + // is exactly one label for it. + Label *getLabel(const CodeGenInstruction *Inst); + + // Binding information for matching rules. + SmallVector MatchingRuleInfos; + + // Mapping between pattern encoding and matching rule info. + MapVector> MatchingRules; + + // Look up a pattern using its label and the subpatterns. + Pattern *lookup(Label *A, ArrayRef Opnds); + + // Add the pattern A [ Opnds ] to the pattern forest. + unsigned addPatternToForest(Label *A, ArrayRef Opnds); + + // Update the match set MS with the pattern L [ child patterns ]. + // Returns true if the pattern was found. + bool updateMatchSetWithPattern(BitVector &MS, Label &L, + ArrayRef ChildPatterns); + +#ifndef NDEBUG + // Dump a match set. + template void dumpMS(T Sets, StringRef Name, unsigned No) const; +#endif + +public: + PatternForestBuilder(); + ~PatternForestBuilder(); + void addPattern(StringRef Name, unsigned RootIdx, const GIMatchDag &MatchDag, + void *Data); + void createMatchSets(); + GIMatchTreeAutomaton *createAutomaton(); + void dump() const; + void writeYAML(raw_ostream &OS) const; +}; + +PatternForestBuilder::PatternForestBuilder() : NumOfPatterns(1) { + Patterns.InsertNode(Pattern::create(nullptr, 0, ArrayRef())); +} + +PatternForestBuilder::~PatternForestBuilder() = default; + +PatternForestBuilder::Label * +PatternForestBuilder::getLabel(const CodeGenInstruction *Inst) { + assert(Inst && "Need instruction to create a label"); + FoldingSetNodeID ID; + ID.AddPointer(Inst->TheDef); + void *InsertPoint; + Label *L = Labels.FindNodeOrInsertPos(ID, InsertPoint); + if (L == nullptr) { + L = Label::create(Inst); + Labels.InsertNode(L, InsertPoint); + } + return L; +} + +void PatternForestBuilder::Pattern::dump() { writeYAML(llvm::dbgs(), 0); } + +void PatternForestBuilder::Pattern::writeYAML(raw_ostream &OS, + unsigned Indent) const { + OS.indent(Indent) << "- " << Enc << ": "; + if (A) { + OS << A->Inst->TheDef->getName() << " ["; + for (unsigned I = 0, E = Opnds.size(); I < E; ++I) { + OS << (I ? ", " : " ") << Opnds[I]; + } + OS << " ]"; + } else { + OS << "*"; + } + OS << "\n"; +} + +PatternForestBuilder::Pattern * +PatternForestBuilder::lookup(Label *A, ArrayRef Opnds) { + FoldingSetNodeID ID; + ID.AddPointer(A); + for (unsigned I = 0, E = Opnds.size(); I < E; ++I) + ID.AddInteger(Opnds[I]); + void *InsertPoint; + return Patterns.FindNodeOrInsertPos(ID, InsertPoint); +} + +unsigned PatternForestBuilder::addPatternToForest(Label *A, + ArrayRef Opnds) { + FoldingSetNodeID ID; + ID.AddPointer(A); + for (unsigned I = 0, E = Opnds.size(); I < E; ++I) + ID.AddInteger(Opnds[I]); + void *InsertPoint; + Pattern *P = Patterns.FindNodeOrInsertPos(ID, InsertPoint); + if (P) + return P->Enc; + P = Pattern::create(A, NumOfPatterns, Opnds); + // Udate P_A_j. + A->updatePA(Opnds); + Patterns.InsertNode(P, InsertPoint); + ++NumOfPatterns; + assert(NumOfPatterns == Patterns.size() && "Counters out of sync"); + return P->Enc; +} + +void PatternForestBuilder::addPattern(StringRef Name, unsigned RootIdx, + const GIMatchDag &MatchDag, void *Data) { + // Mapping from GIMatchDagInstr to outgoing GIMatchDagEdges. + DenseMap> Edges; + + // Mapping from GIMatchDagInstr to associated + // GIMatchDagPredicateDependencyEdge. + DenseMap> + PredEdges; + + // Initializes maps. + for (auto *Edge : MatchDag.edges()) { + Edges[Edge->getFromMI()].push_back(Edge); + } + for (auto *PredEdge : MatchDag.predicate_edges()) { + PredEdges[PredEdge->getRequiredMI()].push_back(PredEdge); + } + + // Lambda to find root element. + auto getRoot = [&RootIdx, &MatchDag]() -> const GIMatchDagInstr * { + for (const auto &Root : enumerate(MatchDag.roots())) { + if (Root.index() == RootIdx) + return Root.value(); + } + return nullptr; + }; + + // Lambda to retrieve the opcode predicate for an instruction. + auto getOpcodePredicate = + [&](const GIMatchDagInstr *Instr) -> const GIMatchDagOpcodePredicate * { + for (auto &PredEgde : PredEdges[Instr]) { + if (auto *P = + dyn_cast(PredEgde->getPredicate())) { + assert(PredEgde->getRequiredMO() == nullptr && "Unexpected operand"); + return P; + } + } + return nullptr; + }; + + // Recursive lambda to add all edges of tree. It combines 2 traversals: + // - It adds instruction/variable bindings in pre-order. + // - it adds edges in post-order. + std::function + addEdge; + addEdge = [&](const GIMatchDagInstr *T, GIMatchPatternInfo &Info, + unsigned BaseInstrID, unsigned FromMoIdx, unsigned Mask, + unsigned &Count) -> unsigned { + auto &EdgeList = Edges[T]; + const CodeGenInstruction *Inst = getOpcodePredicate(T)->getInstr(); + Label *A = getLabel(Inst); + const unsigned MaxOpnds = A->getNumOpnds(); + const unsigned DefOpnds = A->getNumDefOpnds(); + BitVector OperandsWithEdge(MaxOpnds); + SmallVector Encoding; + Encoding.resize(MaxOpnds); + + BaseInstrID = Info.add(T, BaseInstrID, FromMoIdx); + + bool SwapOpnds = false; + if (A->isCommutable()) { + SwapOpnds = (Mask & (1 << Count)) != 0; + ++Count; + } + + for (auto &E : EdgeList) { + assert(E->getFromMI() == T && "Wrong edge?"); + + unsigned Idx = E->getFromMO()->getIdx(); + if (SwapOpnds) { + if (Idx == DefOpnds) + Idx = DefOpnds + 1; + else if (Idx == DefOpnds + 1) + Idx = DefOpnds; + } + unsigned Enc = addEdge(E->getToMI(), Info, BaseInstrID, Idx, Mask, Count); + Encoding[Idx] = Enc; + OperandsWithEdge.set(Idx); + } + + SmallVector Opnds; + // Add accepting Opnd nodes for all other operands. + for (auto &Opnd : T->getOperandInfo()) { + if (Opnd.isDef()) + continue; + if (OperandsWithEdge[Opnd.getIdx()]) + Opnds.push_back(Encoding[Opnd.getIdx()]); + else + Opnds.push_back(0); + } + assert(A->getNumUseOpnds() == Opnds.size() && "Wrong number of operands"); + return addPatternToForest(A, Opnds); + }; + + const GIMatchDagInstr *DAGRoot = getRoot(); + assert(DAGRoot != nullptr && "Missing root element of DAG"); + + // If DAAGRoot is an instruction, then traverse all edges originating there. + if (getOpcodePredicate(DAGRoot)) { + GIMatchPatternInfo Info(Name, Data); + unsigned Mask = 0; + unsigned Count = 0; + unsigned Enc = addEdge(DAGRoot, Info, 0, 0, Mask, Count); + unsigned BaseInfoId = MatchingRuleInfos.size(); + MatchingRuleInfos.push_back(Info); + MatchingRules[Enc].push_back(BaseInfoId); + for (unsigned I = 1, E = 1 << Count; I < E; ++I) { + GIMatchPatternInfo Info(Name, Data, true); + Count = 0; + Enc = addEdge(DAGRoot, Info, 0, 0, I, Count); + if (MatchingRules.find(Enc) == MatchingRules.end()) { + unsigned InfoId = MatchingRuleInfos.size(); + MatchingRuleInfos.push_back(Info); + MatchingRules[Enc].push_back(InfoId); + MatchingRuleInfos[BaseInfoId].addVariant(InfoId); + } + } + } + + // Process one-of-opcode predicates. + std::optional InfoId; + SmallVector Opnds; + for (auto *PredEdge : PredEdges[DAGRoot]) { + if (auto *P = dyn_cast( + PredEdge->getPredicate())) { + for (auto *Inst : P->getInstrs()) { + if (!InfoId) { + // All matches share the same (empty) variable bindings. + GIMatchPatternInfo Info(Name, Data); + Info.add(DAGRoot, 0, 0); + InfoId = MatchingRuleInfos.size(); + MatchingRuleInfos.push_back(Info); + } + Label *A = getLabel(Inst); + Opnds.resize(A->getNumUseOpnds()); + unsigned Enc = addPatternToForest(A, Opnds); + MatchingRules[Enc].push_back(*InfoId); + } + } + } +} + +bool PatternForestBuilder::updateMatchSetWithPattern( + BitVector &MS, Label &L, ArrayRef ChildPatterns) { + if (Pattern *P = lookup(&L, ChildPatterns)) { + MS.set(P->Enc); + return true; + } + return false; +} + +#ifndef NDEBUG +template +void PatternForestBuilder::dumpMS(T Sets, StringRef Name, unsigned No) const { + llvm::dbgs() << Name << "_" << No << " =\n"; + for (auto &MS : Sets) { + llvm::dbgs() << llvm::format("%6d", MS.second) << " = { " << MS.first + << " }\n"; + } + llvm::dbgs() << "\n"; +} +#endif + +void PatternForestBuilder::createMatchSets() { + // Normalize P_A_j, the set of patterns that appear as the j-th child of A. + for (auto &L : Labels) + L.normalizePA(NumOfPatterns); + + // Initialize match set for placeholder *. + const BitVector SetOfStar = BitVector(NumOfPatterns).set(0); + MatchSets[SetOfStar] = 0; + LLVM_DEBUG(dumpMS(MatchSets, "R", 0)); + + // Add the match sets for height 0. + for (auto &L : Labels) { + if (L.isLeaf()) { + if (Pattern *P = lookup(&L, ArrayRef())) { + BitVector MS(SetOfStar); + MS.set(P->Enc); + MatchSets.insert(std::pair(MS, MatchSets.size())); + } + } + } + LLVM_DEBUG(dumpMS(MatchSets, "R", 1)); + + // Calculate S_A_j_0. + for (auto &L : Labels) { + for (auto &MS : MatchSets) { + L.updateSA(MS.first); + } + LLVM_DEBUG(for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I) + dumpMS(L.SA[I], Twine("S_A_j_").concat(Twine(I)).str(), 1)); + } + + unsigned H = 2; + // Compute all match sets. + for (bool Changes = true; Changes; ++H) { + Changes = false; + + // Calculation next match set. + for (auto &L : Labels) { + assert(L.SA.size() == L.getNumUseOpnds() && "Size missmatch"); + for (auto PatternSet : EnumSet(L.SA)) { + BitVector MS(NumOfPatterns); + for (auto P : EnumSet(PatternSet)) { + updateMatchSetWithPattern(MS, L, P); + } + if (MS.any()) + MatchSets.insert(std::pair(MS.set(0), MatchSets.size())); + } + } + LLVM_DEBUG(dumpMS(MatchSets, "R", H)); + + // Calculate S_A_j_i. + for (auto &L : Labels) { + for (auto &MS : MatchSets) { + if (L.updateSA(MS.first)) + Changes = true; + } + LLVM_DEBUG( + for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I) + dumpMS(L.SA[I], Twine("S_A_j_").concat(Twine(I)).str(), H)); + } + } + + // TODO The sorting is only required to make the YAML output testable. This + // is a big performance hit! I think it is possible to represent the data in + // YAML file in a different way which can avoid the sorting. + + // Assign a deterministic encoding to the match sets. + // This is not required for the algorithm. It is only used to make the YAML + // output deterministic, to help with testing. + { + std::vector Tmp; + Tmp.reserve(MatchSets.size()); + for (auto &MS : MatchSets) + Tmp.push_back(&MS.first); + std::sort(Tmp.begin(), Tmp.end(), CmpBitVector); + for (auto &[Enc, MS] : enumerate(Tmp)) + MatchSets[*MS] = Enc; + } + // Assign a deterministic encoding to all representer sets. The only + // requirement is that the set only containing the placeholder * gets always + // the encoding 0. + // This is not required for the algorithm. It is only used to make the YAML + // output deterministic, to help with testing. + { + std::vector Tmp; + for (auto &L : Labels) { + for (auto &Sets : L.SA) { + if (Sets.empty()) + continue; + Tmp.clear(); + Tmp.reserve(Sets.size()); + for (auto &Set : Sets) + Tmp.push_back(&Set.first); + std::sort(Tmp.begin(), Tmp.end(), CmpBitVector); + unsigned Base = *Tmp[0] == SetOfStar ? 0 : 1; + for (auto &[Enc, Set] : enumerate(Tmp)) + Sets[*Set] = Base + Enc; + } + } + } +} + +GIMatchTreeAutomaton *PatternForestBuilder::createAutomaton() { + const BitVector SetOfStar = BitVector(NumOfPatterns).set(0); + + const unsigned DimMatchSets = MatchSets.size(); + GIMatchTreeAutomaton *Automaton = new GIMatchTreeAutomaton(DimMatchSets); + for (auto &L : Labels) { + // Handle leafs aka instructions with zero operands. + if (L.isLeaf()) { + // Look up encoding for match set { *, L }. + BitVector MS(SetOfStar); + updateMatchSetWithPattern(MS, L, ArrayRef()); + Automaton->LeafTables.emplace_back(L.Inst, MatchSets[MS]); + continue; + } + + // Handle all other patterns. + auto &SA = L.SA; + SmallVector DimT; + SmallVector, 3> + ChaseToHOD; // Mapping from the Chase set encoding to a HOD match set. + GIMatchTreeAutomaton::Table T; + T.Inst = L.Inst; + T.DimC = L.getNumUseOpnds(); + + // Initialize the compression tables. + T.C = OwningArrayRef(T.DimC * DimMatchSets); + for (unsigned I = 0, E = T.C.size(); I < E; ++I) + T.C[I] = 0; + for (unsigned Op = 0; Op < T.DimC; ++Op) { + DenseMap M(T.DimC); + auto &PAj = L.PA[Op]; + for (auto &[MS, HODSetEnc] : MatchSets) { + BitVector B(MS); + B &= PAj; + auto It = SA[Op].find(B); + if (It != SA[Op].end()) { + unsigned ChaseSetEnc = It->second; + T.C[Op * DimMatchSets + HODSetEnc] = ChaseSetEnc; + M.insert(std::pair(ChaseSetEnc, MS)); + } + } + ChaseToHOD.push_back(M); + } + + // Initialize the state transition table. + unsigned Size = 1; + for (unsigned Op = 0; Op < T.DimC; ++Op) { + unsigned Sz = SA[Op].size(); + // Account for placeholder * if S_A_j does not contain it. + if (SA[Op].find(SetOfStar) == SA[Op].end()) + ++Sz; + Size *= Sz; + DimT.push_back(Sz); + } + T.T = OwningArrayRef(Size); + unsigned TOffset = 0; // Offset into T array. + for (auto OpndsChase : EnumSet(DimT)) { + // OpndsChase[] is Chase set encoding. + // Opnds[] is the Hoffmann/O'Donnel match set. + SmallVector Opnds; + Opnds.resize_for_overwrite(T.DimC); + for (unsigned I = 0; I < T.DimC; ++I) + Opnds[I] = ChaseToHOD[I][OpndsChase[I]]; + + BitVector MS(SetOfStar); + for (auto P : EnumSet(Opnds)) + updateMatchSetWithPattern(MS, L, P); + auto It = MatchSets.find(MS); + if (It != MatchSets.end()) + T.T[TOffset] = It->second; + else + T.T[TOffset] = 0; + ++TOffset; + } + // Check for special case size equals 1. It means that the state transition + // table contains exactly one element. This happens when the only use of a + // non-leaf label has only * appearing as child patterns. E.g. G_AND [*, *]. + // We can treat this similar to a leaf. + if (Size == 1) { + Automaton->LeafTables.emplace_back(L.Inst, T.T[0]); + continue; + } + T.DimT = OwningArrayRef(DimT); + Automaton->Tables.push_back(std::move(T)); + } + + // Add the matching rules. + for (auto &[MS, MSEnc] : MatchSets) { + for (auto R : MatchingRules) { + if (MS[R.first]) { + Automaton->MatchingRules[MSEnc].append(R.second); + } + } + } + Automaton->MatchingRuleInfos = MatchingRuleInfos; + + return Automaton; +} + +void PatternForestBuilder::dump() const { writeYAML(llvm::dbgs()); } + +void PatternForestBuilder::writeYAML(raw_ostream &OS) const { + auto WriteSet = [&OS](BitVector Set) { + OS << "[ " << Set << (Set.any() ? " " : "") << "]"; + }; + auto WriteSetOfSets = [&OS, &WriteSet](SetOfSetOfPatterns Sets, + unsigned Indent) { + SmallVector Tmp; + Tmp.resize_for_overwrite(Sets.size()); + for (auto &MS : Sets) + Tmp[MS.second] = MS.first; + for (auto [Index, MS] : enumerate(Tmp)) { + OS.indent(Indent) << "- " << Index << ": "; + WriteSet(MS); + OS << "\n"; + } + }; + + OS << "PatternForest: # PF\n"; + for (const Pattern &P : Patterns) { + P.writeYAML(OS, 2); + } + OS << "MatchSets: # R\n"; + WriteSetOfSets(MatchSets, 2); + OS << "ChildPatternSets: # P_A\n"; + for (auto &L : Labels) { + OS.indent(2) << L.Inst->TheDef->getName() << ":\n"; + for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I) { + OS.indent(4) << "- " << I << ": "; + WriteSet(L.PA[I]); + OS << "\n"; + } + } + OS << "RepresenterSets: # S_A\n"; + for (auto &L : Labels) { + OS.indent(2) << L.Inst->TheDef->getName() << ":\n"; + for (unsigned I = 0, E = L.getNumUseOpnds(); I < E; ++I) { + OS.indent(4) << "- " << I << ": \n"; + WriteSetOfSets(L.SA[I], 6); + } + } +} + +GIMatchTreeAutomaton::GIMatchTreeAutomaton(unsigned DimMatchSets) + : DimMatchSets(DimMatchSets) {} + +void GIMatchTreeAutomaton::emitTable(raw_ostream &OS, const Table &T, + unsigned Indent) const { + // Emit compression array. + OS.indent(Indent) << "static unsigned C[" << T.DimC << "][" << DimMatchSets + << "] = "; + emitMultiDimTable(OS, Indent, {T.DimC, DimMatchSets}, T.C, "{}"); + OS << ";\n\n"; + + // Emit transition table. + OS.indent(Indent) << "static unsigned T"; + for (unsigned I = 0, E = T.DimT.size(); I < E; ++I) + OS << "[" << T.DimT[I] << "]"; + OS << " = "; + emitMultiDimTable(OS, Indent, T.DimT, T.T, "{}"); + OS << ";\n\n"; +} + +void GIMatchTreeAutomaton::emitTransitions(raw_ostream &OS, + unsigned Indent) const { + // Avoid emitting an empty switch statement. + if (LeafTables.empty() && Tables.empty()) + return; + // Emit code to calculate the match set. + OS.indent(Indent) << "switch (MI.getOpcode()) {\n"; + // First emit the leaf transitions. + for (auto &[Inst, MS] : LeafTables) { + OS.indent(Indent) << "case " << Inst->Namespace + << "::" << Inst->TheDef->getName() << ":\n"; + OS.indent(Indent + 2) << "MS = " << MS << ";\n"; + OS.indent(Indent + 2) << "break;\n"; + } + // Then emit all other transitions. + for (auto &T : Tables) { + OS.indent(Indent) << "case " << T.Inst->Namespace + << "::" << T.Inst->TheDef->getName() << ": {\n"; + for (unsigned I = 0, E = T.DimT.size(); I < E; ++I) { + unsigned OpNo = T.Inst->Operands.NumDefs + I; + OS.indent(Indent + 2) << "unsigned Idx" << I << " = MI.getOperand(" + << OpNo << ").isReg()\n"; + OS.indent(Indent + 2) + << " ? MatchSets[MRI.getVRegDef(MI.getOperand(" + << OpNo << ").getReg())]\n"; + OS.indent(Indent + 2) << " : 0;\n"; + } + OS << "\n"; + emitTable(OS, T, 4); + OS.indent(Indent + 2) << "MS = T"; + for (unsigned I = 0, E = T.DimT.size(); I < E; ++I) + OS << "[C[" << I << "][Idx" << I << "]]"; + OS << ";\n"; + OS.indent(Indent + 2) << "break;\n }\n"; + } + OS.indent(Indent) << "}\n"; +} + +void GIMatchTreeAutomaton::emitRuleMapping(raw_ostream &OS, + unsigned Indent) const { + OwningArrayRef MSToRule(DimMatchSets); + for (auto &I : MSToRule) + I = 0; + SmallVector, 0> Rules; + unsigned SizeOfAllRules = 0; + for (auto &[Idx, MR] : enumerate(getMatchingRules())) { + MSToRule[MR.first] = Idx + 1; + SmallVector RulesToExecute; + BitVector Filter(getMatchingRuleInfos().size() + 1, true); + for (auto PatternRuleID : MR.second) { + if (Filter[PatternRuleID]) { + RulesToExecute.push_back(PatternRuleID); + Filter[PatternRuleID] = false; + } + } + SizeOfAllRules += RulesToExecute.size(); + Rules.push_back(RulesToExecute); + } + // Do not output the tables in case there are no rules to execute. + if (Rules.empty()) + return ; + OS.indent(Indent) << "static const unsigned MSToRule[" << DimMatchSets + << "] = "; + emitMultiDimTable(OS, Indent, {DimMatchSets}, MSToRule, "{}"); + OS << ";\n"; + OS.indent(Indent) << "static const unsigned AllRules[" << SizeOfAllRules + << "] = {"; + for (auto &[Idx, R] : enumerate(Rules)) { + OS.indent(Indent + 2) << "/* " << Idx << " */ "; + for (unsigned Val : R) + OS << Val << ", "; + OS << "\n"; + } + OS.indent(Indent) << "};\n"; + + OS.indent(Indent) << "static const ArrayRef Rules[" + << static_cast(Rules.size() + 1) << "] = {\n"; + OS.indent(Indent + 2) << "/* 0 */ ArrayRef(),\n"; + unsigned Ofs = 0; + for (auto &[Idx, R] : enumerate(Rules)) { + OS.indent(Indent + 2) << "/* " << (Idx + 1) + << " */ ArrayRef(&AllRules[" << Ofs << "], " + << R.size() << "),\n"; + Ofs += R.size(); + } + OS.indent(Indent) << "};\n"; +} + +void GIMatchTreeAutomaton::dump() const { writeYAML(llvm::dbgs()); } + +void GIMatchTreeAutomaton::writeYAML(raw_ostream &OS) const { + OS << "LeafTables:\n"; + for (auto &[Inst, MS] : LeafTables) { + OS << " " << Inst->TheDef->getName() << ": " << MS << "\n"; + } + OS << "Tables:\n"; + for (auto &T : Tables) { + OS << " " << T.Inst->TheDef->getName() << ":\n"; + OS << " C: "; + emitMultiDimTable(OS, 8, {T.DimC, DimMatchSets}, T.C, "[]"); + OS << "\n T: "; + emitMultiDimTable(OS, 8, T.DimT, T.T, "[]"); + OS << "\n"; + } +} + +GIMatchTreeAutomatonBuilder::GIMatchTreeAutomatonBuilder(RecordKeeper &Records) + : Target(Records) { + PFBuilder = std::make_unique(); +} + +void GIMatchTreeAutomatonBuilder::addLeaf(StringRef Name, uint64_t ID, + unsigned RootIdx, + const GIMatchDag &MatchDag, + void *Data) { + PFBuilder->addPattern(Name, RootIdx, MatchDag, Data); +} + +GIMatchTreeAutomatonBuilder::~GIMatchTreeAutomatonBuilder() = default; + +std::unique_ptr GIMatchTreeAutomatonBuilder::run() { + PFBuilder->createMatchSets(); + return std::unique_ptr(PFBuilder->createAutomaton()); +} + +void GIMatchTreeAutomatonBuilder::dump() const { writeYAML(llvm::dbgs()); } + +void GIMatchTreeAutomatonBuilder::writeYAML(raw_ostream &OS) const { + PFBuilder->writeYAML(OS); +} +} // namespace llvm \ No newline at end of file