X86FixupLEAs.cpp revision a5e5ba611f787f518fd3f7349343f8c4ae863fc2
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#define DEBUG_TYPE "x86-fixup-LEAs" 17#include "X86.h" 18#include "X86InstrInfo.h" 19#include "X86Subtarget.h" 20#include "llvm/ADT/Statistic.h" 21#include "llvm/CodeGen/LiveVariables.h" 22#include "llvm/CodeGen/MachineFunctionPass.h" 23#include "llvm/CodeGen/MachineInstrBuilder.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/Support/Debug.h" 27#include "llvm/Support/raw_ostream.h" 28#include "llvm/Target/TargetInstrInfo.h" 29using namespace llvm; 30 31STATISTIC(NumLEAs, "Number of LEA instructions created"); 32 33namespace { 34 class 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 virtual const char *getPassName() const { return "X86 Atom 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 Determine if an instruction references a machine register 60 /// and, if so, whether it reads or writes the register. 61 RegUsageState usesRegister(MachineOperand& p, 62 MachineBasicBlock::iterator I); 63 64 /// \brief Step backwards through a basic block, looking 65 /// for an instruction which writes a register within 66 /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles. 67 MachineBasicBlock::iterator searchBackwards(MachineOperand& p, 68 MachineBasicBlock::iterator& I, 69 MachineFunction::iterator MFI); 70 71 /// \brief if an instruction can be converted to an 72 /// equivalent LEA, insert the new instruction into the basic block 73 /// and return a pointer to it. Otherwise, return zero. 74 MachineInstr* postRAConvertToLEA(MachineFunction::iterator &MFI, 75 MachineBasicBlock::iterator &MBBI) const; 76 77 public: 78 FixupLEAPass() : MachineFunctionPass(ID) {} 79 80 /// \brief Loop over all of the basic blocks, 81 /// replacing instructions by equivalent LEA instructions 82 /// if needed and when possible. 83 virtual bool runOnMachineFunction(MachineFunction &MF); 84 85 private: 86 MachineFunction *MF; 87 const TargetMachine *TM; 88 const TargetInstrInfo *TII; // Machine instruction info. 89 90 }; 91 char FixupLEAPass::ID = 0; 92} 93 94MachineInstr * 95FixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI, 96 MachineBasicBlock::iterator &MBBI) const { 97 MachineInstr* MI = MBBI; 98 MachineInstr* NewMI; 99 switch (MI->getOpcode()) { 100 case X86::MOV32rr: 101 case X86::MOV64rr: { 102 const MachineOperand& Src = MI->getOperand(1); 103 const MachineOperand& Dest = MI->getOperand(0); 104 NewMI = BuildMI(*MF, MI->getDebugLoc(), 105 TII->get( MI->getOpcode() == X86::MOV32rr ? X86::LEA32r : X86::LEA64r)) 106 .addOperand(Dest) 107 .addOperand(Src).addImm(1).addReg(0).addImm(0).addReg(0); 108 MFI->insert(MBBI, NewMI); // Insert the new inst 109 return NewMI; 110 } 111 case X86::ADD64ri32: 112 case X86::ADD64ri8: 113 case X86::ADD64ri32_DB: 114 case X86::ADD64ri8_DB: 115 case X86::ADD32ri: 116 case X86::ADD32ri8: 117 case X86::ADD32ri_DB: 118 case X86::ADD32ri8_DB: 119 case X86::ADD16ri: 120 case X86::ADD16ri8: 121 case X86::ADD16ri_DB: 122 case X86::ADD16ri8_DB: 123 if (!MI->getOperand(2).isImm()) { 124 // convertToThreeAddress will call getImm() 125 // which requires isImm() to be true 126 return 0; 127 } 128 } 129 return TII->convertToThreeAddress(MFI, MBBI, 0); 130} 131 132FunctionPass *llvm::createX86FixupLEAs() { 133 return new FixupLEAPass(); 134} 135 136bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { 137 MF = &Func; 138 TM = &MF->getTarget(); 139 TII = TM->getInstrInfo(); 140 141 DEBUG(dbgs() << "Start X86FixupLEAs\n";); 142 // Process all basic blocks. 143 for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) 144 processBasicBlock(Func, I); 145 DEBUG(dbgs() << "End X86FixupLEAs\n";); 146 147 return true; 148} 149 150FixupLEAPass::RegUsageState FixupLEAPass::usesRegister(MachineOperand& p, 151 MachineBasicBlock::iterator I) { 152 RegUsageState RegUsage = RU_NotUsed; 153 MachineInstr* MI = I; 154 155 for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { 156 MachineOperand& opnd = MI->getOperand(i); 157 if (opnd.isReg() && opnd.getReg() == p.getReg()){ 158 if (opnd.isDef()) 159 return RU_Write; 160 RegUsage = RU_Read; 161 } 162 } 163 return RegUsage; 164} 165 166/// getPreviousInstr - Given a reference to an instruction in a basic 167/// block, return a reference to the previous instruction in the block, 168/// wrapping around to the last instruction of the block if the block 169/// branches to itself. 170static inline bool getPreviousInstr(MachineBasicBlock::iterator& I, 171 MachineFunction::iterator MFI) { 172 if (I == MFI->begin()) { 173 if (MFI->isPredecessor(MFI)) { 174 I = --MFI->end(); 175 return true; 176 } 177 else 178 return false; 179 } 180 --I; 181 return true; 182} 183 184MachineBasicBlock::iterator FixupLEAPass::searchBackwards(MachineOperand& p, 185 MachineBasicBlock::iterator& I, 186 MachineFunction::iterator MFI) { 187 int InstrDistance = 1; 188 MachineBasicBlock::iterator CurInst; 189 static const int INSTR_DISTANCE_THRESHOLD = 5; 190 191 CurInst = I; 192 bool Found; 193 Found = getPreviousInstr(CurInst, MFI); 194 while( Found && I != CurInst) { 195 if (CurInst->isCall() || CurInst->isInlineAsm()) 196 break; 197 if (InstrDistance > INSTR_DISTANCE_THRESHOLD) 198 break; // too far back to make a difference 199 if (usesRegister(p, CurInst) == RU_Write){ 200 return CurInst; 201 } 202 InstrDistance += TII->getInstrLatency(TM->getInstrItineraryData(), CurInst); 203 Found = getPreviousInstr(CurInst, MFI); 204 } 205 return 0; 206} 207 208void FixupLEAPass::processInstruction(MachineBasicBlock::iterator& I, 209 MachineFunction::iterator MFI) { 210 // Process a load, store, or LEA instruction. 211 MachineInstr *MI = I; 212 int opcode = MI->getOpcode(); 213 const MCInstrDesc& Desc = MI->getDesc(); 214 int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); 215 if (AddrOffset >= 0) { 216 AddrOffset += X86II::getOperandBias(Desc); 217 MachineOperand& p = MI->getOperand(AddrOffset + X86::AddrBaseReg); 218 if (p.isReg() && p.getReg() != X86::ESP) { 219 seekLEAFixup(p, I, MFI); 220 } 221 MachineOperand& q = MI->getOperand(AddrOffset + X86::AddrIndexReg); 222 if (q.isReg() && q.getReg() != X86::ESP) { 223 seekLEAFixup(q, I, MFI); 224 } 225 } 226} 227 228void FixupLEAPass::seekLEAFixup(MachineOperand& p, 229 MachineBasicBlock::iterator& I, 230 MachineFunction::iterator MFI) { 231 MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); 232 if (MBI) { 233 MachineInstr* NewMI = postRAConvertToLEA(MFI, MBI); 234 if (NewMI) { 235 ++NumLEAs; 236 DEBUG(dbgs() << "Candidate to replace:"; MBI->dump();); 237 // now to replace with an equivalent LEA... 238 DEBUG(dbgs() << "Replaced by: "; NewMI->dump();); 239 MFI->erase(MBI); 240 MachineBasicBlock::iterator J = 241 static_cast<MachineBasicBlock::iterator> (NewMI); 242 processInstruction(J, MFI); 243 } 244 } 245} 246 247bool FixupLEAPass::processBasicBlock(MachineFunction &MF, 248 MachineFunction::iterator MFI) { 249 250 for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) 251 processInstruction(I, MFI); 252 return false; 253} 254