1//===-- Thumb2SizeReduction.cpp - Thumb2 code size reduction pass -*- C++ -*-=//
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 "ARMBaseInstrInfo.h"
11#include "ARMSubtarget.h"
12#include "MCTargetDesc/ARMBaseInfo.h"
13#include "Thumb2InstrInfo.h"
14#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/PostOrderIterator.h"
16#include "llvm/ADT/STLExtras.h"
17#include "llvm/ADT/SmallSet.h"
18#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/ADT/StringRef.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineFunction.h"
23#include "llvm/CodeGen/MachineFunctionPass.h"
24#include "llvm/CodeGen/MachineInstr.h"
25#include "llvm/CodeGen/MachineInstrBuilder.h"
26#include "llvm/CodeGen/MachineOperand.h"
27#include "llvm/CodeGen/TargetInstrInfo.h"
28#include "llvm/IR/DebugLoc.h"
29#include "llvm/IR/Function.h"
30#include "llvm/MC/MCInstrDesc.h"
31#include "llvm/MC/MCRegisterInfo.h"
32#include "llvm/Support/CommandLine.h"
33#include "llvm/Support/Compiler.h"
34#include "llvm/Support/Debug.h"
35#include "llvm/Support/ErrorHandling.h"
36#include "llvm/Support/raw_ostream.h"
37#include <algorithm>
38#include <cassert>
39#include <cstdint>
40#include <functional>
41#include <iterator>
42#include <utility>
43
44using namespace llvm;
45
46#define DEBUG_TYPE "t2-reduce-size"
47#define THUMB2_SIZE_REDUCE_NAME "Thumb2 instruction size reduce pass"
48
49STATISTIC(NumNarrows,  "Number of 32-bit instrs reduced to 16-bit ones");
50STATISTIC(Num2Addrs,   "Number of 32-bit instrs reduced to 2addr 16-bit ones");
51STATISTIC(NumLdSts,    "Number of 32-bit load / store reduced to 16-bit ones");
52
53static cl::opt<int> ReduceLimit("t2-reduce-limit",
54                                cl::init(-1), cl::Hidden);
55static cl::opt<int> ReduceLimit2Addr("t2-reduce-limit2",
56                                     cl::init(-1), cl::Hidden);
57static cl::opt<int> ReduceLimitLdSt("t2-reduce-limit3",
58                                     cl::init(-1), cl::Hidden);
59
60namespace {
61
62  /// ReduceTable - A static table with information on mapping from wide
63  /// opcodes to narrow
64  struct ReduceEntry {
65    uint16_t WideOpc;      // Wide opcode
66    uint16_t NarrowOpc1;   // Narrow opcode to transform to
67    uint16_t NarrowOpc2;   // Narrow opcode when it's two-address
68    uint8_t  Imm1Limit;    // Limit of immediate field (bits)
69    uint8_t  Imm2Limit;    // Limit of immediate field when it's two-address
70    unsigned LowRegs1 : 1; // Only possible if low-registers are used
71    unsigned LowRegs2 : 1; // Only possible if low-registers are used (2addr)
72    unsigned PredCC1  : 2; // 0 - If predicated, cc is on and vice versa.
73                           // 1 - No cc field.
74                           // 2 - Always set CPSR.
75    unsigned PredCC2  : 2;
76    unsigned PartFlag : 1; // 16-bit instruction does partial flag update
77    unsigned Special  : 1; // Needs to be dealt with specially
78    unsigned AvoidMovs: 1; // Avoid movs with shifter operand (for Swift)
79  };
80
81  static const ReduceEntry ReduceTable[] = {
82  // Wide,        Narrow1,      Narrow2,     imm1,imm2, lo1, lo2, P/C,PF,S,AM
83  { ARM::t2ADCrr, 0,            ARM::tADC,     0,   0,   0,   1,  0,0, 0,0,0 },
84  { ARM::t2ADDri, ARM::tADDi3,  ARM::tADDi8,   3,   8,   1,   1,  0,0, 0,1,0 },
85  { ARM::t2ADDrr, ARM::tADDrr,  ARM::tADDhirr, 0,   0,   1,   0,  0,1, 0,0,0 },
86  { ARM::t2ADDSri,ARM::tADDi3,  ARM::tADDi8,   3,   8,   1,   1,  2,2, 0,1,0 },
87  { ARM::t2ADDSrr,ARM::tADDrr,  0,             0,   0,   1,   0,  2,0, 0,1,0 },
88  { ARM::t2ANDrr, 0,            ARM::tAND,     0,   0,   0,   1,  0,0, 1,0,0 },
89  { ARM::t2ASRri, ARM::tASRri,  0,             5,   0,   1,   0,  0,0, 1,0,1 },
90  { ARM::t2ASRrr, 0,            ARM::tASRrr,   0,   0,   0,   1,  0,0, 1,0,1 },
91  { ARM::t2BICrr, 0,            ARM::tBIC,     0,   0,   0,   1,  0,0, 1,0,0 },
92  //FIXME: Disable CMN, as CCodes are backwards from compare expectations
93  //{ ARM::t2CMNrr, ARM::tCMN,  0,             0,   0,   1,   0,  2,0, 0,0,0 },
94  { ARM::t2CMNzrr, ARM::tCMNz,  0,             0,   0,   1,   0,  2,0, 0,0,0 },
95  { ARM::t2CMPri, ARM::tCMPi8,  0,             8,   0,   1,   0,  2,0, 0,0,0 },
96  { ARM::t2CMPrr, ARM::tCMPhir, 0,             0,   0,   0,   0,  2,0, 0,1,0 },
97  { ARM::t2EORrr, 0,            ARM::tEOR,     0,   0,   0,   1,  0,0, 1,0,0 },
98  // FIXME: adr.n immediate offset must be multiple of 4.
99  //{ ARM::t2LEApcrelJT,ARM::tLEApcrelJT, 0,   0,   0,   1,   0,  1,0, 0,0,0 },
100  { ARM::t2LSLri, ARM::tLSLri,  0,             5,   0,   1,   0,  0,0, 1,0,1 },
101  { ARM::t2LSLrr, 0,            ARM::tLSLrr,   0,   0,   0,   1,  0,0, 1,0,1 },
102  { ARM::t2LSRri, ARM::tLSRri,  0,             5,   0,   1,   0,  0,0, 1,0,1 },
103  { ARM::t2LSRrr, 0,            ARM::tLSRrr,   0,   0,   0,   1,  0,0, 1,0,1 },
104  { ARM::t2MOVi,  ARM::tMOVi8,  0,             8,   0,   1,   0,  0,0, 1,0,0 },
105  { ARM::t2MOVi16,ARM::tMOVi8,  0,             8,   0,   1,   0,  0,0, 1,1,0 },
106  // FIXME: Do we need the 16-bit 'S' variant?
107  { ARM::t2MOVr,ARM::tMOVr,     0,             0,   0,   0,   0,  1,0, 0,0,0 },
108  { ARM::t2MUL,   0,            ARM::tMUL,     0,   0,   0,   1,  0,0, 1,0,0 },
109  { ARM::t2MVNr,  ARM::tMVN,    0,             0,   0,   1,   0,  0,0, 0,0,0 },
110  { ARM::t2ORRrr, 0,            ARM::tORR,     0,   0,   0,   1,  0,0, 1,0,0 },
111  { ARM::t2REV,   ARM::tREV,    0,             0,   0,   1,   0,  1,0, 0,0,0 },
112  { ARM::t2REV16, ARM::tREV16,  0,             0,   0,   1,   0,  1,0, 0,0,0 },
113  { ARM::t2REVSH, ARM::tREVSH,  0,             0,   0,   1,   0,  1,0, 0,0,0 },
114  { ARM::t2RORrr, 0,            ARM::tROR,     0,   0,   0,   1,  0,0, 1,0,0 },
115  { ARM::t2RSBri, ARM::tRSB,    0,             0,   0,   1,   0,  0,0, 0,1,0 },
116  { ARM::t2RSBSri,ARM::tRSB,    0,             0,   0,   1,   0,  2,0, 0,1,0 },
117  { ARM::t2SBCrr, 0,            ARM::tSBC,     0,   0,   0,   1,  0,0, 0,0,0 },
118  { ARM::t2SUBri, ARM::tSUBi3,  ARM::tSUBi8,   3,   8,   1,   1,  0,0, 0,0,0 },
119  { ARM::t2SUBrr, ARM::tSUBrr,  0,             0,   0,   1,   0,  0,0, 0,0,0 },
120  { ARM::t2SUBSri,ARM::tSUBi3,  ARM::tSUBi8,   3,   8,   1,   1,  2,2, 0,0,0 },
121  { ARM::t2SUBSrr,ARM::tSUBrr,  0,             0,   0,   1,   0,  2,0, 0,0,0 },
122  { ARM::t2SXTB,  ARM::tSXTB,   0,             0,   0,   1,   0,  1,0, 0,1,0 },
123  { ARM::t2SXTH,  ARM::tSXTH,   0,             0,   0,   1,   0,  1,0, 0,1,0 },
124  { ARM::t2TEQrr, ARM::tEOR,    0,             0,   0,   1,   0,  2,0, 0,1,0 },
125  { ARM::t2TSTrr, ARM::tTST,    0,             0,   0,   1,   0,  2,0, 0,0,0 },
126  { ARM::t2UXTB,  ARM::tUXTB,   0,             0,   0,   1,   0,  1,0, 0,1,0 },
127  { ARM::t2UXTH,  ARM::tUXTH,   0,             0,   0,   1,   0,  1,0, 0,1,0 },
128
129  // FIXME: Clean this up after splitting each Thumb load / store opcode
130  // into multiple ones.
131  { ARM::t2LDRi12,ARM::tLDRi,   ARM::tLDRspi,  5,   8,   1,   0,  0,0, 0,1,0 },
132  { ARM::t2LDRs,  ARM::tLDRr,   0,             0,   0,   1,   0,  0,0, 0,1,0 },
133  { ARM::t2LDRBi12,ARM::tLDRBi, 0,             5,   0,   1,   0,  0,0, 0,1,0 },
134  { ARM::t2LDRBs, ARM::tLDRBr,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
135  { ARM::t2LDRHi12,ARM::tLDRHi, 0,             5,   0,   1,   0,  0,0, 0,1,0 },
136  { ARM::t2LDRHs, ARM::tLDRHr,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
137  { ARM::t2LDRSBs,ARM::tLDRSB,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
138  { ARM::t2LDRSHs,ARM::tLDRSH,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
139  { ARM::t2LDR_POST,ARM::tLDMIA_UPD,0,         0,   0,   1,   0,  0,0, 0,1,0 },
140  { ARM::t2STRi12,ARM::tSTRi,   ARM::tSTRspi,  5,   8,   1,   0,  0,0, 0,1,0 },
141  { ARM::t2STRs,  ARM::tSTRr,   0,             0,   0,   1,   0,  0,0, 0,1,0 },
142  { ARM::t2STRBi12,ARM::tSTRBi, 0,             5,   0,   1,   0,  0,0, 0,1,0 },
143  { ARM::t2STRBs, ARM::tSTRBr,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
144  { ARM::t2STRHi12,ARM::tSTRHi, 0,             5,   0,   1,   0,  0,0, 0,1,0 },
145  { ARM::t2STRHs, ARM::tSTRHr,  0,             0,   0,   1,   0,  0,0, 0,1,0 },
146  { ARM::t2STR_POST,ARM::tSTMIA_UPD,0,         0,   0,   1,   0,  0,0, 0,1,0 },
147
148  { ARM::t2LDMIA, ARM::tLDMIA,  0,             0,   0,   1,   1,  1,1, 0,1,0 },
149  { ARM::t2LDMIA_RET,0,         ARM::tPOP_RET, 0,   0,   1,   1,  1,1, 0,1,0 },
150  { ARM::t2LDMIA_UPD,ARM::tLDMIA_UPD,ARM::tPOP,0,   0,   1,   1,  1,1, 0,1,0 },
151  // ARM::t2STMIA (with no basereg writeback) has no Thumb1 equivalent.
152  // tSTMIA_UPD is a change in semantics which can only be used if the base
153  // register is killed. This difference is correctly handled elsewhere.
154  { ARM::t2STMIA, ARM::tSTMIA_UPD, 0,          0,   0,   1,   1,  1,1, 0,1,0 },
155  { ARM::t2STMIA_UPD,ARM::tSTMIA_UPD, 0,       0,   0,   1,   1,  1,1, 0,1,0 },
156  { ARM::t2STMDB_UPD, 0,        ARM::tPUSH,    0,   0,   1,   1,  1,1, 0,1,0 }
157  };
158
159  class Thumb2SizeReduce : public MachineFunctionPass {
160  public:
161    static char ID;
162
163    const Thumb2InstrInfo *TII;
164    const ARMSubtarget *STI;
165
166    Thumb2SizeReduce(std::function<bool(const Function &)> Ftor = nullptr);
167
168    bool runOnMachineFunction(MachineFunction &MF) override;
169
170    MachineFunctionProperties getRequiredProperties() const override {
171      return MachineFunctionProperties().set(
172          MachineFunctionProperties::Property::NoVRegs);
173    }
174
175    StringRef getPassName() const override {
176      return THUMB2_SIZE_REDUCE_NAME;
177    }
178
179  private:
180    /// ReduceOpcodeMap - Maps wide opcode to index of entry in ReduceTable.
181    DenseMap<unsigned, unsigned> ReduceOpcodeMap;
182
183    bool canAddPseudoFlagDep(MachineInstr *Use, bool IsSelfLoop);
184
185    bool VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
186                         bool is2Addr, ARMCC::CondCodes Pred,
187                         bool LiveCPSR, bool &HasCC, bool &CCDead);
188
189    bool ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
190                         const ReduceEntry &Entry);
191
192    bool ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
193                       const ReduceEntry &Entry, bool LiveCPSR, bool IsSelfLoop);
194
195    /// ReduceTo2Addr - Reduce a 32-bit instruction to a 16-bit two-address
196    /// instruction.
197    bool ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
198                       const ReduceEntry &Entry, bool LiveCPSR,
199                       bool IsSelfLoop);
200
201    /// ReduceToNarrow - Reduce a 32-bit instruction to a 16-bit
202    /// non-two-address instruction.
203    bool ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
204                        const ReduceEntry &Entry, bool LiveCPSR,
205                        bool IsSelfLoop);
206
207    /// ReduceMI - Attempt to reduce MI, return true on success.
208    bool ReduceMI(MachineBasicBlock &MBB, MachineInstr *MI,
209                  bool LiveCPSR, bool IsSelfLoop);
210
211    /// ReduceMBB - Reduce width of instructions in the specified basic block.
212    bool ReduceMBB(MachineBasicBlock &MBB);
213
214    bool OptimizeSize;
215    bool MinimizeSize;
216
217    // Last instruction to define CPSR in the current block.
218    MachineInstr *CPSRDef;
219    // Was CPSR last defined by a high latency instruction?
220    // When CPSRDef is null, this refers to CPSR defs in predecessors.
221    bool HighLatencyCPSR;
222
223    struct MBBInfo {
224      // The flags leaving this block have high latency.
225      bool HighLatencyCPSR = false;
226      // Has this block been visited yet?
227      bool Visited = false;
228
229      MBBInfo() = default;
230    };
231
232    SmallVector<MBBInfo, 8> BlockInfo;
233
234    std::function<bool(const Function &)> PredicateFtor;
235  };
236
237  char Thumb2SizeReduce::ID = 0;
238
239} // end anonymous namespace
240
241INITIALIZE_PASS(Thumb2SizeReduce, DEBUG_TYPE, THUMB2_SIZE_REDUCE_NAME, false,
242                false)
243
244Thumb2SizeReduce::Thumb2SizeReduce(std::function<bool(const Function &)> Ftor)
245    : MachineFunctionPass(ID), PredicateFtor(std::move(Ftor)) {
246  OptimizeSize = MinimizeSize = false;
247  for (unsigned i = 0, e = array_lengthof(ReduceTable); i != e; ++i) {
248    unsigned FromOpc = ReduceTable[i].WideOpc;
249    if (!ReduceOpcodeMap.insert(std::make_pair(FromOpc, i)).second)
250      llvm_unreachable("Duplicated entries?");
251  }
252}
253
254static bool HasImplicitCPSRDef(const MCInstrDesc &MCID) {
255  for (const MCPhysReg *Regs = MCID.getImplicitDefs(); *Regs; ++Regs)
256    if (*Regs == ARM::CPSR)
257      return true;
258  return false;
259}
260
261// Check for a likely high-latency flag def.
262static bool isHighLatencyCPSR(MachineInstr *Def) {
263  switch(Def->getOpcode()) {
264  case ARM::FMSTAT:
265  case ARM::tMUL:
266    return true;
267  }
268  return false;
269}
270
271/// canAddPseudoFlagDep - For A9 (and other out-of-order) implementations,
272/// the 's' 16-bit instruction partially update CPSR. Abort the
273/// transformation to avoid adding false dependency on last CPSR setting
274/// instruction which hurts the ability for out-of-order execution engine
275/// to do register renaming magic.
276/// This function checks if there is a read-of-write dependency between the
277/// last instruction that defines the CPSR and the current instruction. If there
278/// is, then there is no harm done since the instruction cannot be retired
279/// before the CPSR setting instruction anyway.
280/// Note, we are not doing full dependency analysis here for the sake of compile
281/// time. We're not looking for cases like:
282/// r0 = muls ...
283/// r1 = add.w r0, ...
284/// ...
285///    = mul.w r1
286/// In this case it would have been ok to narrow the mul.w to muls since there
287/// are indirect RAW dependency between the muls and the mul.w
288bool
289Thumb2SizeReduce::canAddPseudoFlagDep(MachineInstr *Use, bool FirstInSelfLoop) {
290  // Disable the check for -Oz (aka OptimizeForSizeHarder).
291  if (MinimizeSize || !STI->avoidCPSRPartialUpdate())
292    return false;
293
294  if (!CPSRDef)
295    // If this BB loops back to itself, conservatively avoid narrowing the
296    // first instruction that does partial flag update.
297    return HighLatencyCPSR || FirstInSelfLoop;
298
299  SmallSet<unsigned, 2> Defs;
300  for (const MachineOperand &MO : CPSRDef->operands()) {
301    if (!MO.isReg() || MO.isUndef() || MO.isUse())
302      continue;
303    Register Reg = MO.getReg();
304    if (Reg == 0 || Reg == ARM::CPSR)
305      continue;
306    Defs.insert(Reg);
307  }
308
309  for (const MachineOperand &MO : Use->operands()) {
310    if (!MO.isReg() || MO.isUndef() || MO.isDef())
311      continue;
312    Register Reg = MO.getReg();
313    if (Defs.count(Reg))
314      return false;
315  }
316
317  // If the current CPSR has high latency, try to avoid the false dependency.
318  if (HighLatencyCPSR)
319    return true;
320
321  // tMOVi8 usually doesn't start long dependency chains, and there are a lot
322  // of them, so always shrink them when CPSR doesn't have high latency.
323  if (Use->getOpcode() == ARM::t2MOVi ||
324      Use->getOpcode() == ARM::t2MOVi16)
325    return false;
326
327  // No read-after-write dependency. The narrowing will add false dependency.
328  return true;
329}
330
331bool
332Thumb2SizeReduce::VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
333                                  bool is2Addr, ARMCC::CondCodes Pred,
334                                  bool LiveCPSR, bool &HasCC, bool &CCDead) {
335  if ((is2Addr  && Entry.PredCC2 == 0) ||
336      (!is2Addr && Entry.PredCC1 == 0)) {
337    if (Pred == ARMCC::AL) {
338      // Not predicated, must set CPSR.
339      if (!HasCC) {
340        // Original instruction was not setting CPSR, but CPSR is not
341        // currently live anyway. It's ok to set it. The CPSR def is
342        // dead though.
343        if (!LiveCPSR) {
344          HasCC = true;
345          CCDead = true;
346          return true;
347        }
348        return false;
349      }
350    } else {
351      // Predicated, must not set CPSR.
352      if (HasCC)
353        return false;
354    }
355  } else if ((is2Addr  && Entry.PredCC2 == 2) ||
356             (!is2Addr && Entry.PredCC1 == 2)) {
357    /// Old opcode has an optional def of CPSR.
358    if (HasCC)
359      return true;
360    // If old opcode does not implicitly define CPSR, then it's not ok since
361    // these new opcodes' CPSR def is not meant to be thrown away. e.g. CMP.
362    if (!HasImplicitCPSRDef(MI->getDesc()))
363      return false;
364    HasCC = true;
365  } else {
366    // 16-bit instruction does not set CPSR.
367    if (HasCC)
368      return false;
369  }
370
371  return true;
372}
373
374static bool VerifyLowRegs(MachineInstr *MI) {
375  unsigned Opc = MI->getOpcode();
376  bool isPCOk = (Opc == ARM::t2LDMIA_RET || Opc == ARM::t2LDMIA_UPD);
377  bool isLROk = (Opc == ARM::t2STMDB_UPD);
378  bool isSPOk = isPCOk || isLROk;
379  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
380    const MachineOperand &MO = MI->getOperand(i);
381    if (!MO.isReg() || MO.isImplicit())
382      continue;
383    Register Reg = MO.getReg();
384    if (Reg == 0 || Reg == ARM::CPSR)
385      continue;
386    if (isPCOk && Reg == ARM::PC)
387      continue;
388    if (isLROk && Reg == ARM::LR)
389      continue;
390    if (Reg == ARM::SP) {
391      if (isSPOk)
392        continue;
393      if (i == 1 && (Opc == ARM::t2LDRi12 || Opc == ARM::t2STRi12))
394        // Special case for these ldr / str with sp as base register.
395        continue;
396    }
397    if (!isARMLowRegister(Reg))
398      return false;
399  }
400  return true;
401}
402
403bool
404Thumb2SizeReduce::ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
405                                  const ReduceEntry &Entry) {
406  if (ReduceLimitLdSt != -1 && ((int)NumLdSts >= ReduceLimitLdSt))
407    return false;
408
409  unsigned Scale = 1;
410  bool HasImmOffset = false;
411  bool HasShift = false;
412  bool HasOffReg = true;
413  bool isLdStMul = false;
414  unsigned Opc = Entry.NarrowOpc1;
415  unsigned OpNum = 3; // First 'rest' of operands.
416  uint8_t  ImmLimit = Entry.Imm1Limit;
417
418  switch (Entry.WideOpc) {
419  default:
420    llvm_unreachable("Unexpected Thumb2 load / store opcode!");
421  case ARM::t2LDRi12:
422  case ARM::t2STRi12:
423    if (MI->getOperand(1).getReg() == ARM::SP) {
424      Opc = Entry.NarrowOpc2;
425      ImmLimit = Entry.Imm2Limit;
426    }
427
428    Scale = 4;
429    HasImmOffset = true;
430    HasOffReg = false;
431    break;
432  case ARM::t2LDRBi12:
433  case ARM::t2STRBi12:
434    HasImmOffset = true;
435    HasOffReg = false;
436    break;
437  case ARM::t2LDRHi12:
438  case ARM::t2STRHi12:
439    Scale = 2;
440    HasImmOffset = true;
441    HasOffReg = false;
442    break;
443  case ARM::t2LDRs:
444  case ARM::t2LDRBs:
445  case ARM::t2LDRHs:
446  case ARM::t2LDRSBs:
447  case ARM::t2LDRSHs:
448  case ARM::t2STRs:
449  case ARM::t2STRBs:
450  case ARM::t2STRHs:
451    HasShift = true;
452    OpNum = 4;
453    break;
454  case ARM::t2LDR_POST:
455  case ARM::t2STR_POST: {
456    if (!MinimizeSize)
457      return false;
458
459    if (!MI->hasOneMemOperand() ||
460        (*MI->memoperands_begin())->getAlignment() < 4)
461      return false;
462
463    // We're creating a completely different type of load/store - LDM from LDR.
464    // For this reason we can't reuse the logic at the end of this function; we
465    // have to implement the MI building here.
466    bool IsStore = Entry.WideOpc == ARM::t2STR_POST;
467    Register Rt = MI->getOperand(IsStore ? 1 : 0).getReg();
468    Register Rn = MI->getOperand(IsStore ? 0 : 1).getReg();
469    unsigned Offset = MI->getOperand(3).getImm();
470    unsigned PredImm = MI->getOperand(4).getImm();
471    Register PredReg = MI->getOperand(5).getReg();
472    assert(isARMLowRegister(Rt));
473    assert(isARMLowRegister(Rn));
474
475    if (Offset != 4)
476      return false;
477
478    // Add the 16-bit load / store instruction.
479    DebugLoc dl = MI->getDebugLoc();
480    auto MIB = BuildMI(MBB, MI, dl, TII->get(Entry.NarrowOpc1))
481                   .addReg(Rn, RegState::Define)
482                   .addReg(Rn)
483                   .addImm(PredImm)
484                   .addReg(PredReg)
485                   .addReg(Rt, IsStore ? 0 : RegState::Define);
486
487    // Transfer memoperands.
488    MIB.setMemRefs(MI->memoperands());
489
490    // Transfer MI flags.
491    MIB.setMIFlags(MI->getFlags());
492
493    // Kill the old instruction.
494    MI->eraseFromBundle();
495    ++NumLdSts;
496    return true;
497  }
498  case ARM::t2LDMIA: {
499    Register BaseReg = MI->getOperand(0).getReg();
500    assert(isARMLowRegister(BaseReg));
501
502    // For the non-writeback version (this one), the base register must be
503    // one of the registers being loaded.
504    bool isOK = false;
505    for (unsigned i = 3; i < MI->getNumOperands(); ++i) {
506      if (MI->getOperand(i).getReg() == BaseReg) {
507        isOK = true;
508        break;
509      }
510    }
511
512    if (!isOK)
513      return false;
514
515    OpNum = 0;
516    isLdStMul = true;
517    break;
518  }
519  case ARM::t2STMIA:
520    // If the base register is killed, we don't care what its value is after the
521    // instruction, so we can use an updating STMIA.
522    if (!MI->getOperand(0).isKill())
523      return false;
524
525    break;
526  case ARM::t2LDMIA_RET: {
527    Register BaseReg = MI->getOperand(1).getReg();
528    if (BaseReg != ARM::SP)
529      return false;
530    Opc = Entry.NarrowOpc2; // tPOP_RET
531    OpNum = 2;
532    isLdStMul = true;
533    break;
534  }
535  case ARM::t2LDMIA_UPD:
536  case ARM::t2STMIA_UPD:
537  case ARM::t2STMDB_UPD: {
538    OpNum = 0;
539
540    Register BaseReg = MI->getOperand(1).getReg();
541    if (BaseReg == ARM::SP &&
542        (Entry.WideOpc == ARM::t2LDMIA_UPD ||
543         Entry.WideOpc == ARM::t2STMDB_UPD)) {
544      Opc = Entry.NarrowOpc2; // tPOP or tPUSH
545      OpNum = 2;
546    } else if (!isARMLowRegister(BaseReg) ||
547               (Entry.WideOpc != ARM::t2LDMIA_UPD &&
548                Entry.WideOpc != ARM::t2STMIA_UPD)) {
549      return false;
550    }
551
552    isLdStMul = true;
553    break;
554  }
555  }
556
557  unsigned OffsetReg = 0;
558  bool OffsetKill = false;
559  bool OffsetInternal = false;
560  if (HasShift) {
561    OffsetReg  = MI->getOperand(2).getReg();
562    OffsetKill = MI->getOperand(2).isKill();
563    OffsetInternal = MI->getOperand(2).isInternalRead();
564
565    if (MI->getOperand(3).getImm())
566      // Thumb1 addressing mode doesn't support shift.
567      return false;
568  }
569
570  unsigned OffsetImm = 0;
571  if (HasImmOffset) {
572    OffsetImm = MI->getOperand(2).getImm();
573    unsigned MaxOffset = ((1 << ImmLimit) - 1) * Scale;
574
575    if ((OffsetImm & (Scale - 1)) || OffsetImm > MaxOffset)
576      // Make sure the immediate field fits.
577      return false;
578  }
579
580  // Add the 16-bit load / store instruction.
581  DebugLoc dl = MI->getDebugLoc();
582  MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, TII->get(Opc));
583
584  // tSTMIA_UPD takes a defining register operand. We've already checked that
585  // the register is killed, so mark it as dead here.
586  if (Entry.WideOpc == ARM::t2STMIA)
587    MIB.addReg(MI->getOperand(0).getReg(), RegState::Define | RegState::Dead);
588
589  if (!isLdStMul) {
590    MIB.add(MI->getOperand(0));
591    MIB.add(MI->getOperand(1));
592
593    if (HasImmOffset)
594      MIB.addImm(OffsetImm / Scale);
595
596    assert((!HasShift || OffsetReg) && "Invalid so_reg load / store address!");
597
598    if (HasOffReg)
599      MIB.addReg(OffsetReg, getKillRegState(OffsetKill) |
600                            getInternalReadRegState(OffsetInternal));
601  }
602
603  // Transfer the rest of operands.
604  for (unsigned e = MI->getNumOperands(); OpNum != e; ++OpNum)
605    MIB.add(MI->getOperand(OpNum));
606
607  // Transfer memoperands.
608  MIB.setMemRefs(MI->memoperands());
609
610  // Transfer MI flags.
611  MIB.setMIFlags(MI->getFlags());
612
613  LLVM_DEBUG(errs() << "Converted 32-bit: " << *MI
614                    << "       to 16-bit: " << *MIB);
615
616  MBB.erase_instr(MI);
617  ++NumLdSts;
618  return true;
619}
620
621bool
622Thumb2SizeReduce::ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
623                                const ReduceEntry &Entry,
624                                bool LiveCPSR, bool IsSelfLoop) {
625  unsigned Opc = MI->getOpcode();
626  if (Opc == ARM::t2ADDri) {
627    // If the source register is SP, try to reduce to tADDrSPi, otherwise
628    // it's a normal reduce.
629    if (MI->getOperand(1).getReg() != ARM::SP) {
630      if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, IsSelfLoop))
631        return true;
632      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
633    }
634    // Try to reduce to tADDrSPi.
635    unsigned Imm = MI->getOperand(2).getImm();
636    // The immediate must be in range, the destination register must be a low
637    // reg, the predicate must be "always" and the condition flags must not
638    // be being set.
639    if (Imm & 3 || Imm > 1020)
640      return false;
641    if (!isARMLowRegister(MI->getOperand(0).getReg()))
642      return false;
643    if (MI->getOperand(3).getImm() != ARMCC::AL)
644      return false;
645    const MCInstrDesc &MCID = MI->getDesc();
646    if (MCID.hasOptionalDef() &&
647        MI->getOperand(MCID.getNumOperands()-1).getReg() == ARM::CPSR)
648      return false;
649
650    MachineInstrBuilder MIB =
651        BuildMI(MBB, MI, MI->getDebugLoc(),
652                TII->get(ARM::tADDrSPi))
653            .add(MI->getOperand(0))
654            .add(MI->getOperand(1))
655            .addImm(Imm / 4) // The tADDrSPi has an implied scale by four.
656            .add(predOps(ARMCC::AL));
657
658    // Transfer MI flags.
659    MIB.setMIFlags(MI->getFlags());
660
661    LLVM_DEBUG(errs() << "Converted 32-bit: " << *MI
662                      << "       to 16-bit: " << *MIB);
663
664    MBB.erase_instr(MI);
665    ++NumNarrows;
666    return true;
667  }
668
669  if (Entry.LowRegs1 && !VerifyLowRegs(MI))
670    return false;
671
672  if (MI->mayLoadOrStore())
673    return ReduceLoadStore(MBB, MI, Entry);
674
675  switch (Opc) {
676  default: break;
677  case ARM::t2ADDSri:
678  case ARM::t2ADDSrr: {
679    unsigned PredReg = 0;
680    if (getInstrPredicate(*MI, PredReg) == ARMCC::AL) {
681      switch (Opc) {
682      default: break;
683      case ARM::t2ADDSri:
684        if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, IsSelfLoop))
685          return true;
686        LLVM_FALLTHROUGH;
687      case ARM::t2ADDSrr:
688        return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
689      }
690    }
691    break;
692  }
693  case ARM::t2RSBri:
694  case ARM::t2RSBSri:
695  case ARM::t2SXTB:
696  case ARM::t2SXTH:
697  case ARM::t2UXTB:
698  case ARM::t2UXTH:
699    if (MI->getOperand(2).getImm() == 0)
700      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
701    break;
702  case ARM::t2MOVi16:
703    // Can convert only 'pure' immediate operands, not immediates obtained as
704    // globals' addresses.
705    if (MI->getOperand(1).isImm())
706      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
707    break;
708  case ARM::t2CMPrr: {
709    // Try to reduce to the lo-reg only version first. Why there are two
710    // versions of the instruction is a mystery.
711    // It would be nice to just have two entries in the master table that
712    // are prioritized, but the table assumes a unique entry for each
713    // source insn opcode. So for now, we hack a local entry record to use.
714    static const ReduceEntry NarrowEntry =
715      { ARM::t2CMPrr,ARM::tCMPr, 0, 0, 0, 1, 1,2, 0, 0,1,0 };
716    if (ReduceToNarrow(MBB, MI, NarrowEntry, LiveCPSR, IsSelfLoop))
717      return true;
718    return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
719  }
720  case ARM::t2TEQrr: {
721    unsigned PredReg = 0;
722    // Can only convert to eors if we're not in an IT block.
723    if (getInstrPredicate(*MI, PredReg) != ARMCC::AL)
724      break;
725    // TODO if Operand 0 is not killed but Operand 1 is, then we could write
726    // to Op1 instead.
727    if (MI->getOperand(0).isKill())
728      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
729  }
730  }
731  return false;
732}
733
734bool
735Thumb2SizeReduce::ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
736                                const ReduceEntry &Entry,
737                                bool LiveCPSR, bool IsSelfLoop) {
738  if (ReduceLimit2Addr != -1 && ((int)Num2Addrs >= ReduceLimit2Addr))
739    return false;
740
741  if (!OptimizeSize && Entry.AvoidMovs && STI->avoidMOVsShifterOperand())
742    // Don't issue movs with shifter operand for some CPUs unless we
743    // are optimizing for size.
744    return false;
745
746  Register Reg0 = MI->getOperand(0).getReg();
747  Register Reg1 = MI->getOperand(1).getReg();
748  // t2MUL is "special". The tied source operand is second, not first.
749  if (MI->getOpcode() == ARM::t2MUL) {
750    Register Reg2 = MI->getOperand(2).getReg();
751    // Early exit if the regs aren't all low regs.
752    if (!isARMLowRegister(Reg0) || !isARMLowRegister(Reg1)
753        || !isARMLowRegister(Reg2))
754      return false;
755    if (Reg0 != Reg2) {
756      // If the other operand also isn't the same as the destination, we
757      // can't reduce.
758      if (Reg1 != Reg0)
759        return false;
760      // Try to commute the operands to make it a 2-address instruction.
761      MachineInstr *CommutedMI = TII->commuteInstruction(*MI);
762      if (!CommutedMI)
763        return false;
764    }
765  } else if (Reg0 != Reg1) {
766    // Try to commute the operands to make it a 2-address instruction.
767    unsigned CommOpIdx1 = 1;
768    unsigned CommOpIdx2 = TargetInstrInfo::CommuteAnyOperandIndex;
769    if (!TII->findCommutedOpIndices(*MI, CommOpIdx1, CommOpIdx2) ||
770        MI->getOperand(CommOpIdx2).getReg() != Reg0)
771      return false;
772    MachineInstr *CommutedMI =
773        TII->commuteInstruction(*MI, false, CommOpIdx1, CommOpIdx2);
774    if (!CommutedMI)
775      return false;
776  }
777  if (Entry.LowRegs2 && !isARMLowRegister(Reg0))
778    return false;
779  if (Entry.Imm2Limit) {
780    unsigned Imm = MI->getOperand(2).getImm();
781    unsigned Limit = (1 << Entry.Imm2Limit) - 1;
782    if (Imm > Limit)
783      return false;
784  } else {
785    Register Reg2 = MI->getOperand(2).getReg();
786    if (Entry.LowRegs2 && !isARMLowRegister(Reg2))
787      return false;
788  }
789
790  // Check if it's possible / necessary to transfer the predicate.
791  const MCInstrDesc &NewMCID = TII->get(Entry.NarrowOpc2);
792  unsigned PredReg = 0;
793  ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
794  bool SkipPred = false;
795  if (Pred != ARMCC::AL) {
796    if (!NewMCID.isPredicable())
797      // Can't transfer predicate, fail.
798      return false;
799  } else {
800    SkipPred = !NewMCID.isPredicable();
801  }
802
803  bool HasCC = false;
804  bool CCDead = false;
805  const MCInstrDesc &MCID = MI->getDesc();
806  if (MCID.hasOptionalDef()) {
807    unsigned NumOps = MCID.getNumOperands();
808    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
809    if (HasCC && MI->getOperand(NumOps-1).isDead())
810      CCDead = true;
811  }
812  if (!VerifyPredAndCC(MI, Entry, true, Pred, LiveCPSR, HasCC, CCDead))
813    return false;
814
815  // Avoid adding a false dependency on partial flag update by some 16-bit
816  // instructions which has the 's' bit set.
817  if (Entry.PartFlag && NewMCID.hasOptionalDef() && HasCC &&
818      canAddPseudoFlagDep(MI, IsSelfLoop))
819    return false;
820
821  // Add the 16-bit instruction.
822  DebugLoc dl = MI->getDebugLoc();
823  MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID);
824  MIB.add(MI->getOperand(0));
825  if (NewMCID.hasOptionalDef())
826    MIB.add(HasCC ? t1CondCodeOp(CCDead) : condCodeOp());
827
828  // Transfer the rest of operands.
829  unsigned NumOps = MCID.getNumOperands();
830  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
831    if (i < NumOps && MCID.OpInfo[i].isOptionalDef())
832      continue;
833    if (SkipPred && MCID.OpInfo[i].isPredicate())
834      continue;
835    MIB.add(MI->getOperand(i));
836  }
837
838  // Transfer MI flags.
839  MIB.setMIFlags(MI->getFlags());
840
841  LLVM_DEBUG(errs() << "Converted 32-bit: " << *MI
842                    << "       to 16-bit: " << *MIB);
843
844  MBB.erase_instr(MI);
845  ++Num2Addrs;
846  return true;
847}
848
849bool
850Thumb2SizeReduce::ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
851                                 const ReduceEntry &Entry,
852                                 bool LiveCPSR, bool IsSelfLoop) {
853  if (ReduceLimit != -1 && ((int)NumNarrows >= ReduceLimit))
854    return false;
855
856  if (!OptimizeSize && Entry.AvoidMovs && STI->avoidMOVsShifterOperand())
857    // Don't issue movs with shifter operand for some CPUs unless we
858    // are optimizing for size.
859    return false;
860
861  unsigned Limit = ~0U;
862  if (Entry.Imm1Limit)
863    Limit = (1 << Entry.Imm1Limit) - 1;
864
865  const MCInstrDesc &MCID = MI->getDesc();
866  for (unsigned i = 0, e = MCID.getNumOperands(); i != e; ++i) {
867    if (MCID.OpInfo[i].isPredicate())
868      continue;
869    const MachineOperand &MO = MI->getOperand(i);
870    if (MO.isReg()) {
871      Register Reg = MO.getReg();
872      if (!Reg || Reg == ARM::CPSR)
873        continue;
874      if (Entry.LowRegs1 && !isARMLowRegister(Reg))
875        return false;
876    } else if (MO.isImm() &&
877               !MCID.OpInfo[i].isPredicate()) {
878      if (((unsigned)MO.getImm()) > Limit)
879        return false;
880    }
881  }
882
883  // Check if it's possible / necessary to transfer the predicate.
884  const MCInstrDesc &NewMCID = TII->get(Entry.NarrowOpc1);
885  unsigned PredReg = 0;
886  ARMCC::CondCodes Pred = getInstrPredicate(*MI, PredReg);
887  bool SkipPred = false;
888  if (Pred != ARMCC::AL) {
889    if (!NewMCID.isPredicable())
890      // Can't transfer predicate, fail.
891      return false;
892  } else {
893    SkipPred = !NewMCID.isPredicable();
894  }
895
896  bool HasCC = false;
897  bool CCDead = false;
898  if (MCID.hasOptionalDef()) {
899    unsigned NumOps = MCID.getNumOperands();
900    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
901    if (HasCC && MI->getOperand(NumOps-1).isDead())
902      CCDead = true;
903  }
904  if (!VerifyPredAndCC(MI, Entry, false, Pred, LiveCPSR, HasCC, CCDead))
905    return false;
906
907  // Avoid adding a false dependency on partial flag update by some 16-bit
908  // instructions which has the 's' bit set.
909  if (Entry.PartFlag && NewMCID.hasOptionalDef() && HasCC &&
910      canAddPseudoFlagDep(MI, IsSelfLoop))
911    return false;
912
913  // Add the 16-bit instruction.
914  DebugLoc dl = MI->getDebugLoc();
915  MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID);
916
917  // TEQ is special in that it doesn't define a register but we're converting
918  // it into an EOR which does. So add the first operand as a def and then
919  // again as a use.
920  if (MCID.getOpcode() == ARM::t2TEQrr) {
921    MIB.add(MI->getOperand(0));
922    MIB->getOperand(0).setIsKill(false);
923    MIB->getOperand(0).setIsDef(true);
924    MIB->getOperand(0).setIsDead(true);
925
926    if (NewMCID.hasOptionalDef())
927      MIB.add(HasCC ? t1CondCodeOp(CCDead) : condCodeOp());
928    MIB.add(MI->getOperand(0));
929  } else {
930    MIB.add(MI->getOperand(0));
931    if (NewMCID.hasOptionalDef())
932      MIB.add(HasCC ? t1CondCodeOp(CCDead) : condCodeOp());
933  }
934
935  // Transfer the rest of operands.
936  unsigned NumOps = MCID.getNumOperands();
937  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
938    if (i < NumOps && MCID.OpInfo[i].isOptionalDef())
939      continue;
940    if ((MCID.getOpcode() == ARM::t2RSBSri ||
941         MCID.getOpcode() == ARM::t2RSBri ||
942         MCID.getOpcode() == ARM::t2SXTB ||
943         MCID.getOpcode() == ARM::t2SXTH ||
944         MCID.getOpcode() == ARM::t2UXTB ||
945         MCID.getOpcode() == ARM::t2UXTH) && i == 2)
946      // Skip the zero immediate operand, it's now implicit.
947      continue;
948    bool isPred = (i < NumOps && MCID.OpInfo[i].isPredicate());
949    if (SkipPred && isPred)
950        continue;
951    const MachineOperand &MO = MI->getOperand(i);
952    if (MO.isReg() && MO.isImplicit() && MO.getReg() == ARM::CPSR)
953      // Skip implicit def of CPSR. Either it's modeled as an optional
954      // def now or it's already an implicit def on the new instruction.
955      continue;
956    MIB.add(MO);
957  }
958  if (!MCID.isPredicable() && NewMCID.isPredicable())
959    MIB.add(predOps(ARMCC::AL));
960
961  // Transfer MI flags.
962  MIB.setMIFlags(MI->getFlags());
963
964  LLVM_DEBUG(errs() << "Converted 32-bit: " << *MI
965                    << "       to 16-bit: " << *MIB);
966
967  MBB.erase_instr(MI);
968  ++NumNarrows;
969  return true;
970}
971
972static bool UpdateCPSRDef(MachineInstr &MI, bool LiveCPSR, bool &DefCPSR) {
973  bool HasDef = false;
974  for (const MachineOperand &MO : MI.operands()) {
975    if (!MO.isReg() || MO.isUndef() || MO.isUse())
976      continue;
977    if (MO.getReg() != ARM::CPSR)
978      continue;
979
980    DefCPSR = true;
981    if (!MO.isDead())
982      HasDef = true;
983  }
984
985  return HasDef || LiveCPSR;
986}
987
988static bool UpdateCPSRUse(MachineInstr &MI, bool LiveCPSR) {
989  for (const MachineOperand &MO : MI.operands()) {
990    if (!MO.isReg() || MO.isUndef() || MO.isDef())
991      continue;
992    if (MO.getReg() != ARM::CPSR)
993      continue;
994    assert(LiveCPSR && "CPSR liveness tracking is wrong!");
995    if (MO.isKill()) {
996      LiveCPSR = false;
997      break;
998    }
999  }
1000
1001  return LiveCPSR;
1002}
1003
1004bool Thumb2SizeReduce::ReduceMI(MachineBasicBlock &MBB, MachineInstr *MI,
1005                                bool LiveCPSR, bool IsSelfLoop) {
1006  unsigned Opcode = MI->getOpcode();
1007  DenseMap<unsigned, unsigned>::iterator OPI = ReduceOpcodeMap.find(Opcode);
1008  if (OPI == ReduceOpcodeMap.end())
1009    return false;
1010  const ReduceEntry &Entry = ReduceTable[OPI->second];
1011
1012  // Don't attempt normal reductions on "special" cases for now.
1013  if (Entry.Special)
1014    return ReduceSpecial(MBB, MI, Entry, LiveCPSR, IsSelfLoop);
1015
1016  // Try to transform to a 16-bit two-address instruction.
1017  if (Entry.NarrowOpc2 &&
1018      ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, IsSelfLoop))
1019    return true;
1020
1021  // Try to transform to a 16-bit non-two-address instruction.
1022  if (Entry.NarrowOpc1 &&
1023      ReduceToNarrow(MBB, MI, Entry, LiveCPSR, IsSelfLoop))
1024    return true;
1025
1026  return false;
1027}
1028
1029bool Thumb2SizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
1030  bool Modified = false;
1031
1032  // Yes, CPSR could be livein.
1033  bool LiveCPSR = MBB.isLiveIn(ARM::CPSR);
1034  MachineInstr *BundleMI = nullptr;
1035
1036  CPSRDef = nullptr;
1037  HighLatencyCPSR = false;
1038
1039  // Check predecessors for the latest CPSRDef.
1040  for (auto *Pred : MBB.predecessors()) {
1041    const MBBInfo &PInfo = BlockInfo[Pred->getNumber()];
1042    if (!PInfo.Visited) {
1043      // Since blocks are visited in RPO, this must be a back-edge.
1044      continue;
1045    }
1046    if (PInfo.HighLatencyCPSR) {
1047      HighLatencyCPSR = true;
1048      break;
1049    }
1050  }
1051
1052  // If this BB loops back to itself, conservatively avoid narrowing the
1053  // first instruction that does partial flag update.
1054  bool IsSelfLoop = MBB.isSuccessor(&MBB);
1055  MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),E = MBB.instr_end();
1056  MachineBasicBlock::instr_iterator NextMII;
1057  for (; MII != E; MII = NextMII) {
1058    NextMII = std::next(MII);
1059
1060    MachineInstr *MI = &*MII;
1061    if (MI->isBundle()) {
1062      BundleMI = MI;
1063      continue;
1064    }
1065    if (MI->isDebugInstr())
1066      continue;
1067
1068    LiveCPSR = UpdateCPSRUse(*MI, LiveCPSR);
1069
1070    // Does NextMII belong to the same bundle as MI?
1071    bool NextInSameBundle = NextMII != E && NextMII->isBundledWithPred();
1072
1073    if (ReduceMI(MBB, MI, LiveCPSR, IsSelfLoop)) {
1074      Modified = true;
1075      MachineBasicBlock::instr_iterator I = std::prev(NextMII);
1076      MI = &*I;
1077      // Removing and reinserting the first instruction in a bundle will break
1078      // up the bundle. Fix the bundling if it was broken.
1079      if (NextInSameBundle && !NextMII->isBundledWithPred())
1080        NextMII->bundleWithPred();
1081    }
1082
1083    if (BundleMI && !NextInSameBundle && MI->isInsideBundle()) {
1084      // FIXME: Since post-ra scheduler operates on bundles, the CPSR kill
1085      // marker is only on the BUNDLE instruction. Process the BUNDLE
1086      // instruction as we finish with the bundled instruction to work around
1087      // the inconsistency.
1088      if (BundleMI->killsRegister(ARM::CPSR))
1089        LiveCPSR = false;
1090      MachineOperand *MO = BundleMI->findRegisterDefOperand(ARM::CPSR);
1091      if (MO && !MO->isDead())
1092        LiveCPSR = true;
1093      MO = BundleMI->findRegisterUseOperand(ARM::CPSR);
1094      if (MO && !MO->isKill())
1095        LiveCPSR = true;
1096    }
1097
1098    bool DefCPSR = false;
1099    LiveCPSR = UpdateCPSRDef(*MI, LiveCPSR, DefCPSR);
1100    if (MI->isCall()) {
1101      // Calls don't really set CPSR.
1102      CPSRDef = nullptr;
1103      HighLatencyCPSR = false;
1104      IsSelfLoop = false;
1105    } else if (DefCPSR) {
1106      // This is the last CPSR defining instruction.
1107      CPSRDef = MI;
1108      HighLatencyCPSR = isHighLatencyCPSR(CPSRDef);
1109      IsSelfLoop = false;
1110    }
1111  }
1112
1113  MBBInfo &Info = BlockInfo[MBB.getNumber()];
1114  Info.HighLatencyCPSR = HighLatencyCPSR;
1115  Info.Visited = true;
1116  return Modified;
1117}
1118
1119bool Thumb2SizeReduce::runOnMachineFunction(MachineFunction &MF) {
1120  if (PredicateFtor && !PredicateFtor(MF.getFunction()))
1121    return false;
1122
1123  STI = &static_cast<const ARMSubtarget &>(MF.getSubtarget());
1124  if (STI->isThumb1Only() || STI->prefers32BitThumb())
1125    return false;
1126
1127  TII = static_cast<const Thumb2InstrInfo *>(STI->getInstrInfo());
1128
1129  // Optimizing / minimizing size? Minimizing size implies optimizing for size.
1130  OptimizeSize = MF.getFunction().hasOptSize();
1131  MinimizeSize = STI->hasMinSize();
1132
1133  BlockInfo.clear();
1134  BlockInfo.resize(MF.getNumBlockIDs());
1135
1136  // Visit blocks in reverse post-order so LastCPSRDef is known for all
1137  // predecessors.
1138  ReversePostOrderTraversal<MachineFunction*> RPOT(&MF);
1139  bool Modified = false;
1140  for (ReversePostOrderTraversal<MachineFunction*>::rpo_iterator
1141       I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
1142    Modified |= ReduceMBB(**I);
1143  return Modified;
1144}
1145
1146/// createThumb2SizeReductionPass - Returns an instance of the Thumb2 size
1147/// reduction pass.
1148FunctionPass *llvm::createThumb2SizeReductionPass(
1149    std::function<bool(const Function &)> Ftor) {
1150  return new Thumb2SizeReduce(std::move(Ftor));
1151}
1152