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