16cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling//===-- PeepholeOptimizer.cpp - Peephole Optimizations --------------------===// 27da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// 37da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// The LLVM Compiler Infrastructure 47da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// 57da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// This file is distributed under the University of Illinois Open Source 67da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// License. See LICENSE.TXT for details. 77da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng// 87da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng//===----------------------------------------------------------------------===// 9d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng// 106cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// Perform peephole optimizations on the machine code: 11d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng// 126cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// - Optimize Extensions 13d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng// 146cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// Optimization of sign / zero extension instructions. It may be extended to 156cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// handle other instructions with similar properties. 166cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// 176cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// On some targets, some instructions, e.g. X86 sign / zero extension, may 186cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// leave the source value in the lower part of the result. This optimization 196cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// will replace some uses of the pre-extension value with uses of the 206cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// sub-register of the results. 216cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// 226cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// - Optimize Comparisons 236cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// 246cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// Optimization of comparison instructions. For instance, in this code: 256cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// 266cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// sub r1, 1 276cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// cmp r1, 0 286cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// bz L1 296cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// 306cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// If the "sub" instruction all ready sets (or could be modified to set) the 316cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// same flag that the "cmp" instruction sets and that "bz" uses, then we can 326cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// eliminate the "cmp" instruction. 33247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// 34247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// Another instance, in this code: 35247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// 36247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// sub r1, r3 | sub r1, imm 37247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// cmp r3, r1 or cmp r1, r3 | cmp r1, imm 38247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// bge L1 39247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// 40247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// If the branch instruction can use flag from "sub", then we can replace 41247c5ab07c1c136f37f5ad8ade9a1ee086ca452eManman Ren// "sub" with "subs" and eliminate the "cmp" instruction. 42d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// 43d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// - Optimize Bitcast pairs: 44d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// 45d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// v1 = bitcast v0 46d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// v2 = bitcast v1 47d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// = v2 48d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// => 49d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// v1 = bitcast v0 50d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng// = v0 511df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick// 528293b7b8b1c4372095f86097da33f6cc63330289Joel Jones// - Optimize Loads: 538293b7b8b1c4372095f86097da33f6cc63330289Joel Jones// 548293b7b8b1c4372095f86097da33f6cc63330289Joel Jones// Loads that can be folded into a later instruction. A load is foldable 558293b7b8b1c4372095f86097da33f6cc63330289Joel Jones// if it loads to virtual registers and the virtual register defined has 568293b7b8b1c4372095f86097da33f6cc63330289Joel Jones// a single use. 57d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng//===----------------------------------------------------------------------===// 587da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 596cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling#define DEBUG_TYPE "peephole-opt" 607da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/CodeGen/Passes.h" 61d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/DenseMap.h" 62d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 63d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 64d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 657da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/CodeGen/MachineDominators.h" 667da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/CodeGen/MachineInstrBuilder.h" 677da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/CodeGen/MachineRegisterInfo.h" 68d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/CommandLine.h" 69a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper#include "llvm/Support/Debug.h" 707da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/Target/TargetInstrInfo.h" 717da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng#include "llvm/Target/TargetRegisterInfo.h" 727da9ecf9677b751d81515f95168ae3cb2df54160Evan Chengusing namespace llvm; 737da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 746cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling// Optimize Extensions 756cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendlingstatic cl::opt<bool> 766cdb1abe4e4f6364649e7ef656589441754e82aeBill WendlingAggressive("aggressive-ext-opt", cl::Hidden, 776cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling cl::desc("Aggressive extension optimization")); 787da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 7940a5eb18b031fa1a5e9697e21e251e613d441cc5Bill Wendlingstatic cl::opt<bool> 8040a5eb18b031fa1a5e9697e21e251e613d441cc5Bill WendlingDisablePeephole("disable-peephole", cl::Hidden, cl::init(false), 8140a5eb18b031fa1a5e9697e21e251e613d441cc5Bill Wendling cl::desc("Disable the peephole optimizer")); 8240a5eb18b031fa1a5e9697e21e251e613d441cc5Bill Wendling 8369c5eb59f592087af89b971bea072f070f2a5cfaBill WendlingSTATISTIC(NumReuse, "Number of extension results reused"); 84d158fba3e45547f013bbab4c0ac640f31b5e341fEvan ChengSTATISTIC(NumBitcasts, "Number of bitcasts eliminated"); 85d158fba3e45547f013bbab4c0ac640f31b5e341fEvan ChengSTATISTIC(NumCmps, "Number of compares eliminated"); 863b26eb62946a64409f81c8089a362eb582114342Lang HamesSTATISTIC(NumImmFold, "Number of move immediate folded"); 87d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman RenSTATISTIC(NumLoadFold, "Number of loads folded"); 88f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund OlesenSTATISTIC(NumSelects, "Number of selects optimized"); 896cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 907da9ecf9677b751d81515f95168ae3cb2df54160Evan Chengnamespace { 916cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling class PeepholeOptimizer : public MachineFunctionPass { 927da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng const TargetMachine *TM; 937da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng const TargetInstrInfo *TII; 946cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling MachineRegisterInfo *MRI; 956cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling MachineDominatorTree *DT; // Machine dominator tree 967da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 977da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng public: 987da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng static char ID; // Pass identification 99081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson PeepholeOptimizer() : MachineFunctionPass(ID) { 100081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializePeepholeOptimizerPass(*PassRegistry::getPassRegistry()); 101081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 1027da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 1037da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng virtual bool runOnMachineFunction(MachineFunction &MF); 1047da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 1057da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng virtual void getAnalysisUsage(AnalysisUsage &AU) const { 1067da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng AU.setPreservesCFG(); 1077da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng MachineFunctionPass::getAnalysisUsage(AU); 108d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng if (Aggressive) { 109d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng AU.addRequired<MachineDominatorTree>(); 110d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng AU.addPreserved<MachineDominatorTree>(); 111d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng } 1127da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng } 113d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng 114d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng private: 11539cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach bool optimizeBitcastInstr(MachineInstr *MI, MachineBasicBlock *MBB); 11639cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach bool optimizeCmpInstr(MachineInstr *MI, MachineBasicBlock *MBB); 11739cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach bool optimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 1186cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling SmallPtrSet<MachineInstr*, 8> &LocalMIs); 119f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen bool optimizeSelect(MachineInstr *MI); 120c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng bool isMoveImmediate(MachineInstr *MI, 121c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SmallSet<unsigned, 4> &ImmDefRegs, 122c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 12339cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach bool foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 124c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SmallSet<unsigned, 4> &ImmDefRegs, 125c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*> &ImmDefMIs); 126d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren bool isLoadFoldable(MachineInstr *MI, unsigned &FoldAsLoadDefReg); 1277da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng }; 1287da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng} 1297da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 1306cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendlingchar PeepholeOptimizer::ID = 0; 1311dd8c8560d45d36a8e507cd014352f1d313f9f9eAndrew Trickchar &llvm::PeepholeOptimizerID = PeepholeOptimizer::ID; 1322ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(PeepholeOptimizer, "peephole-opts", 1332ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Peephole Optimizations", false, false) 1342ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 1352ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(PeepholeOptimizer, "peephole-opts", 136ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Peephole Optimizations", false, false) 1376cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 13839cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach/// optimizeExtInstr - If instruction is a copy-like instruction, i.e. it reads 1396cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// a single register and writes a single register and it does not modify the 1406cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// source, and if the source value is preserved as a sub-register of the 1416cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// result, then replace all reachable uses of the source with the subreg of the 1426cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// result. 1431df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick/// 1446cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// Do not generate an EXTRACT that is used only in a debug use, as this changes 1456cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// the code. Since this code does not currently share EXTRACTs, just ignore all 1466cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// debug uses. 1476cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendlingbool PeepholeOptimizer:: 14839cc5138707eee563db7a487cd720b232b4b58fdJim GrosbachoptimizeExtInstr(MachineInstr *MI, MachineBasicBlock *MBB, 1496cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling SmallPtrSet<MachineInstr*, 8> &LocalMIs) { 150d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng unsigned SrcReg, DstReg, SubIdx; 15194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (!TII->isCoalescableExtInstr(*MI, SrcReg, DstReg, SubIdx)) 15294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling return false; 1531df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 15494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (TargetRegisterInfo::isPhysicalRegister(DstReg) || 15594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling TargetRegisterInfo::isPhysicalRegister(SrcReg)) 15694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling return false; 15794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling 158d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen if (MRI->hasOneNonDBGUse(SrcReg)) 15994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // No other uses. 16094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling return false; 16194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling 162418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen // Ensure DstReg can get a register class that actually supports 163418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen // sub-registers. Don't change the class until we commit. 164418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI->getRegClass(DstReg); 165418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen DstRC = TM->getRegisterInfo()->getSubClassWithSubReg(DstRC, SubIdx); 166418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen if (!DstRC) 167418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen return false; 168418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen 1697164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // The ext instr may be operating on a sub-register of SrcReg as well. 1707164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // PPC::EXTSW is a 32 -> 64-bit sign extension, but it reads a 64-bit 1717164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // register. 1727164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // If UseSrcSubIdx is Set, SubIdx also applies to SrcReg, and only uses of 1737164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // SrcReg:SubIdx should be replaced. 1747164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen bool UseSrcSubIdx = TM->getRegisterInfo()-> 1757164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen getSubClassWithSubReg(MRI->getRegClass(SrcReg), SubIdx) != 0; 1767164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen 1776cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // The source has other uses. See if we can replace the other uses with use of 1786cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // the result of the extension. 17994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling SmallPtrSet<MachineBasicBlock*, 4> ReachedBBs; 180d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 181d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end(); 18294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling UI != UE; ++UI) 18394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling ReachedBBs.insert(UI->getParent()); 18494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling 18594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Uses that are in the same BB of uses of the result of the instruction. 18694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling SmallVector<MachineOperand*, 8> Uses; 1876cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 18894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Uses that the result of the instruction can reach. 18994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling SmallVector<MachineOperand*, 8> ExtendedUses; 19094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling 1916cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling bool ExtendLife = true; 192d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen for (MachineRegisterInfo::use_nodbg_iterator 193d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen UI = MRI->use_nodbg_begin(SrcReg), UE = MRI->use_nodbg_end(); 19494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling UI != UE; ++UI) { 19594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling MachineOperand &UseMO = UI.getOperand(); 19694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling MachineInstr *UseMI = &*UI; 19794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (UseMI == MI) 19894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling continue; 1996cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 20094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (UseMI->isPHI()) { 20194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling ExtendLife = false; 20294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling continue; 20394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling } 204d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng 2057164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // Only accept uses of SrcReg:SubIdx. 2067164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen if (UseSrcSubIdx && UseMO.getSubReg() != SubIdx) 2077164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen continue; 2087164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen 20994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // It's an error to translate this: 21094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // 21194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // %reg1025 = <sext> %reg1024 21294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // ... 21394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // %reg1026 = SUBREG_TO_REG 0, %reg1024, 4 21494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // 21594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // into this: 21694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // 21794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // %reg1025 = <sext> %reg1024 21894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // ... 21994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // %reg1027 = COPY %reg1025:4 22094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // %reg1026 = SUBREG_TO_REG 0, %reg1027, 4 22194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // 22294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // The problem here is that SUBREG_TO_REG is there to assert that an 22394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // implicit zext occurs. It doesn't insert a zext instruction. If we allow 22494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // the COPY here, it will give us the value after the <sext>, not the 22594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // original value of %reg1024 before <sext>. 22694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (UseMI->getOpcode() == TargetOpcode::SUBREG_TO_REG) 22794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling continue; 22894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling 22994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling MachineBasicBlock *UseMBB = UseMI->getParent(); 23094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (UseMBB == MBB) { 23194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Local uses that come after the extension. 23294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (!LocalMIs.count(UseMI)) 23394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling Uses.push_back(&UseMO); 2346cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } else if (ReachedBBs.count(UseMBB)) { 2356cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // Non-local uses where the result of the extension is used. Always 2366cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // replace these unless it's a PHI. 23794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling Uses.push_back(&UseMO); 2386cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } else if (Aggressive && DT->dominates(MBB, UseMBB)) { 2396cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // We may want to extend the live range of the extension result in order 2406cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // to replace these uses. 24194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling ExtendedUses.push_back(&UseMO); 2426cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } else { 24394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Both will be live out of the def MBB anyway. Don't extend live range of 24494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // the extension result. 24594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling ExtendLife = false; 24694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling break; 24794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling } 24894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling } 249d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng 25094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (ExtendLife && !ExtendedUses.empty()) 2516cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // Extend the liveness of the extension result. 25294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling std::copy(ExtendedUses.begin(), ExtendedUses.end(), 25394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling std::back_inserter(Uses)); 254eb18812f755b634f3e7554c1912aeb2d7476cb53Evan Cheng 25594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Now replace all uses. 25694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling bool Changed = false; 25794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (!Uses.empty()) { 25894e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling SmallPtrSet<MachineBasicBlock*, 4> PHIBBs; 2596cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 26094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // Look for PHI uses of the extended result, we don't want to extend the 26194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // liveness of a PHI input. It breaks all kinds of assumptions down 26294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling // stream. A PHI use is expected to be the kill of its source values. 2636cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling for (MachineRegisterInfo::use_nodbg_iterator 264d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen UI = MRI->use_nodbg_begin(DstReg), UE = MRI->use_nodbg_end(); 265d8d0279c007e70c325b4ac9d9893b31ee5f21085Jakob Stoklund Olesen UI != UE; ++UI) 26694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (UI->isPHI()) 26794e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling PHIBBs.insert(UI->getParent()); 268d64ba3ee62cc854218d9b76b9420493d82313d06Bill Wendling 26994e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling const TargetRegisterClass *RC = MRI->getRegClass(SrcReg); 27094e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling for (unsigned i = 0, e = Uses.size(); i != e; ++i) { 27194e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling MachineOperand *UseMO = Uses[i]; 27294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling MachineInstr *UseMI = UseMO->getParent(); 273d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng MachineBasicBlock *UseMBB = UseMI->getParent(); 27494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling if (PHIBBs.count(UseMBB)) 27594e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling continue; 2766cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 277c69cbd0a7431b047dbc4a9758e81bf122926ba0aLang Hames // About to add uses of DstReg, clear DstReg's kill flags. 278418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen if (!Changed) { 279c69cbd0a7431b047dbc4a9758e81bf122926ba0aLang Hames MRI->clearKillFlags(DstReg); 280418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen MRI->constrainRegClass(DstReg, DstRC); 281418a3638acfa95e4212a38100adfc2f8cdd45919Jakob Stoklund Olesen } 282c69cbd0a7431b047dbc4a9758e81bf122926ba0aLang Hames 28394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling unsigned NewVR = MRI->createVirtualRegister(RC); 2847164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen MachineInstr *Copy = BuildMI(*UseMBB, UseMI, UseMI->getDebugLoc(), 2857164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen TII->get(TargetOpcode::COPY), NewVR) 28694e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling .addReg(DstReg, 0, SubIdx); 2877164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen // SubIdx applies to both SrcReg and DstReg when UseSrcSubIdx is set. 2887164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen if (UseSrcSubIdx) { 2897164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen Copy->getOperand(0).setSubReg(SubIdx); 2907164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen Copy->getOperand(0).setIsUndef(); 2917164288c3eb52e20454fc757440f867f04eb13a4Jakob Stoklund Olesen } 29294e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling UseMO->setReg(NewVR); 29394e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling ++NumReuse; 29494e4008fbaa85600777b55605098bfd9cc3b9294Bill Wendling Changed = true; 295d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng } 296d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng } 297d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng 298d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng return Changed; 299d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng} 300d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng 30139cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach/// optimizeBitcastInstr - If the instruction is a bitcast instruction A that 302d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// cannot be optimized away during isel (e.g. ARM::VMOVSR, which bitcast 303d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// a value cross register classes), and the source is defined by another 304d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// bitcast instruction B. And if the register class of source of B matches 305d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// the register class of instruction A, then it is legal to replace all uses 306d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// of the def of A with source of B. e.g. 307d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// %vreg0<def> = VMOVSR %vreg1 308d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// %vreg3<def> = VMOVRS %vreg0 309d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng/// Replace all uses of vreg3 with vreg1. 310d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 31139cc5138707eee563db7a487cd720b232b4b58fdJim Grosbachbool PeepholeOptimizer::optimizeBitcastInstr(MachineInstr *MI, 312d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MachineBasicBlock *MBB) { 313d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned NumDefs = MI->getDesc().getNumDefs(); 314d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned NumSrcs = MI->getDesc().getNumOperands() - NumDefs; 315d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (NumDefs != 1) 316d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return false; 317d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 318d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned Def = 0; 319d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned Src = 0; 320d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) { 321d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng const MachineOperand &MO = MI->getOperand(i); 322d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (!MO.isReg()) 323d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng continue; 324d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned Reg = MO.getReg(); 325d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (!Reg) 326d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng continue; 327d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (MO.isDef()) 328d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng Def = Reg; 329d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng else if (Src) 330d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng // Multiple sources? 331d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return false; 332d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng else 333d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng Src = Reg; 334d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng } 335d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 336d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng assert(Def && Src && "Malformed bitcast instruction!"); 337d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 338d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MachineInstr *DefMI = MRI->getVRegDef(Src); 3395a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI || !DefMI->isBitcast()) 340d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return false; 341d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 342d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned SrcSrc = 0; 343d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng NumDefs = DefMI->getDesc().getNumDefs(); 344d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng NumSrcs = DefMI->getDesc().getNumOperands() - NumDefs; 345d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (NumDefs != 1) 346d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return false; 347d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng for (unsigned i = 0, e = NumDefs + NumSrcs; i != e; ++i) { 348d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng const MachineOperand &MO = DefMI->getOperand(i); 349d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (!MO.isReg() || MO.isDef()) 350d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng continue; 351d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng unsigned Reg = MO.getReg(); 352d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (!Reg) 353d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng continue; 3547becbc41ab2875153868c21a84153eca442cc28fDuncan Sands if (!MO.isDef()) { 3557becbc41ab2875153868c21a84153eca442cc28fDuncan Sands if (SrcSrc) 3567becbc41ab2875153868c21a84153eca442cc28fDuncan Sands // Multiple sources? 3577becbc41ab2875153868c21a84153eca442cc28fDuncan Sands return false; 3587becbc41ab2875153868c21a84153eca442cc28fDuncan Sands else 3597becbc41ab2875153868c21a84153eca442cc28fDuncan Sands SrcSrc = Reg; 3607becbc41ab2875153868c21a84153eca442cc28fDuncan Sands } 361d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng } 362d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 363d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng if (MRI->getRegClass(SrcSrc) != MRI->getRegClass(Def)) 364d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return false; 365d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 366d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MRI->replaceRegWith(Def, SrcSrc); 367d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MRI->clearKillFlags(SrcSrc); 368d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MI->eraseFromParent(); 369d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng ++NumBitcasts; 370d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng return true; 371d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng} 372d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng 37339cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach/// optimizeCmpInstr - If the instruction is a compare and the previous 3746cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// instruction it's comparing against all ready sets (or could be modified to 3756cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// set) the same flag as the compare, then we can remove the comparison and use 3766cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling/// the flag from the previous instruction. 37739cc5138707eee563db7a487cd720b232b4b58fdJim Grosbachbool PeepholeOptimizer::optimizeCmpInstr(MachineInstr *MI, 378d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng MachineBasicBlock *MBB) { 3796cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // If this instruction is a comparison against zero and isn't comparing a 3806cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling // physical register, we can try to optimize it. 381de7266c611b37ec050efb53b73166081a98cea13Manman Ren unsigned SrcReg, SrcReg2; 38204ac81d5db058a3a9492e1aff1f398a8643bfda9Gabor Greif int CmpMask, CmpValue; 383de7266c611b37ec050efb53b73166081a98cea13Manman Ren if (!TII->analyzeCompare(MI, SrcReg, SrcReg2, CmpMask, CmpValue) || 384de7266c611b37ec050efb53b73166081a98cea13Manman Ren TargetRegisterInfo::isPhysicalRegister(SrcReg) || 385de7266c611b37ec050efb53b73166081a98cea13Manman Ren (SrcReg2 != 0 && TargetRegisterInfo::isPhysicalRegister(SrcReg2))) 3866cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling return false; 3876cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 388a65568676d0d9d53dd4aae8f1c58271bb4cfff10Bill Wendling // Attempt to optimize the comparison instruction. 389de7266c611b37ec050efb53b73166081a98cea13Manman Ren if (TII->optimizeCompareInstr(MI, SrcReg, SrcReg2, CmpMask, CmpValue, MRI)) { 390d158fba3e45547f013bbab4c0ac640f31b5e341fEvan Cheng ++NumCmps; 3916cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling return true; 3926cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } 3936cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 3946cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling return false; 3956cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling} 3966cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 397f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen/// Optimize a select instruction. 398f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesenbool PeepholeOptimizer::optimizeSelect(MachineInstr *MI) { 399f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen unsigned TrueOp = 0; 400f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen unsigned FalseOp = 0; 401f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen bool Optimizable = false; 402f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen SmallVector<MachineOperand, 4> Cond; 403f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen if (TII->analyzeSelect(MI, Cond, TrueOp, FalseOp, Optimizable)) 404f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen return false; 405f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen if (!Optimizable) 406f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen return false; 407f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen if (!TII->optimizeSelect(MI)) 408f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen return false; 409f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen MI->eraseFromParent(); 410f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen ++NumSelects; 411f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen return true; 412f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen} 413f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen 414d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren/// isLoadFoldable - Check whether MI is a candidate for folding into a later 415d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren/// instruction. We only fold loads to virtual registers and the virtual 416d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren/// register defined has a single use. 417d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Renbool PeepholeOptimizer::isLoadFoldable(MachineInstr *MI, 418d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren unsigned &FoldAsLoadDefReg) { 419127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren if (!MI->canFoldAsLoad() || !MI->mayLoad()) 420127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren return false; 421127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren const MCInstrDesc &MCID = MI->getDesc(); 422127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren if (MCID.getNumDefs() != 1) 423127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren return false; 424127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren 425127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren unsigned Reg = MI->getOperand(0).getReg(); 426127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren // To reduce compilation time, we check MRI->hasOneUse when inserting 427127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren // loads. It should be checked when processing uses of the load, since 428127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren // uses can be removed during peephole. 429127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren if (!MI->getOperand(0).getSubReg() && 430127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren TargetRegisterInfo::isVirtualRegister(Reg) && 431127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren MRI->hasOneUse(Reg)) { 432127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren FoldAsLoadDefReg = Reg; 433127eea87d666ccc9fe7025f41148c33af0f8c84bManman Ren return true; 434d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren } 435d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren return false; 436d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren} 437d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren 438c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Chengbool PeepholeOptimizer::isMoveImmediate(MachineInstr *MI, 439c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SmallSet<unsigned, 4> &ImmDefRegs, 440c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 441e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = MI->getDesc(); 4425a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!MI->isMoveImmediate()) 443c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return false; 444e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getNumDefs() != 1) 445c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return false; 446c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng unsigned Reg = MI->getOperand(0).getReg(); 447c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng if (TargetRegisterInfo::isVirtualRegister(Reg)) { 448c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng ImmDefMIs.insert(std::make_pair(Reg, MI)); 449c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng ImmDefRegs.insert(Reg); 450c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return true; 451c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng } 4521df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 453c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return false; 454c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng} 455c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng 45639cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach/// foldImmediate - Try folding register operands that are defined by move 457c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng/// immediate instructions, i.e. a trivial constant folding optimization, if 458c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng/// and only if the def and use are in the same BB. 45939cc5138707eee563db7a487cd720b232b4b58fdJim Grosbachbool PeepholeOptimizer::foldImmediate(MachineInstr *MI, MachineBasicBlock *MBB, 460c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SmallSet<unsigned, 4> &ImmDefRegs, 461c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*> &ImmDefMIs) { 462c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng for (unsigned i = 0, e = MI->getDesc().getNumOperands(); i != e; ++i) { 463c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng MachineOperand &MO = MI->getOperand(i); 464c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng if (!MO.isReg() || MO.isDef()) 465c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng continue; 466c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng unsigned Reg = MO.getReg(); 467c9df025e33ac435adb3b3318d237c36ca7cec659Jakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 468c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng continue; 469c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng if (ImmDefRegs.count(Reg) == 0) 470c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng continue; 471c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*>::iterator II = ImmDefMIs.find(Reg); 472c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng assert(II != ImmDefMIs.end()); 473c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng if (TII->FoldImmediate(MI, II->second, Reg, MRI)) { 474c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng ++NumImmFold; 475c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return true; 476c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng } 477c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng } 478c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng return false; 479c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng} 480c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng 4816cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendlingbool PeepholeOptimizer::runOnMachineFunction(MachineFunction &MF) { 482a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper DEBUG(dbgs() << "********** PEEPHOLE OPTIMIZER **********\n"); 483a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper DEBUG(dbgs() << "********** Function: " << MF.getName() << '\n'); 484a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper 485eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng if (DisablePeephole) 486eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng return false; 4871df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 4886cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling TM = &MF.getTarget(); 4897da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng TII = TM->getInstrInfo(); 4907da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng MRI = &MF.getRegInfo(); 4916cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling DT = Aggressive ? &getAnalysis<MachineDominatorTree>() : 0; 4927da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 4937da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng bool Changed = false; 4947da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 4957da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng SmallPtrSet<MachineInstr*, 8> LocalMIs; 496c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SmallSet<unsigned, 4> ImmDefRegs; 497c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng DenseMap<unsigned, MachineInstr*> ImmDefMIs; 498d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren unsigned FoldAsLoadDefReg; 4997da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I) { 5007da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng MachineBasicBlock *MBB = &*I; 5011df91b0e54bc62f8fc7a06a4f75220e40aa2dfe0Andrew Trick 502c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng bool SeenMoveImm = false; 503d89d5180d12107a2cdffa179c213370db2e088d5Evan Cheng LocalMIs.clear(); 504c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng ImmDefRegs.clear(); 505c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng ImmDefMIs.clear(); 506d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren FoldAsLoadDefReg = 0; 5076cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling 5086cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling for (MachineBasicBlock::iterator 509220e240bdf3235252c2a1fc8fcc5d4b8e8117918Bill Wendling MII = I->begin(), MIE = I->end(); MII != MIE; ) { 510cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng MachineInstr *MI = &*MII; 511cabc0699ea32cad78028a6533aef1e380064262eJakob Stoklund Olesen // We may be erasing MI below, increment MII now. 512cabc0699ea32cad78028a6533aef1e380064262eJakob Stoklund Olesen ++MII; 513eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng LocalMIs.insert(MI); 514eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng 515d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // If there exists an instruction which belongs to the following 516d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // categories, we will discard the load candidate. 51730a343aeedf777f9b8b6be9823da750afbf765b1Evan Cheng if (MI->isLabel() || MI->isPHI() || MI->isImplicitDef() || 51830a343aeedf777f9b8b6be9823da750afbf765b1Evan Cheng MI->isKill() || MI->isInlineAsm() || MI->isDebugValue() || 519cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng MI->hasUnmodeledSideEffects()) { 520d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren FoldAsLoadDefReg = 0; 521eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng continue; 522cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng } 523d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren if (MI->mayStore() || MI->isCall()) 524d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren FoldAsLoadDefReg = 0; 525eb96a2f6c03c0ec97c56a3493ac38024afacc774Evan Cheng 526f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen if ((MI->isBitcast() && optimizeBitcastInstr(MI, MBB)) || 527f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen (MI->isCompare() && optimizeCmpInstr(MI, MBB)) || 528f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen (MI->isSelect() && optimizeSelect(MI))) { 529f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen // MI is deleted. 530f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen LocalMIs.erase(MI); 531f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen Changed = true; 532f2c64ef519b38a4328809b27b4a3a8e0c26e9709Jakob Stoklund Olesen continue; 533cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng } 534cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng 535cf75ab597514effb6f8e915f05d74f45debb89ecEvan Cheng if (isMoveImmediate(MI, ImmDefRegs, ImmDefMIs)) { 536c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng SeenMoveImm = true; 5376cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } else { 53839cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach Changed |= optimizeExtInstr(MI, MBB, LocalMIs); 53910ad98bbbb00d67d4272e8f29186a65e2a75215eRafael Espindola // optimizeExtInstr might have created new instructions after MI 54010ad98bbbb00d67d4272e8f29186a65e2a75215eRafael Espindola // and before the already incremented MII. Adjust MII so that the 54110ad98bbbb00d67d4272e8f29186a65e2a75215eRafael Espindola // next iteration sees the new instructions. 54210ad98bbbb00d67d4272e8f29186a65e2a75215eRafael Espindola MII = MI; 54310ad98bbbb00d67d4272e8f29186a65e2a75215eRafael Espindola ++MII; 544c4af4638dfdab0dc3b6257276cfad2ee45053060Evan Cheng if (SeenMoveImm) 54539cc5138707eee563db7a487cd720b232b4b58fdJim Grosbach Changed |= foldImmediate(MI, MBB, ImmDefRegs, ImmDefMIs); 5466cdb1abe4e4f6364649e7ef656589441754e82aeBill Wendling } 547326d976eb2b03d1f2b7537d7b90dff264fd84378Evan Cheng 548d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // Check whether MI is a load candidate for folding into a later 549d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // instruction. If MI is not a candidate, check whether we can fold an 550d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // earlier load into MI. 551d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren if (!isLoadFoldable(MI, FoldAsLoadDefReg) && FoldAsLoadDefReg) { 552d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // We need to fold load after optimizeCmpInstr, since optimizeCmpInstr 553d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // can enable folding by converting SUB to CMP. 554d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren MachineInstr *DefMI = 0; 555d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren MachineInstr *FoldMI = TII->optimizeLoadInstr(MI, MRI, 556d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren FoldAsLoadDefReg, DefMI); 557d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren if (FoldMI) { 558d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // Update LocalMIs since we replaced MI with FoldMI and deleted DefMI. 559a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper DEBUG(dbgs() << "Replacing: " << *MI); 560a1032b7e4c405474f8a26c731873d413b1f1d25bCraig Topper DEBUG(dbgs() << " With: " << *FoldMI); 561d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren LocalMIs.erase(MI); 562d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren LocalMIs.erase(DefMI); 563d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren LocalMIs.insert(FoldMI); 564d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren MI->eraseFromParent(); 565d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren DefMI->eraseFromParent(); 566d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren ++NumLoadFold; 567d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren 568d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren // MI is replaced with FoldMI. 569d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren Changed = true; 570d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren continue; 571d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren } 572d7d003c2b7b7f657eed364e4ac06f4ab32fc8c2dManman Ren } 5737da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng } 5747da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng } 5757da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng 5767da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng return Changed; 5777da9ecf9677b751d81515f95168ae3cb2df54160Evan Cheng} 578