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