Thumb2SizeReduction.cpp revision 971b83b67a9812556cdb97bb58aa96fb37af458d 
1//===-- Thumb2SizeReduction.cpp - Thumb2 code size reduction pass -*- C++ -*-=//
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#define DEBUG_TYPE "t2-reduce-size"
11#include "ARM.h"
12#include "ARMAddressingModes.h"
13#include "ARMBaseRegisterInfo.h"
14#include "ARMBaseInstrInfo.h"
15#include "Thumb2InstrInfo.h"
16#include "llvm/CodeGen/MachineInstr.h"
17#include "llvm/CodeGen/MachineInstrBuilder.h"
18#include "llvm/CodeGen/MachineFunctionPass.h"
19#include "llvm/Support/CommandLine.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22#include "llvm/ADT/DenseMap.h"
23#include "llvm/ADT/Statistic.h"
24using namespace llvm;
25
26STATISTIC(NumNarrows,  "Number of 32-bit instrs reduced to 16-bit ones");
27STATISTIC(Num2Addrs,   "Number of 32-bit instrs reduced to 2addr 16-bit ones");
28STATISTIC(NumLdSts,    "Number of 32-bit load / store reduced to 16-bit ones");
29
30static cl::opt<int> ReduceLimit("t2-reduce-limit",
31                                cl::init(-1), cl::Hidden);
32static cl::opt<int> ReduceLimit2Addr("t2-reduce-limit2",
33                                     cl::init(-1), cl::Hidden);
34static cl::opt<int> ReduceLimitLdSt("t2-reduce-limit3",
35                                     cl::init(-1), cl::Hidden);
36
37namespace {
38  /// ReduceTable - A static table with information on mapping from wide
39  /// opcodes to narrow
40  struct ReduceEntry {
41    unsigned WideOpc;      // Wide opcode
42    unsigned NarrowOpc1;   // Narrow opcode to transform to
43    unsigned NarrowOpc2;   // Narrow opcode when it's two-address
44    uint8_t  Imm1Limit;    // Limit of immediate field (bits)
45    uint8_t  Imm2Limit;    // Limit of immediate field when it's two-address
46    unsigned LowRegs1 : 1; // Only possible if low-registers are used
47    unsigned LowRegs2 : 1; // Only possible if low-registers are used (2addr)
48    unsigned PredCC1  : 2; // 0 - If predicated, cc is on and vice versa.
49                           // 1 - No cc field.
50                           // 2 - Always set CPSR.
51    unsigned PredCC2  : 2;
52    unsigned Special  : 1; // Needs to be dealt with specially
53  };
54
55  static const ReduceEntry ReduceTable[] = {
56    // Wide,        Narrow1,      Narrow2,     imm1,imm2,  lo1, lo2, P/C, S
57    { ARM::t2ADCrr, 0,            ARM::tADC,     0,   0,    0,   1,  0,0, 0 },
58    { ARM::t2ADDri, ARM::tADDi3,  ARM::tADDi8,   3,   8,    1,   1,  0,0, 0 },
59    { ARM::t2ADDrr, ARM::tADDrr,  ARM::tADDhirr, 0,   0,    1,   0,  0,1, 0 },
60    // Note: immediate scale is 4.
61    { ARM::t2ADDrSPi,ARM::tADDrSPi,0,            8,   0,    1,   0,  1,0, 1 },
62    { ARM::t2ADDSri,ARM::tADDi3,  ARM::tADDi8,   3,   8,    1,   1,  2,2, 1 },
63    { ARM::t2ADDSrr,ARM::tADDrr,  0,             0,   0,    1,   0,  2,0, 1 },
64    { ARM::t2ANDrr, 0,            ARM::tAND,     0,   0,    0,   1,  0,0, 0 },
65    { ARM::t2ASRri, ARM::tASRri,  0,             5,   0,    1,   0,  0,0, 0 },
66    { ARM::t2ASRrr, 0,            ARM::tASRrr,   0,   0,    0,   1,  0,0, 0 },
67    { ARM::t2BICrr, 0,            ARM::tBIC,     0,   0,    0,   1,  0,0, 0 },
68    //FIXME: Disable CMN, as CCodes are backwards from compare expectations
69    //{ ARM::t2CMNrr, ARM::tCMN,    0,             0,   0,    1,   0,  2,0, 0 },
70    { ARM::t2CMPri, ARM::tCMPi8,  0,             8,   0,    1,   0,  2,0, 0 },
71    { ARM::t2CMPrr, ARM::tCMPhir, 0,             0,   0,    0,   0,  2,0, 1 },
72    { ARM::t2EORrr, 0,            ARM::tEOR,     0,   0,    0,   1,  0,0, 0 },
73    // FIXME: adr.n immediate offset must be multiple of 4.
74    //{ ARM::t2LEApcrelJT,ARM::tLEApcrelJT, 0,     0,   0,    1,   0,  1,0, 0 },
75    { ARM::t2LSLri, ARM::tLSLri,  0,             5,   0,    1,   0,  0,0, 0 },
76    { ARM::t2LSLrr, 0,            ARM::tLSLrr,   0,   0,    0,   1,  0,0, 0 },
77    { ARM::t2LSRri, ARM::tLSRri,  0,             5,   0,    1,   0,  0,0, 0 },
78    { ARM::t2LSRrr, 0,            ARM::tLSRrr,   0,   0,    0,   1,  0,0, 0 },
79    { ARM::t2MOVi,  ARM::tMOVi8,  0,             8,   0,    1,   0,  0,0, 0 },
80    { ARM::t2MOVi16,ARM::tMOVi8,  0,             8,   0,    1,   0,  0,0, 1 },
81    // FIXME: Do we need the 16-bit 'S' variant?
82    { ARM::t2MOVr,ARM::tMOVgpr2gpr,0,            0,   0,    0,   0,  1,0, 0 },
83    { ARM::t2MOVCCr,0,            ARM::tMOVCCr,  0,   0,    0,   0,  0,1, 0 },
84    { ARM::t2MOVCCi,0,            ARM::tMOVCCi,  0,   8,    0,   1,  0,1, 0 },
85    { ARM::t2MUL,   0,            ARM::tMUL,     0,   0,    0,   1,  0,0, 0 },
86    { ARM::t2MVNr,  ARM::tMVN,    0,             0,   0,    1,   0,  0,0, 0 },
87    { ARM::t2ORRrr, 0,            ARM::tORR,     0,   0,    0,   1,  0,0, 0 },
88    { ARM::t2REV,   ARM::tREV,    0,             0,   0,    1,   0,  1,0, 0 },
89    { ARM::t2REV16, ARM::tREV16,  0,             0,   0,    1,   0,  1,0, 0 },
90    { ARM::t2REVSH, ARM::tREVSH,  0,             0,   0,    1,   0,  1,0, 0 },
91    { ARM::t2RORrr, 0,            ARM::tROR,     0,   0,    0,   1,  0,0, 0 },
92    { ARM::t2RSBri, ARM::tRSB,    0,             0,   0,    1,   0,  0,0, 1 },
93    { ARM::t2RSBSri,ARM::tRSB,    0,             0,   0,    1,   0,  2,0, 1 },
94    { ARM::t2SBCrr, 0,            ARM::tSBC,     0,   0,    0,   1,  0,0, 0 },
95    { ARM::t2SUBri, ARM::tSUBi3,  ARM::tSUBi8,   3,   8,    1,   1,  0,0, 0 },
96    { ARM::t2SUBrr, ARM::tSUBrr,  0,             0,   0,    1,   0,  0,0, 0 },
97    { ARM::t2SUBSri,ARM::tSUBi3,  ARM::tSUBi8,   3,   8,    1,   1,  2,2, 0 },
98    { ARM::t2SUBSrr,ARM::tSUBrr,  0,             0,   0,    1,   0,  2,0, 0 },
99    { ARM::t2SXTBr, ARM::tSXTB,   0,             0,   0,    1,   0,  1,0, 0 },
100    { ARM::t2SXTHr, ARM::tSXTH,   0,             0,   0,    1,   0,  1,0, 0 },
101    { ARM::t2TSTrr, ARM::tTST,    0,             0,   0,    1,   0,  2,0, 0 },
102    { ARM::t2UXTBr, ARM::tUXTB,   0,             0,   0,    1,   0,  1,0, 0 },
103    { ARM::t2UXTHr, ARM::tUXTH,   0,             0,   0,    1,   0,  1,0, 0 },
104
105    // FIXME: Clean this up after splitting each Thumb load / store opcode
106    // into multiple ones.
107    { ARM::t2LDRi12,ARM::tLDRi,   ARM::tLDRspi,  5,   8,    1,   0,  0,0, 1 },
108    { ARM::t2LDRs,  ARM::tLDRr,   0,             0,   0,    1,   0,  0,0, 1 },
109    { ARM::t2LDRBi12,ARM::tLDRBi, 0,             5,   0,    1,   0,  0,0, 1 },
110    { ARM::t2LDRBs, ARM::tLDRBr,  0,             0,   0,    1,   0,  0,0, 1 },
111    { ARM::t2LDRHi12,ARM::tLDRHi, 0,             5,   0,    1,   0,  0,0, 1 },
112    { ARM::t2LDRHs, ARM::tLDRHr,  0,             0,   0,    1,   0,  0,0, 1 },
113    { ARM::t2LDRSBs,ARM::tLDRSB,  0,             0,   0,    1,   0,  0,0, 1 },
114    { ARM::t2LDRSHs,ARM::tLDRSH,  0,             0,   0,    1,   0,  0,0, 1 },
115    { ARM::t2STRi12,ARM::tSTRi,   ARM::tSTRspi,  5,   8,    1,   0,  0,0, 1 },
116    { ARM::t2STRs,  ARM::tSTRr,   0,             0,   0,    1,   0,  0,0, 1 },
117    { ARM::t2STRBi12,ARM::tSTRBi, 0,             5,   0,    1,   0,  0,0, 1 },
118    { ARM::t2STRBs, ARM::tSTRBr,  0,             0,   0,    1,   0,  0,0, 1 },
119    { ARM::t2STRHi12,ARM::tSTRHi, 0,             5,   0,    1,   0,  0,0, 1 },
120    { ARM::t2STRHs, ARM::tSTRHr,  0,             0,   0,    1,   0,  0,0, 1 },
121
122    { ARM::t2LDMIA, ARM::tLDMIA,  0,             0,   0,    1,   1,  1,1, 1 },
123    { ARM::t2LDMIA_RET,0,         ARM::tPOP_RET, 0,   0,    1,   1,  1,1, 1 },
124    { ARM::t2LDMIA_UPD,ARM::tLDMIA_UPD,ARM::tPOP,0,   0,    1,   1,  1,1, 1 },
125    // ARM::t2STM (with no basereg writeback) has no Thumb1 equivalent
126    { ARM::t2STMIA_UPD,ARM::tSTMIA_UPD, 0,       0,   0,    1,   1,  1,1, 1 },
127    { ARM::t2STMDB_UPD, 0,        ARM::tPUSH,    0,   0,    1,   1,  1,1, 1 },
128  };
129
130  class Thumb2SizeReduce : public MachineFunctionPass {
131  public:
132    static char ID;
133    Thumb2SizeReduce();
134
135    const Thumb2InstrInfo *TII;
136
137    virtual bool runOnMachineFunction(MachineFunction &MF);
138
139    virtual const char *getPassName() const {
140      return "Thumb2 instruction size reduction pass";
141    }
142
143  private:
144    /// ReduceOpcodeMap - Maps wide opcode to index of entry in ReduceTable.
145    DenseMap<unsigned, unsigned> ReduceOpcodeMap;
146
147    bool VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
148                         bool is2Addr, ARMCC::CondCodes Pred,
149                         bool LiveCPSR, bool &HasCC, bool &CCDead);
150
151    bool ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
152                         const ReduceEntry &Entry);
153
154    bool ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
155                       const ReduceEntry &Entry, bool LiveCPSR);
156
157    /// ReduceTo2Addr - Reduce a 32-bit instruction to a 16-bit two-address
158    /// instruction.
159    bool ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
160                       const ReduceEntry &Entry,
161                       bool LiveCPSR);
162
163    /// ReduceToNarrow - Reduce a 32-bit instruction to a 16-bit
164    /// non-two-address instruction.
165    bool ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
166                        const ReduceEntry &Entry,
167                        bool LiveCPSR);
168
169    /// ReduceMBB - Reduce width of instructions in the specified basic block.
170    bool ReduceMBB(MachineBasicBlock &MBB);
171  };
172  char Thumb2SizeReduce::ID = 0;
173}
174
175Thumb2SizeReduce::Thumb2SizeReduce() : MachineFunctionPass(ID) {
176  for (unsigned i = 0, e = array_lengthof(ReduceTable); i != e; ++i) {
177    unsigned FromOpc = ReduceTable[i].WideOpc;
178    if (!ReduceOpcodeMap.insert(std::make_pair(FromOpc, i)).second)
179      assert(false && "Duplicated entries?");
180  }
181}
182
183static bool HasImplicitCPSRDef(const TargetInstrDesc &TID) {
184  for (const unsigned *Regs = TID.ImplicitDefs; *Regs; ++Regs)
185    if (*Regs == ARM::CPSR)
186      return true;
187  return false;
188}
189
190bool
191Thumb2SizeReduce::VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
192                                  bool is2Addr, ARMCC::CondCodes Pred,
193                                  bool LiveCPSR, bool &HasCC, bool &CCDead) {
194  if ((is2Addr  && Entry.PredCC2 == 0) ||
195      (!is2Addr && Entry.PredCC1 == 0)) {
196    if (Pred == ARMCC::AL) {
197      // Not predicated, must set CPSR.
198      if (!HasCC) {
199        // Original instruction was not setting CPSR, but CPSR is not
200        // currently live anyway. It's ok to set it. The CPSR def is
201        // dead though.
202        if (!LiveCPSR) {
203          HasCC = true;
204          CCDead = true;
205          return true;
206        }
207        return false;
208      }
209    } else {
210      // Predicated, must not set CPSR.
211      if (HasCC)
212        return false;
213    }
214  } else if ((is2Addr  && Entry.PredCC2 == 2) ||
215             (!is2Addr && Entry.PredCC1 == 2)) {
216    /// Old opcode has an optional def of CPSR.
217    if (HasCC)
218      return true;
219    // If old opcode does not implicitly define CPSR, then it's not ok since
220    // these new opcodes' CPSR def is not meant to be thrown away. e.g. CMP.
221    if (!HasImplicitCPSRDef(MI->getDesc()))
222      return false;
223    HasCC = true;
224  } else {
225    // 16-bit instruction does not set CPSR.
226    if (HasCC)
227      return false;
228  }
229
230  return true;
231}
232
233static bool VerifyLowRegs(MachineInstr *MI) {
234  unsigned Opc = MI->getOpcode();
235  bool isPCOk = (Opc == ARM::t2LDMIA_RET || Opc == ARM::t2LDMIA     ||
236                 Opc == ARM::t2LDMDB     || Opc == ARM::t2LDMIA_UPD ||
237                 Opc == ARM::t2LDMDB_UPD);
238  bool isLROk = (Opc == ARM::t2STMIA_UPD || Opc == ARM::t2STMDB_UPD);
239  bool isSPOk = isPCOk || isLROk || (Opc == ARM::t2ADDrSPi);
240  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
241    const MachineOperand &MO = MI->getOperand(i);
242    if (!MO.isReg() || MO.isImplicit())
243      continue;
244    unsigned Reg = MO.getReg();
245    if (Reg == 0 || Reg == ARM::CPSR)
246      continue;
247    if (isPCOk && Reg == ARM::PC)
248      continue;
249    if (isLROk && Reg == ARM::LR)
250      continue;
251    if (Reg == ARM::SP) {
252      if (isSPOk)
253        continue;
254      if (i == 1 && (Opc == ARM::t2LDRi12 || Opc == ARM::t2STRi12))
255        // Special case for these ldr / str with sp as base register.
256        continue;
257    }
258    if (!isARMLowRegister(Reg))
259      return false;
260  }
261  return true;
262}
263
264bool
265Thumb2SizeReduce::ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
266                                  const ReduceEntry &Entry) {
267  if (ReduceLimitLdSt != -1 && ((int)NumLdSts >= ReduceLimitLdSt))
268    return false;
269
270  unsigned Scale = 1;
271  bool HasImmOffset = false;
272  bool HasShift = false;
273  bool HasOffReg = true;
274  bool isLdStMul = false;
275  unsigned Opc = Entry.NarrowOpc1;
276  unsigned OpNum = 3; // First 'rest' of operands.
277  uint8_t  ImmLimit = Entry.Imm1Limit;
278
279  switch (Entry.WideOpc) {
280  default:
281    llvm_unreachable("Unexpected Thumb2 load / store opcode!");
282  case ARM::t2LDRi12:
283  case ARM::t2STRi12:
284    if (MI->getOperand(1).getReg() == ARM::SP) {
285      Opc = Entry.NarrowOpc2;
286      ImmLimit = Entry.Imm2Limit;
287      HasOffReg = false;
288    }
289
290    Scale = 4;
291    HasImmOffset = true;
292    HasOffReg = false;
293    break;
294  case ARM::t2LDRBi12:
295  case ARM::t2STRBi12:
296    HasImmOffset = true;
297    HasOffReg = false;
298    break;
299  case ARM::t2LDRHi12:
300  case ARM::t2STRHi12:
301    Scale = 2;
302    HasImmOffset = true;
303    HasOffReg = false;
304    break;
305  case ARM::t2LDRs:
306  case ARM::t2LDRBs:
307  case ARM::t2LDRHs:
308  case ARM::t2LDRSBs:
309  case ARM::t2LDRSHs:
310  case ARM::t2STRs:
311  case ARM::t2STRBs:
312  case ARM::t2STRHs:
313    HasShift = true;
314    OpNum = 4;
315    break;
316  case ARM::t2LDMIA:
317  case ARM::t2LDMDB: {
318    unsigned BaseReg = MI->getOperand(0).getReg();
319    if (!isARMLowRegister(BaseReg) || Entry.WideOpc != ARM::t2LDMIA)
320      return false;
321
322    // For the non-writeback version (this one), the base register must be
323    // one of the registers being loaded.
324    bool isOK = false;
325    for (unsigned i = 4; i < MI->getNumOperands(); ++i) {
326      if (MI->getOperand(i).getReg() == BaseReg) {
327        isOK = true;
328        break;
329      }
330    }
331
332    if (!isOK)
333      return false;
334
335    OpNum = 0;
336    isLdStMul = true;
337    break;
338  }
339  case ARM::t2LDMIA_RET: {
340    unsigned BaseReg = MI->getOperand(1).getReg();
341    if (BaseReg != ARM::SP)
342      return false;
343    Opc = Entry.NarrowOpc2; // tPOP_RET
344    OpNum = 2;
345    isLdStMul = true;
346    break;
347  }
348  case ARM::t2LDMIA_UPD:
349  case ARM::t2LDMDB_UPD:
350  case ARM::t2STMIA_UPD:
351  case ARM::t2STMDB_UPD: {
352    OpNum = 0;
353
354    unsigned BaseReg = MI->getOperand(1).getReg();
355    if (BaseReg == ARM::SP &&
356        (Entry.WideOpc == ARM::t2LDMIA_UPD ||
357         Entry.WideOpc == ARM::t2STMDB_UPD)) {
358      Opc = Entry.NarrowOpc2; // tPOP or tPUSH
359      OpNum = 2;
360    } else if (!isARMLowRegister(BaseReg) ||
361               (Entry.WideOpc != ARM::t2LDMIA_UPD &&
362                Entry.WideOpc != ARM::t2STMIA_UPD)) {
363      return false;
364    }
365
366    isLdStMul = true;
367    break;
368  }
369  }
370
371  unsigned OffsetReg = 0;
372  bool OffsetKill = false;
373  if (HasShift) {
374    OffsetReg  = MI->getOperand(2).getReg();
375    OffsetKill = MI->getOperand(2).isKill();
376
377    if (MI->getOperand(3).getImm())
378      // Thumb1 addressing mode doesn't support shift.
379      return false;
380  }
381
382  unsigned OffsetImm = 0;
383  if (HasImmOffset) {
384    OffsetImm = MI->getOperand(2).getImm();
385    unsigned MaxOffset = ((1 << ImmLimit) - 1) * Scale;
386
387    if ((OffsetImm & (Scale - 1)) || OffsetImm > MaxOffset)
388      // Make sure the immediate field fits.
389      return false;
390  }
391
392  // Add the 16-bit load / store instruction.
393  DebugLoc dl = MI->getDebugLoc();
394  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, TII->get(Opc));
395  if (!isLdStMul) {
396    MIB.addOperand(MI->getOperand(0));
397    MIB.addOperand(MI->getOperand(1));
398
399    if (HasImmOffset)
400      MIB.addImm(OffsetImm / Scale);
401
402    assert((!HasShift || OffsetReg) && "Invalid so_reg load / store address!");
403
404    if (HasOffReg)
405      MIB.addReg(OffsetReg, getKillRegState(OffsetKill));
406  }
407
408  // Transfer the rest of operands.
409  for (unsigned e = MI->getNumOperands(); OpNum != e; ++OpNum)
410    MIB.addOperand(MI->getOperand(OpNum));
411
412  // Transfer memoperands.
413  (*MIB).setMemRefs(MI->memoperands_begin(), MI->memoperands_end());
414
415  DEBUG(errs() << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB);
416
417  MBB.erase(MI);
418  ++NumLdSts;
419  return true;
420}
421
422bool
423Thumb2SizeReduce::ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
424                                const ReduceEntry &Entry,
425                                bool LiveCPSR) {
426  if (Entry.LowRegs1 && !VerifyLowRegs(MI))
427    return false;
428
429  const TargetInstrDesc &TID = MI->getDesc();
430  if (TID.mayLoad() || TID.mayStore())
431    return ReduceLoadStore(MBB, MI, Entry);
432
433  unsigned Opc = MI->getOpcode();
434  switch (Opc) {
435  default: break;
436  case ARM::t2ADDSri:
437  case ARM::t2ADDSrr: {
438    unsigned PredReg = 0;
439    if (getInstrPredicate(MI, PredReg) == ARMCC::AL) {
440      switch (Opc) {
441      default: break;
442      case ARM::t2ADDSri: {
443        if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR))
444          return true;
445        // fallthrough
446      }
447      case ARM::t2ADDSrr:
448        return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
449      }
450    }
451    break;
452  }
453  case ARM::t2RSBri:
454  case ARM::t2RSBSri:
455    if (MI->getOperand(2).getImm() == 0)
456      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
457    break;
458  case ARM::t2MOVi16:
459    // Can convert only 'pure' immediate operands, not immediates obtained as
460    // globals' addresses.
461    if (MI->getOperand(1).isImm())
462      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
463    break;
464  case ARM::t2CMPrr: {
465    // Try to reduce to the lo-reg only version first. Why there are two
466    // versions of the instruction is a mystery.
467    // It would be nice to just have two entries in the master table that
468    // are prioritized, but the table assumes a unique entry for each
469    // source insn opcode. So for now, we hack a local entry record to use.
470    static const ReduceEntry NarrowEntry =
471      { ARM::t2CMPrr,ARM::tCMPr, 0, 0, 0, 1, 1,2, 0, 1 };
472    if (ReduceToNarrow(MBB, MI, NarrowEntry, LiveCPSR))
473      return true;
474    return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
475  }
476  case ARM::t2ADDrSPi: {
477    static const ReduceEntry NarrowEntry =
478      { ARM::t2ADDrSPi,ARM::tADDspi, 0, 7, 0, 1, 0, 1, 0, 1 };
479    if (MI->getOperand(0).getReg() == ARM::SP)
480      return ReduceToNarrow(MBB, MI, NarrowEntry, LiveCPSR);
481    return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
482  }
483  }
484  return false;
485}
486
487bool
488Thumb2SizeReduce::ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
489                                const ReduceEntry &Entry,
490                                bool LiveCPSR) {
491
492  if (ReduceLimit2Addr != -1 && ((int)Num2Addrs >= ReduceLimit2Addr))
493    return false;
494
495  unsigned Reg0 = MI->getOperand(0).getReg();
496  unsigned Reg1 = MI->getOperand(1).getReg();
497  if (Reg0 != Reg1) {
498    // Try to commute the operands to make it a 2-address instruction.
499    unsigned CommOpIdx1, CommOpIdx2;
500    if (!TII->findCommutedOpIndices(MI, CommOpIdx1, CommOpIdx2) ||
501        CommOpIdx1 != 1 || MI->getOperand(CommOpIdx2).getReg() != Reg0)
502      return false;
503    MachineInstr *CommutedMI = TII->commuteInstruction(MI);
504    if (!CommutedMI)
505      return false;
506  }
507  if (Entry.LowRegs2 && !isARMLowRegister(Reg0))
508    return false;
509  if (Entry.Imm2Limit) {
510    unsigned Imm = MI->getOperand(2).getImm();
511    unsigned Limit = (1 << Entry.Imm2Limit) - 1;
512    if (Imm > Limit)
513      return false;
514  } else {
515    unsigned Reg2 = MI->getOperand(2).getReg();
516    if (Entry.LowRegs2 && !isARMLowRegister(Reg2))
517      return false;
518  }
519
520  // Check if it's possible / necessary to transfer the predicate.
521  const TargetInstrDesc &NewTID = TII->get(Entry.NarrowOpc2);
522  unsigned PredReg = 0;
523  ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
524  bool SkipPred = false;
525  if (Pred != ARMCC::AL) {
526    if (!NewTID.isPredicable())
527      // Can't transfer predicate, fail.
528      return false;
529  } else {
530    SkipPred = !NewTID.isPredicable();
531  }
532
533  bool HasCC = false;
534  bool CCDead = false;
535  const TargetInstrDesc &TID = MI->getDesc();
536  if (TID.hasOptionalDef()) {
537    unsigned NumOps = TID.getNumOperands();
538    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
539    if (HasCC && MI->getOperand(NumOps-1).isDead())
540      CCDead = true;
541  }
542  if (!VerifyPredAndCC(MI, Entry, true, Pred, LiveCPSR, HasCC, CCDead))
543    return false;
544
545  // Add the 16-bit instruction.
546  DebugLoc dl = MI->getDebugLoc();
547  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, NewTID);
548  MIB.addOperand(MI->getOperand(0));
549  if (NewTID.hasOptionalDef()) {
550    if (HasCC)
551      AddDefaultT1CC(MIB, CCDead);
552    else
553      AddNoT1CC(MIB);
554  }
555
556  // Transfer the rest of operands.
557  unsigned NumOps = TID.getNumOperands();
558  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
559    if (i < NumOps && TID.OpInfo[i].isOptionalDef())
560      continue;
561    if (SkipPred && TID.OpInfo[i].isPredicate())
562      continue;
563    MIB.addOperand(MI->getOperand(i));
564  }
565
566  DEBUG(errs() << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB);
567
568  MBB.erase(MI);
569  ++Num2Addrs;
570  return true;
571}
572
573bool
574Thumb2SizeReduce::ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
575                                 const ReduceEntry &Entry,
576                                 bool LiveCPSR) {
577  if (ReduceLimit != -1 && ((int)NumNarrows >= ReduceLimit))
578    return false;
579
580  unsigned Limit = ~0U;
581  unsigned Scale = (Entry.WideOpc == ARM::t2ADDrSPi) ? 4 : 1;
582  if (Entry.Imm1Limit)
583    Limit = ((1 << Entry.Imm1Limit) - 1) * Scale;
584
585  const TargetInstrDesc &TID = MI->getDesc();
586  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
587    if (TID.OpInfo[i].isPredicate())
588      continue;
589    const MachineOperand &MO = MI->getOperand(i);
590    if (MO.isReg()) {
591      unsigned Reg = MO.getReg();
592      if (!Reg || Reg == ARM::CPSR)
593        continue;
594      if (Entry.WideOpc == ARM::t2ADDrSPi && Reg == ARM::SP)
595        continue;
596      if (Entry.LowRegs1 && !isARMLowRegister(Reg))
597        return false;
598    } else if (MO.isImm() &&
599               !TID.OpInfo[i].isPredicate()) {
600      if (((unsigned)MO.getImm()) > Limit || (MO.getImm() & (Scale-1)) != 0)
601        return false;
602    }
603  }
604
605  // Check if it's possible / necessary to transfer the predicate.
606  const TargetInstrDesc &NewTID = TII->get(Entry.NarrowOpc1);
607  unsigned PredReg = 0;
608  ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
609  bool SkipPred = false;
610  if (Pred != ARMCC::AL) {
611    if (!NewTID.isPredicable())
612      // Can't transfer predicate, fail.
613      return false;
614  } else {
615    SkipPred = !NewTID.isPredicable();
616  }
617
618  bool HasCC = false;
619  bool CCDead = false;
620  if (TID.hasOptionalDef()) {
621    unsigned NumOps = TID.getNumOperands();
622    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
623    if (HasCC && MI->getOperand(NumOps-1).isDead())
624      CCDead = true;
625  }
626  if (!VerifyPredAndCC(MI, Entry, false, Pred, LiveCPSR, HasCC, CCDead))
627    return false;
628
629  // Add the 16-bit instruction.
630  DebugLoc dl = MI->getDebugLoc();
631  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, NewTID);
632  MIB.addOperand(MI->getOperand(0));
633  if (NewTID.hasOptionalDef()) {
634    if (HasCC)
635      AddDefaultT1CC(MIB, CCDead);
636    else
637      AddNoT1CC(MIB);
638  }
639
640  // Transfer the rest of operands.
641  unsigned NumOps = TID.getNumOperands();
642  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
643    if (i < NumOps && TID.OpInfo[i].isOptionalDef())
644      continue;
645    if ((TID.getOpcode() == ARM::t2RSBSri ||
646         TID.getOpcode() == ARM::t2RSBri) && i == 2)
647      // Skip the zero immediate operand, it's now implicit.
648      continue;
649    bool isPred = (i < NumOps && TID.OpInfo[i].isPredicate());
650    if (SkipPred && isPred)
651        continue;
652    const MachineOperand &MO = MI->getOperand(i);
653    if (Scale > 1 && !isPred && MO.isImm())
654      MIB.addImm(MO.getImm() / Scale);
655    else {
656      if (MO.isReg() && MO.isImplicit() && MO.getReg() == ARM::CPSR)
657        // Skip implicit def of CPSR. Either it's modeled as an optional
658        // def now or it's already an implicit def on the new instruction.
659        continue;
660      MIB.addOperand(MO);
661    }
662  }
663  if (!TID.isPredicable() && NewTID.isPredicable())
664    AddDefaultPred(MIB);
665
666  DEBUG(errs() << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB);
667
668  MBB.erase(MI);
669  ++NumNarrows;
670  return true;
671}
672
673static bool UpdateCPSRDef(MachineInstr &MI, bool LiveCPSR) {
674  bool HasDef = false;
675  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
676    const MachineOperand &MO = MI.getOperand(i);
677    if (!MO.isReg() || MO.isUndef() || MO.isUse())
678      continue;
679    if (MO.getReg() != ARM::CPSR)
680      continue;
681    if (!MO.isDead())
682      HasDef = true;
683  }
684
685  return HasDef || LiveCPSR;
686}
687
688static bool UpdateCPSRUse(MachineInstr &MI, bool LiveCPSR) {
689  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
690    const MachineOperand &MO = MI.getOperand(i);
691    if (!MO.isReg() || MO.isUndef() || MO.isDef())
692      continue;
693    if (MO.getReg() != ARM::CPSR)
694      continue;
695    assert(LiveCPSR && "CPSR liveness tracking is wrong!");
696    if (MO.isKill()) {
697      LiveCPSR = false;
698      break;
699    }
700  }
701
702  return LiveCPSR;
703}
704
705bool Thumb2SizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
706  bool Modified = false;
707
708  // Yes, CPSR could be livein.
709  bool LiveCPSR = MBB.isLiveIn(ARM::CPSR);
710
711  MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
712  MachineBasicBlock::iterator NextMII;
713  for (; MII != E; MII = NextMII) {
714    NextMII = llvm::next(MII);
715
716    MachineInstr *MI = &*MII;
717    LiveCPSR = UpdateCPSRUse(*MI, LiveCPSR);
718
719    unsigned Opcode = MI->getOpcode();
720    DenseMap<unsigned, unsigned>::iterator OPI = ReduceOpcodeMap.find(Opcode);
721    if (OPI != ReduceOpcodeMap.end()) {
722      const ReduceEntry &Entry = ReduceTable[OPI->second];
723      // Ignore "special" cases for now.
724      if (Entry.Special) {
725        if (ReduceSpecial(MBB, MI, Entry, LiveCPSR)) {
726          Modified = true;
727          MachineBasicBlock::iterator I = prior(NextMII);
728          MI = &*I;
729        }
730        goto ProcessNext;
731      }
732
733      // Try to transform to a 16-bit two-address instruction.
734      if (Entry.NarrowOpc2 && ReduceTo2Addr(MBB, MI, Entry, LiveCPSR)) {
735        Modified = true;
736        MachineBasicBlock::iterator I = prior(NextMII);
737        MI = &*I;
738        goto ProcessNext;
739      }
740
741      // Try to transform to a 16-bit non-two-address instruction.
742      if (Entry.NarrowOpc1 && ReduceToNarrow(MBB, MI, Entry, LiveCPSR)) {
743        Modified = true;
744        MachineBasicBlock::iterator I = prior(NextMII);
745        MI = &*I;
746      }
747    }
748
749  ProcessNext:
750    LiveCPSR = UpdateCPSRDef(*MI, LiveCPSR);
751  }
752
753  return Modified;
754}
755
756bool Thumb2SizeReduce::runOnMachineFunction(MachineFunction &MF) {
757  const TargetMachine &TM = MF.getTarget();
758  TII = static_cast<const Thumb2InstrInfo*>(TM.getInstrInfo());
759
760  bool Modified = false;
761  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
762    Modified |= ReduceMBB(*I);
763  return Modified;
764}
765
766/// createThumb2SizeReductionPass - Returns an instance of the Thumb2 size
767/// reduction pass.
768FunctionPass *llvm::createThumb2SizeReductionPass() {
769  return new Thumb2SizeReduce();
770}
771