LLVM API Documentation
00001 //===-- ARMLoadStoreOptimizer.cpp - ARM load / store opt. pass ----*- C++ -*-=// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file contains a pass that performs load / store related peephole 00011 // optimizations. This pass should be run after register allocation. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #define DEBUG_TYPE "arm-ldst-opt" 00016 #include "ARM.h" 00017 #include "ARMAddressingModes.h" 00018 #include "ARMBaseInstrInfo.h" 00019 #include "ARMMachineFunctionInfo.h" 00020 #include "ARMRegisterInfo.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/Function.h" 00023 #include "llvm/CodeGen/MachineBasicBlock.h" 00024 #include "llvm/CodeGen/MachineFunctionPass.h" 00025 #include "llvm/CodeGen/MachineInstr.h" 00026 #include "llvm/CodeGen/MachineInstrBuilder.h" 00027 #include "llvm/CodeGen/MachineRegisterInfo.h" 00028 #include "llvm/CodeGen/RegisterScavenging.h" 00029 #include "llvm/Target/TargetData.h" 00030 #include "llvm/Target/TargetInstrInfo.h" 00031 #include "llvm/Target/TargetMachine.h" 00032 #include "llvm/Target/TargetRegisterInfo.h" 00033 #include "llvm/Support/Compiler.h" 00034 #include "llvm/Support/ErrorHandling.h" 00035 #include "llvm/ADT/DenseMap.h" 00036 #include "llvm/ADT/STLExtras.h" 00037 #include "llvm/ADT/SmallPtrSet.h" 00038 #include "llvm/ADT/SmallSet.h" 00039 #include "llvm/ADT/SmallVector.h" 00040 #include "llvm/ADT/Statistic.h" 00041 using namespace llvm; 00042 00043 STATISTIC(NumLDMGened , "Number of ldm instructions generated"); 00044 STATISTIC(NumSTMGened , "Number of stm instructions generated"); 00045 STATISTIC(NumFLDMGened, "Number of fldm instructions generated"); 00046 STATISTIC(NumFSTMGened, "Number of fstm instructions generated"); 00047 STATISTIC(NumLdStMoved, "Number of load / store instructions moved"); 00048 STATISTIC(NumLDRDFormed,"Number of ldrd created before allocation"); 00049 STATISTIC(NumSTRDFormed,"Number of strd created before allocation"); 00050 STATISTIC(NumLDRD2LDM, "Number of ldrd instructions turned back into ldm"); 00051 STATISTIC(NumSTRD2STM, "Number of strd instructions turned back into stm"); 00052 STATISTIC(NumLDRD2LDR, "Number of ldrd instructions turned back into ldr's"); 00053 STATISTIC(NumSTRD2STR, "Number of strd instructions turned back into str's"); 00054 00055 /// ARMAllocLoadStoreOpt - Post- register allocation pass the combine 00056 /// load / store instructions to form ldm / stm instructions. 00057 00058 namespace { 00059 struct VISIBILITY_HIDDEN ARMLoadStoreOpt : public MachineFunctionPass { 00060 static char ID; 00061 ARMLoadStoreOpt() : MachineFunctionPass(&ID) {} 00062 00063 const TargetInstrInfo *TII; 00064 const TargetRegisterInfo *TRI; 00065 ARMFunctionInfo *AFI; 00066 RegScavenger *RS; 00067 bool isThumb2; 00068 00069 virtual bool runOnMachineFunction(MachineFunction &Fn); 00070 00071 virtual const char *getPassName() const { 00072 return "ARM load / store optimization pass"; 00073 } 00074 00075 private: 00076 struct MemOpQueueEntry { 00077 int Offset; 00078 unsigned Position; 00079 MachineBasicBlock::iterator MBBI; 00080 bool Merged; 00081 MemOpQueueEntry(int o, int p, MachineBasicBlock::iterator i) 00082 : Offset(o), Position(p), MBBI(i), Merged(false) {}; 00083 }; 00084 typedef SmallVector<MemOpQueueEntry,8> MemOpQueue; 00085 typedef MemOpQueue::iterator MemOpQueueIter; 00086 00087 bool MergeOps(MachineBasicBlock &MBB, MachineBasicBlock::iterator MBBI, 00088 int Offset, unsigned Base, bool BaseKill, int Opcode, 00089 ARMCC::CondCodes Pred, unsigned PredReg, unsigned Scratch, 00090 DebugLoc dl, SmallVector<std::pair<unsigned, bool>, 8> &Regs); 00091 void MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, unsigned Base, 00092 int Opcode, unsigned Size, 00093 ARMCC::CondCodes Pred, unsigned PredReg, 00094 unsigned Scratch, MemOpQueue &MemOps, 00095 SmallVector<MachineBasicBlock::iterator, 4> &Merges); 00096 00097 void AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps); 00098 bool FixInvalidRegPairOp(MachineBasicBlock &MBB, 00099 MachineBasicBlock::iterator &MBBI); 00100 bool MergeBaseUpdateLoadStore(MachineBasicBlock &MBB, 00101 MachineBasicBlock::iterator MBBI, 00102 const TargetInstrInfo *TII, 00103 bool &Advance, 00104 MachineBasicBlock::iterator &I); 00105 bool MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB, 00106 MachineBasicBlock::iterator MBBI, 00107 bool &Advance, 00108 MachineBasicBlock::iterator &I); 00109 bool LoadStoreMultipleOpti(MachineBasicBlock &MBB); 00110 bool MergeReturnIntoLDM(MachineBasicBlock &MBB); 00111 }; 00112 char ARMLoadStoreOpt::ID = 0; 00113 } 00114 00115 static int getLoadStoreMultipleOpcode(int Opcode) { 00116 switch (Opcode) { 00117 case ARM::LDR: 00118 NumLDMGened++; 00119 return ARM::LDM; 00120 case ARM::STR: 00121 NumSTMGened++; 00122 return ARM::STM; 00123 case ARM::t2LDRi8: 00124 case ARM::t2LDRi12: 00125 NumLDMGened++; 00126 return ARM::t2LDM; 00127 case ARM::t2STRi8: 00128 case ARM::t2STRi12: 00129 NumSTMGened++; 00130 return ARM::t2STM; 00131 case ARM::FLDS: 00132 NumFLDMGened++; 00133 return ARM::FLDMS; 00134 case ARM::FSTS: 00135 NumFSTMGened++; 00136 return ARM::FSTMS; 00137 case ARM::FLDD: 00138 NumFLDMGened++; 00139 return ARM::FLDMD; 00140 case ARM::FSTD: 00141 NumFSTMGened++; 00142 return ARM::FSTMD; 00143 default: llvm_unreachable("Unhandled opcode!"); 00144 } 00145 return 0; 00146 } 00147 00148 static bool isT2i32Load(unsigned Opc) { 00149 return Opc == ARM::t2LDRi12 || Opc == ARM::t2LDRi8; 00150 } 00151 00152 static bool isi32Load(unsigned Opc) { 00153 return Opc == ARM::LDR || isT2i32Load(Opc); 00154 } 00155 00156 static bool isT2i32Store(unsigned Opc) { 00157 return Opc == ARM::t2STRi12 || Opc == ARM::t2STRi8; 00158 } 00159 00160 static bool isi32Store(unsigned Opc) { 00161 return Opc == ARM::STR || isT2i32Store(Opc); 00162 } 00163 00164 /// MergeOps - Create and insert a LDM or STM with Base as base register and 00165 /// registers in Regs as the register operands that would be loaded / stored. 00166 /// It returns true if the transformation is done. 00167 bool 00168 ARMLoadStoreOpt::MergeOps(MachineBasicBlock &MBB, 00169 MachineBasicBlock::iterator MBBI, 00170 int Offset, unsigned Base, bool BaseKill, 00171 int Opcode, ARMCC::CondCodes Pred, 00172 unsigned PredReg, unsigned Scratch, DebugLoc dl, 00173 SmallVector<std::pair<unsigned, bool>, 8> &Regs) { 00174 // Only a single register to load / store. Don't bother. 00175 unsigned NumRegs = Regs.size(); 00176 if (NumRegs <= 1) 00177 return false; 00178 00179 ARM_AM::AMSubMode Mode = ARM_AM::ia; 00180 bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode); 00181 if (isAM4 && Offset == 4) { 00182 if (isThumb2) 00183 // Thumb2 does not support ldmib / stmib. 00184 return false; 00185 Mode = ARM_AM::ib; 00186 } else if (isAM4 && Offset == -4 * (int)NumRegs + 4) { 00187 if (isThumb2) 00188 // Thumb2 does not support ldmda / stmda. 00189 return false; 00190 Mode = ARM_AM::da; 00191 } else if (isAM4 && Offset == -4 * (int)NumRegs) { 00192 Mode = ARM_AM::db; 00193 } else if (Offset != 0) { 00194 // If starting offset isn't zero, insert a MI to materialize a new base. 00195 // But only do so if it is cost effective, i.e. merging more than two 00196 // loads / stores. 00197 if (NumRegs <= 2) 00198 return false; 00199 00200 unsigned NewBase; 00201 if (isi32Load(Opcode)) 00202 // If it is a load, then just use one of the destination register to 00203 // use as the new base. 00204 NewBase = Regs[NumRegs-1].first; 00205 else { 00206 // Use the scratch register to use as a new base. 00207 NewBase = Scratch; 00208 if (NewBase == 0) 00209 return false; 00210 } 00211 int BaseOpc = !isThumb2 00212 ? ARM::ADDri 00213 : ((Base == ARM::SP) ? ARM::t2ADDrSPi : ARM::t2ADDri); 00214 if (Offset < 0) { 00215 BaseOpc = !isThumb2 00216 ? ARM::SUBri 00217 : ((Base == ARM::SP) ? ARM::t2SUBrSPi : ARM::t2SUBri); 00218 Offset = - Offset; 00219 } 00220 int ImmedOffset = isThumb2 00221 ? ARM_AM::getT2SOImmVal(Offset) : ARM_AM::getSOImmVal(Offset); 00222 if (ImmedOffset == -1) 00223 // FIXME: Try t2ADDri12 or t2SUBri12? 00224 return false; // Probably not worth it then. 00225 00226 BuildMI(MBB, MBBI, dl, TII->get(BaseOpc), NewBase) 00227 .addReg(Base, getKillRegState(BaseKill)).addImm(Offset) 00228 .addImm(Pred).addReg(PredReg).addReg(0); 00229 Base = NewBase; 00230 BaseKill = true; // New base is always killed right its use. 00231 } 00232 00233 bool isDPR = Opcode == ARM::FLDD || Opcode == ARM::FSTD; 00234 bool isDef = isi32Load(Opcode) || Opcode == ARM::FLDS || Opcode == ARM::FLDD; 00235 Opcode = getLoadStoreMultipleOpcode(Opcode); 00236 MachineInstrBuilder MIB = (isAM4) 00237 ? BuildMI(MBB, MBBI, dl, TII->get(Opcode)) 00238 .addReg(Base, getKillRegState(BaseKill)) 00239 .addImm(ARM_AM::getAM4ModeImm(Mode)).addImm(Pred).addReg(PredReg) 00240 : BuildMI(MBB, MBBI, dl, TII->get(Opcode)) 00241 .addReg(Base, getKillRegState(BaseKill)) 00242 .addImm(ARM_AM::getAM5Opc(Mode, false, isDPR ? NumRegs<<1 : NumRegs)) 00243 .addImm(Pred).addReg(PredReg); 00244 for (unsigned i = 0; i != NumRegs; ++i) 00245 MIB = MIB.addReg(Regs[i].first, getDefRegState(isDef) 00246 | getKillRegState(Regs[i].second)); 00247 00248 return true; 00249 } 00250 00251 /// MergeLDR_STR - Merge a number of load / store instructions into one or more 00252 /// load / store multiple instructions. 00253 void 00254 ARMLoadStoreOpt::MergeLDR_STR(MachineBasicBlock &MBB, unsigned SIndex, 00255 unsigned Base, int Opcode, unsigned Size, 00256 ARMCC::CondCodes Pred, unsigned PredReg, 00257 unsigned Scratch, MemOpQueue &MemOps, 00258 SmallVector<MachineBasicBlock::iterator, 4> &Merges) { 00259 bool isAM4 = isi32Load(Opcode) || isi32Store(Opcode); 00260 int Offset = MemOps[SIndex].Offset; 00261 int SOffset = Offset; 00262 unsigned Pos = MemOps[SIndex].Position; 00263 MachineBasicBlock::iterator Loc = MemOps[SIndex].MBBI; 00264 DebugLoc dl = Loc->getDebugLoc(); 00265 unsigned PReg = Loc->getOperand(0).getReg(); 00266 unsigned PRegNum = ARMRegisterInfo::getRegisterNumbering(PReg); 00267 bool isKill = Loc->getOperand(0).isKill(); 00268 00269 SmallVector<std::pair<unsigned,bool>, 8> Regs; 00270 Regs.push_back(std::make_pair(PReg, isKill)); 00271 for (unsigned i = SIndex+1, e = MemOps.size(); i != e; ++i) { 00272 int NewOffset = MemOps[i].Offset; 00273 unsigned Reg = MemOps[i].MBBI->getOperand(0).getReg(); 00274 unsigned RegNum = ARMRegisterInfo::getRegisterNumbering(Reg); 00275 isKill = MemOps[i].MBBI->getOperand(0).isKill(); 00276 // AM4 - register numbers in ascending order. 00277 // AM5 - consecutive register numbers in ascending order. 00278 if (NewOffset == Offset + (int)Size && 00279 ((isAM4 && RegNum > PRegNum) || RegNum == PRegNum+1)) { 00280 Offset += Size; 00281 Regs.push_back(std::make_pair(Reg, isKill)); 00282 PRegNum = RegNum; 00283 } else { 00284 // Can't merge this in. Try merge the earlier ones first. 00285 if (MergeOps(MBB, ++Loc, SOffset, Base, false, Opcode, Pred, PredReg, 00286 Scratch, dl, Regs)) { 00287 Merges.push_back(prior(Loc)); 00288 for (unsigned j = SIndex; j < i; ++j) { 00289 MBB.erase(MemOps[j].MBBI); 00290 MemOps[j].Merged = true; 00291 } 00292 } 00293 MergeLDR_STR(MBB, i, Base, Opcode, Size, Pred, PredReg, Scratch, 00294 MemOps, Merges); 00295 return; 00296 } 00297 00298 if (MemOps[i].Position > Pos) { 00299 Pos = MemOps[i].Position; 00300 Loc = MemOps[i].MBBI; 00301 } 00302 } 00303 00304 bool BaseKill = Loc->findRegisterUseOperandIdx(Base, true) != -1; 00305 if (MergeOps(MBB, ++Loc, SOffset, Base, BaseKill, Opcode, Pred, PredReg, 00306 Scratch, dl, Regs)) { 00307 Merges.push_back(prior(Loc)); 00308 for (unsigned i = SIndex, e = MemOps.size(); i != e; ++i) { 00309 MBB.erase(MemOps[i].MBBI); 00310 MemOps[i].Merged = true; 00311 } 00312 } 00313 00314 return; 00315 } 00316 00317 static inline bool isMatchingDecrement(MachineInstr *MI, unsigned Base, 00318 unsigned Bytes, unsigned Limit, 00319 ARMCC::CondCodes Pred, unsigned PredReg){ 00320 unsigned MyPredReg = 0; 00321 if (!MI) 00322 return false; 00323 if (MI->getOpcode() != ARM::t2SUBri && 00324 MI->getOpcode() != ARM::t2SUBrSPi && 00325 MI->getOpcode() != ARM::t2SUBrSPi12 && 00326 MI->getOpcode() != ARM::tSUBspi && 00327 MI->getOpcode() != ARM::SUBri) 00328 return false; 00329 00330 // Make sure the offset fits in 8 bits. 00331 if (Bytes <= 0 || (Limit && Bytes >= Limit)) 00332 return false; 00333 00334 unsigned Scale = (MI->getOpcode() == ARM::tSUBspi) ? 4 : 1; // FIXME 00335 return (MI->getOperand(0).getReg() == Base && 00336 MI->getOperand(1).getReg() == Base && 00337 (MI->getOperand(2).getImm()*Scale) == Bytes && 00338 llvm::getInstrPredicate(MI, MyPredReg) == Pred && 00339 MyPredReg == PredReg); 00340 } 00341 00342 static inline bool isMatchingIncrement(MachineInstr *MI, unsigned Base, 00343 unsigned Bytes, unsigned Limit, 00344 ARMCC::CondCodes Pred, unsigned PredReg){ 00345 unsigned MyPredReg = 0; 00346 if (!MI) 00347 return false; 00348 if (MI->getOpcode() != ARM::t2ADDri && 00349 MI->getOpcode() != ARM::t2ADDrSPi && 00350 MI->getOpcode() != ARM::t2ADDrSPi12 && 00351 MI->getOpcode() != ARM::tADDspi && 00352 MI->getOpcode() != ARM::ADDri) 00353 return false; 00354 00355 if (Bytes <= 0 || (Limit && Bytes >= Limit)) 00356 // Make sure the offset fits in 8 bits. 00357 return false; 00358 00359 unsigned Scale = (MI->getOpcode() == ARM::tADDspi) ? 4 : 1; // FIXME 00360 return (MI->getOperand(0).getReg() == Base && 00361 MI->getOperand(1).getReg() == Base && 00362 (MI->getOperand(2).getImm()*Scale) == Bytes && 00363 llvm::getInstrPredicate(MI, MyPredReg) == Pred && 00364 MyPredReg == PredReg); 00365 } 00366 00367 static inline unsigned getLSMultipleTransferSize(MachineInstr *MI) { 00368 switch (MI->getOpcode()) { 00369 default: return 0; 00370 case ARM::LDR: 00371 case ARM::STR: 00372 case ARM::t2LDRi8: 00373 case ARM::t2LDRi12: 00374 case ARM::t2STRi8: 00375 case ARM::t2STRi12: 00376 case ARM::FLDS: 00377 case ARM::FSTS: 00378 return 4; 00379 case ARM::FLDD: 00380 case ARM::FSTD: 00381 return 8; 00382 case ARM::LDM: 00383 case ARM::STM: 00384 case ARM::t2LDM: 00385 case ARM::t2STM: 00386 return (MI->getNumOperands() - 4) * 4; 00387 case ARM::FLDMS: 00388 case ARM::FSTMS: 00389 case ARM::FLDMD: 00390 case ARM::FSTMD: 00391 return ARM_AM::getAM5Offset(MI->getOperand(1).getImm()) * 4; 00392 } 00393 } 00394 00395 /// MergeBaseUpdateLSMultiple - Fold proceeding/trailing inc/dec of base 00396 /// register into the LDM/STM/FLDM{D|S}/FSTM{D|S} op when possible: 00397 /// 00398 /// stmia rn, <ra, rb, rc> 00399 /// rn := rn + 4 * 3; 00400 /// => 00401 /// stmia rn!, <ra, rb, rc> 00402 /// 00403 /// rn := rn - 4 * 3; 00404 /// ldmia rn, <ra, rb, rc> 00405 /// => 00406 /// ldmdb rn!, <ra, rb, rc> 00407 bool ARMLoadStoreOpt::MergeBaseUpdateLSMultiple(MachineBasicBlock &MBB, 00408 MachineBasicBlock::iterator MBBI, 00409 bool &Advance, 00410 MachineBasicBlock::iterator &I) { 00411 MachineInstr *MI = MBBI; 00412 unsigned Base = MI->getOperand(0).getReg(); 00413 unsigned Bytes = getLSMultipleTransferSize(MI); 00414 unsigned PredReg = 0; 00415 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 00416 int Opcode = MI->getOpcode(); 00417 bool isAM4 = Opcode == ARM::LDM || Opcode == ARM::t2LDM || 00418 Opcode == ARM::STM || Opcode == ARM::t2STM; 00419 00420 if (isAM4) { 00421 if (ARM_AM::getAM4WBFlag(MI->getOperand(1).getImm())) 00422 return false; 00423 00424 // Can't use the updating AM4 sub-mode if the base register is also a dest 00425 // register. e.g. ldmdb r0!, {r0, r1, r2}. The behavior is undefined. 00426 for (unsigned i = 3, e = MI->getNumOperands(); i != e; ++i) { 00427 if (MI->getOperand(i).getReg() == Base) 00428 return false; 00429 } 00430 00431 ARM_AM::AMSubMode Mode = ARM_AM::getAM4SubMode(MI->getOperand(1).getImm()); 00432 if (MBBI != MBB.begin()) { 00433 MachineBasicBlock::iterator PrevMBBI = prior(MBBI); 00434 if (Mode == ARM_AM::ia && 00435 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) { 00436 MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::db, true)); 00437 MBB.erase(PrevMBBI); 00438 return true; 00439 } else if (Mode == ARM_AM::ib && 00440 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) { 00441 MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(ARM_AM::da, true)); 00442 MBB.erase(PrevMBBI); 00443 return true; 00444 } 00445 } 00446 00447 if (MBBI != MBB.end()) { 00448 MachineBasicBlock::iterator NextMBBI = next(MBBI); 00449 if ((Mode == ARM_AM::ia || Mode == ARM_AM::ib) && 00450 isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) { 00451 MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true)); 00452 if (NextMBBI == I) { 00453 Advance = true; 00454 ++I; 00455 } 00456 MBB.erase(NextMBBI); 00457 return true; 00458 } else if ((Mode == ARM_AM::da || Mode == ARM_AM::db) && 00459 isMatchingDecrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) { 00460 MI->getOperand(1).setImm(ARM_AM::getAM4ModeImm(Mode, true)); 00461 if (NextMBBI == I) { 00462 Advance = true; 00463 ++I; 00464 } 00465 MBB.erase(NextMBBI); 00466 return true; 00467 } 00468 } 00469 } else { 00470 // FLDM{D|S}, FSTM{D|S} addressing mode 5 ops. 00471 if (ARM_AM::getAM5WBFlag(MI->getOperand(1).getImm())) 00472 return false; 00473 00474 ARM_AM::AMSubMode Mode = ARM_AM::getAM5SubMode(MI->getOperand(1).getImm()); 00475 unsigned Offset = ARM_AM::getAM5Offset(MI->getOperand(1).getImm()); 00476 if (MBBI != MBB.begin()) { 00477 MachineBasicBlock::iterator PrevMBBI = prior(MBBI); 00478 if (Mode == ARM_AM::ia && 00479 isMatchingDecrement(PrevMBBI, Base, Bytes, 0, Pred, PredReg)) { 00480 MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::db, true, Offset)); 00481 MBB.erase(PrevMBBI); 00482 return true; 00483 } 00484 } 00485 00486 if (MBBI != MBB.end()) { 00487 MachineBasicBlock::iterator NextMBBI = next(MBBI); 00488 if (Mode == ARM_AM::ia && 00489 isMatchingIncrement(NextMBBI, Base, Bytes, 0, Pred, PredReg)) { 00490 MI->getOperand(1).setImm(ARM_AM::getAM5Opc(ARM_AM::ia, true, Offset)); 00491 if (NextMBBI == I) { 00492 Advance = true; 00493 ++I; 00494 } 00495 MBB.erase(NextMBBI); 00496 } 00497 return true; 00498 } 00499 } 00500 00501 return false; 00502 } 00503 00504 static unsigned getPreIndexedLoadStoreOpcode(unsigned Opc) { 00505 switch (Opc) { 00506 case ARM::LDR: return ARM::LDR_PRE; 00507 case ARM::STR: return ARM::STR_PRE; 00508 case ARM::FLDS: return ARM::FLDMS; 00509 case ARM::FLDD: return ARM::FLDMD; 00510 case ARM::FSTS: return ARM::FSTMS; 00511 case ARM::FSTD: return ARM::FSTMD; 00512 case ARM::t2LDRi8: 00513 case ARM::t2LDRi12: 00514 return ARM::t2LDR_PRE; 00515 case ARM::t2STRi8: 00516 case ARM::t2STRi12: 00517 return ARM::t2STR_PRE; 00518 default: llvm_unreachable("Unhandled opcode!"); 00519 } 00520 return 0; 00521 } 00522 00523 static unsigned getPostIndexedLoadStoreOpcode(unsigned Opc) { 00524 switch (Opc) { 00525 case ARM::LDR: return ARM::LDR_POST; 00526 case ARM::STR: return ARM::STR_POST; 00527 case ARM::FLDS: return ARM::FLDMS; 00528 case ARM::FLDD: return ARM::FLDMD; 00529 case ARM::FSTS: return ARM::FSTMS; 00530 case ARM::FSTD: return ARM::FSTMD; 00531 case ARM::t2LDRi8: 00532 case ARM::t2LDRi12: 00533 return ARM::t2LDR_POST; 00534 case ARM::t2STRi8: 00535 case ARM::t2STRi12: 00536 return ARM::t2STR_POST; 00537 default: llvm_unreachable("Unhandled opcode!"); 00538 } 00539 return 0; 00540 } 00541 00542 /// MergeBaseUpdateLoadStore - Fold proceeding/trailing inc/dec of base 00543 /// register into the LDR/STR/FLD{D|S}/FST{D|S} op when possible: 00544 bool ARMLoadStoreOpt::MergeBaseUpdateLoadStore(MachineBasicBlock &MBB, 00545 MachineBasicBlock::iterator MBBI, 00546 const TargetInstrInfo *TII, 00547 bool &Advance, 00548 MachineBasicBlock::iterator &I) { 00549 MachineInstr *MI = MBBI; 00550 unsigned Base = MI->getOperand(1).getReg(); 00551 bool BaseKill = MI->getOperand(1).isKill(); 00552 unsigned Bytes = getLSMultipleTransferSize(MI); 00553 int Opcode = MI->getOpcode(); 00554 DebugLoc dl = MI->getDebugLoc(); 00555 bool isAM5 = Opcode == ARM::FLDD || Opcode == ARM::FLDS || 00556 Opcode == ARM::FSTD || Opcode == ARM::FSTS; 00557 bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR; 00558 if (isAM2 && ARM_AM::getAM2Offset(MI->getOperand(3).getImm()) != 0) 00559 return false; 00560 else if (isAM5 && ARM_AM::getAM5Offset(MI->getOperand(2).getImm()) != 0) 00561 return false; 00562 else if (isT2i32Load(Opcode) || isT2i32Store(Opcode)) 00563 if (MI->getOperand(2).getImm() != 0) 00564 return false; 00565 00566 bool isLd = isi32Load(Opcode) || Opcode == ARM::FLDS || Opcode == ARM::FLDD; 00567 // Can't do the merge if the destination register is the same as the would-be 00568 // writeback register. 00569 if (isLd && MI->getOperand(0).getReg() == Base) 00570 return false; 00571 00572 unsigned PredReg = 0; 00573 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 00574 bool DoMerge = false; 00575 ARM_AM::AddrOpc AddSub = ARM_AM::add; 00576 unsigned NewOpc = 0; 00577 // AM2 - 12 bits, thumb2 - 8 bits. 00578 unsigned Limit = isAM5 ? 0 : (isAM2 ? 0x1000 : 0x100); 00579 if (MBBI != MBB.begin()) { 00580 MachineBasicBlock::iterator PrevMBBI = prior(MBBI); 00581 if (isMatchingDecrement(PrevMBBI, Base, Bytes, Limit, Pred, PredReg)) { 00582 DoMerge = true; 00583 AddSub = ARM_AM::sub; 00584 NewOpc = getPreIndexedLoadStoreOpcode(Opcode); 00585 } else if (!isAM5 && 00586 isMatchingIncrement(PrevMBBI, Base, Bytes, Limit,Pred,PredReg)) { 00587 DoMerge = true; 00588 NewOpc = getPreIndexedLoadStoreOpcode(Opcode); 00589 } 00590 if (DoMerge) 00591 MBB.erase(PrevMBBI); 00592 } 00593 00594 if (!DoMerge && MBBI != MBB.end()) { 00595 MachineBasicBlock::iterator NextMBBI = next(MBBI); 00596 if (!isAM5 && 00597 isMatchingDecrement(NextMBBI, Base, Bytes, Limit, Pred, PredReg)) { 00598 DoMerge = true; 00599 AddSub = ARM_AM::sub; 00600 NewOpc = getPostIndexedLoadStoreOpcode(Opcode); 00601 } else if (isMatchingIncrement(NextMBBI, Base, Bytes, Limit,Pred,PredReg)) { 00602 DoMerge = true; 00603 NewOpc = getPostIndexedLoadStoreOpcode(Opcode); 00604 } 00605 if (DoMerge) { 00606 if (NextMBBI == I) { 00607 Advance = true; 00608 ++I; 00609 } 00610 MBB.erase(NextMBBI); 00611 } 00612 } 00613 00614 if (!DoMerge) 00615 return false; 00616 00617 bool isDPR = NewOpc == ARM::FLDMD || NewOpc == ARM::FSTMD; 00618 unsigned Offset = 0; 00619 if (isAM5) 00620 Offset = ARM_AM::getAM5Opc((AddSub == ARM_AM::sub) 00621 ? ARM_AM::db 00622 : ARM_AM::ia, true, (isDPR ? 2 : 1)); 00623 else if (isAM2) 00624 Offset = ARM_AM::getAM2Opc(AddSub, Bytes, ARM_AM::no_shift); 00625 else 00626 Offset = AddSub == ARM_AM::sub ? -Bytes : Bytes; 00627 if (isLd) { 00628 if (isAM5) 00629 // FLDMS, FLDMD 00630 BuildMI(MBB, MBBI, dl, TII->get(NewOpc)) 00631 .addReg(Base, getKillRegState(BaseKill)) 00632 .addImm(Offset).addImm(Pred).addReg(PredReg) 00633 .addReg(MI->getOperand(0).getReg(), RegState::Define); 00634 else if (isAM2) 00635 // LDR_PRE, LDR_POST, 00636 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg()) 00637 .addReg(Base, RegState::Define) 00638 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg); 00639 else 00640 // t2LDR_PRE, t2LDR_POST 00641 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), MI->getOperand(0).getReg()) 00642 .addReg(Base, RegState::Define) 00643 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg); 00644 } else { 00645 MachineOperand &MO = MI->getOperand(0); 00646 if (isAM5) 00647 // FSTMS, FSTMD 00648 BuildMI(MBB, MBBI, dl, TII->get(NewOpc)).addReg(Base).addImm(Offset) 00649 .addImm(Pred).addReg(PredReg) 00650 .addReg(MO.getReg(), getKillRegState(MO.isKill())); 00651 else if (isAM2) 00652 // STR_PRE, STR_POST 00653 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base) 00654 .addReg(MO.getReg(), getKillRegState(MO.isKill())) 00655 .addReg(Base).addReg(0).addImm(Offset).addImm(Pred).addReg(PredReg); 00656 else 00657 // t2STR_PRE, t2STR_POST 00658 BuildMI(MBB, MBBI, dl, TII->get(NewOpc), Base) 00659 .addReg(MO.getReg(), getKillRegState(MO.isKill())) 00660 .addReg(Base).addImm(Offset).addImm(Pred).addReg(PredReg); 00661 } 00662 MBB.erase(MBBI); 00663 00664 return true; 00665 } 00666 00667 /// isMemoryOp - Returns true if instruction is a memory operations (that this 00668 /// pass is capable of operating on). 00669 static bool isMemoryOp(const MachineInstr *MI) { 00670 int Opcode = MI->getOpcode(); 00671 switch (Opcode) { 00672 default: break; 00673 case ARM::LDR: 00674 case ARM::STR: 00675 return MI->getOperand(1).isReg() && MI->getOperand(2).getReg() == 0; 00676 case ARM::FLDS: 00677 case ARM::FSTS: 00678 return MI->getOperand(1).isReg(); 00679 case ARM::FLDD: 00680 case ARM::FSTD: 00681 return MI->getOperand(1).isReg(); 00682 case ARM::t2LDRi8: 00683 case ARM::t2LDRi12: 00684 case ARM::t2STRi8: 00685 case ARM::t2STRi12: 00686 return true; 00687 } 00688 return false; 00689 } 00690 00691 /// AdvanceRS - Advance register scavenger to just before the earliest memory 00692 /// op that is being merged. 00693 void ARMLoadStoreOpt::AdvanceRS(MachineBasicBlock &MBB, MemOpQueue &MemOps) { 00694 MachineBasicBlock::iterator Loc = MemOps[0].MBBI; 00695 unsigned Position = MemOps[0].Position; 00696 for (unsigned i = 1, e = MemOps.size(); i != e; ++i) { 00697 if (MemOps[i].Position < Position) { 00698 Position = MemOps[i].Position; 00699 Loc = MemOps[i].MBBI; 00700 } 00701 } 00702 00703 if (Loc != MBB.begin()) 00704 RS->forward(prior(Loc)); 00705 } 00706 00707 static int getMemoryOpOffset(const MachineInstr *MI) { 00708 int Opcode = MI->getOpcode(); 00709 bool isAM2 = Opcode == ARM::LDR || Opcode == ARM::STR; 00710 bool isAM3 = Opcode == ARM::LDRD || Opcode == ARM::STRD; 00711 unsigned NumOperands = MI->getDesc().getNumOperands(); 00712 unsigned OffField = MI->getOperand(NumOperands-3).getImm(); 00713 00714 if (Opcode == ARM::t2LDRi12 || Opcode == ARM::t2LDRi8 || 00715 Opcode == ARM::t2STRi12 || Opcode == ARM::t2STRi8 || 00716 Opcode == ARM::t2LDRDi8 || Opcode == ARM::t2STRDi8) 00717 return OffField; 00718 00719 int Offset = isAM2 00720 ? ARM_AM::getAM2Offset(OffField) 00721 : (isAM3 ? ARM_AM::getAM3Offset(OffField) 00722 : ARM_AM::getAM5Offset(OffField) * 4); 00723 if (isAM2) { 00724 if (ARM_AM::getAM2Op(OffField) == ARM_AM::sub) 00725 Offset = -Offset; 00726 } else if (isAM3) { 00727 if (ARM_AM::getAM3Op(OffField) == ARM_AM::sub) 00728 Offset = -Offset; 00729 } else { 00730 if (ARM_AM::getAM5Op(OffField) == ARM_AM::sub) 00731 Offset = -Offset; 00732 } 00733 return Offset; 00734 } 00735 00736 static void InsertLDR_STR(MachineBasicBlock &MBB, 00737 MachineBasicBlock::iterator &MBBI, 00738 int OffImm, bool isDef, 00739 DebugLoc dl, unsigned NewOpc, 00740 unsigned Reg, bool RegDeadKill, 00741 unsigned BaseReg, bool BaseKill, 00742 unsigned OffReg, bool OffKill, 00743 ARMCC::CondCodes Pred, unsigned PredReg, 00744 const TargetInstrInfo *TII) { 00745 unsigned Offset; 00746 if (OffImm < 0) 00747 Offset = ARM_AM::getAM2Opc(ARM_AM::sub, -OffImm, ARM_AM::no_shift); 00748 else 00749 Offset = ARM_AM::getAM2Opc(ARM_AM::add, OffImm, ARM_AM::no_shift); 00750 if (isDef) 00751 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 00752 .addReg(Reg, getDefRegState(true) | getDeadRegState(RegDeadKill)) 00753 .addReg(BaseReg, getKillRegState(BaseKill)) 00754 .addReg(OffReg, getKillRegState(OffKill)) 00755 .addImm(Offset) 00756 .addImm(Pred).addReg(PredReg); 00757 else 00758 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 00759 .addReg(Reg, getKillRegState(RegDeadKill)) 00760 .addReg(BaseReg, getKillRegState(BaseKill)) 00761 .addReg(OffReg, getKillRegState(OffKill)) 00762 .addImm(Offset) 00763 .addImm(Pred).addReg(PredReg); 00764 } 00765 00766 bool ARMLoadStoreOpt::FixInvalidRegPairOp(MachineBasicBlock &MBB, 00767 MachineBasicBlock::iterator &MBBI) { 00768 MachineInstr *MI = &*MBBI; 00769 unsigned Opcode = MI->getOpcode(); 00770 if (Opcode == ARM::LDRD || Opcode == ARM::STRD) { 00771 unsigned EvenReg = MI->getOperand(0).getReg(); 00772 unsigned OddReg = MI->getOperand(1).getReg(); 00773 unsigned EvenRegNum = TRI->getDwarfRegNum(EvenReg, false); 00774 unsigned OddRegNum = TRI->getDwarfRegNum(OddReg, false); 00775 if ((EvenRegNum & 1) == 0 && (EvenRegNum + 1) == OddRegNum) 00776 return false; 00777 00778 bool isLd = Opcode == ARM::LDRD; 00779 bool EvenDeadKill = isLd ? 00780 MI->getOperand(0).isDead() : MI->getOperand(0).isKill(); 00781 bool OddDeadKill = isLd ? 00782 MI->getOperand(1).isDead() : MI->getOperand(1).isKill(); 00783 const MachineOperand &BaseOp = MI->getOperand(2); 00784 unsigned BaseReg = BaseOp.getReg(); 00785 bool BaseKill = BaseOp.isKill(); 00786 const MachineOperand &OffOp = MI->getOperand(3); 00787 unsigned OffReg = OffOp.getReg(); 00788 bool OffKill = OffOp.isKill(); 00789 int OffImm = getMemoryOpOffset(MI); 00790 unsigned PredReg = 0; 00791 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MI, PredReg); 00792 00793 if (OddRegNum > EvenRegNum && OffReg == 0 && OffImm == 0) { 00794 // Ascending register numbers and no offset. It's safe to change it to a 00795 // ldm or stm. 00796 unsigned NewOpc = (Opcode == ARM::LDRD) ? ARM::LDM : ARM::STM; 00797 if (isLd) { 00798 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 00799 .addReg(BaseReg, getKillRegState(BaseKill)) 00800 .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia)) 00801 .addImm(Pred).addReg(PredReg) 00802 .addReg(EvenReg, getDefRegState(isLd) | getDeadRegState(EvenDeadKill)) 00803 .addReg(OddReg, getDefRegState(isLd) | getDeadRegState(OddDeadKill)); 00804 ++NumLDRD2LDM; 00805 } else { 00806 BuildMI(MBB, MBBI, MBBI->getDebugLoc(), TII->get(NewOpc)) 00807 .addReg(BaseReg, getKillRegState(BaseKill)) 00808 .addImm(ARM_AM::getAM4ModeImm(ARM_AM::ia)) 00809 .addImm(Pred).addReg(PredReg) 00810 .addReg(EvenReg, getKillRegState(EvenDeadKill)) 00811 .addReg(OddReg, getKillRegState(OddDeadKill)); 00812 ++NumSTRD2STM; 00813 } 00814 } else { 00815 // Split into two instructions. 00816 unsigned NewOpc = (Opcode == ARM::LDRD) ? ARM::LDR : ARM::STR; 00817 DebugLoc dl = MBBI->getDebugLoc(); 00818 // If this is a load and base register is killed, it may have been 00819 // re-defed by the load, make sure the first load does not clobber it. 00820 if (isLd && 00821 (BaseKill || OffKill) && 00822 (TRI->regsOverlap(EvenReg, BaseReg) || 00823 (OffReg && TRI->regsOverlap(EvenReg, OffReg)))) { 00824 assert(!TRI->regsOverlap(OddReg, BaseReg) && 00825 (!OffReg || !TRI->regsOverlap(OddReg, OffReg))); 00826 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc, OddReg, OddDeadKill, 00827 BaseReg, false, OffReg, false, Pred, PredReg, TII); 00828 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc, EvenReg, EvenDeadKill, 00829 BaseReg, BaseKill, OffReg, OffKill, Pred, PredReg, TII); 00830 } else { 00831 InsertLDR_STR(MBB, MBBI, OffImm, isLd, dl, NewOpc, 00832 EvenReg, EvenDeadKill, BaseReg, false, OffReg, false, 00833 Pred, PredReg, TII); 00834 InsertLDR_STR(MBB, MBBI, OffImm+4, isLd, dl, NewOpc, 00835 OddReg, OddDeadKill, BaseReg, BaseKill, OffReg, OffKill, 00836 Pred, PredReg, TII); 00837 } 00838 if (isLd) 00839 ++NumLDRD2LDR; 00840 else 00841 ++NumSTRD2STR; 00842 } 00843 00844 MBBI = prior(MBBI); 00845 MBB.erase(MI); 00846 } 00847 return false; 00848 } 00849 00850 /// LoadStoreMultipleOpti - An optimization pass to turn multiple LDR / STR 00851 /// ops of the same base and incrementing offset into LDM / STM ops. 00852 bool ARMLoadStoreOpt::LoadStoreMultipleOpti(MachineBasicBlock &MBB) { 00853 unsigned NumMerges = 0; 00854 unsigned NumMemOps = 0; 00855 MemOpQueue MemOps; 00856 unsigned CurrBase = 0; 00857 int CurrOpc = -1; 00858 unsigned CurrSize = 0; 00859 ARMCC::CondCodes CurrPred = ARMCC::AL; 00860 unsigned CurrPredReg = 0; 00861 unsigned Position = 0; 00862 SmallVector<MachineBasicBlock::iterator,4> Merges; 00863 00864 RS->enterBasicBlock(&MBB); 00865 MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end(); 00866 while (MBBI != E) { 00867 if (FixInvalidRegPairOp(MBB, MBBI)) 00868 continue; 00869 00870 bool Advance = false; 00871 bool TryMerge = false; 00872 bool Clobber = false; 00873 00874 bool isMemOp = isMemoryOp(MBBI); 00875 if (isMemOp) { 00876 int Opcode = MBBI->getOpcode(); 00877 unsigned Size = getLSMultipleTransferSize(MBBI); 00878 unsigned Base = MBBI->getOperand(1).getReg(); 00879 unsigned PredReg = 0; 00880 ARMCC::CondCodes Pred = llvm::getInstrPredicate(MBBI, PredReg); 00881 int Offset = getMemoryOpOffset(MBBI); 00882 // Watch out for: 00883 // r4 := ldr [r5] 00884 // r5 := ldr [r5, #4] 00885 // r6 := ldr [r5, #8] 00886 // 00887 // The second ldr has effectively broken the chain even though it 00888 // looks like the later ldr(s) use the same base register. Try to 00889 // merge the ldr's so far, including this one. But don't try to 00890 // combine the following ldr(s). 00891 Clobber = (isi32Load(Opcode) && Base == MBBI->getOperand(0).getReg()); 00892 if (CurrBase == 0 && !Clobber) { 00893 // Start of a new chain. 00894 CurrBase = Base; 00895 CurrOpc = Opcode; 00896 CurrSize = Size; 00897 CurrPred = Pred; 00898 CurrPredReg = PredReg; 00899 MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI)); 00900 NumMemOps++; 00901 Advance = true; 00902 } else { 00903 if (Clobber) { 00904 TryMerge = true; 00905 Advance = true; 00906 } 00907 00908 if (CurrOpc == Opcode && CurrBase == Base && CurrPred == Pred) { 00909 // No need to match PredReg. 00910 // Continue adding to the queue. 00911 if (Offset > MemOps.back().Offset) { 00912 MemOps.push_back(MemOpQueueEntry(Offset, Position, MBBI)); 00913 NumMemOps++; 00914 Advance = true; 00915 } else { 00916 for (MemOpQueueIter I = MemOps.begin(), E = MemOps.end(); 00917 I != E; ++I) { 00918 if (Offset < I->Offset) { 00919 MemOps.insert(I, MemOpQueueEntry(Offset, Position, MBBI)); 00920 NumMemOps++; 00921 Advance = true; 00922 break; 00923 } else if (Offset == I->Offset) { 00924 // Collision! This can't be merged! 00925 break; 00926 } 00927 } 00928 } 00929 } 00930 } 00931 } 00932 00933 if (Advance) { 00934 ++Position; 00935 ++MBBI; 00936 } else 00937 TryMerge = true; 00938 00939 if (TryMerge) { 00940 if (NumMemOps > 1) { 00941 // Try to find a free register to use as a new base in case it's needed. 00942 // First advance to the instruction just before the start of the chain. 00943 AdvanceRS(MBB, MemOps); 00944 // Find a scratch register. 00945 unsigned Scratch = RS->FindUnusedReg(&ARM::GPRRegClass); 00946 // Process the load / store instructions. 00947 RS->forward(prior(MBBI)); 00948 00949 // Merge ops. 00950 Merges.clear(); 00951 MergeLDR_STR(MBB, 0, CurrBase, CurrOpc, CurrSize, 00952 CurrPred, CurrPredReg, Scratch, MemOps, Merges); 00953 00954 // Try folding preceeding/trailing base inc/dec into the generated 00955 // LDM/STM ops. 00956 for (unsigned i = 0, e = Merges.size(); i < e; ++i) 00957 if (MergeBaseUpdateLSMultiple(MBB, Merges[i], Advance, MBBI)) 00958 ++NumMerges; 00959 NumMerges += Merges.size(); 00960 00961 // Try folding preceeding/trailing base inc/dec into those load/store 00962 // that were not merged to form LDM/STM ops. 00963 for (unsigned i = 0; i != NumMemOps; ++i) 00964 if (!MemOps[i].Merged) 00965 if (MergeBaseUpdateLoadStore(MBB, MemOps[i].MBBI, TII,Advance,MBBI)) 00966 ++NumMerges; 00967 00968 // RS may be pointing to an instruction that's deleted. 00969 RS->skipTo(prior(MBBI)); 00970 } else if (NumMemOps == 1) { 00971 // Try folding preceeding/trailing base inc/dec into the single 00972 // load/store. 00973 if (MergeBaseUpdateLoadStore(MBB, MemOps[0].MBBI, TII, Advance, MBBI)) { 00974 ++NumMerges; 00975 RS->forward(prior(MBBI)); 00976 } 00977 } 00978 00979 CurrBase = 0; 00980 CurrOpc = -1; 00981 CurrSize = 0; 00982 CurrPred = ARMCC::AL; 00983 CurrPredReg = 0; 00984 if (NumMemOps) { 00985 MemOps.clear(); 00986 NumMemOps = 0; 00987 } 00988 00989 // If iterator hasn't been advanced and this is not a memory op, skip it. 00990 // It can't start a new chain anyway. 00991 if (!Advance && !isMemOp && MBBI != E) { 00992 ++Position; 00993 ++MBBI; 00994 } 00995 } 00996 } 00997 return NumMerges > 0; 00998 } 00999 01000 namespace { 01001 struct OffsetCompare { 01002 bool operator()(const MachineInstr *LHS, const MachineInstr *RHS) const { 01003 int LOffset = getMemoryOpOffset(LHS); 01004 int ROffset = getMemoryOpOffset(RHS); 01005 assert(LHS == RHS || LOffset != ROffset); 01006 return LOffset > ROffset; 01007 } 01008 }; 01009 } 01010 01011 /// MergeReturnIntoLDM - If this is a exit BB, try merging the return op 01012 /// (bx lr) into the preceeding stack restore so it directly restore the value 01013 /// of LR into pc. 01014 /// ldmfd sp!, {r7, lr} 01015 /// bx lr 01016 /// => 01017 /// ldmfd sp!, {r7, pc} 01018 bool ARMLoadStoreOpt::MergeReturnIntoLDM(MachineBasicBlock &MBB) { 01019 if (MBB.empty()) return false; 01020 01021 MachineBasicBlock::iterator MBBI = prior(MBB.end()); 01022 if (MBBI != MBB.begin() && 01023 (MBBI->getOpcode() == ARM::BX_RET || MBBI->getOpcode() == ARM::tBX_RET)) { 01024 MachineInstr *PrevMI = prior(MBBI); 01025 if (PrevMI->getOpcode() == ARM::LDM || PrevMI->getOpcode() == ARM::t2LDM) { 01026 MachineOperand &MO = PrevMI->getOperand(PrevMI->getNumOperands()-1); 01027 if (MO.getReg() != ARM::LR) 01028 return false; 01029 unsigned NewOpc = isThumb2 ? ARM::t2LDM_RET : ARM::LDM_RET; 01030 PrevMI->setDesc(TII->get(NewOpc)); 01031 MO.setReg(ARM::PC); 01032 MBB.erase(MBBI); 01033 return true; 01034 } 01035 } 01036 return false; 01037 } 01038 01039 bool ARMLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { 01040 const TargetMachine &TM = Fn.getTarget(); 01041 AFI = Fn.getInfo<ARMFunctionInfo>(); 01042 TII = TM.getInstrInfo(); 01043 TRI = TM.getRegisterInfo(); 01044 RS = new RegScavenger(); 01045 isThumb2 = AFI->isThumb2Function(); 01046 01047 bool Modified = false; 01048 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 01049 ++MFI) { 01050 MachineBasicBlock &MBB = *MFI; 01051 Modified |= LoadStoreMultipleOpti(MBB); 01052 Modified |= MergeReturnIntoLDM(MBB); 01053 } 01054 01055 delete RS; 01056 return Modified; 01057 } 01058 01059 01060 /// ARMPreAllocLoadStoreOpt - Pre- register allocation pass that move 01061 /// load / stores from consecutive locations close to make it more 01062 /// likely they will be combined later. 01063 01064 namespace { 01065 struct VISIBILITY_HIDDEN ARMPreAllocLoadStoreOpt : public MachineFunctionPass{ 01066 static char ID; 01067 ARMPreAllocLoadStoreOpt() : MachineFunctionPass(&ID) {} 01068 01069 const TargetData *TD; 01070 const TargetInstrInfo *TII; 01071 const TargetRegisterInfo *TRI; 01072 const ARMSubtarget *STI; 01073 MachineRegisterInfo *MRI; 01074 01075 virtual bool runOnMachineFunction(MachineFunction &Fn); 01076 01077 virtual const char *getPassName() const { 01078 return "ARM pre- register allocation load / store optimization pass"; 01079 } 01080 01081 private: 01082 bool CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, DebugLoc &dl, 01083 unsigned &NewOpc, unsigned &EvenReg, 01084 unsigned &OddReg, unsigned &BaseReg, 01085 unsigned &OffReg, unsigned &Offset, 01086 unsigned &PredReg, ARMCC::CondCodes &Pred); 01087 bool RescheduleOps(MachineBasicBlock *MBB, 01088 SmallVector<MachineInstr*, 4> &Ops, 01089 unsigned Base, bool isLd, 01090 DenseMap<MachineInstr*, unsigned> &MI2LocMap); 01091 bool RescheduleLoadStoreInstrs(MachineBasicBlock *MBB); 01092 }; 01093 char ARMPreAllocLoadStoreOpt::ID = 0; 01094 } 01095 01096 bool ARMPreAllocLoadStoreOpt::runOnMachineFunction(MachineFunction &Fn) { 01097 TD = Fn.getTarget().getTargetData(); 01098 TII = Fn.getTarget().getInstrInfo(); 01099 TRI = Fn.getTarget().getRegisterInfo(); 01100 STI = &Fn.getTarget().getSubtarget<ARMSubtarget>(); 01101 MRI = &Fn.getRegInfo(); 01102 01103 bool Modified = false; 01104 for (MachineFunction::iterator MFI = Fn.begin(), E = Fn.end(); MFI != E; 01105 ++MFI) 01106 Modified |= RescheduleLoadStoreInstrs(MFI); 01107 01108 return Modified; 01109 } 01110 01111 static bool IsSafeAndProfitableToMove(bool isLd, unsigned Base, 01112 MachineBasicBlock::iterator I, 01113 MachineBasicBlock::iterator E, 01114 SmallPtrSet<MachineInstr*, 4> &MemOps, 01115 SmallSet<unsigned, 4> &MemRegs, 01116 const TargetRegisterInfo *TRI) { 01117 // Are there stores / loads / calls between them? 01118 // FIXME: This is overly conservative. We should make use of alias information 01119 // some day. 01120 SmallSet<unsigned, 4> AddedRegPressure; 01121 while (++I != E) { 01122 if (MemOps.count(&*I)) 01123 continue; 01124 const TargetInstrDesc &TID = I->getDesc(); 01125 if (TID.isCall() || TID.isTerminator() || TID.hasUnmodeledSideEffects()) 01126 return false; 01127 if (isLd && TID.mayStore()) 01128 return false; 01129 if (!isLd) { 01130 if (TID.mayLoad()) 01131 return false; 01132 // It's not safe to move the first 'str' down. 01133 // str r1, [r0] 01134 // strh r5, [r0] 01135 // str r4, [r0, #+4] 01136 if (TID.mayStore()) 01137 return false; 01138 } 01139 for (unsigned j = 0, NumOps = I->getNumOperands(); j != NumOps; ++j) { 01140 MachineOperand &MO = I->getOperand(j); 01141 if (!MO.isReg()) 01142 continue; 01143 unsigned Reg = MO.getReg(); 01144 if (MO.isDef() && TRI->regsOverlap(Reg, Base)) 01145 return false; 01146 if (Reg != Base && !MemRegs.count(Reg)) 01147 AddedRegPressure.insert(Reg); 01148 } 01149 } 01150 01151 // Estimate register pressure increase due to the transformation. 01152 if (MemRegs.size() <= 4) 01153 // Ok if we are moving small number of instructions. 01154 return true; 01155 return AddedRegPressure.size() <= MemRegs.size() * 2; 01156 } 01157 01158 bool 01159 ARMPreAllocLoadStoreOpt::CanFormLdStDWord(MachineInstr *Op0, MachineInstr *Op1, 01160 DebugLoc &dl, 01161 unsigned &NewOpc, unsigned &EvenReg, 01162 unsigned &OddReg, unsigned &BaseReg, 01163 unsigned &OffReg, unsigned &Offset, 01164 unsigned &PredReg, 01165 ARMCC::CondCodes &Pred) { 01166 // FIXME: FLDS / FSTS -> FLDD / FSTD 01167 unsigned Opcode = Op0->getOpcode(); 01168 if (Opcode == ARM::LDR) 01169 NewOpc = ARM::LDRD; 01170 else if (Opcode == ARM::STR) 01171 NewOpc = ARM::STRD; 01172 else 01173 return 0; 01174 01175 // Must sure the base address satisfies i64 ld / st alignment requirement. 01176 if (!Op0->hasOneMemOperand() || 01177 !Op0->memoperands_begin()->getValue() || 01178 Op0->memoperands_begin()->isVolatile()) 01179 return false; 01180 01181 unsigned Align = Op0->memoperands_begin()->getAlignment(); 01182 unsigned ReqAlign = STI->hasV6Ops() 01183 ? TD->getPrefTypeAlignment( 01184 Type::getInt64Ty(Op0->getParent()->getParent()->getFunction()->getContext())) 01185 : 8; // Pre-v6 need 8-byte align 01186 if (Align < ReqAlign) 01187 return false; 01188 01189 // Then make sure the immediate offset fits. 01190 int OffImm = getMemoryOpOffset(Op0); 01191 ARM_AM::AddrOpc AddSub = ARM_AM::add; 01192 if (OffImm < 0) { 01193 AddSub = ARM_AM::sub; 01194 OffImm = - OffImm; 01195 } 01196 if (OffImm >= 256) // 8 bits 01197 return false; 01198 Offset = ARM_AM::getAM3Opc(AddSub, OffImm); 01199 01200 EvenReg = Op0->getOperand(0).getReg(); 01201 OddReg = Op1->getOperand(0).getReg(); 01202 if (EvenReg == OddReg) 01203 return false; 01204 BaseReg = Op0->getOperand(1).getReg(); 01205 OffReg = Op0->getOperand(2).getReg(); 01206 Pred = llvm::getInstrPredicate(Op0, PredReg); 01207 dl = Op0->getDebugLoc(); 01208 return true; 01209 } 01210 01211 bool ARMPreAllocLoadStoreOpt::RescheduleOps(MachineBasicBlock *MBB, 01212 SmallVector<MachineInstr*, 4> &Ops, 01213 unsigned Base, bool isLd, 01214 DenseMap<MachineInstr*, unsigned> &MI2LocMap) { 01215 bool RetVal = false; 01216 01217 // Sort by offset (in reverse order). 01218 std::sort(Ops.begin(), Ops.end(), OffsetCompare()); 01219 01220 // The loads / stores of the same base are in order. Scan them from first to 01221 // last and check for the followins: 01222 // 1. Any def of base. 01223 // 2. Any gaps. 01224 while (Ops.size() > 1) { 01225 unsigned FirstLoc = ~0U; 01226 unsigned LastLoc = 0; 01227 MachineInstr *FirstOp = 0; 01228 MachineInstr *LastOp = 0; 01229 int LastOffset = 0; 01230 unsigned LastOpcode = 0; 01231 unsigned LastBytes = 0; 01232 unsigned NumMove = 0; 01233 for (int i = Ops.size() - 1; i >= 0; --i) { 01234 MachineInstr *Op = Ops[i]; 01235 unsigned Loc = MI2LocMap[Op]; 01236 if (Loc <= FirstLoc) { 01237 FirstLoc = Loc; 01238 FirstOp = Op; 01239 } 01240 if (Loc >= LastLoc) { 01241 LastLoc = Loc; 01242 LastOp = Op; 01243 } 01244 01245 unsigned Opcode = Op->getOpcode(); 01246 if (LastOpcode && Opcode != LastOpcode) 01247 break; 01248 01249 int Offset = getMemoryOpOffset(Op); 01250 unsigned Bytes = getLSMultipleTransferSize(Op); 01251 if (LastBytes) { 01252 if (Bytes != LastBytes || Offset != (LastOffset + (int)Bytes)) 01253 break; 01254 } 01255 LastOffset = Offset; 01256 LastBytes = Bytes; 01257 LastOpcode = Opcode; 01258 if (++NumMove == 8) // FIXME: Tune 01259 break; 01260 } 01261 01262 if (NumMove <= 1) 01263 Ops.pop_back(); 01264 else { 01265 SmallPtrSet<MachineInstr*, 4> MemOps; 01266 SmallSet<unsigned, 4> MemRegs; 01267 for (int i = NumMove-1; i >= 0; --i) { 01268 MemOps.insert(Ops[i]); 01269 MemRegs.insert(Ops[i]->getOperand(0).getReg()); 01270 } 01271 01272 // Be conservative, if the instructions are too far apart, don't 01273 // move them. We want to limit the increase of register pressure. 01274 bool DoMove = (LastLoc - FirstLoc) <= NumMove*4; // FIXME: Tune this. 01275 if (DoMove) 01276 DoMove = IsSafeAndProfitableToMove(isLd, Base, FirstOp, LastOp, 01277 MemOps, MemRegs, TRI); 01278 if (!DoMove) { 01279 for (unsigned i = 0; i != NumMove; ++i) 01280 Ops.pop_back(); 01281 } else { 01282 // This is the new location for the loads / stores. 01283 MachineBasicBlock::iterator InsertPos = isLd ? FirstOp : LastOp; 01284 while (InsertPos != MBB->end() && MemOps.count(InsertPos)) 01285 ++InsertPos; 01286 01287 // If we are moving a pair of loads / stores, see if it makes sense 01288 // to try to allocate a pair of registers that can form register pairs. 01289 MachineInstr *Op0 = Ops.back(); 01290 MachineInstr *Op1 = Ops[Ops.size()-2]; 01291 unsigned EvenReg = 0, OddReg = 0; 01292 unsigned BaseReg = 0, OffReg = 0, PredReg = 0; 01293 ARMCC::CondCodes Pred = ARMCC::AL; 01294 unsigned NewOpc = 0; 01295 unsigned Offset = 0; 01296 DebugLoc dl; 01297 if (NumMove == 2 && CanFormLdStDWord(Op0, Op1, dl, NewOpc, 01298 EvenReg, OddReg, BaseReg, OffReg, 01299 Offset, PredReg, Pred)) { 01300 Ops.pop_back(); 01301 Ops.pop_back(); 01302 01303 // Form the pair instruction. 01304 if (isLd) { 01305 BuildMI(*MBB, InsertPos, dl, TII->get(NewOpc)) 01306 .addReg(EvenReg, RegState::Define) 01307 .addReg(OddReg, RegState::Define) 01308 .addReg(BaseReg).addReg(0).addImm(Offset) 01309 .addImm(Pred).addReg(PredReg); 01310 ++NumLDRDFormed; 01311 } else { 01312 BuildMI(*MBB, InsertPos, dl, TII->get(NewOpc)) 01313 .addReg(EvenReg) 01314 .addReg(OddReg) 01315 .addReg(BaseReg).addReg(0).addImm(Offset) 01316 .addImm(Pred).addReg(PredReg); 01317 ++NumSTRDFormed; 01318 } 01319 MBB->erase(Op0); 01320 MBB->erase(Op1); 01321 01322 // Add register allocation hints to form register pairs. 01323 MRI->setRegAllocationHint(EvenReg, ARMRI::RegPairEven, OddReg); 01324 MRI->setRegAllocationHint(OddReg, ARMRI::RegPairOdd, EvenReg); 01325 } else { 01326 for (unsigned i = 0; i != NumMove; ++i) { 01327 MachineInstr *Op = Ops.back(); 01328 Ops.pop_back(); 01329 MBB->splice(InsertPos, MBB, Op); 01330 } 01331 } 01332 01333 NumLdStMoved += NumMove; 01334 RetVal = true; 01335 } 01336 } 01337 } 01338 01339 return RetVal; 01340 } 01341 01342 bool 01343 ARMPreAllocLoadStoreOpt::RescheduleLoadStoreInstrs(MachineBasicBlock *MBB) { 01344 bool RetVal = false; 01345 01346 DenseMap<MachineInstr*, unsigned> MI2LocMap; 01347 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2LdsMap; 01348 DenseMap<unsigned, SmallVector<MachineInstr*, 4> > Base2StsMap; 01349 SmallVector<unsigned, 4> LdBases; 01350 SmallVector<unsigned, 4> StBases; 01351 01352 unsigned Loc = 0; 01353 MachineBasicBlock::iterator MBBI = MBB->begin(); 01354 MachineBasicBlock::iterator E = MBB->end(); 01355 while (MBBI != E) { 01356 for (; MBBI != E; ++MBBI) { 01357 MachineInstr *MI = MBBI; 01358 const TargetInstrDesc &TID = MI->getDesc(); 01359 if (TID.isCall() || TID.isTerminator()) { 01360 // Stop at barriers. 01361 ++MBBI; 01362 break; 01363 } 01364 01365 MI2LocMap[MI] = Loc++; 01366 if (!isMemoryOp(MI)) 01367 continue; 01368 unsigned PredReg = 0; 01369 if (llvm::getInstrPredicate(MI, PredReg) != ARMCC::AL) 01370 continue; 01371 01372 int Opcode = MI->getOpcode(); 01373 bool isLd = Opcode == ARM::LDR || 01374 Opcode == ARM::FLDS || Opcode == ARM::FLDD; 01375 unsigned Base = MI->getOperand(1).getReg(); 01376 int Offset = getMemoryOpOffset(MI); 01377 01378 bool StopHere = false; 01379 if (isLd) { 01380 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI = 01381 Base2LdsMap.find(Base); 01382 if (BI != Base2LdsMap.end()) { 01383 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) { 01384 if (Offset == getMemoryOpOffset(BI->second[i])) { 01385 StopHere = true; 01386 break; 01387 } 01388 } 01389 if (!StopHere) 01390 BI->second.push_back(MI); 01391 } else { 01392 SmallVector<MachineInstr*, 4> MIs; 01393 MIs.push_back(MI); 01394 Base2LdsMap[Base] = MIs; 01395 LdBases.push_back(Base); 01396 } 01397 } else { 01398 DenseMap<unsigned, SmallVector<MachineInstr*, 4> >::iterator BI = 01399 Base2StsMap.find(Base); 01400 if (BI != Base2StsMap.end()) { 01401 for (unsigned i = 0, e = BI->second.size(); i != e; ++i) { 01402 if (Offset == getMemoryOpOffset(BI->second[i])) { 01403 StopHere = true; 01404 break; 01405 } 01406 } 01407 if (!StopHere) 01408 BI->second.push_back(MI); 01409 } else { 01410 SmallVector<MachineInstr*, 4> MIs; 01411 MIs.push_back(MI); 01412 Base2StsMap[Base] = MIs; 01413 StBases.push_back(Base); 01414 } 01415 } 01416 01417 if (StopHere) { 01418 // Found a duplicate (a base+offset combination that's seen earlier). 01419 // Backtrack. 01420 --Loc; 01421 break; 01422 } 01423 } 01424 01425 // Re-schedule loads. 01426 for (unsigned i = 0, e = LdBases.size(); i != e; ++i) { 01427 unsigned Base = LdBases[i]; 01428 SmallVector<MachineInstr*, 4> &Lds = Base2LdsMap[Base]; 01429 if (Lds.size() > 1) 01430 RetVal |= RescheduleOps(MBB, Lds, Base, true, MI2LocMap); 01431 } 01432 01433 // Re-schedule stores. 01434 for (unsigned i = 0, e = StBases.size(); i != e; ++i) { 01435 unsigned Base = StBases[i]; 01436 SmallVector<MachineInstr*, 4> &Sts = Base2StsMap[Base]; 01437 if (Sts.size() > 1) 01438 RetVal |= RescheduleOps(MBB, Sts, Base, false, MI2LocMap); 01439 } 01440 01441 if (MBBI != E) { 01442 Base2LdsMap.clear(); 01443 Base2StsMap.clear(); 01444 LdBases.clear(); 01445 StBases.clear(); 01446 } 01447 } 01448 01449 return RetVal; 01450 } 01451 01452 01453 /// createARMLoadStoreOptimizationPass - returns an instance of the load / store 01454 /// optimization pass. 01455 FunctionPass *llvm::createARMLoadStoreOptimizationPass(bool PreAlloc) { 01456 if (PreAlloc) 01457 return new ARMPreAllocLoadStoreOpt(); 01458 return new ARMLoadStoreOpt(); 01459 }