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 "ARMBaseRegisterInfo.h"
  13 #include "ARMBaseInstrInfo.h"
  14 #include "Thumb2InstrInfo.h"
  15 #include "llvm/CodeGen/MachineInstr.h"
  16 #include "llvm/CodeGen/MachineInstrBuilder.h"
  17 #include "llvm/CodeGen/MachineFunctionPass.h"
  18 #include "llvm/Support/Compiler.h"
  19 #include "llvm/Support/Debug.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/Statistic.h"
  22 using namespace llvm;
  23
  24 STATISTIC(NumNarrows,  "Number of 32-bit instructions reduced to 16-bit ones");
  25 STATISTIC(Num2Addrs,   "Number of 32-bit instructions reduced to 2-address");
  26
  27 namespace {
  28   /// ReduceTable - A static table with information on mapping from wide
  29   /// opcodes to narrow
  30   struct ReduceEntry {
  31     unsigned WideOpc;      // Wide opcode
  32     unsigned NarrowOpc1;   // Narrow opcode to transform to
  33     unsigned NarrowOpc2;   // Narrow opcode when it's two-address
  34     uint8_t  Imm1Limit;    // Limit of immediate field (bits)
  35     uint8_t  Imm2Limit;    // Limit of immediate field when it's two-address
  36     unsigned LowRegs1 : 1; // Only possible if low-registers are used
  37     unsigned LowRegs2 : 1; // Only possible if low-registers are used (2addr)
  38     unsigned PredCC1  : 1; // 0 - If predicated, cc is on and vice versa.
  39                            // 1 - No cc field.
  40     unsigned PredCC2  : 1;
  41     unsigned Special  : 1; // Needs to be dealt with specially
  42   };
  43
  44   static const ReduceEntry ReduceTable[] = {
  45     // Wide,        Narrow1,      Narrow2,     imm1,imm2,  lo1, lo2, P/C, S
  46     { ARM::t2ADCrr, ARM::tADC,    0,             0,   0,    1,   0,  0,0, 0 },
  47     // FIXME: t2ADDS variants.
  48     { ARM::t2ADDri, ARM::tADDi3,  ARM::tADDi8,   3,   8,    1,   1,  0,0, 0 },
  49     { ARM::t2ADDrr, ARM::tADDrr,  ARM::tADDhirr, 0,   0,    1,   0,  0,1, 0 },
  50     { ARM::t2ANDrr, ARM::tAND,    0,             0,   0,    1,   0,  0,0, 0 },
  51     { ARM::t2ASRri, ARM::tASRri,  0,             5,   0,    1,   0,  0,0, 0 },
  52     { ARM::t2ASRrr, ARM::tASRrr,  0,             0,   0,    1,   0,  0,0, 0 },
  53     { ARM::t2BICrr, ARM::tBIC,    0,             0,   0,    1,   0,  0,0, 0 },
  54     { ARM::t2CMNrr, ARM::tCMN,    0,             0,   0,    1,   0,  1,0, 0 },
  55     { ARM::t2CMPri, ARM::tCMPi8,  0,             8,   0,    1,   0,  1,0, 0 },
  56     { ARM::t2CMPrr, ARM::tCMPhir, 0,             0,   0,    0,   0,  1,0, 0 },
  57     { ARM::t2CMPzri,ARM::tCMPzi8, 0,             8,   0,    1,   0,  1,0, 0 },
  58     { ARM::t2CMPzrr,ARM::tCMPzhir,0,             0,   0,    0,   0,  1,0, 0 },
  59     { ARM::t2EORrr, ARM::tEOR,    0,             0,   0,    1,   0,  0,0, 0 },
  60     { ARM::t2LSLri, ARM::tLSLri,  0,             5,   0,    1,   0,  0,0, 0 },
  61     { ARM::t2LSLrr, ARM::tLSLrr,  0,             0,   0,    1,   0,  0,0, 0 },
  62     { ARM::t2LSRri, ARM::tLSRri,  0,             5,   0,    1,   0,  0,0, 0 },
  63     { ARM::t2LSRrr, ARM::tLSRrr,  0,             0,   0,    1,   0,  0,0, 0 },
  64     { ARM::t2MOVi,  ARM::tMOVi8,  0,             8,   0,    1,   0,  0,0, 0 },
  65     // FIXME: Do we need the 16-bit 'S' variant?
  66     { ARM::t2MOVr,ARM::tMOVgpr2gpr,0,            0,   0,    0,   0,  1,0, 0 },
  67     { ARM::t2MUL,   ARM::tMUL,    0,             0,   0,    1,   0,  0,0, 0 },
  68     { ARM::t2MVNr,  ARM::tMVN,    0,             0,   0,    1,   0,  0,0, 0 },
  69     { ARM::t2ORRrr, ARM::tORR,    0,             0,   0,    1,   0,  0,0, 0 },
  70     { ARM::t2REV,   ARM::tREV,    0,             0,   0,    1,   0,  0,0, 0 },
  71     { ARM::t2REV16, ARM::tREV16,  0,             0,   0,    1,   0,  0,0, 0 },
  72     { ARM::t2REVSH, ARM::tREVSH,  0,             0,   0,    1,   0,  0,0, 0 },
  73     { ARM::t2RORrr, ARM::tROR,    0,             0,   0,    1,   0,  0,0, 0 },
  74     // FIXME: T2RSBri immediate must be zero. Also need entry for T2RSBS
  75     //{ ARM::t2RSBri, ARM::tRSB,    0,             0,   0,    1,   0,  0,0, 0 },
  76     { ARM::t2SUBri, ARM::tSUBi3,  ARM::tSUBi8,   3,   8,    1,   1,  0,0, 0 },
  77     { ARM::t2SUBrr, ARM::tSUBrr,  0,             0,   0,    1,   0,  0,0, 0 },
  78     { ARM::t2SXTBr, ARM::tSXTB,   0,             0,   0,    1,   0,  1,0, 0 },
  79     { ARM::t2SXTHr, ARM::tSXTH,   0,             0,   0,    1,   0,  1,0, 0 },
  80     { ARM::t2TSTrr, ARM::tTST,    0,             0,   0,    1,   0,  1,0, 0 },
  81     { ARM::t2UXTBr, ARM::tUXTB,   0,             0,   0,    1,   0,  1,0, 0 },
  82     { ARM::t2UXTHr, ARM::tUXTH,   0,             0,   0,    1,   0,  1,0, 0 }
  83   };
  84
  85   class VISIBILITY_HIDDEN Thumb2SizeReduce : public MachineFunctionPass {
  86   public:
  87     static char ID;
  88     Thumb2SizeReduce();
  89
  90     const TargetInstrInfo *TII;
  91
  92     virtual bool runOnMachineFunction(MachineFunction &MF);
  93
  94     virtual const char *getPassName() const {
  95       return "Thumb2 instruction size reduction pass";
  96     }
  97
  98   private:
  99     /// ReduceOpcodeMap - Maps wide opcode to index of entry in ReduceTable.
 100     DenseMap<unsigned, unsigned> ReduceOpcodeMap;
 101
 102     /// ReduceTo2Addr - Reduce a 32-bit instruction to a 16-bit two-address
 103     /// instruction.
 104     bool ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
 105                        const ReduceEntry &Entry,
 106                        bool LiveCPSR);
 107
 108     /// ReduceToNarrow - Reduce a 32-bit instruction to a 16-bit
 109     /// non-two-address instruction.
 110     bool ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
 111                         const ReduceEntry &Entry,
 112                         bool LiveCPSR);
 113
 114     /// ReduceMBB - Reduce width of instructions in the specified basic block.
 115     bool ReduceMBB(MachineBasicBlock &MBB);
 116   };
 117   char Thumb2SizeReduce::ID = 0;
 118 }
 119
 120 Thumb2SizeReduce::Thumb2SizeReduce() : MachineFunctionPass(&ID) {
 121   for (unsigned i = 0, e = array_lengthof(ReduceTable); i != e; ++i) {
 122     unsigned FromOpc = ReduceTable[i].WideOpc;
 123     if (!ReduceOpcodeMap.insert(std::make_pair(FromOpc, i)).second)
 124       assert(false && "Duplicated entries?");
 125   }
 126 }
 127
 128 static bool VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry,
 129                             bool is2Addr, bool LiveCPSR,
 130                             bool &HasCC, bool &CCDead) {
 131   unsigned PredReg = 0;
 132   ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg);
 133   if ((is2Addr  && Entry.PredCC2 == 0) ||
 134       (!is2Addr && Entry.PredCC1 == 0)) {
 135     if (Pred == ARMCC::AL) {
 136       // Not predicated, must set CPSR.
 137       if (!HasCC) {
 138         // Original instruction was not setting CPSR, but CPSR is not
 139         // currently live anyway. It's ok to set it. The CPSR def is
 140         // dead though.
 141         if (!LiveCPSR) {
 142           HasCC = true;
 143           CCDead = true;
 144           return true;
 145         }
 146         return false;
 147       }
 148     } else {
 149       // Predicated, must not set CPSR.
 150       if (HasCC)
 151         return false;
 152     }
 153   } else {
 154     // 16-bit instruction does not set CPSR.
 155     if (HasCC)
 156       return false;
 157   }
 158
 159   return true;
 160 }
 161
 162 bool
 163 Thumb2SizeReduce::ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI,
 164                                 const ReduceEntry &Entry,
 165                                 bool LiveCPSR) {
 166   const TargetInstrDesc &TID = MI->getDesc();
 167   unsigned Reg0 = MI->getOperand(0).getReg();
 168   unsigned Reg1 = MI->getOperand(1).getReg();
 169   if (Reg0 != Reg1)
 170     return false;
 171   if (Entry.LowRegs2 && !isARMLowRegister(Reg0))
 172     return false;
 173   if (Entry.Imm2Limit) {
 174     unsigned Imm = MI->getOperand(2).getImm();
 175     unsigned Limit = (1 << Entry.Imm2Limit) - 1;
 176     if (Imm > Limit)
 177       return false;
 178   } else {
 179     unsigned Reg2 = MI->getOperand(2).getReg();
 180     if (Entry.LowRegs2 && !isARMLowRegister(Reg2))
 181       return false;
 182   }
 183
 184   bool HasCC = false;
 185   bool CCDead = false;
 186   if (TID.hasOptionalDef()) {
 187     unsigned NumOps = TID.getNumOperands();
 188     HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
 189     if (HasCC && MI->getOperand(NumOps-1).isDead())
 190       CCDead = true;
 191   }
 192   if (!VerifyPredAndCC(MI, Entry, true, LiveCPSR, HasCC, CCDead))
 193     return false;
 194
 195   // Add the 16-bit instruction.
 196   DebugLoc dl = MI->getDebugLoc();
 197   MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, TII->get(Entry.NarrowOpc2));
 198   MIB.addOperand(MI->getOperand(0));
 199   if (HasCC)
 200     AddDefaultT1CC(MIB, CCDead);
 201
 202   // Transfer the rest of operands.
 203   unsigned NumOps = TID.getNumOperands();
 204   for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i)
 205     if (!(i < NumOps && TID.OpInfo[i].isOptionalDef()))
 206       MIB.addOperand(MI->getOperand(i));
 207
 208   DOUT << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB;
 209
 210   MBB.erase(MI);
 211   ++Num2Addrs;
 212   ++NumNarrows;
 213   return true;
 214 }
 215
 216 bool
 217 Thumb2SizeReduce::ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI,
 218                                  const ReduceEntry &Entry,
 219                                  bool LiveCPSR) {
 220   unsigned Limit = ~0U;
 221   if (Entry.Imm1Limit)
 222     Limit = (1 << Entry.Imm1Limit) - 1;
 223
 224   const TargetInstrDesc &TID = MI->getDesc();
 225   for (unsigned i = 0, e = TID.getNumOperands(); i != e; ++i) {
 226     if (TID.OpInfo[i].isPredicate())
 227       continue;
 228     const MachineOperand &MO = MI->getOperand(i);
 229     if (MO.isReg()) {
 230       unsigned Reg = MO.getReg();
 231       if (!Reg || Reg == ARM::CPSR)
 232         continue;
 233       if (Entry.LowRegs1 && !isARMLowRegister(Reg))
 234         return false;
 235     } else if (MO.isImm()) {
 236       if (MO.getImm() > Limit)
 237         return false;
 238     }
 239   }
 240
 241   bool HasCC = false;
 242   bool CCDead = false;
 243   if (TID.hasOptionalDef()) {
 244     unsigned NumOps = TID.getNumOperands();
 245     HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR);
 246     if (HasCC && MI->getOperand(NumOps-1).isDead())
 247       CCDead = true;
 248   }
 249   if (!VerifyPredAndCC(MI, Entry, false, LiveCPSR, HasCC, CCDead))
 250     return false;
 251
 252   // Add the 16-bit instruction.
 253   DebugLoc dl = MI->getDebugLoc();
 254   MachineInstrBuilder MIB = BuildMI(MBB, *MI, dl, TII->get(Entry.NarrowOpc1));
 255   MIB.addOperand(MI->getOperand(0));
 256   if (HasCC)
 257     AddDefaultT1CC(MIB, CCDead);
 258
 259   // Transfer the rest of operands.
 260   unsigned NumOps = TID.getNumOperands();
 261   for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i)
 262     if (!(i < NumOps && TID.OpInfo[i].isOptionalDef()))
 263       MIB.addOperand(MI->getOperand(i));
 264
 265
 266   DOUT << "Converted 32-bit: " << *MI << "       to 16-bit: " << *MIB;
 267
 268   MBB.erase(MI);
 269   ++Num2Addrs;
 270   ++NumNarrows;
 271   return true;
 272 }
 273
 274 static bool UpdateCPSRLiveness(MachineInstr &MI, bool LiveCPSR) {
 275   bool HasDef = false;
 276   for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) {
 277     const MachineOperand &MO = MI.getOperand(i);
 278     if (!MO.isReg() || MO.isUndef())
 279       continue;
 280     if (MO.getReg() != ARM::CPSR)
 281       continue;
 282     if (MO.isDef()) {
 283       if (!MO.isDead())
 284         HasDef = true;
 285       continue;
 286     }
 287
 288     assert(LiveCPSR && "CPSR liveness tracking is wrong!");
 289     if (MO.isKill()) {
 290       LiveCPSR = false;
 291       break;
 292     }
 293   }
 294
 295   return HasDef || LiveCPSR;
 296 }
 297
 298 bool Thumb2SizeReduce::ReduceMBB(MachineBasicBlock &MBB) {
 299   bool Modified = false;
 300
 301   // FIXME: Track whether CPSR is live. If not, then it's possible to convert
 302   // one that doesn't set CPSR to one that does.
 303   bool LiveCPSR = false;
 304   MachineBasicBlock::iterator MII = MBB.begin(), E = MBB.end();
 305   MachineBasicBlock::iterator NextMII = next(MII);
 306   for (; MII != E; MII = NextMII) {
 307     NextMII = next(MII);
 308
 309     MachineInstr *MI = &*MII;
 310     unsigned Opcode = MI->getOpcode();
 311     DenseMap<unsigned, unsigned>::iterator OPI = ReduceOpcodeMap.find(Opcode);
 312     if (OPI != ReduceOpcodeMap.end()) {
 313       const ReduceEntry &Entry = ReduceTable[OPI->second];
 314       // Ignore "special" cases for now.
 315       if (Entry.Special)
 316         goto ProcessNext;
 317
 318       // Try to transform to a 16-bit two-address instruction.
 319       if (Entry.NarrowOpc2 && ReduceTo2Addr(MBB, MI, Entry, LiveCPSR)) {
 320         Modified = true;
 321         MachineBasicBlock::iterator I = prior(NextMII);
 322         MI = &*I;
 323         goto ProcessNext;
 324       }
 325
 326       // Try to transform ro a 16-bit non-two-address instruction.
 327       if (Entry.NarrowOpc1 && ReduceToNarrow(MBB, MI, Entry, LiveCPSR))
 328         Modified = true;
 329     }
 330
 331   ProcessNext:
 332     LiveCPSR = UpdateCPSRLiveness(*MI, LiveCPSR);
 333   }
 334
 335   return Modified;
 336 }
 337
 338 bool Thumb2SizeReduce::runOnMachineFunction(MachineFunction &MF) {
 339   const TargetMachine &TM = MF.getTarget();
 340   TII = TM.getInstrInfo();
 341
 342   bool Modified = false;
 343   for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
 344     Modified |= ReduceMBB(*I);
 345   return Modified;
 346 }
 347
 348 /// createThumb2SizeReductionPass - Returns an instance of the Thumb2 size
 349 /// reduction pass.
 350 FunctionPass *llvm::createThumb2SizeReductionPass() {
 351   return new Thumb2SizeReduce();
 352 }