1 //===- AArch64MacroFusion.cpp - AArch64 Macro Fusion ----------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // \file This file contains the AArch64 implementation of the DAG scheduling mutation
11 // to pair instructions back to back.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "AArch64MacroFusion.h"
16 #include "AArch64Subtarget.h"
17 #include "llvm/ADT/Statistic.h"
18 #include "llvm/Support/CommandLine.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 
21 #define DEBUG_TYPE "misched"
22 
23 STATISTIC(NumFused, "Number of instr pairs fused");
24 
25 using namespace llvm;
26 
27 static cl::opt<bool> EnableMacroFusion("aarch64-misched-fusion", cl::Hidden,
28   cl::desc("Enable scheduling for macro fusion."), cl::init(true));
29 
30 namespace {
31 
32 /// \brief Verify that the instruction pair, First and Second,
33 /// should be scheduled back to back.  Given an anchor instruction, if the other
34 /// instruction is unspecified, then verify that the anchor instruction may be
35 /// part of a pair at all.
36 static bool shouldScheduleAdjacent(const AArch64InstrInfo &TII,
37                                    const AArch64Subtarget &ST,
38                                    const MachineInstr *First,
39                                    const MachineInstr *Second) {
40   assert((First || Second) && "At least one instr must be specified");
41   unsigned FirstOpcode =
42     First ? First->getOpcode()
43 	  : static_cast<unsigned>(AArch64::INSTRUCTION_LIST_END);
44   unsigned SecondOpcode =
45     Second ? Second->getOpcode()
46            : static_cast<unsigned>(AArch64::INSTRUCTION_LIST_END);
47 
48   if (ST.hasArithmeticBccFusion())
49     // Fuse CMN, CMP, TST followed by Bcc.
50     if (SecondOpcode == AArch64::Bcc)
51       switch (FirstOpcode) {
52       default:
53         return false;
54       case AArch64::ADDSWri:
55       case AArch64::ADDSWrr:
56       case AArch64::ADDSXri:
57       case AArch64::ADDSXrr:
58       case AArch64::ANDSWri:
59       case AArch64::ANDSWrr:
60       case AArch64::ANDSXri:
61       case AArch64::ANDSXrr:
62       case AArch64::SUBSWri:
63       case AArch64::SUBSWrr:
64       case AArch64::SUBSXri:
65       case AArch64::SUBSXrr:
66       case AArch64::BICSWrr:
67       case AArch64::BICSXrr:
68         return true;
69       case AArch64::ADDSWrs:
70       case AArch64::ADDSXrs:
71       case AArch64::ANDSWrs:
72       case AArch64::ANDSXrs:
73       case AArch64::SUBSWrs:
74       case AArch64::SUBSXrs:
75       case AArch64::BICSWrs:
76       case AArch64::BICSXrs:
77         // Shift value can be 0 making these behave like the "rr" variant...
78         return !TII.hasShiftedReg(*First);
79       case AArch64::INSTRUCTION_LIST_END:
80         return true;
81       }
82 
83   if (ST.hasArithmeticCbzFusion())
84     // Fuse ALU operations followed by CBZ/CBNZ.
85     if (SecondOpcode == AArch64::CBNZW || SecondOpcode == AArch64::CBNZX ||
86         SecondOpcode == AArch64::CBZW || SecondOpcode == AArch64::CBZX)
87       switch (FirstOpcode) {
88       default:
89         return false;
90       case AArch64::ADDWri:
91       case AArch64::ADDWrr:
92       case AArch64::ADDXri:
93       case AArch64::ADDXrr:
94       case AArch64::ANDWri:
95       case AArch64::ANDWrr:
96       case AArch64::ANDXri:
97       case AArch64::ANDXrr:
98       case AArch64::EORWri:
99       case AArch64::EORWrr:
100       case AArch64::EORXri:
101       case AArch64::EORXrr:
102       case AArch64::ORRWri:
103       case AArch64::ORRWrr:
104       case AArch64::ORRXri:
105       case AArch64::ORRXrr:
106       case AArch64::SUBWri:
107       case AArch64::SUBWrr:
108       case AArch64::SUBXri:
109       case AArch64::SUBXrr:
110         return true;
111       case AArch64::ADDWrs:
112       case AArch64::ADDXrs:
113       case AArch64::ANDWrs:
114       case AArch64::ANDXrs:
115       case AArch64::SUBWrs:
116       case AArch64::SUBXrs:
117       case AArch64::BICWrs:
118       case AArch64::BICXrs:
119         // Shift value can be 0 making these behave like the "rr" variant...
120         return !TII.hasShiftedReg(*First);
121       case AArch64::INSTRUCTION_LIST_END:
122         return true;
123       }
124 
125   if (ST.hasFuseAES())
126     // Fuse AES crypto operations.
127     switch(FirstOpcode) {
128     // AES encode.
129     case AArch64::AESErr:
130       return SecondOpcode == AArch64::AESMCrr ||
131              SecondOpcode == AArch64::INSTRUCTION_LIST_END;
132     // AES decode.
133     case AArch64::AESDrr:
134       return SecondOpcode == AArch64::AESIMCrr ||
135              SecondOpcode == AArch64::INSTRUCTION_LIST_END;
136     }
137 
138   if (ST.hasFuseLiterals())
139     // Fuse literal generation operations.
140     switch (FirstOpcode) {
141     // PC relative address.
142     case AArch64::ADRP:
143       return SecondOpcode == AArch64::ADDXri ||
144              SecondOpcode == AArch64::INSTRUCTION_LIST_END;
145     // 32 bit immediate.
146     case AArch64::MOVZWi:
147       return (SecondOpcode == AArch64::MOVKWi &&
148               Second->getOperand(3).getImm() == 16) ||
149              SecondOpcode == AArch64::INSTRUCTION_LIST_END;
150     // Lower half of 64 bit immediate.
151     case AArch64::MOVZXi:
152       return (SecondOpcode == AArch64::MOVKXi &&
153               Second->getOperand(3).getImm() == 16) ||
154              SecondOpcode == AArch64::INSTRUCTION_LIST_END;
155     // Upper half of 64 bit immediate.
156     case AArch64::MOVKXi:
157       return First->getOperand(3).getImm() == 32 &&
158              ((SecondOpcode == AArch64::MOVKXi &&
159                Second->getOperand(3).getImm() == 48) ||
160               SecondOpcode == AArch64::INSTRUCTION_LIST_END);
161     }
162 
163   return false;
164 }
165 
166 /// \brief Implement the fusion of instruction pairs in the scheduling
167 /// DAG, anchored at the instruction in ASU. Preds
168 /// indicates if its dependencies in \param APreds are predecessors instead of
169 /// successors.
170 static bool scheduleAdjacentImpl(ScheduleDAGMI *DAG, SUnit *ASU,
171                                  SmallVectorImpl<SDep> &APreds, bool Preds) {
172   const AArch64InstrInfo *TII = static_cast<const AArch64InstrInfo *>(DAG->TII);
173   const AArch64Subtarget &ST = DAG->MF.getSubtarget<AArch64Subtarget>();
174 
175   const MachineInstr *AMI = ASU->getInstr();
176   if (!AMI || AMI->isPseudo() || AMI->isTransient() ||
177       (Preds && !shouldScheduleAdjacent(*TII, ST, nullptr, AMI)) ||
178       (!Preds && !shouldScheduleAdjacent(*TII, ST, AMI, nullptr)))
179     return false;
180 
181   for (SDep &BDep : APreds) {
182     if (BDep.isWeak())
183       continue;
184 
185     SUnit *BSU = BDep.getSUnit();
186     const MachineInstr *BMI = BSU->getInstr();
187     if (!BMI || BMI->isPseudo() || BMI->isTransient() ||
188         (Preds && !shouldScheduleAdjacent(*TII, ST, BMI, AMI)) ||
189         (!Preds && !shouldScheduleAdjacent(*TII, ST, AMI, BMI)))
190       continue;
191 
192     // Create a single weak edge between the adjacent instrs. The only
193     // effect is to cause bottom-up scheduling to heavily prioritize the
194     // clustered instrs.
195     if (Preds)
196       DAG->addEdge(ASU, SDep(BSU, SDep::Cluster));
197     else
198       DAG->addEdge(BSU, SDep(ASU, SDep::Cluster));
199 
200     // Adjust the latency between the 1st instr and its predecessors/successors.
201     for (SDep &Dep : APreds)
202       if (Dep.getSUnit() == BSU)
203         Dep.setLatency(0);
204 
205     // Adjust the latency between the 2nd instr and its successors/predecessors.
206     auto &BSuccs = Preds ? BSU->Succs : BSU->Preds;
207     for (SDep &Dep : BSuccs)
208       if (Dep.getSUnit() == ASU)
209         Dep.setLatency(0);
210 
211     ++NumFused;
212     DEBUG(dbgs() << "Macro fuse ";
213           Preds ? BSU->print(dbgs(), DAG) : ASU->print(dbgs(), DAG);
214           dbgs() << " - ";
215           Preds ? ASU->print(dbgs(), DAG) : BSU->print(dbgs(), DAG);
216           dbgs() << '\n');
217 
218     return true;
219   }
220 
221   return false;
222 }
223 
224 /// \brief Post-process the DAG to create cluster edges between instructions
225 /// that may be fused by the processor into a single operation.
226 class AArch64MacroFusion : public ScheduleDAGMutation {
227 public:
228   AArch64MacroFusion() {}
229 
230   void apply(ScheduleDAGInstrs *DAGInstrs) override;
231 };
232 
233 void AArch64MacroFusion::apply(ScheduleDAGInstrs *DAGInstrs) {
234   ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
235 
236   // For each of the SUnits in the scheduling block, try to fuse the instruction
237   // in it with one in its successors.
238   for (SUnit &ASU : DAG->SUnits)
239     scheduleAdjacentImpl(DAG, &ASU, ASU.Succs, false);
240 
241   // Try to fuse the instruction in the ExitSU with one in its predecessors.
242   scheduleAdjacentImpl(DAG, &DAG->ExitSU, DAG->ExitSU.Preds, true);
243 }
244 
245 } // end namespace
246 
247 
248 namespace llvm {
249 
250 std::unique_ptr<ScheduleDAGMutation> createAArch64MacroFusionDAGMutation () {
251   return EnableMacroFusion ? make_unique<AArch64MacroFusion>() : nullptr;
252 }
253 
254 } // end namespace llvm
255