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 break; 129 case X86::ADD16rr: 130 case X86::ADD16rr_DB: 131 if (MI->getOperand(1).getReg() != MI->getOperand(2).getReg()) { 132 // if src1 != src2, then convertToThreeAddress will 133 // need to create a Virtual register, which we cannot do 134 // after register allocation. 135 return 0; 136 } 137 } 138 return TII->convertToThreeAddress(MFI, MBBI, 0); 139} 140 141FunctionPass *llvm::createX86FixupLEAs() { 142 return new FixupLEAPass(); 143} 144 145bool FixupLEAPass::runOnMachineFunction(MachineFunction &Func) { 146 MF = &Func; 147 TM = &MF->getTarget(); 148 TII = TM->getInstrInfo(); 149 150 DEBUG(dbgs() << "Start X86FixupLEAs\n";); 151 // Process all basic blocks. 152 for (MachineFunction::iterator I = Func.begin(), E = Func.end(); I != E; ++I) 153 processBasicBlock(Func, I); 154 DEBUG(dbgs() << "End X86FixupLEAs\n";); 155 156 return true; 157} 158 159FixupLEAPass::RegUsageState FixupLEAPass::usesRegister(MachineOperand& p, 160 MachineBasicBlock::iterator I) { 161 RegUsageState RegUsage = RU_NotUsed; 162 MachineInstr* MI = I; 163 164 for (unsigned int i = 0; i < MI->getNumOperands(); ++i) { 165 MachineOperand& opnd = MI->getOperand(i); 166 if (opnd.isReg() && opnd.getReg() == p.getReg()){ 167 if (opnd.isDef()) 168 return RU_Write; 169 RegUsage = RU_Read; 170 } 171 } 172 return RegUsage; 173} 174 175/// getPreviousInstr - Given a reference to an instruction in a basic 176/// block, return a reference to the previous instruction in the block, 177/// wrapping around to the last instruction of the block if the block 178/// branches to itself. 179static inline bool getPreviousInstr(MachineBasicBlock::iterator& I, 180 MachineFunction::iterator MFI) { 181 if (I == MFI->begin()) { 182 if (MFI->isPredecessor(MFI)) { 183 I = --MFI->end(); 184 return true; 185 } 186 else 187 return false; 188 } 189 --I; 190 return true; 191} 192 193MachineBasicBlock::iterator FixupLEAPass::searchBackwards(MachineOperand& p, 194 MachineBasicBlock::iterator& I, 195 MachineFunction::iterator MFI) { 196 int InstrDistance = 1; 197 MachineBasicBlock::iterator CurInst; 198 static const int INSTR_DISTANCE_THRESHOLD = 5; 199 200 CurInst = I; 201 bool Found; 202 Found = getPreviousInstr(CurInst, MFI); 203 while( Found && I != CurInst) { 204 if (CurInst->isCall() || CurInst->isInlineAsm()) 205 break; 206 if (InstrDistance > INSTR_DISTANCE_THRESHOLD) 207 break; // too far back to make a difference 208 if (usesRegister(p, CurInst) == RU_Write){ 209 return CurInst; 210 } 211 InstrDistance += TII->getInstrLatency(TM->getInstrItineraryData(), CurInst); 212 Found = getPreviousInstr(CurInst, MFI); 213 } 214 return 0; 215} 216 217void FixupLEAPass::processInstruction(MachineBasicBlock::iterator& I, 218 MachineFunction::iterator MFI) { 219 // Process a load, store, or LEA instruction. 220 MachineInstr *MI = I; 221 int opcode = MI->getOpcode(); 222 const MCInstrDesc& Desc = MI->getDesc(); 223 int AddrOffset = X86II::getMemoryOperandNo(Desc.TSFlags, opcode); 224 if (AddrOffset >= 0) { 225 AddrOffset += X86II::getOperandBias(Desc); 226 MachineOperand& p = MI->getOperand(AddrOffset + X86::AddrBaseReg); 227 if (p.isReg() && p.getReg() != X86::ESP) { 228 seekLEAFixup(p, I, MFI); 229 } 230 MachineOperand& q = MI->getOperand(AddrOffset + X86::AddrIndexReg); 231 if (q.isReg() && q.getReg() != X86::ESP) { 232 seekLEAFixup(q, I, MFI); 233 } 234 } 235} 236 237void FixupLEAPass::seekLEAFixup(MachineOperand& p, 238 MachineBasicBlock::iterator& I, 239 MachineFunction::iterator MFI) { 240 MachineBasicBlock::iterator MBI = searchBackwards(p, I, MFI); 241 if (MBI) { 242 MachineInstr* NewMI = postRAConvertToLEA(MFI, MBI); 243 if (NewMI) { 244 ++NumLEAs; 245 DEBUG(dbgs() << "Candidate to replace:"; MBI->dump();); 246 // now to replace with an equivalent LEA... 247 DEBUG(dbgs() << "Replaced by: "; NewMI->dump();); 248 MFI->erase(MBI); 249 MachineBasicBlock::iterator J = 250 static_cast<MachineBasicBlock::iterator> (NewMI); 251 processInstruction(J, MFI); 252 } 253 } 254} 255 256bool FixupLEAPass::processBasicBlock(MachineFunction &MF, 257 MachineFunction::iterator MFI) { 258 259 for (MachineBasicBlock::iterator I = MFI->begin(); I != MFI->end(); ++I) 260 processInstruction(I, MFI); 261 return false; 262} 263