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