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