1 //===-- X86FixupLEAs.cpp - use or replace LEA instructions -----------===// 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 // This file defines the pass which will find instructions which 11 // can be re-written as LEA instructions in order to reduce pipeline 12 // delays for some models of the Intel Atom family. 13 // 14 //===----------------------------------------------------------------------===// 15 16 #include "X86.h" 17 #include "X86InstrInfo.h" 18 #include "X86Subtarget.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/CodeGen/LiveVariables.h" 21 #include "llvm/CodeGen/MachineFunctionPass.h" 22 #include "llvm/CodeGen/MachineInstrBuilder.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/CodeGen/Passes.h" 25 #include "llvm/Support/Debug.h" 26 #include "llvm/Support/raw_ostream.h" 27 #include "llvm/Target/TargetInstrInfo.h" 28 using namespace llvm; 29 30 #define DEBUG_TYPE "x86-fixup-LEAs" 31 32 STATISTIC(NumLEAs, "Number of LEA instructions created"); 33 34 namespace { 35 class FixupLEAPass : public MachineFunctionPass { 36 enum RegUsageState { RU_NotUsed, RU_Write, RU_Read }; 37 static char ID; 38 /// \brief Loop over all of the instructions in the basic block 39 /// replacing applicable instructions with LEA instructions, 40 /// where appropriate. 41 bool processBasicBlock(MachineFunction &MF, MachineFunction::iterator MFI); 42 43 const char *getPassName() const override { return "X86 Atom LEA Fixup"; } 44 45 /// \brief Given a machine register, look for the instruction 46 /// which writes it in the current basic block. If found, 47 /// try to replace it with an equivalent LEA instruction. 48 /// If replacement succeeds, then also process the the newly created 49 /// instruction. 50 void seekLEAFixup(MachineOperand &p, MachineBasicBlock::iterator &I, 51 MachineFunction::iterator MFI); 52 53 /// \brief Given a memory access or LEA instruction 54 /// whose address mode uses a base and/or index register, look for 55 /// an opportunity to replace the instruction which sets the base or index 56 /// register with an equivalent LEA instruction. 57 void processInstruction(MachineBasicBlock::iterator &I, 58 MachineFunction::iterator MFI); 59 60 /// \brief Given a LEA instruction which is unprofitable 61 /// on Silvermont try to replace it with an equivalent ADD instruction 62 void processInstructionForSLM(MachineBasicBlock::iterator &I, 63 MachineFunction::iterator MFI); 64 65 /// \brief Determine if an instruction references a machine register 66 /// and, if so, whether it reads or writes the register. 67 RegUsageState usesRegister(MachineOperand &p, MachineBasicBlock::iterator I); 68 69 /// \brief Step backwards through a basic block, looking 70 /// for an instruction which writes a register within 71 /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles. 72 MachineBasicBlock::iterator searchBackwards(MachineOperand &p, 73 MachineBasicBlock::iterator &I, 74 MachineFunction::iterator MFI); 75 76 /// \brief if an instruction can be converted to an 77 /// equivalent LEA, insert the new instruction into the basic block 78 /// and return a pointer to it. Otherwise, return zero. 79 MachineInstr *postRAConvertToLEA(MachineFunction::iterator &MFI, 80 MachineBasicBlock::iterator &MBBI) const; 81 82 public: 83 FixupLEAPass() : MachineFunctionPass(ID) {} 84 85 /// \brief Loop over all of the basic blocks, 86 /// replacing instructions by equivalent LEA instructions 87 /// if needed and when possible. 88 bool runOnMachineFunction(MachineFunction &MF) override; 89 90 private: 91 MachineFunction *MF; 92 const TargetMachine *TM; 93 const X86InstrInfo *TII; // Machine instruction info. 94 }; 95 char FixupLEAPass::ID = 0; 96 } 97 98 MachineInstr * 99 FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI, 100 MachineBasicBlock::iterator &MBBI) const { 101 MachineInstr *MI = MBBI; 102 MachineInstr *NewMI; 103 switch (MI->getOpcode()) { 104 case X86::MOV32rr: 105 case X86::MOV64rr: { 106 const MachineOperand &Src = MI->getOperand(1); 107 const MachineOperand &Dest = MI->getOperand(0); 108 NewMI = BuildMI(*MF, MI->getDebugLoc(), 109 TII->get(MI->getOpcode() == X86::MOV32rr ? X86::LEA32r 110 : X86::LEA64r)) 111 .addOperand(Dest) 112 .addOperand(Src) 113 .addImm(1) 114 .addReg(0) 115 .addImm(0) 116 .addReg(0); 117 MFI->insert(MBBI, NewMI); // Insert the new inst 118 return NewMI; 119 } 120 case X86::ADD64ri32: 121 case X86::ADD64ri8: 122 case X86::ADD64ri32_DB: 123 case X86::ADD64ri8_DB: 124 case X86::ADD32ri: 125 case X86::ADD32ri8: 126 case X86::ADD32ri_DB: 127 case X86::ADD32ri8_DB: 128 case X86::ADD16ri: 129 case X86::ADD16ri8: 130 case X86::ADD16ri_DB: 131 case X86::ADD16ri8_DB: 132 if (!MI->getOperand(2).isImm()) { 133 // convertToThreeAddress will call getImm() 134 // which requires isImm() to be true 135 return nullptr; 136 } 137 break; 138 case X86::ADD16rr: 139 case X86::ADD16rr_DB: 140 if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) { 141 // if src1 != src2, then convertToThreeAddress will 142 // need to create a Virtual register, which we cannot do 143 // after register allocation. 144 return nullptr; 145 } 146 } 147 return TII->convertToThreeAddress(MFI, MBBI, nullptr); 148 } 149 150 FunctionPass *llvm::createX86FixupLEAs() { return new FixupLEAPass(); } 151 152 bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { 153 MF = &Func; 154 TM = &Func.getTarget(); 155 const X86Subtarget &ST = TM->getSubtarget<X86Subtarget>(); 156 if (!ST.LEAusesAG() && !ST.slowLEA()) 157 return false; 158 159 TII = static_cast<const X86InstrInfo *>(TM->getInstrInfo()); 160 161 DEBUG(dbgs() << "Start X86FixupLEAs\n";); 162 // Process all basic blocks. 163 for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) 164 processBasicBlock(Func, I); 165 DEBUG(dbgs() << "End X86FixupLEAs\n";); 166 167 return true; 168 } 169 170 FixupLEAPass::RegUsageState 171 FixupLEAPass::usesRegister(MachineOperand &p, MachineBasicBlock::iterator I) { 172 RegUsageState RegUsage = RU_NotUsed; 173 MachineInstr *MI = I; 174 175 for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { 176 MachineOperand &opnd = MI->getOperand(i); 177 if (opnd.isReg() && opnd.getReg() == p.getReg()) { 178 if (opnd.isDef()) 179 return RU_Write; 180 RegUsage = RU_Read; 181 } 182 } 183 return RegUsage; 184 } 185 186 /// getPreviousInstr - Given a reference to an instruction in a basic 187 /// block, return a reference to the previous instruction in the block, 188 /// wrapping around to the last instruction of the block if the block 189 /// branches to itself. 190 static inline bool getPreviousInstr(MachineBasicBlock::iterator &I, 191 MachineFunction::iterator MFI) { 192 if (I == MFI->begin()) { 193 if (MFI->isPredecessor(MFI)) { 194 I = --MFI->end(); 195 return true; 196 } else 197 return false; 198 } 199 --I; 200 return true; 201 } 202 203 MachineBasicBlock::iterator 204 FixupLEAPass::searchBackwards(MachineOperand &p, MachineBasicBlock::iterator &I, 205 MachineFunction::iterator MFI) { 206 int InstrDistance = 1; 207 MachineBasicBlock::iterator CurInst; 208 static const int INSTR_DISTANCE_THRESHOLD = 5; 209 210 CurInst = I; 211 bool Found; 212 Found = getPreviousInstr(CurInst, MFI); 213 while (Found && I != CurInst) { 214 if (CurInst->isCall() || CurInst->isInlineAsm()) 215 break; 216 if (InstrDistance > INSTR_DISTANCE_THRESHOLD) 217 break; // too far back to make a difference 218 if (usesRegister(p, CurInst) == RU_Write) { 219 return CurInst; 220 } 221 InstrDistance += TII->getInstrLatency(TM->getInstrItineraryData(), CurInst); 222 Found = getPreviousInstr(CurInst, MFI); 223 } 224 return nullptr; 225 } 226 227 void FixupLEAPass::processInstruction(MachineBasicBlock::iterator &I, 228 MachineFunction::iterator MFI) { 229 // Process a load, store, or LEA instruction. 230 MachineInstr *MI = I; 231 int opcode = MI->getOpcode(); 232 const MCInstrDesc &Desc = MI->getDesc(); 233 int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); 234 if (AddrOffset >= 0) { 235 AddrOffset += X86II::getOperandBias(Desc); 236 MachineOperand &p = MI->getOperand(AddrOffset + X86::AddrBaseReg); 237 if (p.isReg() && p.getReg() != X86::ESP) { 238 seekLEAFixup(p, I, MFI); 239 } 240 MachineOperand &q = MI->getOperand(AddrOffset + X86::AddrIndexReg); 241 if (q.isReg() && q.getReg() != X86::ESP) { 242 seekLEAFixup(q, I, MFI); 243 } 244 } 245 } 246 247 void FixupLEAPass::seekLEAFixup(MachineOperand &p, 248 MachineBasicBlock::iterator &I, 249 MachineFunction::iterator MFI) { 250 MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); 251 if (MBI) { 252 MachineInstr *NewMI = postRAConvertToLEA(MFI, MBI); 253 if (NewMI) { 254 ++NumLEAs; 255 DEBUG(dbgs() << "FixLEA: Candidate to replace:"; MBI->dump();); 256 // now to replace with an equivalent LEA... 257 DEBUG(dbgs() << "FixLEA: Replaced by: "; NewMI->dump();); 258 MFI->erase(MBI); 259 MachineBasicBlock::iterator J = 260 static_cast<MachineBasicBlock::iterator>(NewMI); 261 processInstruction(J, MFI); 262 } 263 } 264 } 265 266 void FixupLEAPass::processInstructionForSLM(MachineBasicBlock::iterator &I, 267 MachineFunction::iterator MFI) { 268 MachineInstr *MI = I; 269 const int opcode = MI->getOpcode(); 270 if (opcode != X86::LEA16r && opcode != X86::LEA32r && opcode != X86::LEA64r && 271 opcode != X86::LEA64_32r) 272 return; 273 if (MI->getOperand(5).getReg() != 0 || !MI->getOperand(4).isImm() || 274 !TII->isSafeToClobberEFLAGS(*MFI, I)) 275 return; 276 const unsigned DstR = MI->getOperand(0).getReg(); 277 const unsigned SrcR1 = MI->getOperand(1).getReg(); 278 const unsigned SrcR2 = MI->getOperand(3).getReg(); 279 if ((SrcR1 == 0 || SrcR1 != DstR) && (SrcR2 == 0 || SrcR2 != DstR)) 280 return; 281 if (MI->getOperand(2).getImm() > 1) 282 return; 283 int addrr_opcode, addri_opcode; 284 switch (opcode) { 285 case X86::LEA16r: 286 addrr_opcode = X86::ADD16rr; 287 addri_opcode = X86::ADD16ri; 288 break; 289 case X86::LEA32r: 290 addrr_opcode = X86::ADD32rr; 291 addri_opcode = X86::ADD32ri; 292 break; 293 case X86::LEA64_32r: 294 case X86::LEA64r: 295 addrr_opcode = X86::ADD64rr; 296 addri_opcode = X86::ADD64ri32; 297 break; 298 default: 299 assert(false && "Unexpected LEA instruction"); 300 } 301 DEBUG(dbgs() << "FixLEA: Candidate to replace:"; I->dump();); 302 DEBUG(dbgs() << "FixLEA: Replaced by: ";); 303 MachineInstr *NewMI = nullptr; 304 const MachineOperand &Dst = MI->getOperand(0); 305 // Make ADD instruction for two registers writing to LEA's destination 306 if (SrcR1 != 0 && SrcR2 != 0) { 307 const MachineOperand &Src1 = MI->getOperand(SrcR1 == DstR ? 1 : 3); 308 const MachineOperand &Src2 = MI->getOperand(SrcR1 == DstR ? 3 : 1); 309 NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addrr_opcode)) 310 .addOperand(Dst) 311 .addOperand(Src1) 312 .addOperand(Src2); 313 MFI->insert(I, NewMI); 314 DEBUG(NewMI->dump();); 315 } 316 // Make ADD instruction for immediate 317 if (MI->getOperand(4).getImm() != 0) { 318 const MachineOperand &SrcR = MI->getOperand(SrcR1 == DstR ? 1 : 3); 319 NewMI = BuildMI(*MF, MI->getDebugLoc(), TII->get(addri_opcode)) 320 .addOperand(Dst) 321 .addOperand(SrcR) 322 .addImm(MI->getOperand(4).getImm()); 323 MFI->insert(I, NewMI); 324 DEBUG(NewMI->dump();); 325 } 326 if (NewMI) { 327 MFI->erase(I); 328 I = static_cast<MachineBasicBlock::iterator>(NewMI); 329 } 330 } 331 332 bool FixupLEAPass::processBasicBlock(MachineFunction &MF, 333 MachineFunction::iterator MFI) { 334 335 for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) { 336 if (TM->getSubtarget<X86Subtarget>().isSLM()) 337 processInstructionForSLM(I, MFI); 338 else 339 processInstruction(I, MFI); 340 } 341 return false; 342 } 343
