1 //===- MacroFusion.cpp - Macro Fusion -------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file This file contains the implementation of the DAG scheduling mutation 10 /// to pair instructions back to back. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/MacroFusion.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/Statistic.h" 17 #include "llvm/CodeGen/MachineInstr.h" 18 #include "llvm/CodeGen/MachineScheduler.h" 19 #include "llvm/CodeGen/ScheduleDAG.h" 20 #include "llvm/CodeGen/ScheduleDAGMutation.h" 21 #include "llvm/CodeGen/TargetInstrInfo.h" 22 #include "llvm/Support/CommandLine.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/raw_ostream.h" 25 26 #define DEBUG_TYPE "machine-scheduler" 27 28 STATISTIC(NumFused, "Number of instr pairs fused"); 29 30 using namespace llvm; 31 32 static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden, 33 cl::desc("Enable scheduling for macro fusion."), cl::init(true)); 34 35 static bool isHazard(const SDep &Dep) { 36 return Dep.getKind() == SDep::Anti || Dep.getKind() == SDep::Output; 37 } 38 39 static bool fuseInstructionPair(ScheduleDAGMI &DAG, SUnit &FirstSU, 40 SUnit &SecondSU) { 41 // Check that neither instr is already paired with another along the edge 42 // between them. 43 for (SDep &SI : FirstSU.Succs) 44 if (SI.isCluster()) 45 return false; 46 47 for (SDep &SI : SecondSU.Preds) 48 if (SI.isCluster()) 49 return false; 50 // Though the reachability checks above could be made more generic, 51 // perhaps as part of ScheduleDAGMI::addEdge(), since such edges are valid, 52 // the extra computation cost makes it less interesting in general cases. 53 54 // Create a single weak edge between the adjacent instrs. The only effect is 55 // to cause bottom-up scheduling to heavily prioritize the clustered instrs. 56 if (!DAG.addEdge(&SecondSU, SDep(&FirstSU, SDep::Cluster))) 57 return false; 58 59 // Adjust the latency between both instrs. 60 for (SDep &SI : FirstSU.Succs) 61 if (SI.getSUnit() == &SecondSU) 62 SI.setLatency(0); 63 64 for (SDep &SI : SecondSU.Preds) 65 if (SI.getSUnit() == &FirstSU) 66 SI.setLatency(0); 67 68 LLVM_DEBUG( 69 dbgs() << "Macro fuse: "; DAG.dumpNodeName(FirstSU); dbgs() << " - "; 70 DAG.dumpNodeName(SecondSU); dbgs() << " / "; 71 dbgs() << DAG.TII->getName(FirstSU.getInstr()->getOpcode()) << " - " 72 << DAG.TII->getName(SecondSU.getInstr()->getOpcode()) << '\n';); 73 74 // Make data dependencies from the FirstSU also dependent on the SecondSU to 75 // prevent them from being scheduled between the FirstSU and the SecondSU. 76 if (&SecondSU != &DAG.ExitSU) 77 for (const SDep &SI : FirstSU.Succs) { 78 SUnit *SU = SI.getSUnit(); 79 if (SI.isWeak() || isHazard(SI) || 80 SU == &DAG.ExitSU || SU == &SecondSU || SU->isPred(&SecondSU)) 81 continue; 82 LLVM_DEBUG(dbgs() << " Bind "; DAG.dumpNodeName(SecondSU); 83 dbgs() << " - "; DAG.dumpNodeName(*SU); dbgs() << '\n';); 84 DAG.addEdge(SU, SDep(&SecondSU, SDep::Artificial)); 85 } 86 87 // Make the FirstSU also dependent on the dependencies of the SecondSU to 88 // prevent them from being scheduled between the FirstSU and the SecondSU. 89 if (&FirstSU != &DAG.EntrySU) { 90 for (const SDep &SI : SecondSU.Preds) { 91 SUnit *SU = SI.getSUnit(); 92 if (SI.isWeak() || isHazard(SI) || &FirstSU == SU || FirstSU.isSucc(SU)) 93 continue; 94 LLVM_DEBUG(dbgs() << " Bind "; DAG.dumpNodeName(*SU); dbgs() << " - "; 95 DAG.dumpNodeName(FirstSU); dbgs() << '\n';); 96 DAG.addEdge(&FirstSU, SDep(SU, SDep::Artificial)); 97 } 98 // ExitSU comes last by design, which acts like an implicit dependency 99 // between ExitSU and any bottom root in the graph. We should transfer 100 // this to FirstSU as well. 101 if (&SecondSU == &DAG.ExitSU) { 102 for (SUnit &SU : DAG.SUnits) { 103 if (SU.Succs.empty()) 104 DAG.addEdge(&FirstSU, SDep(&SU, SDep::Artificial)); 105 } 106 } 107 } 108 109 ++NumFused; 110 return true; 111 } 112 113 namespace { 114 115 /// Post-process the DAG to create cluster edges between instrs that may 116 /// be fused by the processor into a single operation. 117 class MacroFusion : public ScheduleDAGMutation { 118 ShouldSchedulePredTy shouldScheduleAdjacent; 119 bool FuseBlock; 120 bool scheduleAdjacentImpl(ScheduleDAGMI &DAG, SUnit &AnchorSU); 121 122 public: 123 MacroFusion(ShouldSchedulePredTy shouldScheduleAdjacent, bool FuseBlock) 124 : shouldScheduleAdjacent(shouldScheduleAdjacent), FuseBlock(FuseBlock) {} 125 126 void apply(ScheduleDAGInstrs *DAGInstrs) override; 127 }; 128 129 } // end anonymous namespace 130 131 void MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) { 132 ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs); 133 134 if (FuseBlock) 135 // For each of the SUnits in the scheduling block, try to fuse the instr in 136 // it with one in its predecessors. 137 for (SUnit &ISU : DAG->SUnits) 138 scheduleAdjacentImpl(*DAG, ISU); 139 140 if (DAG->ExitSU.getInstr()) 141 // Try to fuse the instr in the ExitSU with one in its predecessors. 142 scheduleAdjacentImpl(*DAG, DAG->ExitSU); 143 } 144 145 /// Implement the fusion of instr pairs in the scheduling DAG, 146 /// anchored at the instr in AnchorSU.. 147 bool MacroFusion::scheduleAdjacentImpl(ScheduleDAGMI &DAG, SUnit &AnchorSU) { 148 const MachineInstr &AnchorMI = *AnchorSU.getInstr(); 149 const TargetInstrInfo &TII = *DAG.TII; 150 const TargetSubtargetInfo &ST = DAG.MF.getSubtarget(); 151 152 // Check if the anchor instr may be fused. 153 if (!shouldScheduleAdjacent(TII, ST, nullptr, AnchorMI)) 154 return false; 155 156 // Explorer for fusion candidates among the dependencies of the anchor instr. 157 for (SDep &Dep : AnchorSU.Preds) { 158 // Ignore dependencies other than data or strong ordering. 159 if (Dep.isWeak() || isHazard(Dep)) 160 continue; 161 162 SUnit &DepSU = *Dep.getSUnit(); 163 if (DepSU.isBoundaryNode()) 164 continue; 165 166 const MachineInstr *DepMI = DepSU.getInstr(); 167 if (!shouldScheduleAdjacent(TII, ST, DepMI, AnchorMI)) 168 continue; 169 170 if (fuseInstructionPair(DAG, DepSU, AnchorSU)) 171 return true; 172 } 173 174 return false; 175 } 176 177 std::unique_ptr<ScheduleDAGMutation> 178 llvm::createMacroFusionDAGMutation( 179 ShouldSchedulePredTy shouldScheduleAdjacent) { 180 if(EnableMacroFusion) 181 return llvm::make_unique<MacroFusion>(shouldScheduleAdjacent, true); 182 return nullptr; 183 } 184 185 std::unique_ptr<ScheduleDAGMutation> 186 llvm::createBranchMacroFusionDAGMutation( 187 ShouldSchedulePredTy shouldScheduleAdjacent) { 188 if(EnableMacroFusion) 189 return llvm::make_unique<MacroFusion>(shouldScheduleAdjacent, false); 190 return nullptr; 191 } 192