lib/Target/ARM/Thumb2SizeReduction.cpp

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