Thumb2SizeReduction.cpp revision 05c269c64593d8cc6aeb0780a5a8afbb86da5691 
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/Compiler.h"
21#include "llvm/Support/Debug.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  : 1;
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, 0 },
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    { ARM::t2CMNrr, ARM::tCMN,    0,             0,   0,    1,   0,  2,0, 0 },
69    { ARM::t2CMPri, ARM::tCMPi8,  0,             8,   0,    1,   0,  2,0, 0 },
70    { ARM::t2CMPrr, ARM::tCMPhir, 0,             0,   0,    0,   0,  2,0, 0 },
71    { ARM::t2CMPzri,ARM::tCMPzi8, 0,             8,   0,    1,   0,  2,0, 0 },
72    { ARM::t2CMPzrr,ARM::tCMPzhir,0,             0,   0,    0,   0,  2,0, 0 },
73    { ARM::t2EORrr, 0,            ARM::tEOR,     0,   0,    0,   1,  0,0, 0 },
74    { ARM::t2LSLri, ARM::tLSLri,  0,             5,   0,    1,   0,  0,0, 0 },
75    { ARM::t2LSLrr, 0,            ARM::tLSLrr,   0,   0,    0,   1,  0,0, 0 },
76    { ARM::t2LSRri, ARM::tLSRri,  0,             5,   0,    1,   0,  0,0, 0 },
77    { ARM::t2LSRrr, 0,            ARM::tLSRrr,   0,   0,    0,   1,  0,0, 0 },
78    { ARM::t2MOVi,  ARM::tMOVi8,  0,             8,   0,    1,   0,  0,0, 0 },
79    // FIXME: Do we need the 16-bit 'S' variant?
80    // FIXME: t2MOVcc
81    { ARM::t2MOVr,ARM::tMOVgpr2gpr,0,            0,   0,    0,   0,  1,0, 0 },
82    { ARM::t2MUL,   0,            ARM::tMUL,     0,   0,    0,   1,  0,0, 0 },
83    { ARM::t2MVNr,  ARM::tMVN,    0,             0,   0,    1,   0,  0,0, 0 },
84    { ARM::t2ORRrr, 0,            ARM::tORR,     0,   0,    0,   1,  0,0, 0 },
85    { ARM::t2REV,   ARM::tREV,    0,             0,   0,    1,   0,  1,0, 0 },
86    { ARM::t2REV16, ARM::tREV16,  0,             0,   0,    1,   0,  1,0, 0 },
87    { ARM::t2REVSH, ARM::tREVSH,  0,             0,   0,    1,   0,  1,0, 0 },
88    { ARM::t2RORrr, 0,            ARM::tROR,     0,   0,    0,   1,  0,0, 0 },
89    { ARM::t2RSBri, ARM::tRSB,    0,             0,   0,    1,   0,  0,0, 1 },
90    { ARM::t2RSBSri,ARM::tRSB,    0,             0,   0,    1,   0,  2,0, 1 },
91    { ARM::t2SBCrr, 0,            ARM::tSBC,     0,   0,    0,   1,  0,0, 0 },
92    { ARM::t2SUBri, ARM::tSUBi3,  ARM::tSUBi8,   3,   8,    1,   1,  0,0, 0 },
93    { ARM::t2SUBrr, ARM::tSUBrr,  0,             0,   0,    1,   0,  0,0, 0 },
94    { ARM::t2SUBSri,ARM::tSUBi3,  ARM::tSUBi8,   3,   8,    1,   1,  2,2, 0 },
95    { ARM::t2SUBSrr,ARM::tSUBrr,  0,             0,   0,    1,   0,  2,0, 0 },
96    { ARM::t2SXTBr, ARM::tSXTB,   0,             0,   0,    1,   0,  1,0, 0 },
97    { ARM::t2SXTHr, ARM::tSXTH,   0,             0,   0,    1,   0,  1,0, 0 },
98    { ARM::t2TSTrr, ARM::tTST,    0,             0,   0,    1,   0,  2,0, 0 },
99    { ARM::t2UXTBr, ARM::tUXTB,   0,             0,   0,    1,   0,  1,0, 0 },
100    { ARM::t2UXTHr, ARM::tUXTH,   0,             0,   0,    1,   0,  1,0, 0 },
101
102    // FIXME: Clean this up after splitting each Thumb load / store opcode
103    // into multiple ones.
104    { ARM::t2LDRi12,ARM::tLDR,    0,             5,   0,    1,   0,  0,0, 1 },
105    { ARM::t2LDRs,  ARM::tLDR,    0,             0,   0,    1,   0,  0,0, 1 },
106    { ARM::t2LDRBi12,ARM::tLDRB,  0,             5,   0,    1,   0,  0,0, 1 },
107    { ARM::t2LDRBs, ARM::tLDRB,   0,             0,   0,    1,   0,  0,0, 1 },
108    { ARM::t2LDRHi12,ARM::tLDRH,  0,             5,   0,    1,   0,  0,0, 1 },
109    { ARM::t2LDRHs, ARM::tLDRH,   0,             0,   0,    1,   0,  0,0, 1 },
110    { ARM::t2LDRSBs,ARM::tLDRSB,  0,             0,   0,    1,   0,  0,0, 1 },
111    { ARM::t2LDRSHs,ARM::tLDRSH,  0,             0,   0,    1,   0,  0,0, 1 },
112    { ARM::t2STRi12,ARM::tSTR,    0,             5,   0,    1,   0,  0,0, 1 },
113    { ARM::t2STRs,  ARM::tSTR,    0,             0,   0,    1,   0,  0,0, 1 },
114    { ARM::t2STRBi12,ARM::tSTRB,  0,             5,   0,    1,   0,  0,0, 1 },
115    { ARM::t2STRBs, ARM::tSTRB,   0,             0,   0,    1,   0,  0,0, 1 },
116    { ARM::t2STRHi12,ARM::tSTRH,  0,             5,   0,    1,   0,  0,0, 1 },
117    { ARM::t2STRHs, ARM::tSTRH,   0,             0,   0,    1,   0,  0,0, 1 },
118
119    { ARM::t2LDM_RET,0,           ARM::tPOP_RET, 0,   0,    1,   1,  1,1, 1 },
120    { ARM::t2LDM,   ARM::tLDM,    ARM::tPOP,     0,   0,    1,   1,  1,1, 1 },
121    { ARM::t2STM,   ARM::tSTM,    ARM::tPUSH,    0,   0,    1,   1,  1,1, 1 },
122  };
123
124  class VISIBILITY_HIDDEN Thumb2SizeReduce : public MachineFunctionPass {
125  public:
126    static char ID;
127    Thumb2SizeReduce();
128
129    const TargetInstrInfo *TII;
130
131    virtual bool runOnMachineFunction(MachineFunction &MF);
132
133    virtual const char *getPassName() const {
134      return "Thumb2 instruction size reduction pass";
135    }
136
137  private:
138    /// ReduceOpcodeMap - Maps wide opcode to index of entry in ReduceTable.
139    DenseMap<unsigned, unsigned> ReduceOpcodeMap;
140
141    bool VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
142                         bool is2Addr, ARMCC::CondCodes Pred,
143                         bool LiveCPSR, bool &HasCC, bool &CCDead);
144
145    bool ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
146                         const ReduceEntry &Entry);
147
148    bool ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
149                       const ReduceEntry &Entry, bool LiveCPSR);
150
151    /// ReduceTo2Addr - Reduce a 32-bit instruction to a 16-bit two-address
152    /// instruction.
153    bool ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
154                       const ReduceEntry &Entry,
155                       bool LiveCPSR);
156
157    /// ReduceToNarrow - Reduce a 32-bit instruction to a 16-bit
158    /// non-two-address instruction.
159    bool ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
160                        const ReduceEntry &Entry,
161                        bool LiveCPSR);
162
163    /// ReduceMBB - Reduce width of instructions in the specified basic block.
164    bool ReduceMBB(MachineBasicBlock &MBB);
165  };
166  char Thumb2SizeReduce::ID = 0;
167}
168
169Thumb2SizeReduce::Thumb2SizeReduce() : MachineFunctionPass(&ID) {
170  for (unsigned i = 0, e = array_lengthof(ReduceTable); i != e; ++i) {
171    unsigned FromOpc = ReduceTable[i].WideOpc;
172    if (!ReduceOpcodeMap.insert(std::make_pair(FromOpc, i)).second)
173      assert(false && "Duplicated entries?");
174  }
175}
176
177static bool HasImplicitCPSRDef(const TargetInstrDesc &TID) {
178  for (const unsigned *Regs = TID.ImplicitDefs; *Regs; ++Regs)
179    if (*Regs == ARM::CPSR)
180      return true;
181  return false;
182}
183
184bool
185Thumb2SizeReduce::VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
186                                  bool is2Addr, ARMCC::CondCodes Pred,
187                                  bool LiveCPSR, bool &HasCC, bool &CCDead) {
188  if ((is2Addr  && Entry.PredCC2 == 0) ||
189      (!is2Addr && Entry.PredCC1 == 0)) {
190    if (Pred == ARMCC::AL) {
191      // Not predicated, must set CPSR.
192      if (!HasCC) {
193        // Original instruction was not setting CPSR, but CPSR is not
194        // currently live anyway. It's ok to set it. The CPSR def is
195        // dead though.
196        if (!LiveCPSR) {
197          HasCC = true;
198          CCDead = true;
199          return true;
200        }
201        return false;
202      }
203    } else {
204      // Predicated, must not set CPSR.
205      if (HasCC)
206        return false;
207    }
208  } else if ((is2Addr  && Entry.PredCC2 == 2) ||
209             (!is2Addr && Entry.PredCC1 == 2)) {
210    /// Old opcode has an optional def of CPSR.
211    if (HasCC)
212      return true;
213    // If both old opcode does not implicit CPSR def, then it's not ok since
214    // these new opcodes CPSR def is not meant to be thrown away. e.g. CMP.
215    if (!HasImplicitCPSRDef(MI->getDesc()))
216      return false;
217    HasCC = true;
218  } else {
219    // 16-bit instruction does not set CPSR.
220    if (HasCC)
221      return false;
222  }
223
224  return true;
225}
226
227static bool VerifyLowRegs(MachineInstr *MI) {
228  unsigned Opc = MI->getOpcode();
229  bool isPCOk = (Opc == ARM::t2LDM_RET) || (Opc == ARM::t2LDM);
230  bool isLROk = (Opc == ARM::t2STM);
231  bool isSPOk = isPCOk || isLROk || (Opc == ARM::t2ADDrSPi);
232  for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
233    const MachineOperand &MO = MI->getOperand(i);
234    if (!MO.isReg() || MO.isImplicit())
235      continue;
236    unsigned Reg = MO.getReg();
237    if (Reg == 0 || Reg == ARM::CPSR)
238      continue;
239    if (isPCOk && Reg == ARM::PC)
240      continue;
241    if (isLROk && Reg == ARM::LR)
242      continue;
243    if (isSPOk && Reg == ARM::SP)
244      continue;
245    if (!isARMLowRegister(Reg))
246      return false;
247  }
248  return true;
249}
250
251bool
252Thumb2SizeReduce::ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI,
253                                  const ReduceEntry &Entry) {
254  if (ReduceLimitLdSt != -1 && ((int)NumLdSts >= ReduceLimitLdSt))
255    return false;
256
257  unsigned Scale = 1;
258  bool HasImmOffset = false;
259  bool HasShift = false;
260  bool isLdStMul = false;
261  bool isPopPush = false;
262  unsigned Opc = Entry.NarrowOpc1;
263  unsigned OpNum = 3; // First 'rest' of operands.
264  switch (Entry.WideOpc) {
265  default:
266    llvm_unreachable("Unexpected Thumb2 load / store opcode!");
267  case ARM::t2LDRi12:
268  case ARM::t2STRi12:
269    Scale = 4;
270    HasImmOffset = true;
271    break;
272  case ARM::t2LDRBi12:
273  case ARM::t2STRBi12:
274    HasImmOffset = true;
275    break;
276  case ARM::t2LDRHi12:
277  case ARM::t2STRHi12:
278    Scale = 2;
279    HasImmOffset = true;
280    break;
281  case ARM::t2LDRs:
282  case ARM::t2LDRBs:
283  case ARM::t2LDRHs:
284  case ARM::t2LDRSBs:
285  case ARM::t2LDRSHs:
286  case ARM::t2STRs:
287  case ARM::t2STRBs:
288  case ARM::t2STRHs:
289    HasShift = true;
290    OpNum = 4;
291    break;
292  case ARM::t2LDM_RET:
293  case ARM::t2LDM:
294  case ARM::t2STM: {
295    OpNum = 0;
296    unsigned BaseReg = MI->getOperand(0).getReg();
297    unsigned Mode = MI->getOperand(1).getImm();
298    if (BaseReg == ARM::SP && ARM_AM::getAM4WBFlag(Mode)) {
299      Opc = Entry.NarrowOpc2;
300      isPopPush = true;
301      OpNum = 2;
302    } else if (Entry.WideOpc == ARM::t2LDM_RET ||
303               !isARMLowRegister(BaseReg) ||
304               !ARM_AM::getAM4WBFlag(Mode) ||
305               ARM_AM::getAM4SubMode(Mode) != ARM_AM::ia) {
306      return false;
307    }
308    isLdStMul = true;
309    break;
310  }
311  }
312
313  unsigned OffsetReg = 0;
314  bool OffsetKill = false;
315  if (HasShift) {
316    OffsetReg  = MI->getOperand(2).getReg();
317    OffsetKill = MI->getOperand(2).isKill();
318    if (MI->getOperand(3).getImm())
319      // Thumb1 addressing mode doesn't support shift.
320      return false;
321  }
322
323  unsigned OffsetImm = 0;
324  if (HasImmOffset) {
325    OffsetImm = MI->getOperand(2).getImm();
326    unsigned MaxOffset = ((1 << Entry.Imm1Limit) - 1) * Scale;
327    if ((OffsetImm & (Scale-1)) || OffsetImm > MaxOffset)
328      // Make sure the immediate field fits.
329      return false;
330  }
331
332  // Add the 16-bit load / store instruction.
333  // FIXME: Thumb1 addressing mode encode both immediate and register offset.
334  DebugLoc dl = MI->getDebugLoc();
335  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, TII->get(Opc));
336  if (!isLdStMul) {
337    MIB.addOperand(MI->getOperand(0)).addOperand(MI->getOperand(1));
338    if (Entry.NarrowOpc1 != ARM::tLDRSB && Entry.NarrowOpc1 != ARM::tLDRSH) {
339      // tLDRSB and tLDRSH do not have an immediate offset field. On the other
340      // hand, it must have an offset register.
341      // FIXME: Remove this special case.
342      MIB.addImm(OffsetImm/Scale);
343    }
344    assert((!HasShift || OffsetReg) && "Invalid so_reg load / store address!");
345
346    MIB.addReg(OffsetReg, getKillRegState(OffsetKill));
347  }
348
349  // Transfer the rest of operands.
350  for (unsigned e = MI->getNumOperands(); OpNum != e; ++OpNum)
351    MIB.addOperand(MI->getOperand(OpNum));
352
353  DOUT << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB;
354
355  MBB.erase(MI);
356  ++NumLdSts;
357  return true;
358}
359
360bool
361Thumb2SizeReduce::ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI,
362                                const ReduceEntry &Entry,
363                                bool LiveCPSR) {
364  if (Entry.LowRegs1 && !VerifyLowRegs(MI))
365    return false;
366
367  const TargetInstrDesc &TID = MI->getDesc();
368  if (TID.mayLoad() || TID.mayStore())
369    return ReduceLoadStore(MBB, MI, Entry);
370
371  unsigned Opc = MI->getOpcode();
372  switch (Opc) {
373  default: break;
374  case ARM::t2ADDSri:
375  case ARM::t2ADDSrr: {
376    unsigned PredReg = 0;
377    if (getInstrPredicate(MI, PredReg) == ARMCC::AL) {
378      switch (Opc) {
379      default: break;
380      case ARM::t2ADDSri: {
381        if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR))
382          return true;
383        // fallthrough
384      }
385      case ARM::t2ADDSrr:
386        return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
387      }
388    }
389    break;
390  }
391  case ARM::t2RSBri:
392  case ARM::t2RSBSri:
393    if (MI->getOperand(2).getImm() == 0)
394      return ReduceToNarrow(MBB, MI, Entry, LiveCPSR);
395    break;
396  }
397  return false;
398}
399
400bool
401Thumb2SizeReduce::ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
402                                const ReduceEntry &Entry,
403                                bool LiveCPSR) {
404
405  if (ReduceLimit2Addr != -1 && ((int)Num2Addrs >= ReduceLimit2Addr))
406    return false;
407
408  const TargetInstrDesc &TID = MI->getDesc();
409  unsigned Reg0 = MI->getOperand(0).getReg();
410  unsigned Reg1 = MI->getOperand(1).getReg();
411  if (Reg0 != Reg1)
412    return false;
413  if (Entry.LowRegs2 && !isARMLowRegister(Reg0))
414    return false;
415  if (Entry.Imm2Limit) {
416    unsigned Imm = MI->getOperand(2).getImm();
417    unsigned Limit = (1 << Entry.Imm2Limit) - 1;
418    if (Imm > Limit)
419      return false;
420  } else {
421    unsigned Reg2 = MI->getOperand(2).getReg();
422    if (Entry.LowRegs2 && !isARMLowRegister(Reg2))
423      return false;
424  }
425
426  // Check if it's possible / necessary to transfer the predicate.
427  const TargetInstrDesc &NewTID = TII->get(Entry.NarrowOpc2);
428  unsigned PredReg = 0;
429  ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
430  bool SkipPred = false;
431  if (Pred != ARMCC::AL) {
432    if (!NewTID.isPredicable())
433      // Can't transfer predicate, fail.
434      return false;
435  } else {
436    SkipPred = !NewTID.isPredicable();
437  }
438
439  bool HasCC = false;
440  bool CCDead = false;
441  if (TID.hasOptionalDef()) {
442    unsigned NumOps = TID.getNumOperands();
443    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
444    if (HasCC && MI->getOperand(NumOps-1).isDead())
445      CCDead = true;
446  }
447  if (!VerifyPredAndCC(MI, Entry, true, Pred, LiveCPSR, HasCC, CCDead))
448    return false;
449
450  // Add the 16-bit instruction.
451  DebugLoc dl = MI->getDebugLoc();
452  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, NewTID);
453  MIB.addOperand(MI->getOperand(0));
454  if (HasCC && NewTID.hasOptionalDef())
455    AddDefaultT1CC(MIB, CCDead);
456
457  // Transfer the rest of operands.
458  unsigned NumOps = TID.getNumOperands();
459  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
460    if (i < NumOps && TID.OpInfo[i].isOptionalDef())
461      continue;
462    if (SkipPred && TID.OpInfo[i].isPredicate())
463      continue;
464    MIB.addOperand(MI->getOperand(i));
465  }
466
467  DOUT << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB;
468
469  MBB.erase(MI);
470  ++Num2Addrs;
471  return true;
472}
473
474bool
475Thumb2SizeReduce::ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
476                                 const ReduceEntry &Entry,
477                                 bool LiveCPSR) {
478  if (ReduceLimit != -1 && ((int)NumNarrows >= ReduceLimit))
479    return false;
480
481  unsigned Limit = ~0U;
482  unsigned Scale = (Entry.WideOpc == ARM::t2ADDrSPi) ? 4 : 1;
483  if (Entry.Imm1Limit)
484    Limit = ((1 << Entry.Imm1Limit) - 1) * Scale;
485
486  const TargetInstrDesc &TID = MI->getDesc();
487  for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
488    if (TID.OpInfo[i].isPredicate())
489      continue;
490    const MachineOperand &MO = MI->getOperand(i);
491    if (MO.isReg()) {
492      unsigned Reg = MO.getReg();
493      if (!Reg || Reg == ARM::CPSR)
494        continue;
495      if (Entry.WideOpc == ARM::t2ADDrSPi && Reg == ARM::SP)
496        continue;
497      if (Entry.LowRegs1 && !isARMLowRegister(Reg))
498        return false;
499    } else if (MO.isImm() &&
500               !TID.OpInfo[i].isPredicate()) {
501      if (MO.getImm() > Limit || (MO.getImm() & (Scale-1)) != 0)
502        return false;
503    }
504  }
505
506  // Check if it's possible / necessary to transfer the predicate.
507  const TargetInstrDesc &NewTID = TII->get(Entry.NarrowOpc1);
508  unsigned PredReg = 0;
509  ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
510  bool SkipPred = false;
511  if (Pred != ARMCC::AL) {
512    if (!NewTID.isPredicable())
513      // Can't transfer predicate, fail.
514      return false;
515  } else {
516    SkipPred = !NewTID.isPredicable();
517  }
518
519  bool HasCC = false;
520  bool CCDead = false;
521  if (TID.hasOptionalDef()) {
522    unsigned NumOps = TID.getNumOperands();
523    HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
524    if (HasCC && MI->getOperand(NumOps-1).isDead())
525      CCDead = true;
526  }
527  if (!VerifyPredAndCC(MI, Entry, false, Pred, LiveCPSR, HasCC, CCDead))
528    return false;
529
530  // Add the 16-bit instruction.
531  DebugLoc dl = MI->getDebugLoc();
532  MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, NewTID);
533  MIB.addOperand(MI->getOperand(0));
534  if (HasCC && NewTID.hasOptionalDef())
535    AddDefaultT1CC(MIB, CCDead);
536
537  // Transfer the rest of operands.
538  unsigned NumOps = TID.getNumOperands();
539  for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) {
540    if (i < NumOps && TID.OpInfo[i].isOptionalDef())
541      continue;
542    if ((TID.getOpcode() == ARM::t2RSBSri ||
543         TID.getOpcode() == ARM::t2RSBri) && i == 2)
544      // Skip the zero immediate operand, it's now implicit.
545      continue;
546    bool isPred = (i < NumOps && TID.OpInfo[i].isPredicate());
547    if (SkipPred && isPred)
548        continue;
549    const MachineOperand &MO = MI->getOperand(i);
550    if (Scale > 1 && !isPred && MO.isImm())
551      MIB.addImm(MO.getImm() / Scale);
552    else {
553      if (MO.isReg() && MO.isImplicit() && MO.getReg() == ARM::CPSR)
554        // Skip implicit def of CPSR. Either it's modeled as an optional
555        // def now or it's already an implicit def on the new instruction.
556        continue;
557      MIB.addOperand(MO);
558    }
559  }
560  if (!TID.isPredicable() && NewTID.isPredicable())
561    AddDefaultPred(MIB);
562
563  DOUT << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB;
564
565  MBB.erase(MI);
566  ++NumNarrows;
567  return true;
568}
569
570static bool UpdateCPSRDef(MachineInstr &MI, bool LiveCPSR) {
571  bool HasDef = false;
572  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
573    const MachineOperand &MO = MI.getOperand(i);
574    if (!MO.isReg() || MO.isUndef() || MO.isUse())
575      continue;
576    if (MO.getReg() != ARM::CPSR)
577      continue;
578    if (!MO.isDead())
579      HasDef = true;
580  }
581
582  return HasDef || LiveCPSR;
583}
584
585static bool UpdateCPSRUse(MachineInstr &MI, bool LiveCPSR) {
586  for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
587    const MachineOperand &MO = MI.getOperand(i);
588    if (!MO.isReg() || MO.isUndef() || MO.isDef())
589      continue;
590    if (MO.getReg() != ARM::CPSR)
591      continue;
592    assert(LiveCPSR && "CPSR liveness tracking is wrong!");
593    if (MO.isKill()) {
594      LiveCPSR = false;
595      break;
596    }
597  }
598
599  return LiveCPSR;
600}
601
602bool Thumb2SizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
603  bool Modified = false;
604
605  bool LiveCPSR = false;
606  // Yes, CPSR could be livein.
607  for (MachineBasicBlock::const_livein_iterator I = MBB.livein_begin(),
608         E = MBB.livein_end(); I != E; ++I) {
609    if (*I == ARM::CPSR) {
610      LiveCPSR = true;
611      break;
612    }
613  }
614
615  MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
616  MachineBasicBlock::iterator NextMII;
617  for (; MII != E; MII = NextMII) {
618    NextMII = next(MII);
619
620    MachineInstr *MI = &*MII;
621    LiveCPSR = UpdateCPSRUse(*MI, LiveCPSR);
622
623    unsigned Opcode = MI->getOpcode();
624    DenseMap<unsigned, unsigned>::iterator OPI = ReduceOpcodeMap.find(Opcode);
625    if (OPI != ReduceOpcodeMap.end()) {
626      const ReduceEntry &Entry = ReduceTable[OPI->second];
627      // Ignore "special" cases for now.
628      if (Entry.Special) {
629        if (ReduceSpecial(MBB, MI, Entry, LiveCPSR)) {
630          Modified = true;
631          MachineBasicBlock::iterator I = prior(NextMII);
632          MI = &*I;
633        }
634        goto ProcessNext;
635      }
636
637      // Try to transform to a 16-bit two-address instruction.
638      if (Entry.NarrowOpc2 && ReduceTo2Addr(MBB, MI, Entry, LiveCPSR)) {
639        Modified = true;
640        MachineBasicBlock::iterator I = prior(NextMII);
641        MI = &*I;
642        goto ProcessNext;
643      }
644
645      // Try to transform ro a 16-bit non-two-address instruction.
646      if (Entry.NarrowOpc1 && ReduceToNarrow(MBB, MI, Entry, LiveCPSR))
647        Modified = true;
648    }
649
650  ProcessNext:
651    LiveCPSR = UpdateCPSRDef(*MI, LiveCPSR);
652  }
653
654  return Modified;
655}
656
657bool Thumb2SizeReduce::runOnMachineFunction(MachineFunction &MF) {
658  const TargetMachine &TM = MF.getTarget();
659  TII = TM.getInstrInfo();
660
661  bool Modified = false;
662  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
663    Modified |= ReduceMBB(*I);
664  return Modified;
665}
666
667/// createThumb2SizeReductionPass - Returns an instance of the Thumb2 size
668/// reduction pass.
669FunctionPass *llvm::createThumb2SizeReductionPass() {
670  return new Thumb2SizeReduce();
671}
672