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 "ARMSubtarget.h" 15 #include "Thumb2InstrInfo.h" 16 #include "MCTargetDesc/ARMAddressingModes.h" 17 #include "llvm/CodeGen/MachineInstr.h" 18 #include "llvm/CodeGen/MachineInstrBuilder.h" 19 #include "llvm/CodeGen/MachineFunctionPass.h" 20 #include "llvm/Support/CommandLine.h" 21 #include "llvm/Support/Debug.h" 22 #include "llvm/Support/raw_ostream.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include "llvm/ADT/Statistic.h" 25 using namespace llvm; 26 27 STATISTIC(NumNarrows, "Number of 32-bit instrs reduced to 16-bit ones"); 28 STATISTIC(Num2Addrs, "Number of 32-bit instrs reduced to 2addr 16-bit ones"); 29 STATISTIC(NumLdSts, "Number of 32-bit load / store reduced to 16-bit ones"); 30 31 static cl::opt<int> ReduceLimit("t2-reduce-limit", 32 cl::init(-1), cl::Hidden); 33 static cl::opt<int> ReduceLimit2Addr("t2-reduce-limit2", 34 cl::init(-1), cl::Hidden); 35 static cl::opt<int> ReduceLimitLdSt("t2-reduce-limit3", 36 cl::init(-1), cl::Hidden); 37 38 namespace { 39 /// ReduceTable - A static table with information on mapping from wide 40 /// opcodes to narrow 41 struct ReduceEntry { 42 uint16_t WideOpc; // Wide opcode 43 uint16_t NarrowOpc1; // Narrow opcode to transform to 44 uint16_t NarrowOpc2; // Narrow opcode when it's two-address 45 uint8_t Imm1Limit; // Limit of immediate field (bits) 46 uint8_t Imm2Limit; // Limit of immediate field when it's two-address 47 unsigned LowRegs1 : 1; // Only possible if low-registers are used 48 unsigned LowRegs2 : 1; // Only possible if low-registers are used (2addr) 49 unsigned PredCC1 : 2; // 0 - If predicated, cc is on and vice versa. 50 // 1 - No cc field. 51 // 2 - Always set CPSR. 52 unsigned PredCC2 : 2; 53 unsigned PartFlag : 1; // 16-bit instruction does partial flag update 54 unsigned Special : 1; // Needs to be dealt with specially 55 }; 56 57 static const ReduceEntry ReduceTable[] = { 58 // Wide, Narrow1, Narrow2, imm1,imm2, lo1, lo2, P/C, PF, S 59 { ARM::t2ADCrr, 0, ARM::tADC, 0, 0, 0, 1, 0,0, 0,0 }, 60 { ARM::t2ADDri, ARM::tADDi3, ARM::tADDi8, 3, 8, 1, 1, 0,0, 0,1 }, 61 { ARM::t2ADDrr, ARM::tADDrr, ARM::tADDhirr, 0, 0, 1, 0, 0,1, 0,0 }, 62 { ARM::t2ADDSri,ARM::tADDi3, ARM::tADDi8, 3, 8, 1, 1, 2,2, 0,1 }, 63 { ARM::t2ADDSrr,ARM::tADDrr, 0, 0, 0, 1, 0, 2,0, 0,1 }, 64 { ARM::t2ANDrr, 0, ARM::tAND, 0, 0, 0, 1, 0,0, 1,0 }, 65 { ARM::t2ASRri, ARM::tASRri, 0, 5, 0, 1, 0, 0,0, 1,0 }, 66 { ARM::t2ASRrr, 0, ARM::tASRrr, 0, 0, 0, 1, 0,0, 1,0 }, 67 { ARM::t2BICrr, 0, ARM::tBIC, 0, 0, 0, 1, 0,0, 1,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,0 }, 70 { ARM::t2CMPri, ARM::tCMPi8, 0, 8, 0, 1, 0, 2,0, 0,0 }, 71 { ARM::t2CMPrr, ARM::tCMPhir, 0, 0, 0, 0, 0, 2,0, 0,1 }, 72 { ARM::t2EORrr, 0, ARM::tEOR, 0, 0, 0, 1, 0,0, 1,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,0 }, 75 { ARM::t2LSLri, ARM::tLSLri, 0, 5, 0, 1, 0, 0,0, 1,0 }, 76 { ARM::t2LSLrr, 0, ARM::tLSLrr, 0, 0, 0, 1, 0,0, 1,0 }, 77 { ARM::t2LSRri, ARM::tLSRri, 0, 5, 0, 1, 0, 0,0, 1,0 }, 78 { ARM::t2LSRrr, 0, ARM::tLSRrr, 0, 0, 0, 1, 0,0, 1,0 }, 79 // FIXME: tMOVi8 and tMVN also partially update CPSR but they are less 80 // likely to cause issue in the loop. As a size / performance workaround, 81 // they are not marked as such. 82 { ARM::t2MOVi, ARM::tMOVi8, 0, 8, 0, 1, 0, 0,0, 0,0 }, 83 { ARM::t2MOVi16,ARM::tMOVi8, 0, 8, 0, 1, 0, 0,0, 0,1 }, 84 // FIXME: Do we need the 16-bit 'S' variant? 85 { ARM::t2MOVr,ARM::tMOVr, 0, 0, 0, 0, 0, 1,0, 0,0 }, 86 { ARM::t2MUL, 0, ARM::tMUL, 0, 0, 0, 1, 0,0, 1,0 }, 87 { ARM::t2MVNr, ARM::tMVN, 0, 0, 0, 1, 0, 0,0, 0,0 }, 88 { ARM::t2ORRrr, 0, ARM::tORR, 0, 0, 0, 1, 0,0, 1,0 }, 89 { ARM::t2REV, ARM::tREV, 0, 0, 0, 1, 0, 1,0, 0,0 }, 90 { ARM::t2REV16, ARM::tREV16, 0, 0, 0, 1, 0, 1,0, 0,0 }, 91 { ARM::t2REVSH, ARM::tREVSH, 0, 0, 0, 1, 0, 1,0, 0,0 }, 92 { ARM::t2RORrr, 0, ARM::tROR, 0, 0, 0, 1, 0,0, 1,0 }, 93 { ARM::t2RSBri, ARM::tRSB, 0, 0, 0, 1, 0, 0,0, 0,1 }, 94 { ARM::t2RSBSri,ARM::tRSB, 0, 0, 0, 1, 0, 2,0, 0,1 }, 95 { ARM::t2SBCrr, 0, ARM::tSBC, 0, 0, 0, 1, 0,0, 0,0 }, 96 { ARM::t2SUBri, ARM::tSUBi3, ARM::tSUBi8, 3, 8, 1, 1, 0,0, 0,0 }, 97 { ARM::t2SUBrr, ARM::tSUBrr, 0, 0, 0, 1, 0, 0,0, 0,0 }, 98 { ARM::t2SUBSri,ARM::tSUBi3, ARM::tSUBi8, 3, 8, 1, 1, 2,2, 0,0 }, 99 { ARM::t2SUBSrr,ARM::tSUBrr, 0, 0, 0, 1, 0, 2,0, 0,0 }, 100 { ARM::t2SXTB, ARM::tSXTB, 0, 0, 0, 1, 0, 1,0, 0,1 }, 101 { ARM::t2SXTH, ARM::tSXTH, 0, 0, 0, 1, 0, 1,0, 0,1 }, 102 { ARM::t2TSTrr, ARM::tTST, 0, 0, 0, 1, 0, 2,0, 0,0 }, 103 { ARM::t2UXTB, ARM::tUXTB, 0, 0, 0, 1, 0, 1,0, 0,1 }, 104 { ARM::t2UXTH, ARM::tUXTH, 0, 0, 0, 1, 0, 1,0, 0,1 }, 105 106 // FIXME: Clean this up after splitting each Thumb load / store opcode 107 // into multiple ones. 108 { ARM::t2LDRi12,ARM::tLDRi, ARM::tLDRspi, 5, 8, 1, 0, 0,0, 0,1 }, 109 { ARM::t2LDRs, ARM::tLDRr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 110 { ARM::t2LDRBi12,ARM::tLDRBi, 0, 5, 0, 1, 0, 0,0, 0,1 }, 111 { ARM::t2LDRBs, ARM::tLDRBr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 112 { ARM::t2LDRHi12,ARM::tLDRHi, 0, 5, 0, 1, 0, 0,0, 0,1 }, 113 { ARM::t2LDRHs, ARM::tLDRHr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 114 { ARM::t2LDRSBs,ARM::tLDRSB, 0, 0, 0, 1, 0, 0,0, 0,1 }, 115 { ARM::t2LDRSHs,ARM::tLDRSH, 0, 0, 0, 1, 0, 0,0, 0,1 }, 116 { ARM::t2STRi12,ARM::tSTRi, ARM::tSTRspi, 5, 8, 1, 0, 0,0, 0,1 }, 117 { ARM::t2STRs, ARM::tSTRr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 118 { ARM::t2STRBi12,ARM::tSTRBi, 0, 5, 0, 1, 0, 0,0, 0,1 }, 119 { ARM::t2STRBs, ARM::tSTRBr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 120 { ARM::t2STRHi12,ARM::tSTRHi, 0, 5, 0, 1, 0, 0,0, 0,1 }, 121 { ARM::t2STRHs, ARM::tSTRHr, 0, 0, 0, 1, 0, 0,0, 0,1 }, 122 123 { ARM::t2LDMIA, ARM::tLDMIA, 0, 0, 0, 1, 1, 1,1, 0,1 }, 124 { ARM::t2LDMIA_RET,0, ARM::tPOP_RET, 0, 0, 1, 1, 1,1, 0,1 }, 125 { ARM::t2LDMIA_UPD,ARM::tLDMIA_UPD,ARM::tPOP,0, 0, 1, 1, 1,1, 0,1 }, 126 // ARM::t2STM (with no basereg writeback) has no Thumb1 equivalent 127 { ARM::t2STMIA_UPD,ARM::tSTMIA_UPD, 0, 0, 0, 1, 1, 1,1, 0,1 }, 128 { ARM::t2STMDB_UPD, 0, ARM::tPUSH, 0, 0, 1, 1, 1,1, 0,1 }, 129 }; 130 131 class Thumb2SizeReduce : public MachineFunctionPass { 132 public: 133 static char ID; 134 Thumb2SizeReduce(); 135 136 const Thumb2InstrInfo *TII; 137 const ARMSubtarget *STI; 138 139 virtual bool runOnMachineFunction(MachineFunction &MF); 140 141 virtual const char *getPassName() const { 142 return "Thumb2 instruction size reduction pass"; 143 } 144 145 private: 146 /// ReduceOpcodeMap - Maps wide opcode to index of entry in ReduceTable. 147 DenseMap<unsigned, unsigned> ReduceOpcodeMap; 148 149 bool canAddPseudoFlagDep(MachineInstr *Def, MachineInstr *Use, 150 bool IsSelfLoop); 151 152 bool VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry, 153 bool is2Addr, ARMCC::CondCodes Pred, 154 bool LiveCPSR, bool &HasCC, bool &CCDead); 155 156 bool ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI, 157 const ReduceEntry &Entry); 158 159 bool ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI, 160 const ReduceEntry &Entry, bool LiveCPSR, 161 MachineInstr *CPSRDef, bool IsSelfLoop); 162 163 /// ReduceTo2Addr - Reduce a 32-bit instruction to a 16-bit two-address 164 /// instruction. 165 bool ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI, 166 const ReduceEntry &Entry, 167 bool LiveCPSR, MachineInstr *CPSRDef, 168 bool IsSelfLoop); 169 170 /// ReduceToNarrow - Reduce a 32-bit instruction to a 16-bit 171 /// non-two-address instruction. 172 bool ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI, 173 const ReduceEntry &Entry, 174 bool LiveCPSR, MachineInstr *CPSRDef, 175 bool IsSelfLoop); 176 177 /// ReduceMBB - Reduce width of instructions in the specified basic block. 178 bool ReduceMBB(MachineBasicBlock &MBB); 179 }; 180 char Thumb2SizeReduce::ID = 0; 181 } 182 183 Thumb2SizeReduce::Thumb2SizeReduce() : MachineFunctionPass(ID) { 184 for (unsigned i = 0, e = array_lengthof(ReduceTable); i != e; ++i) { 185 unsigned FromOpc = ReduceTable[i].WideOpc; 186 if (!ReduceOpcodeMap.insert(std::make_pair(FromOpc, i)).second) 187 assert(false && "Duplicated entries?"); 188 } 189 } 190 191 static bool HasImplicitCPSRDef(const MCInstrDesc &MCID) { 192 for (const uint16_t *Regs = MCID.getImplicitDefs(); *Regs; ++Regs) 193 if (*Regs == ARM::CPSR) 194 return true; 195 return false; 196 } 197 198 /// canAddPseudoFlagDep - For A9 (and other out-of-order) implementations, 199 /// the 's' 16-bit instruction partially update CPSR. Abort the 200 /// transformation to avoid adding false dependency on last CPSR setting 201 /// instruction which hurts the ability for out-of-order execution engine 202 /// to do register renaming magic. 203 /// This function checks if there is a read-of-write dependency between the 204 /// last instruction that defines the CPSR and the current instruction. If there 205 /// is, then there is no harm done since the instruction cannot be retired 206 /// before the CPSR setting instruction anyway. 207 /// Note, we are not doing full dependency analysis here for the sake of compile 208 /// time. We're not looking for cases like: 209 /// r0 = muls ... 210 /// r1 = add.w r0, ... 211 /// ... 212 /// = mul.w r1 213 /// In this case it would have been ok to narrow the mul.w to muls since there 214 /// are indirect RAW dependency between the muls and the mul.w 215 bool 216 Thumb2SizeReduce::canAddPseudoFlagDep(MachineInstr *Def, MachineInstr *Use, 217 bool FirstInSelfLoop) { 218 // FIXME: Disable check for -Oz (aka OptimizeForSizeHarder). 219 if (!STI->avoidCPSRPartialUpdate()) 220 return false; 221 222 if (!Def) 223 // If this BB loops back to itself, conservatively avoid narrowing the 224 // first instruction that does partial flag update. 225 return FirstInSelfLoop; 226 227 SmallSet<unsigned, 2> Defs; 228 for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) { 229 const MachineOperand &MO = Def->getOperand(i); 230 if (!MO.isReg() || MO.isUndef() || MO.isUse()) 231 continue; 232 unsigned Reg = MO.getReg(); 233 if (Reg == 0 || Reg == ARM::CPSR) 234 continue; 235 Defs.insert(Reg); 236 } 237 238 for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { 239 const MachineOperand &MO = Use->getOperand(i); 240 if (!MO.isReg() || MO.isUndef() || MO.isDef()) 241 continue; 242 unsigned Reg = MO.getReg(); 243 if (Defs.count(Reg)) 244 return false; 245 } 246 247 // No read-after-write dependency. The narrowing will add false dependency. 248 return true; 249 } 250 251 bool 252 Thumb2SizeReduce::VerifyPredAndCC(MachineInstr *MI, const ReduceEntry &Entry, 253 bool is2Addr, ARMCC::CondCodes Pred, 254 bool LiveCPSR, bool &HasCC, bool &CCDead) { 255 if ((is2Addr && Entry.PredCC2 == 0) || 256 (!is2Addr && Entry.PredCC1 == 0)) { 257 if (Pred == ARMCC::AL) { 258 // Not predicated, must set CPSR. 259 if (!HasCC) { 260 // Original instruction was not setting CPSR, but CPSR is not 261 // currently live anyway. It's ok to set it. The CPSR def is 262 // dead though. 263 if (!LiveCPSR) { 264 HasCC = true; 265 CCDead = true; 266 return true; 267 } 268 return false; 269 } 270 } else { 271 // Predicated, must not set CPSR. 272 if (HasCC) 273 return false; 274 } 275 } else if ((is2Addr && Entry.PredCC2 == 2) || 276 (!is2Addr && Entry.PredCC1 == 2)) { 277 /// Old opcode has an optional def of CPSR. 278 if (HasCC) 279 return true; 280 // If old opcode does not implicitly define CPSR, then it's not ok since 281 // these new opcodes' CPSR def is not meant to be thrown away. e.g. CMP. 282 if (!HasImplicitCPSRDef(MI->getDesc())) 283 return false; 284 HasCC = true; 285 } else { 286 // 16-bit instruction does not set CPSR. 287 if (HasCC) 288 return false; 289 } 290 291 return true; 292 } 293 294 static bool VerifyLowRegs(MachineInstr *MI) { 295 unsigned Opc = MI->getOpcode(); 296 bool isPCOk = (Opc == ARM::t2LDMIA_RET || Opc == ARM::t2LDMIA || 297 Opc == ARM::t2LDMDB || Opc == ARM::t2LDMIA_UPD || 298 Opc == ARM::t2LDMDB_UPD); 299 bool isLROk = (Opc == ARM::t2STMIA_UPD || Opc == ARM::t2STMDB_UPD); 300 bool isSPOk = isPCOk || isLROk; 301 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 302 const MachineOperand &MO = MI->getOperand(i); 303 if (!MO.isReg() || MO.isImplicit()) 304 continue; 305 unsigned Reg = MO.getReg(); 306 if (Reg == 0 || Reg == ARM::CPSR) 307 continue; 308 if (isPCOk && Reg == ARM::PC) 309 continue; 310 if (isLROk && Reg == ARM::LR) 311 continue; 312 if (Reg == ARM::SP) { 313 if (isSPOk) 314 continue; 315 if (i == 1 && (Opc == ARM::t2LDRi12 || Opc == ARM::t2STRi12)) 316 // Special case for these ldr / str with sp as base register. 317 continue; 318 } 319 if (!isARMLowRegister(Reg)) 320 return false; 321 } 322 return true; 323 } 324 325 bool 326 Thumb2SizeReduce::ReduceLoadStore(MachineBasicBlock &MBB, MachineInstr *MI, 327 const ReduceEntry &Entry) { 328 if (ReduceLimitLdSt != -1 && ((int)NumLdSts >= ReduceLimitLdSt)) 329 return false; 330 331 unsigned Scale = 1; 332 bool HasImmOffset = false; 333 bool HasShift = false; 334 bool HasOffReg = true; 335 bool isLdStMul = false; 336 unsigned Opc = Entry.NarrowOpc1; 337 unsigned OpNum = 3; // First 'rest' of operands. 338 uint8_t ImmLimit = Entry.Imm1Limit; 339 340 switch (Entry.WideOpc) { 341 default: 342 llvm_unreachable("Unexpected Thumb2 load / store opcode!"); 343 case ARM::t2LDRi12: 344 case ARM::t2STRi12: 345 if (MI->getOperand(1).getReg() == ARM::SP) { 346 Opc = Entry.NarrowOpc2; 347 ImmLimit = Entry.Imm2Limit; 348 HasOffReg = false; 349 } 350 351 Scale = 4; 352 HasImmOffset = true; 353 HasOffReg = false; 354 break; 355 case ARM::t2LDRBi12: 356 case ARM::t2STRBi12: 357 HasImmOffset = true; 358 HasOffReg = false; 359 break; 360 case ARM::t2LDRHi12: 361 case ARM::t2STRHi12: 362 Scale = 2; 363 HasImmOffset = true; 364 HasOffReg = false; 365 break; 366 case ARM::t2LDRs: 367 case ARM::t2LDRBs: 368 case ARM::t2LDRHs: 369 case ARM::t2LDRSBs: 370 case ARM::t2LDRSHs: 371 case ARM::t2STRs: 372 case ARM::t2STRBs: 373 case ARM::t2STRHs: 374 HasShift = true; 375 OpNum = 4; 376 break; 377 case ARM::t2LDMIA: 378 case ARM::t2LDMDB: { 379 unsigned BaseReg = MI->getOperand(0).getReg(); 380 if (!isARMLowRegister(BaseReg) || Entry.WideOpc != ARM::t2LDMIA) 381 return false; 382 383 // For the non-writeback version (this one), the base register must be 384 // one of the registers being loaded. 385 bool isOK = false; 386 for (unsigned i = 4; i < MI->getNumOperands(); ++i) { 387 if (MI->getOperand(i).getReg() == BaseReg) { 388 isOK = true; 389 break; 390 } 391 } 392 393 if (!isOK) 394 return false; 395 396 OpNum = 0; 397 isLdStMul = true; 398 break; 399 } 400 case ARM::t2LDMIA_RET: { 401 unsigned BaseReg = MI->getOperand(1).getReg(); 402 if (BaseReg != ARM::SP) 403 return false; 404 Opc = Entry.NarrowOpc2; // tPOP_RET 405 OpNum = 2; 406 isLdStMul = true; 407 break; 408 } 409 case ARM::t2LDMIA_UPD: 410 case ARM::t2LDMDB_UPD: 411 case ARM::t2STMIA_UPD: 412 case ARM::t2STMDB_UPD: { 413 OpNum = 0; 414 415 unsigned BaseReg = MI->getOperand(1).getReg(); 416 if (BaseReg == ARM::SP && 417 (Entry.WideOpc == ARM::t2LDMIA_UPD || 418 Entry.WideOpc == ARM::t2STMDB_UPD)) { 419 Opc = Entry.NarrowOpc2; // tPOP or tPUSH 420 OpNum = 2; 421 } else if (!isARMLowRegister(BaseReg) || 422 (Entry.WideOpc != ARM::t2LDMIA_UPD && 423 Entry.WideOpc != ARM::t2STMIA_UPD)) { 424 return false; 425 } 426 427 isLdStMul = true; 428 break; 429 } 430 } 431 432 unsigned OffsetReg = 0; 433 bool OffsetKill = false; 434 if (HasShift) { 435 OffsetReg = MI->getOperand(2).getReg(); 436 OffsetKill = MI->getOperand(2).isKill(); 437 438 if (MI->getOperand(3).getImm()) 439 // Thumb1 addressing mode doesn't support shift. 440 return false; 441 } 442 443 unsigned OffsetImm = 0; 444 if (HasImmOffset) { 445 OffsetImm = MI->getOperand(2).getImm(); 446 unsigned MaxOffset = ((1 << ImmLimit) - 1) * Scale; 447 448 if ((OffsetImm & (Scale - 1)) || OffsetImm > MaxOffset) 449 // Make sure the immediate field fits. 450 return false; 451 } 452 453 // Add the 16-bit load / store instruction. 454 DebugLoc dl = MI->getDebugLoc(); 455 MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, TII->get(Opc)); 456 if (!isLdStMul) { 457 MIB.addOperand(MI->getOperand(0)); 458 MIB.addOperand(MI->getOperand(1)); 459 460 if (HasImmOffset) 461 MIB.addImm(OffsetImm / Scale); 462 463 assert((!HasShift || OffsetReg) && "Invalid so_reg load / store address!"); 464 465 if (HasOffReg) 466 MIB.addReg(OffsetReg, getKillRegState(OffsetKill)); 467 } 468 469 // Transfer the rest of operands. 470 for (unsigned e = MI->getNumOperands(); OpNum != e; ++OpNum) 471 MIB.addOperand(MI->getOperand(OpNum)); 472 473 // Transfer memoperands. 474 MIB->setMemRefs(MI->memoperands_begin(), MI->memoperands_end()); 475 476 // Transfer MI flags. 477 MIB.setMIFlags(MI->getFlags()); 478 479 DEBUG(errs() << "Converted 32-bit: " << *MI << " to 16-bit: " << *MIB); 480 481 MBB.erase_instr(MI); 482 ++NumLdSts; 483 return true; 484 } 485 486 bool 487 Thumb2SizeReduce::ReduceSpecial(MachineBasicBlock &MBB, MachineInstr *MI, 488 const ReduceEntry &Entry, 489 bool LiveCPSR, MachineInstr *CPSRDef, 490 bool IsSelfLoop) { 491 unsigned Opc = MI->getOpcode(); 492 if (Opc == ARM::t2ADDri) { 493 // If the source register is SP, try to reduce to tADDrSPi, otherwise 494 // it's a normal reduce. 495 if (MI->getOperand(1).getReg() != ARM::SP) { 496 if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop)) 497 return true; 498 return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop); 499 } 500 // Try to reduce to tADDrSPi. 501 unsigned Imm = MI->getOperand(2).getImm(); 502 // The immediate must be in range, the destination register must be a low 503 // reg, the predicate must be "always" and the condition flags must not 504 // be being set. 505 if (Imm & 3 || Imm > 1020) 506 return false; 507 if (!isARMLowRegister(MI->getOperand(0).getReg())) 508 return false; 509 if (MI->getOperand(3).getImm() != ARMCC::AL) 510 return false; 511 const MCInstrDesc &MCID = MI->getDesc(); 512 if (MCID.hasOptionalDef() && 513 MI->getOperand(MCID.getNumOperands()-1).getReg() == ARM::CPSR) 514 return false; 515 516 MachineInstrBuilder MIB = BuildMI(MBB, MI, MI->getDebugLoc(), 517 TII->get(ARM::tADDrSPi)) 518 .addOperand(MI->getOperand(0)) 519 .addOperand(MI->getOperand(1)) 520 .addImm(Imm / 4); // The tADDrSPi has an implied scale by four. 521 AddDefaultPred(MIB); 522 523 // Transfer MI flags. 524 MIB.setMIFlags(MI->getFlags()); 525 526 DEBUG(errs() << "Converted 32-bit: " << *MI << " to 16-bit: " <<*MIB); 527 528 MBB.erase_instr(MI); 529 ++NumNarrows; 530 return true; 531 } 532 533 if (Entry.LowRegs1 && !VerifyLowRegs(MI)) 534 return false; 535 536 if (MI->mayLoad() || MI->mayStore()) 537 return ReduceLoadStore(MBB, MI, Entry); 538 539 switch (Opc) { 540 default: break; 541 case ARM::t2ADDSri: 542 case ARM::t2ADDSrr: { 543 unsigned PredReg = 0; 544 if (getInstrPredicate(MI, PredReg) == ARMCC::AL) { 545 switch (Opc) { 546 default: break; 547 case ARM::t2ADDSri: { 548 if (ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop)) 549 return true; 550 // fallthrough 551 } 552 case ARM::t2ADDSrr: 553 return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop); 554 } 555 } 556 break; 557 } 558 case ARM::t2RSBri: 559 case ARM::t2RSBSri: 560 case ARM::t2SXTB: 561 case ARM::t2SXTH: 562 case ARM::t2UXTB: 563 case ARM::t2UXTH: 564 if (MI->getOperand(2).getImm() == 0) 565 return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop); 566 break; 567 case ARM::t2MOVi16: 568 // Can convert only 'pure' immediate operands, not immediates obtained as 569 // globals' addresses. 570 if (MI->getOperand(1).isImm()) 571 return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop); 572 break; 573 case ARM::t2CMPrr: { 574 // Try to reduce to the lo-reg only version first. Why there are two 575 // versions of the instruction is a mystery. 576 // It would be nice to just have two entries in the master table that 577 // are prioritized, but the table assumes a unique entry for each 578 // source insn opcode. So for now, we hack a local entry record to use. 579 static const ReduceEntry NarrowEntry = 580 { ARM::t2CMPrr,ARM::tCMPr, 0, 0, 0, 1, 1,2, 0, 0,1 }; 581 if (ReduceToNarrow(MBB, MI, NarrowEntry, LiveCPSR, CPSRDef, IsSelfLoop)) 582 return true; 583 return ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop); 584 } 585 } 586 return false; 587 } 588 589 bool 590 Thumb2SizeReduce::ReduceTo2Addr(MachineBasicBlock &MBB, MachineInstr *MI, 591 const ReduceEntry &Entry, 592 bool LiveCPSR, MachineInstr *CPSRDef, 593 bool IsSelfLoop) { 594 595 if (ReduceLimit2Addr != -1 && ((int)Num2Addrs >= ReduceLimit2Addr)) 596 return false; 597 598 unsigned Reg0 = MI->getOperand(0).getReg(); 599 unsigned Reg1 = MI->getOperand(1).getReg(); 600 // t2MUL is "special". The tied source operand is second, not first. 601 if (MI->getOpcode() == ARM::t2MUL) { 602 unsigned Reg2 = MI->getOperand(2).getReg(); 603 // Early exit if the regs aren't all low regs. 604 if (!isARMLowRegister(Reg0) || !isARMLowRegister(Reg1) 605 || !isARMLowRegister(Reg2)) 606 return false; 607 if (Reg0 != Reg2) { 608 // If the other operand also isn't the same as the destination, we 609 // can't reduce. 610 if (Reg1 != Reg0) 611 return false; 612 // Try to commute the operands to make it a 2-address instruction. 613 MachineInstr *CommutedMI = TII->commuteInstruction(MI); 614 if (!CommutedMI) 615 return false; 616 } 617 } else if (Reg0 != Reg1) { 618 // Try to commute the operands to make it a 2-address instruction. 619 unsigned CommOpIdx1, CommOpIdx2; 620 if (!TII->findCommutedOpIndices(MI, CommOpIdx1, CommOpIdx2) || 621 CommOpIdx1 != 1 || MI->getOperand(CommOpIdx2).getReg() != Reg0) 622 return false; 623 MachineInstr *CommutedMI = TII->commuteInstruction(MI); 624 if (!CommutedMI) 625 return false; 626 } 627 if (Entry.LowRegs2 && !isARMLowRegister(Reg0)) 628 return false; 629 if (Entry.Imm2Limit) { 630 unsigned Imm = MI->getOperand(2).getImm(); 631 unsigned Limit = (1 << Entry.Imm2Limit) - 1; 632 if (Imm > Limit) 633 return false; 634 } else { 635 unsigned Reg2 = MI->getOperand(2).getReg(); 636 if (Entry.LowRegs2 && !isARMLowRegister(Reg2)) 637 return false; 638 } 639 640 // Check if it's possible / necessary to transfer the predicate. 641 const MCInstrDesc &NewMCID = TII->get(Entry.NarrowOpc2); 642 unsigned PredReg = 0; 643 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg); 644 bool SkipPred = false; 645 if (Pred != ARMCC::AL) { 646 if (!NewMCID.isPredicable()) 647 // Can't transfer predicate, fail. 648 return false; 649 } else { 650 SkipPred = !NewMCID.isPredicable(); 651 } 652 653 bool HasCC = false; 654 bool CCDead = false; 655 const MCInstrDesc &MCID = MI->getDesc(); 656 if (MCID.hasOptionalDef()) { 657 unsigned NumOps = MCID.getNumOperands(); 658 HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR); 659 if (HasCC && MI->getOperand(NumOps-1).isDead()) 660 CCDead = true; 661 } 662 if (!VerifyPredAndCC(MI, Entry, true, Pred, LiveCPSR, HasCC, CCDead)) 663 return false; 664 665 // Avoid adding a false dependency on partial flag update by some 16-bit 666 // instructions which has the 's' bit set. 667 if (Entry.PartFlag && NewMCID.hasOptionalDef() && HasCC && 668 canAddPseudoFlagDep(CPSRDef, MI, IsSelfLoop)) 669 return false; 670 671 // Add the 16-bit instruction. 672 DebugLoc dl = MI->getDebugLoc(); 673 MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID); 674 MIB.addOperand(MI->getOperand(0)); 675 if (NewMCID.hasOptionalDef()) { 676 if (HasCC) 677 AddDefaultT1CC(MIB, CCDead); 678 else 679 AddNoT1CC(MIB); 680 } 681 682 // Transfer the rest of operands. 683 unsigned NumOps = MCID.getNumOperands(); 684 for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) { 685 if (i < NumOps && MCID.OpInfo[i].isOptionalDef()) 686 continue; 687 if (SkipPred && MCID.OpInfo[i].isPredicate()) 688 continue; 689 MIB.addOperand(MI->getOperand(i)); 690 } 691 692 // Transfer MI flags. 693 MIB.setMIFlags(MI->getFlags()); 694 695 DEBUG(errs() << "Converted 32-bit: " << *MI << " to 16-bit: " << *MIB); 696 697 MBB.erase_instr(MI); 698 ++Num2Addrs; 699 return true; 700 } 701 702 bool 703 Thumb2SizeReduce::ReduceToNarrow(MachineBasicBlock &MBB, MachineInstr *MI, 704 const ReduceEntry &Entry, 705 bool LiveCPSR, MachineInstr *CPSRDef, 706 bool IsSelfLoop) { 707 if (ReduceLimit != -1 && ((int)NumNarrows >= ReduceLimit)) 708 return false; 709 710 unsigned Limit = ~0U; 711 if (Entry.Imm1Limit) 712 Limit = (1 << Entry.Imm1Limit) - 1; 713 714 const MCInstrDesc &MCID = MI->getDesc(); 715 for (unsigned i = 0, e = MCID.getNumOperands(); i != e; ++i) { 716 if (MCID.OpInfo[i].isPredicate()) 717 continue; 718 const MachineOperand &MO = MI->getOperand(i); 719 if (MO.isReg()) { 720 unsigned Reg = MO.getReg(); 721 if (!Reg || Reg == ARM::CPSR) 722 continue; 723 if (Entry.LowRegs1 && !isARMLowRegister(Reg)) 724 return false; 725 } else if (MO.isImm() && 726 !MCID.OpInfo[i].isPredicate()) { 727 if (((unsigned)MO.getImm()) > Limit) 728 return false; 729 } 730 } 731 732 // Check if it's possible / necessary to transfer the predicate. 733 const MCInstrDesc &NewMCID = TII->get(Entry.NarrowOpc1); 734 unsigned PredReg = 0; 735 ARMCC::CondCodes Pred = getInstrPredicate(MI, PredReg); 736 bool SkipPred = false; 737 if (Pred != ARMCC::AL) { 738 if (!NewMCID.isPredicable()) 739 // Can't transfer predicate, fail. 740 return false; 741 } else { 742 SkipPred = !NewMCID.isPredicable(); 743 } 744 745 bool HasCC = false; 746 bool CCDead = false; 747 if (MCID.hasOptionalDef()) { 748 unsigned NumOps = MCID.getNumOperands(); 749 HasCC = (MI->getOperand(NumOps-1).getReg() == ARM::CPSR); 750 if (HasCC && MI->getOperand(NumOps-1).isDead()) 751 CCDead = true; 752 } 753 if (!VerifyPredAndCC(MI, Entry, false, Pred, LiveCPSR, HasCC, CCDead)) 754 return false; 755 756 // Avoid adding a false dependency on partial flag update by some 16-bit 757 // instructions which has the 's' bit set. 758 if (Entry.PartFlag && NewMCID.hasOptionalDef() && HasCC && 759 canAddPseudoFlagDep(CPSRDef, MI, IsSelfLoop)) 760 return false; 761 762 // Add the 16-bit instruction. 763 DebugLoc dl = MI->getDebugLoc(); 764 MachineInstrBuilder MIB = BuildMI(MBB, MI, dl, NewMCID); 765 MIB.addOperand(MI->getOperand(0)); 766 if (NewMCID.hasOptionalDef()) { 767 if (HasCC) 768 AddDefaultT1CC(MIB, CCDead); 769 else 770 AddNoT1CC(MIB); 771 } 772 773 // Transfer the rest of operands. 774 unsigned NumOps = MCID.getNumOperands(); 775 for (unsigned i = 1, e = MI->getNumOperands(); i != e; ++i) { 776 if (i < NumOps && MCID.OpInfo[i].isOptionalDef()) 777 continue; 778 if ((MCID.getOpcode() == ARM::t2RSBSri || 779 MCID.getOpcode() == ARM::t2RSBri || 780 MCID.getOpcode() == ARM::t2SXTB || 781 MCID.getOpcode() == ARM::t2SXTH || 782 MCID.getOpcode() == ARM::t2UXTB || 783 MCID.getOpcode() == ARM::t2UXTH) && i == 2) 784 // Skip the zero immediate operand, it's now implicit. 785 continue; 786 bool isPred = (i < NumOps && MCID.OpInfo[i].isPredicate()); 787 if (SkipPred && isPred) 788 continue; 789 const MachineOperand &MO = MI->getOperand(i); 790 if (MO.isReg() && MO.isImplicit() && MO.getReg() == ARM::CPSR) 791 // Skip implicit def of CPSR. Either it's modeled as an optional 792 // def now or it's already an implicit def on the new instruction. 793 continue; 794 MIB.addOperand(MO); 795 } 796 if (!MCID.isPredicable() && NewMCID.isPredicable()) 797 AddDefaultPred(MIB); 798 799 // Transfer MI flags. 800 MIB.setMIFlags(MI->getFlags()); 801 802 DEBUG(errs() << "Converted 32-bit: " << *MI << " to 16-bit: " << *MIB); 803 804 MBB.erase_instr(MI); 805 ++NumNarrows; 806 return true; 807 } 808 809 static bool UpdateCPSRDef(MachineInstr &MI, bool LiveCPSR, bool &DefCPSR) { 810 bool HasDef = false; 811 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 812 const MachineOperand &MO = MI.getOperand(i); 813 if (!MO.isReg() || MO.isUndef() || MO.isUse()) 814 continue; 815 if (MO.getReg() != ARM::CPSR) 816 continue; 817 818 DefCPSR = true; 819 if (!MO.isDead()) 820 HasDef = true; 821 } 822 823 return HasDef || LiveCPSR; 824 } 825 826 static bool UpdateCPSRUse(MachineInstr &MI, bool LiveCPSR) { 827 for (unsigned i = 0, e = MI.getNumOperands(); i != e; ++i) { 828 const MachineOperand &MO = MI.getOperand(i); 829 if (!MO.isReg() || MO.isUndef() || MO.isDef()) 830 continue; 831 if (MO.getReg() != ARM::CPSR) 832 continue; 833 assert(LiveCPSR && "CPSR liveness tracking is wrong!"); 834 if (MO.isKill()) { 835 LiveCPSR = false; 836 break; 837 } 838 } 839 840 return LiveCPSR; 841 } 842 843 bool Thumb2SizeReduce::ReduceMBB(MachineBasicBlock &MBB) { 844 bool Modified = false; 845 846 // Yes, CPSR could be livein. 847 bool LiveCPSR = MBB.isLiveIn(ARM::CPSR); 848 MachineInstr *CPSRDef = 0; 849 MachineInstr *BundleMI = 0; 850 851 // If this BB loops back to itself, conservatively avoid narrowing the 852 // first instruction that does partial flag update. 853 bool IsSelfLoop = MBB.isSuccessor(&MBB); 854 MachineBasicBlock::instr_iterator MII = MBB.instr_begin(),E = MBB.instr_end(); 855 MachineBasicBlock::instr_iterator NextMII; 856 for (; MII != E; MII = NextMII) { 857 NextMII = llvm::next(MII); 858 859 MachineInstr *MI = &*MII; 860 if (MI->isBundle()) { 861 BundleMI = MI; 862 continue; 863 } 864 865 LiveCPSR = UpdateCPSRUse(*MI, LiveCPSR); 866 867 unsigned Opcode = MI->getOpcode(); 868 DenseMap<unsigned, unsigned>::iterator OPI = ReduceOpcodeMap.find(Opcode); 869 if (OPI != ReduceOpcodeMap.end()) { 870 const ReduceEntry &Entry = ReduceTable[OPI->second]; 871 // Ignore "special" cases for now. 872 if (Entry.Special) { 873 if (ReduceSpecial(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop)) { 874 Modified = true; 875 MachineBasicBlock::instr_iterator I = prior(NextMII); 876 MI = &*I; 877 } 878 goto ProcessNext; 879 } 880 881 // Try to transform to a 16-bit two-address instruction. 882 if (Entry.NarrowOpc2 && 883 ReduceTo2Addr(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop)) { 884 Modified = true; 885 MachineBasicBlock::instr_iterator I = prior(NextMII); 886 MI = &*I; 887 goto ProcessNext; 888 } 889 890 // Try to transform to a 16-bit non-two-address instruction. 891 if (Entry.NarrowOpc1 && 892 ReduceToNarrow(MBB, MI, Entry, LiveCPSR, CPSRDef, IsSelfLoop)) { 893 Modified = true; 894 MachineBasicBlock::instr_iterator I = prior(NextMII); 895 MI = &*I; 896 } 897 } 898 899 ProcessNext: 900 if (NextMII != E && MI->isInsideBundle() && !NextMII->isInsideBundle()) { 901 // FIXME: Since post-ra scheduler operates on bundles, the CPSR kill 902 // marker is only on the BUNDLE instruction. Process the BUNDLE 903 // instruction as we finish with the bundled instruction to work around 904 // the inconsistency. 905 if (BundleMI->killsRegister(ARM::CPSR)) 906 LiveCPSR = false; 907 MachineOperand *MO = BundleMI->findRegisterDefOperand(ARM::CPSR); 908 if (MO && !MO->isDead()) 909 LiveCPSR = true; 910 } 911 912 bool DefCPSR = false; 913 LiveCPSR = UpdateCPSRDef(*MI, LiveCPSR, DefCPSR); 914 if (MI->isCall()) { 915 // Calls don't really set CPSR. 916 CPSRDef = 0; 917 IsSelfLoop = false; 918 } else if (DefCPSR) { 919 // This is the last CPSR defining instruction. 920 CPSRDef = MI; 921 IsSelfLoop = false; 922 } 923 } 924 925 return Modified; 926 } 927 928 bool Thumb2SizeReduce::runOnMachineFunction(MachineFunction &MF) { 929 const TargetMachine &TM = MF.getTarget(); 930 TII = static_cast<const Thumb2InstrInfo*>(TM.getInstrInfo()); 931 STI = &TM.getSubtarget<ARMSubtarget>(); 932 933 bool Modified = false; 934 for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) 935 Modified |= ReduceMBB(*I); 936 return Modified; 937 } 938 939 /// createThumb2SizeReductionPass - Returns an instance of the Thumb2 size 940 /// reduction pass. 941 FunctionPass *llvm::createThumb2SizeReductionPass() { 942 return new Thumb2SizeReduce(); 943 } 944
