X86FixupLEAs.cpp revision 251607
1251607Sdim//===-- X86FixupLEAs.cpp - use or replace LEA instructions -----------===// 2251607Sdim// 3251607Sdim// The LLVM Compiler Infrastructure 4251607Sdim// 5251607Sdim// This file is distributed under the University of Illinois Open Source 6251607Sdim// License. See LICENSE.TXT for details. 7251607Sdim// 8251607Sdim//===----------------------------------------------------------------------===// 9251607Sdim// 10251607Sdim// This file defines the pass which will find instructions which 11251607Sdim// can be re-written as LEA instructions in order to reduce pipeline 12251607Sdim// delays for some models of the Intel Atom family. 13251607Sdim// 14251607Sdim//===----------------------------------------------------------------------===// 15251607Sdim 16251607Sdim#define DEBUG_TYPE "x86-fixup-LEAs" 17251607Sdim#include "X86.h" 18251607Sdim#include "X86InstrInfo.h" 19251607Sdim#include "X86Subtarget.h" 20251607Sdim#include "llvm/ADT/Statistic.h" 21251607Sdim#include "llvm/CodeGen/LiveVariables.h" 22251607Sdim#include "llvm/CodeGen/MachineFunctionPass.h" 23251607Sdim#include "llvm/CodeGen/MachineInstrBuilder.h" 24251607Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 25251607Sdim#include "llvm/CodeGen/Passes.h" 26251607Sdim#include "llvm/Support/Debug.h" 27251607Sdim#include "llvm/Support/raw_ostream.h" 28251607Sdim#include "llvm/Target/TargetInstrInfo.h" 29251607Sdimusing namespace llvm; 30251607Sdim 31251607SdimSTATISTIC(NumLEAs, "Number of LEA instructions created"); 32251607Sdim 33251607Sdimnamespace { 34251607Sdim class FixupLEAPass : public MachineFunctionPass { 35251607Sdim enum RegUsageState { RU_NotUsed, RU_Write, RU_Read }; 36251607Sdim static char ID; 37251607Sdim /// \brief Loop over all of the instructions in the basic block 38251607Sdim /// replacing applicable instructions with LEA instructions, 39251607Sdim /// where appropriate. 40251607Sdim bool processBasicBlock(MachineFunction &MF, MachineFunction::iterator MFI); 41251607Sdim 42251607Sdim virtual const char *getPassName() const { return "X86 Atom LEA Fixup";} 43251607Sdim 44251607Sdim /// \brief Given a machine register, look for the instruction 45251607Sdim /// which writes it in the current basic block. If found, 46251607Sdim /// try to replace it with an equivalent LEA instruction. 47251607Sdim /// If replacement succeeds, then also process the the newly created 48251607Sdim /// instruction. 49251607Sdim void seekLEAFixup(MachineOperand& p, MachineBasicBlock::iterator& I, 50251607Sdim MachineFunction::iterator MFI); 51251607Sdim 52251607Sdim /// \brief Given a memory access or LEA instruction 53251607Sdim /// whose address mode uses a base and/or index register, look for 54251607Sdim /// an opportunity to replace the instruction which sets the base or index 55251607Sdim /// register with an equivalent LEA instruction. 56251607Sdim void processInstruction(MachineBasicBlock::iterator& I, 57251607Sdim MachineFunction::iterator MFI); 58251607Sdim 59251607Sdim /// \brief Determine if an instruction references a machine register 60251607Sdim /// and, if so, whether it reads or writes the register. 61251607Sdim RegUsageState usesRegister(MachineOperand& p, 62251607Sdim MachineBasicBlock::iterator I); 63251607Sdim 64251607Sdim /// \brief Step backwards through a basic block, looking 65251607Sdim /// for an instruction which writes a register within 66251607Sdim /// a maximum of INSTR_DISTANCE_THRESHOLD instruction latency cycles. 67251607Sdim MachineBasicBlock::iterator searchBackwards(MachineOperand& p, 68251607Sdim MachineBasicBlock::iterator& I, 69251607Sdim MachineFunction::iterator MFI); 70251607Sdim 71251607Sdim /// \brief if an instruction can be converted to an 72251607Sdim /// equivalent LEA, insert the new instruction into the basic block 73251607Sdim /// and return a pointer to it. Otherwise, return zero. 74251607Sdim MachineInstr* postRAConvertToLEA(MachineFunction::iterator &MFI, 75251607Sdim MachineBasicBlock::iterator &MBBI) const; 76251607Sdim 77251607Sdim public: 78251607Sdim FixupLEAPass() : MachineFunctionPass(ID) {} 79251607Sdim 80251607Sdim /// \brief Loop over all of the basic blocks, 81251607Sdim /// replacing instructions by equivalent LEA instructions 82251607Sdim /// if needed and when possible. 83251607Sdim virtual bool runOnMachineFunction(MachineFunction &MF); 84251607Sdim 85251607Sdim private: 86251607Sdim MachineFunction *MF; 87251607Sdim const TargetMachine *TM; 88251607Sdim const TargetInstrInfo *TII; // Machine instruction info. 89251607Sdim 90251607Sdim }; 91251607Sdim char FixupLEAPass::ID = 0; 92251607Sdim} 93251607Sdim 94251607SdimMachineInstr * 95251607SdimFixupLEAPass::postRAConvertToLEA(MachineFunction::iterator &MFI, 96251607Sdim MachineBasicBlock::iterator &MBBI) const { 97251607Sdim MachineInstr* MI = MBBI; 98251607Sdim MachineInstr* NewMI; 99251607Sdim switch (MI->getOpcode()) { 100251607Sdim case X86::MOV32rr: 101251607Sdim case X86::MOV64rr: { 102251607Sdim const MachineOperand& Src = MI->getOperand(1); 103251607Sdim const MachineOperand& Dest = MI->getOperand(0); 104251607Sdim NewMI = BuildMI(*MF, MI->getDebugLoc(), 105251607Sdim TII->get( MI->getOpcode() == X86::MOV32rr ? X86::LEA32r : X86::LEA64r)) 106251607Sdim .addOperand(Dest) 107251607Sdim .addOperand(Src).addImm(1).addReg(0).addImm(0).addReg(0); 108251607Sdim MFI->insert(MBBI, NewMI); // Insert the new inst 109251607Sdim return NewMI; 110251607Sdim } 111251607Sdim case X86::ADD64ri32: 112251607Sdim case X86::ADD64ri8: 113251607Sdim case X86::ADD64ri32_DB: 114251607Sdim case X86::ADD64ri8_DB: 115251607Sdim case X86::ADD32ri: 116251607Sdim case X86::ADD32ri8: 117251607Sdim case X86::ADD32ri_DB: 118251607Sdim case X86::ADD32ri8_DB: 119251607Sdim case X86::ADD16ri: 120251607Sdim case X86::ADD16ri8: 121251607Sdim case X86::ADD16ri_DB: 122251607Sdim case X86::ADD16ri8_DB: 123251607Sdim if (!MI->getOperand(2).isImm()) { 124251607Sdim // convertToThreeAddress will call getImm() 125251607Sdim // which requires isImm() to be true 126251607Sdim return 0; 127251607Sdim } 128251607Sdim } 129251607Sdim return TII->convertToThreeAddress(MFI, MBBI, 0); 130251607Sdim} 131251607Sdim 132251607SdimFunctionPass *llvm::createX86FixupLEAs() { 133251607Sdim return new FixupLEAPass(); 134251607Sdim} 135251607Sdim 136251607Sdimbool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { 137251607Sdim MF = &Func; 138251607Sdim TII = Func.getTarget().getInstrInfo(); 139251607Sdim TM = &MF->getTarget(); 140251607Sdim 141251607Sdim DEBUG(dbgs() << "Start X86FixupLEAs\n";); 142251607Sdim // Process all basic blocks. 143251607Sdim for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) 144251607Sdim processBasicBlock(Func, I); 145251607Sdim DEBUG(dbgs() << "End X86FixupLEAs\n";); 146251607Sdim 147251607Sdim return true; 148251607Sdim} 149251607Sdim 150251607SdimFixupLEAPass::RegUsageState FixupLEAPass::usesRegister(MachineOperand& p, 151251607Sdim MachineBasicBlock::iterator I) { 152251607Sdim RegUsageState RegUsage = RU_NotUsed; 153251607Sdim MachineInstr* MI = I; 154251607Sdim 155251607Sdim for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { 156251607Sdim MachineOperand& opnd = MI->getOperand(i); 157251607Sdim if (opnd.isReg() && opnd.getReg() == p.getReg()){ 158251607Sdim if (opnd.isDef()) 159251607Sdim return RU_Write; 160251607Sdim RegUsage = RU_Read; 161251607Sdim } 162251607Sdim } 163251607Sdim return RegUsage; 164251607Sdim} 165251607Sdim 166251607Sdim/// getPreviousInstr - Given a reference to an instruction in a basic 167251607Sdim/// block, return a reference to the previous instruction in the block, 168251607Sdim/// wrapping around to the last instruction of the block if the block 169251607Sdim/// branches to itself. 170251607Sdimstatic inline bool getPreviousInstr(MachineBasicBlock::iterator& I, 171251607Sdim MachineFunction::iterator MFI) { 172251607Sdim if (I == MFI->begin()) { 173251607Sdim if (MFI->isPredecessor(MFI)) { 174251607Sdim I = --MFI->end(); 175251607Sdim return true; 176251607Sdim } 177251607Sdim else 178251607Sdim return false; 179251607Sdim } 180251607Sdim --I; 181251607Sdim return true; 182251607Sdim} 183251607Sdim 184251607SdimMachineBasicBlock::iterator FixupLEAPass::searchBackwards(MachineOperand& p, 185251607Sdim MachineBasicBlock::iterator& I, 186251607Sdim MachineFunction::iterator MFI) { 187251607Sdim int InstrDistance = 1; 188251607Sdim MachineBasicBlock::iterator CurInst; 189251607Sdim static const int INSTR_DISTANCE_THRESHOLD = 5; 190251607Sdim 191251607Sdim CurInst = I; 192251607Sdim bool Found; 193251607Sdim Found = getPreviousInstr(CurInst, MFI); 194251607Sdim while( Found && I != CurInst) { 195251607Sdim if (CurInst->isCall() || CurInst->isInlineAsm()) 196251607Sdim break; 197251607Sdim if (InstrDistance > INSTR_DISTANCE_THRESHOLD) 198251607Sdim break; // too far back to make a difference 199251607Sdim if (usesRegister(p, CurInst) == RU_Write){ 200251607Sdim return CurInst; 201251607Sdim } 202251607Sdim InstrDistance += TII->getInstrLatency(TM->getInstrItineraryData(), CurInst); 203251607Sdim Found = getPreviousInstr(CurInst, MFI); 204251607Sdim } 205251607Sdim return 0; 206251607Sdim} 207251607Sdim 208251607Sdimvoid FixupLEAPass::processInstruction(MachineBasicBlock::iterator& I, 209251607Sdim MachineFunction::iterator MFI) { 210251607Sdim // Process a load, store, or LEA instruction. 211251607Sdim MachineInstr *MI = I; 212251607Sdim int opcode = MI->getOpcode(); 213251607Sdim const MCInstrDesc& Desc = MI->getDesc(); 214251607Sdim int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); 215251607Sdim if (AddrOffset >= 0) { 216251607Sdim AddrOffset += X86II::getOperandBias(Desc); 217251607Sdim MachineOperand& p = MI->getOperand(AddrOffset + X86::AddrBaseReg); 218251607Sdim if (p.isReg() && p.getReg() != X86::ESP) { 219251607Sdim seekLEAFixup(p, I, MFI); 220251607Sdim } 221251607Sdim MachineOperand& q = MI->getOperand(AddrOffset + X86::AddrIndexReg); 222251607Sdim if (q.isReg() && q.getReg() != X86::ESP) { 223251607Sdim seekLEAFixup(q, I, MFI); 224251607Sdim } 225251607Sdim } 226251607Sdim} 227251607Sdim 228251607Sdimvoid FixupLEAPass::seekLEAFixup(MachineOperand& p, 229251607Sdim MachineBasicBlock::iterator& I, 230251607Sdim MachineFunction::iterator MFI) { 231251607Sdim MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); 232251607Sdim if (MBI) { 233251607Sdim MachineInstr* NewMI = postRAConvertToLEA(MFI, MBI); 234251607Sdim if (NewMI) { 235251607Sdim ++NumLEAs; 236251607Sdim DEBUG(dbgs() << "Candidate to replace:"; MBI->dump();); 237251607Sdim // now to replace with an equivalent LEA... 238251607Sdim DEBUG(dbgs() << "Replaced by: "; NewMI->dump();); 239251607Sdim MFI->erase(MBI); 240251607Sdim MachineBasicBlock::iterator J = 241251607Sdim static_cast<MachineBasicBlock::iterator> (NewMI); 242251607Sdim processInstruction(J, MFI); 243251607Sdim } 244251607Sdim } 245251607Sdim} 246251607Sdim 247251607Sdimbool FixupLEAPass::processBasicBlock(MachineFunction &MF, 248251607Sdim MachineFunction::iterator MFI) { 249251607Sdim 250251607Sdim for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) 251251607Sdim processInstruction(I, MFI); 252251607Sdim return false; 253251607Sdim} 254