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