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