1 //===-- Thumb2ITBlockPass.cpp - Insert Thumb-2 IT blocks ------------------===//
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 #include "ARM.h"
10 #include "ARMMachineFunctionInfo.h"
11 #include "ARMSubtarget.h"
12 #include "MCTargetDesc/ARMBaseInfo.h"
13 #include "Thumb2InstrInfo.h"
14 #include "llvm/ADT/SmallSet.h"
15 #include "llvm/ADT/SmallVector.h"
16 #include "llvm/ADT/Statistic.h"
17 #include "llvm/ADT/StringRef.h"
18 #include "llvm/CodeGen/MachineBasicBlock.h"
19 #include "llvm/CodeGen/MachineFunction.h"
20 #include "llvm/CodeGen/MachineFunctionPass.h"
21 #include "llvm/CodeGen/MachineInstr.h"
22 #include "llvm/CodeGen/MachineInstrBuilder.h"
23 #include "llvm/CodeGen/MachineInstrBundle.h"
24 #include "llvm/CodeGen/MachineOperand.h"
25 #include "llvm/IR/DebugLoc.h"
26 #include "llvm/MC/MCInstrDesc.h"
27 #include "llvm/MC/MCRegisterInfo.h"
28 #include <cassert>
29 #include <new>
30 
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "thumb2-it"
34 
35 STATISTIC(NumITs,        "Number of IT blocks inserted");
36 STATISTIC(NumMovedInsts, "Number of predicated instructions moved");
37 
38 namespace {
39 
40   class Thumb2ITBlockPass : public MachineFunctionPass {
41   public:
42     static char ID;
43 
44     bool restrictIT;
45     const Thumb2InstrInfo *TII;
46     const TargetRegisterInfo *TRI;
47     ARMFunctionInfo *AFI;
48 
49     Thumb2ITBlockPass() : MachineFunctionPass(ID) {}
50 
51     bool runOnMachineFunction(MachineFunction &Fn) override;
52 
53     MachineFunctionProperties getRequiredProperties() const override {
54       return MachineFunctionProperties().set(
55           MachineFunctionProperties::Property::NoVRegs);
56     }
57 
58     StringRef getPassName() const override {
59       return "Thumb IT blocks insertion pass";
60     }
61 
62   private:
63     bool MoveCopyOutOfITBlock(MachineInstr *MI,
64                               ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
65                               SmallSet<unsigned, 4> &Defs,
66                               SmallSet<unsigned, 4> &Uses);
67     bool InsertITInstructions(MachineBasicBlock &MBB);
68   };
69 
70   char Thumb2ITBlockPass::ID = 0;
71 
72 } // end anonymous namespace
73 
74 /// TrackDefUses - Tracking what registers are being defined and used by
75 /// instructions in the IT block. This also tracks "dependencies", i.e. uses
76 /// in the IT block that are defined before the IT instruction.
77 static void TrackDefUses(MachineInstr *MI,
78                          SmallSet<unsigned, 4> &Defs,
79                          SmallSet<unsigned, 4> &Uses,
80                          const TargetRegisterInfo *TRI) {
81   SmallVector<unsigned, 4> LocalDefs;
82   SmallVector<unsigned, 4> LocalUses;
83 
84   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
85     MachineOperand &MO = MI->getOperand(i);
86     if (!MO.isReg())
87       continue;
88     unsigned Reg = MO.getReg();
89     if (!Reg || Reg == ARM::ITSTATE || Reg == ARM::SP)
90       continue;
91     if (MO.isUse())
92       LocalUses.push_back(Reg);
93     else
94       LocalDefs.push_back(Reg);
95   }
96 
97   for (unsigned i = 0, e = LocalUses.size(); i != e; ++i) {
98     unsigned Reg = LocalUses[i];
99     for (MCSubRegIterator Subreg(Reg, TRI, /*IncludeSelf=*/true);
100          Subreg.isValid(); ++Subreg)
101       Uses.insert(*Subreg);
102   }
103 
104   for (unsigned i = 0, e = LocalDefs.size(); i != e; ++i) {
105     unsigned Reg = LocalDefs[i];
106     for (MCSubRegIterator Subreg(Reg, TRI, /*IncludeSelf=*/true);
107          Subreg.isValid(); ++Subreg)
108       Defs.insert(*Subreg);
109     if (Reg == ARM::CPSR)
110       continue;
111   }
112 }
113 
114 /// Clear kill flags for any uses in the given set.  This will likely
115 /// conservatively remove more kill flags than are necessary, but removing them
116 /// is safer than incorrect kill flags remaining on instructions.
117 static void ClearKillFlags(MachineInstr *MI, SmallSet<unsigned, 4> &Uses) {
118   for (MachineOperand &MO : MI->operands()) {
119     if (!MO.isReg() || MO.isDef() || !MO.isKill())
120       continue;
121     if (!Uses.count(MO.getReg()))
122       continue;
123     MO.setIsKill(false);
124   }
125 }
126 
127 static bool isCopy(MachineInstr *MI) {
128   switch (MI->getOpcode()) {
129   default:
130     return false;
131   case ARM::MOVr:
132   case ARM::MOVr_TC:
133   case ARM::tMOVr:
134   case ARM::t2MOVr:
135     return true;
136   }
137 }
138 
139 bool
140 Thumb2ITBlockPass::MoveCopyOutOfITBlock(MachineInstr *MI,
141                                       ARMCC::CondCodes CC, ARMCC::CondCodes OCC,
142                                         SmallSet<unsigned, 4> &Defs,
143                                         SmallSet<unsigned, 4> &Uses) {
144   if (!isCopy(MI))
145     return false;
146   // llvm models select's as two-address instructions. That means a copy
147   // is inserted before a t2MOVccr, etc. If the copy is scheduled in
148   // between selects we would end up creating multiple IT blocks.
149   assert(MI->getOperand(0).getSubReg() == 0 &&
150          MI->getOperand(1).getSubReg() == 0 &&
151          "Sub-register indices still around?");
152 
153   unsigned DstReg = MI->getOperand(0).getReg();
154   unsigned SrcReg = MI->getOperand(1).getReg();
155 
156   // First check if it's safe to move it.
157   if (Uses.count(DstReg) || Defs.count(SrcReg))
158     return false;
159 
160   // If the CPSR is defined by this copy, then we don't want to move it. E.g.,
161   // if we have:
162   //
163   //   movs  r1, r1
164   //   rsb   r1, 0
165   //   movs  r2, r2
166   //   rsb   r2, 0
167   //
168   // we don't want this to be converted to:
169   //
170   //   movs  r1, r1
171   //   movs  r2, r2
172   //   itt   mi
173   //   rsb   r1, 0
174   //   rsb   r2, 0
175   //
176   const MCInstrDesc &MCID = MI->getDesc();
177   if (MI->hasOptionalDef() &&
178       MI->getOperand(MCID.getNumOperands() - 1).getReg() == ARM::CPSR)
179     return false;
180 
181   // Then peek at the next instruction to see if it's predicated on CC or OCC.
182   // If not, then there is nothing to be gained by moving the copy.
183   MachineBasicBlock::iterator I = MI; ++I;
184   MachineBasicBlock::iterator E = MI->getParent()->end();
185   while (I != E && I->isDebugInstr())
186     ++I;
187   if (I != E) {
188     unsigned NPredReg = 0;
189     ARMCC::CondCodes NCC = getITInstrPredicate(*I, NPredReg);
190     if (NCC == CC || NCC == OCC)
191       return true;
192   }
193   return false;
194 }
195 
196 bool Thumb2ITBlockPass::InsertITInstructions(MachineBasicBlock &MBB) {
197   bool Modified = false;
198 
199   SmallSet<unsigned, 4> Defs;
200   SmallSet<unsigned, 4> Uses;
201   MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
202   while (MBBI != E) {
203     MachineInstr *MI = &*MBBI;
204     DebugLoc dl = MI->getDebugLoc();
205     unsigned PredReg = 0;
206     ARMCC::CondCodes CC = getITInstrPredicate(*MI, PredReg);
207     if (CC == ARMCC::AL) {
208       ++MBBI;
209       continue;
210     }
211 
212     Defs.clear();
213     Uses.clear();
214     TrackDefUses(MI, Defs, Uses, TRI);
215 
216     // Insert an IT instruction.
217     MachineInstrBuilder MIB = BuildMI(MBB, MBBI, dl, TII->get(ARM::t2IT))
218       .addImm(CC);
219 
220     // Add implicit use of ITSTATE to IT block instructions.
221     MI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
222                                              true/*isImp*/, false/*isKill*/));
223 
224     MachineInstr *LastITMI = MI;
225     MachineBasicBlock::iterator InsertPos = MIB.getInstr();
226     ++MBBI;
227 
228     // Form IT block.
229     ARMCC::CondCodes OCC = ARMCC::getOppositeCondition(CC);
230     unsigned Mask = 0, Pos = 3;
231 
232     // v8 IT blocks are limited to one conditional op unless -arm-no-restrict-it
233     // is set: skip the loop
234     if (!restrictIT) {
235       // Branches, including tricky ones like LDM_RET, need to end an IT
236       // block so check the instruction we just put in the block.
237       for (; MBBI != E && Pos &&
238              (!MI->isBranch() && !MI->isReturn()) ; ++MBBI) {
239         if (MBBI->isDebugInstr())
240           continue;
241 
242         MachineInstr *NMI = &*MBBI;
243         MI = NMI;
244 
245         unsigned NPredReg = 0;
246         ARMCC::CondCodes NCC = getITInstrPredicate(*NMI, NPredReg);
247         if (NCC == CC || NCC == OCC) {
248           Mask |= (NCC & 1) << Pos;
249           // Add implicit use of ITSTATE.
250           NMI->addOperand(MachineOperand::CreateReg(ARM::ITSTATE, false/*ifDef*/,
251                                                  true/*isImp*/, false/*isKill*/));
252           LastITMI = NMI;
253         } else {
254           if (NCC == ARMCC::AL &&
255               MoveCopyOutOfITBlock(NMI, CC, OCC, Defs, Uses)) {
256             --MBBI;
257             MBB.remove(NMI);
258             MBB.insert(InsertPos, NMI);
259             ClearKillFlags(MI, Uses);
260             ++NumMovedInsts;
261             continue;
262           }
263           break;
264         }
265         TrackDefUses(NMI, Defs, Uses, TRI);
266         --Pos;
267       }
268     }
269 
270     // Finalize IT mask.
271     Mask |= (1 << Pos);
272     // Tag along (firstcond[0] << 4) with the mask.
273     Mask |= (CC & 1) << 4;
274     MIB.addImm(Mask);
275 
276     // Last instruction in IT block kills ITSTATE.
277     LastITMI->findRegisterUseOperand(ARM::ITSTATE)->setIsKill();
278 
279     // Finalize the bundle.
280     finalizeBundle(MBB, InsertPos.getInstrIterator(),
281                    ++LastITMI->getIterator());
282 
283     Modified = true;
284     ++NumITs;
285   }
286 
287   return Modified;
288 }
289 
290 bool Thumb2ITBlockPass::runOnMachineFunction(MachineFunction &Fn) {
291   const ARMSubtarget &STI =
292       static_cast<const ARMSubtarget &>(Fn.getSubtarget());
293   if (!STI.isThumb2())
294     return false;
295   AFI = Fn.getInfo<ARMFunctionInfo>();
296   TII = static_cast<const Thumb2InstrInfo *>(STI.getInstrInfo());
297   TRI = STI.getRegisterInfo();
298   restrictIT = STI.restrictIT();
299 
300   if (!AFI->isThumbFunction())
301     return false;
302 
303   bool Modified = false;
304   for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; ) {
305     MachineBasicBlock &MBB = *MFI;
306     ++MFI;
307     Modified |= InsertITInstructions(MBB);
308   }
309 
310   if (Modified)
311     AFI->setHasITBlocks(true);
312 
313   return Modified;
314 }
315 
316 /// createThumb2ITBlockPass - Returns an instance of the Thumb2 IT blocks
317 /// insertion pass.
318 FunctionPass *llvm::createThumb2ITBlockPass() {
319   return new Thumb2ITBlockPass();
320 }
321