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 @@ -45,10 +45,14 @@ /// modifications it makes to the MIR to the GISelChangeObserver and the /// observer subclass will act on these events. In this case, instruction /// erasure will cancel any future visits to the erased instruction and -/// instruction creation will schedule that instruction for a future visit. +/// instruction creation and change will schedule that instruction for a future +/// visit. In addition, all instructions which lay on paths between the +/// created/changed instructions and the scheduled instructions are scheduled +/// for a revisit. /// Other Combiner implementations may require more complex behaviour from /// their GISelChangeObserver subclass. class WorkListMaintainer : public GISelChangeObserver { + MachineRegisterInfo *MRI; using WorkListTy = GISelWorkList<512>; WorkListTy &WorkList; /// The instructions that have been created but we want to report once they @@ -57,8 +61,11 @@ SetVector CreatedInstrs; #endif + SmallVector, 512> WorkStack; + public: - WorkListMaintainer(WorkListTy &WorkList) : WorkList(WorkList) {} + WorkListMaintainer(MachineRegisterInfo *MRI, WorkListTy &WorkList) + : MRI(MRI), WorkList(WorkList) {} virtual ~WorkListMaintainer() = default; void erasingInstr(MachineInstr &MI) override { @@ -67,16 +74,16 @@ } void createdInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Creating: " << MI << "\n"); - WorkList.insert(&MI); + WorkStack.emplace_back(&MI, false); LLVM_DEBUG(CreatedInstrs.insert(&MI)); } void changingInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Changing: " << MI << "\n"); - WorkList.insert(&MI); + // No need to record the annoucement. } void changedInstr(MachineInstr &MI) override { LLVM_DEBUG(dbgs() << "Changed: " << MI << "\n"); - WorkList.insert(&MI); + WorkStack.emplace_back(&MI, false); } void reportFullyCreatedInstrs() { @@ -87,8 +94,37 @@ }); LLVM_DEBUG(CreatedInstrs.clear()); } + + // For each changed/created node, add 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. + void updateWorklist() { + SmallPtrSet Visited; + + while (!WorkStack.empty()) { + auto &MIFlagPair = WorkStack.back(); + MachineInstr *MI = MIFlagPair.first; + if (WorkList.contains(MI)) { + WorkStack.pop_back(); + } else if (MIFlagPair.second) { + WorkStack.pop_back(); + WorkList.insert(MI); + } else if (!Visited.contains(MI)) { + Visited.insert(MI); + MIFlagPair.second = true; + for (auto Op : MI->operands()) { + if (!Op.isReg() || !Op.isDef()) + continue; + for (auto &UseMI : MRI->use_nodbg_instructions(Op.getReg())) + WorkStack.emplace_back(&UseMI, false); + } + } else + WorkStack.pop_back(); + } + } }; -} +} // namespace Combiner::Combiner(CombinerInfo &Info, const TargetPassConfig *TPC) : CInfo(Info), TPC(TPC) { @@ -117,6 +153,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,7 +161,7 @@ // down RPOT. Changed = false; GISelWorkList<512> WorkList; - WorkListMaintainer Observer(WorkList); + WorkListMaintainer Observer(MRI, WorkList); GISelObserverWrapper WrapperObserver(&Observer); if (CSEInfo) WrapperObserver.addObserver(CSEInfo); @@ -143,11 +180,13 @@ } } 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.updateWorklist(); Observer.reportFullyCreatedInstrs(); } MFChanged |= 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,127 @@ +// 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-DAG: - [[MS0:[0-9]+]]: [ 0 ] +// CHECK-DAG: - [[MS1:[0-9]+]]: [ 0, 1 ] +// CHECK-DAG: - [[MS2:[0-9]+]]: [ 0, 2 ] +// CHECK-DAG: - [[MS3:[0-9]+]]: [ 0, 3 ] +// CHECK-DAG: - [[MS4:[0-9]+]]: [ 0, 4 ] +// CHECK-DAG: - [[MS5:[0-9]+]]: [ 0, 5 ] +// CHECK-DAG: - [[MS6:[0-9]+]]: [ 0, 2, 5 ] +// CHECK-DAG: - [[MS7:[0-9]+]]: [ 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-DAG: - [ 0 ] +// CHECK-DAG: - [ 0, 1 ] +// CHECK-DAG: - [ 0, 2 ] +// CHECK-DAG: - [ 0, 5 ] +// CHECK-DAG: - [ 0, 2, 5 ] +// CHECK-NEXT: - 1: +// CHECK-DAG: - [ 0 ] +// CHECK-DAG: - [ 0, 1 ] +// CHECK-DAG: - [ 0, 4 ] +// CHECK-NEXT: B: +// CHECK-NEXT: C: +// CHECK-NEXT:LeafTables: +// CHECK-DAG: B: [[MS1]] +// CHECK-DAG: C: [[MS4]] +// CHECK-NEXT:Tables: +// CHECK-NEXT: A: +// CHECK-NEXT: C: +// CHECK-DAG: - [ 0, [[MS0]], [[X00:[0-9]+]] ] +// CHECK-DAG: - [ 0, [[MS1]], [[X01:[0-9]+]] ] +// CHECK-DAG: - [ 0, [[MS2]], [[X02:[0-9]+]] ] +// CHECK-DAG: - [ 0, [[MS3]], [[X00]] ] +// CHECK-DAG: - [ 0, [[MS4]], [[X00]] ] +// CHECK-DAG: - [ 0, [[MS5]], [[X03:[0-9]+]] ] +// CHECK-DAG: - [ 0, [[MS6]], [[X04:[0-9]+]] ] +// CHECK-DAG: - [ 0, [[MS7]], [[X03]] ] +// CHECK-DAG: - [ 1, [[MS0]], [[X10:[0-9]+]] ] +// CHECK-DAG: - [ 1, [[MS1]], [[X11:[0-9]+]] ] +// CHECK-DAG: - [ 1, [[MS2]], [[X10]] ] +// CHECK-DAG: - [ 1, [[MS3]], [[X10]] ] +// CHECK-DAG: - [ 1, [[MS4]], [[X12:[0-9]+]] ] +// CHECK-DAG: - [ 1, [[MS5]], [[X10]] ] +// CHECK-DAG: - [ 1, [[MS6]], [[X10]] ] +// CHECK-DAG: - [ 1, [[MS7]], [[X10]] ] +// CHECK-NEXT: T: +// CHECK-DAG: - [ [[X00]], [[X10]], [[MS0]] ] +// CHECK-DAG: - [ [[X00]], [[X11]], [[MS0]] ] +// CHECK-DAG: - [ [[X00]], [[X12]], [[MS5]] ] +// CHECK-DAG: - [ [[X01]], [[X10]], [[MS2]] ] +// CHECK-DAG: - [ [[X01]], [[X11]], [[MS2]] ] +// CHECK-DAG: - [ [[X01]], [[X12]], [[MS6]] ] +// CHECK-DAG: - [ [[X02]], [[X10]], [[MS0]] ] +// CHECK-DAG: - [ [[X02]], [[X11]], [[MS3]] ] +// CHECK-DAG: - [ [[X02]], [[X12]], [[MS5]] ] +// CHECK-DAG: - [ [[X03]], [[X10]], [[MS0]] ] +// CHECK-DAG: - [ [[X03]], [[X11]], [[MS0]] ] +// CHECK-DAG: - [ [[X03]], [[X12]], [[MS7]] ] +// CHECK-DAG: - [ [[X04]], [[X10]], [[MS0]] ] +// CHECK-DAG: - [ [[X04]], [[X11]], [[MS3]] ] +// CHECK-DAG: - [ [[X04]], [[X12]], [[MS7]] ] 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" @@ -53,6 +54,10 @@ "gicombiner-stop-after-build", cl::desc("Stop processing after building the match tree"), cl::cat(GICombinerEmitterCat)); +static cl::opt CompactYAML( + "gicombiner-compact-yaml", + cl::desc("Use compact representation of tables in YAML"), + cl::cat(GICombinerEmitterCat)); namespace { typedef uint64_t RuleID; @@ -68,22 +73,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 +604,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 +707,72 @@ } } -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); - OS << Indent << "// Rule: " << RuleDef.getName() << "\n" - << Indent << "if (!RuleConfig->isRuleDisabled(" << Rule->getID() - << ")) {\n"; + // Emit code to execute a rule. + if (TreeAutomaton.getMatchingRuleInfos().empty()) + return; + OS.indent(Indent) << "for (const unsigned *PatternRuleID = MSToRule[MS]; ; ++PatternRuleID) {\n"; + OS.indent(Indent + 2) << "switch (*PatternRuleID) {\n"; + OS.indent(Indent + 2) << "case 0:\n"; + OS.indent(Indent + 4) << "return false;\n"; + for (auto &[Idx, Info] : enumerate(TreeAutomaton.getMatchingRuleInfos())) { + if (Info.isVariant()) + continue; + OS.indent(Indent + 2) << "case " << (Idx+1) << ":\n"; + for (unsigned VariantId : Info.getVariants()) { + OS.indent(Indent + 2) << "case " << (VariantId+1) << ":\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 +784,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 +808,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 +826,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 +877,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(), CompactYAML); PrintNote(Combiner->getLoc(), "Terminating due to -gicombiner-stop-after-build"); return; @@ -941,6 +937,7 @@ OS << "RuleConfig(&RuleConfig) {}\n" << "\n" << " bool tryCombineAll(\n" + << " DenseMap &MatchSets,\n" << " GISelChangeObserver &Observer,\n" << " MachineInstr &MI,\n" << " MachineIRBuilder &B"; @@ -1034,6 +1031,7 @@ << "}\n\n"; OS << "bool " << getClassName() << "::tryCombineAll(\n" + << " DenseMap &MatchSets,\n" << " GISelChangeObserver &Observer,\n" << " MachineInstr &MI,\n" << " MachineIRBuilder &B"; @@ -1051,8 +1049,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, bool Compact = false) 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,1204 @@ +//===- 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 FoldingVector. +/// Each pattern is given a numeric encoding. The set of all subpatterns, +/// called the pattern forest, is also implemented using 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 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) + 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. + + (b) + 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. + + (c) + 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; +} +} // 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. + FoldingSet