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 } 128256059Sdim break; 129256059Sdim case X86::ADD16rr: 130256059Sdim case X86::ADD16rr_DB: 131256059Sdim if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) { 132256059Sdim // if src1 != src2, then convertToThreeAddress will 133256059Sdim // need to create a Virtual register, which we cannot do 134256059Sdim // after register allocation. 135256059Sdim return 0; 136256059Sdim } 137251607Sdim } 138251607Sdim return TII->convertToThreeAddress(MFI, MBBI, 0); 139251607Sdim} 140251607Sdim 141251607SdimFunctionPass *llvm::createX86FixupLEAs() { 142251607Sdim return new FixupLEAPass(); 143251607Sdim} 144251607Sdim 145251607Sdimbool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { 146251607Sdim MF = &Func; 147251607Sdim TM = &MF->getTarget(); 148263509Sdim TII = TM->getInstrInfo(); 149251607Sdim 150251607Sdim DEBUG(dbgs() << "Start X86FixupLEAs\n";); 151251607Sdim // Process all basic blocks. 152251607Sdim for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) 153251607Sdim processBasicBlock(Func, I); 154251607Sdim DEBUG(dbgs() << "End X86FixupLEAs\n";); 155251607Sdim 156251607Sdim return true; 157251607Sdim} 158251607Sdim 159251607SdimFixupLEAPass::RegUsageState FixupLEAPass::usesRegister(MachineOperand& p, 160251607Sdim MachineBasicBlock::iterator I) { 161251607Sdim RegUsageState RegUsage = RU_NotUsed; 162251607Sdim MachineInstr* MI = I; 163251607Sdim 164251607Sdim for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { 165251607Sdim MachineOperand& opnd = MI->getOperand(i); 166251607Sdim if (opnd.isReg() && opnd.getReg() == p.getReg()){ 167251607Sdim if (opnd.isDef()) 168251607Sdim return RU_Write; 169251607Sdim RegUsage = RU_Read; 170251607Sdim } 171251607Sdim } 172251607Sdim return RegUsage; 173251607Sdim} 174251607Sdim 175251607Sdim/// getPreviousInstr - Given a reference to an instruction in a basic 176251607Sdim/// block, return a reference to the previous instruction in the block, 177251607Sdim/// wrapping around to the last instruction of the block if the block 178251607Sdim/// branches to itself. 179251607Sdimstatic inline bool getPreviousInstr(MachineBasicBlock::iterator& I, 180251607Sdim MachineFunction::iterator MFI) { 181251607Sdim if (I == MFI->begin()) { 182251607Sdim if (MFI->isPredecessor(MFI)) { 183251607Sdim I = --MFI->end(); 184251607Sdim return true; 185251607Sdim } 186251607Sdim else 187251607Sdim return false; 188251607Sdim } 189251607Sdim --I; 190251607Sdim return true; 191251607Sdim} 192251607Sdim 193251607SdimMachineBasicBlock::iterator FixupLEAPass::searchBackwards(MachineOperand& p, 194251607Sdim MachineBasicBlock::iterator& I, 195251607Sdim MachineFunction::iterator MFI) { 196251607Sdim int InstrDistance = 1; 197251607Sdim MachineBasicBlock::iterator CurInst; 198251607Sdim static const int INSTR_DISTANCE_THRESHOLD = 5; 199251607Sdim 200251607Sdim CurInst = I; 201251607Sdim bool Found; 202251607Sdim Found = getPreviousInstr(CurInst, MFI); 203251607Sdim while( Found && I != CurInst) { 204251607Sdim if (CurInst->isCall() || CurInst->isInlineAsm()) 205251607Sdim break; 206251607Sdim if (InstrDistance > INSTR_DISTANCE_THRESHOLD) 207251607Sdim break; // too far back to make a difference 208251607Sdim if (usesRegister(p, CurInst) == RU_Write){ 209251607Sdim return CurInst; 210251607Sdim } 211251607Sdim InstrDistance += TII->getInstrLatency(TM->getInstrItineraryData(), CurInst); 212251607Sdim Found = getPreviousInstr(CurInst, MFI); 213251607Sdim } 214251607Sdim return 0; 215251607Sdim} 216251607Sdim 217251607Sdimvoid FixupLEAPass::processInstruction(MachineBasicBlock::iterator& I, 218251607Sdim MachineFunction::iterator MFI) { 219251607Sdim // Process a load, store, or LEA instruction. 220251607Sdim MachineInstr *MI = I; 221251607Sdim int opcode = MI->getOpcode(); 222251607Sdim const MCInstrDesc& Desc = MI->getDesc(); 223251607Sdim int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); 224251607Sdim if (AddrOffset >= 0) { 225251607Sdim AddrOffset += X86II::getOperandBias(Desc); 226251607Sdim MachineOperand& p = MI->getOperand(AddrOffset + X86::AddrBaseReg); 227251607Sdim if (p.isReg() && p.getReg() != X86::ESP) { 228251607Sdim seekLEAFixup(p, I, MFI); 229251607Sdim } 230251607Sdim MachineOperand& q = MI->getOperand(AddrOffset + X86::AddrIndexReg); 231251607Sdim if (q.isReg() && q.getReg() != X86::ESP) { 232251607Sdim seekLEAFixup(q, I, MFI); 233251607Sdim } 234251607Sdim } 235251607Sdim} 236251607Sdim 237251607Sdimvoid FixupLEAPass::seekLEAFixup(MachineOperand& p, 238251607Sdim MachineBasicBlock::iterator& I, 239251607Sdim MachineFunction::iterator MFI) { 240251607Sdim MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); 241251607Sdim if (MBI) { 242251607Sdim MachineInstr* NewMI = postRAConvertToLEA(MFI, MBI); 243251607Sdim if (NewMI) { 244251607Sdim ++NumLEAs; 245251607Sdim DEBUG(dbgs() << "Candidate to replace:"; MBI->dump();); 246251607Sdim // now to replace with an equivalent LEA... 247251607Sdim DEBUG(dbgs() << "Replaced by: "; NewMI->dump();); 248251607Sdim MFI->erase(MBI); 249251607Sdim MachineBasicBlock::iterator J = 250251607Sdim static_cast<MachineBasicBlock::iterator> (NewMI); 251251607Sdim processInstruction(J, MFI); 252251607Sdim } 253251607Sdim } 254251607Sdim} 255251607Sdim 256251607Sdimbool FixupLEAPass::processBasicBlock(MachineFunction &MF, 257251607Sdim MachineFunction::iterator MFI) { 258251607Sdim 259251607Sdim for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) 260251607Sdim processInstruction(I, MFI); 261251607Sdim return false; 262251607Sdim} 263