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