RegisterCoalescer.cpp revision 04ce06dc4c9dff4ff7a8b97079e3cbb7b60da3ab
12c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 22c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 32c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// The LLVM Compiler Infrastructure 42c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 82c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 92c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 102c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// This file implements the generic RegisterCoalescer interface which 112c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// is used as the common interface used by all clients and 122c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// implementations of register coalescing. 132c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 142c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 152c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 164281e20aab7f1fe1b35b31c9237ad89c20937e02Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 17fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 18655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "LiveDebugVariables.h" 198e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen#include "VirtRegMap.h" 20655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 21655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Pass.h" 22655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Value.h" 23bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/OwningPtr.h" 24bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 25bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 26bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 27bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 282c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/LiveRangeEdit.h" 31655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineFrameInfo.h" 32655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineInstr.h" 33bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 34655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineLoopInfo.h" 35655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineRegisterInfo.h" 36bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 37655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/Passes.h" 381525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 39655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/CommandLine.h" 40655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/Debug.h" 41655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/ErrorHandling.h" 42655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/raw_ostream.h" 43bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 44bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 45bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 46bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 47bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetRegisterInfo.h" 48655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <algorithm> 49655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <cmath> 502c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greeneusing namespace llvm; 512c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 52655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numJoins , "Number of interval joins performed"); 53655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 54655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCommutes , "Number of instruction commuting performed"); 55655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numExtends , "Number of copies extended"); 56655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(NumReMats , "Number of instructions re-materialized"); 574a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund OlesenSTATISTIC(NumInflated , "Number of register classes inflated"); 58655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 59655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 60655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnableJoining("join-liveintervals", 61655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Coalesce copies (default=true)"), 62655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(true)); 63655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 64655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 65655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaVerifyCoalescing("verify-coalescing", 66655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Verify machine instrs before and after register coalescing"), 67655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::Hidden); 68655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 698e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesennamespace { 70bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen class RegisterCoalescer : public MachineFunctionPass, 71bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 72c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineFunction* MF; 73c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineRegisterInfo* MRI; 74c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetMachine* TM; 75c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterInfo* TRI; 76c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetInstrInfo* TII; 77c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveIntervals *LIS; 78c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveDebugVariables *LDV; 79c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const MachineLoopInfo* Loops; 808e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen AliasAnalysis *AA; 818e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterClassInfo RegClassInfo; 828e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 83b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// WorkList - Copy instructions yet to be coalesced. 84b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> WorkList; 85b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 86bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// ErasedInstrs - Set of instruction pointers that have been erased, and 87bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// that may be present in WorkList. 88bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 89bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 90bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// Dead instructions that are about to be deleted. 91bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> DeadDefs; 92bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 9303c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen /// Virtual registers to be considered for register class inflation. 9403c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen SmallVector<unsigned, 8> InflateRegs; 9503c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen 96bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// Recursively eliminate dead defs in DeadDefs. 97bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen void eliminateDeadDefs(); 98bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 99bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// LiveRangeEdit callback. 100bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr *MI); 101bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 1029790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinAllIntervals - join compatible live intervals 1039790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen void joinAllIntervals(); 1048e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1059790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 106b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// copies that cannot yet be coalesced into WorkList. 107b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen void copyCoalesceInMBB(MachineBasicBlock *MBB); 108b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 109b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// copyCoalesceWorkList - Try to coalesce all copies in WorkList after 110b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// position From. Return true if any progress was made. 111b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool copyCoalesceWorkList(unsigned From = 0); 1128e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1139790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1148e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// which are the src/dst of the copy instruction CopyMI. This returns 1158e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// true if the copy was successfully coalesced away. If it is not 1168e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// currently possible to coalesce this interval, but it may be possible if 1178e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// other things get coalesced, then it returns true by reference in 1188e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// 'Again'. 1199790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool joinCopy(MachineInstr *TheCopy, bool &Again); 1208e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1219790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinIntervals - Attempt to join these two intervals. On failure, this 1228e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// returns false. The output "SrcInt" will not have been modified, so we 1238e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// can use this information below to update aliases. 1249790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool joinIntervals(CoalescerPair &CP); 1258e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 12692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen /// Attempt joining with a reserved physreg. 12792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen bool joinReservedPhysReg(CoalescerPair &CP); 12892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1299790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 1308e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// the source value number is defined by a copy from the destination reg 1318e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// see if we can merge these two destination reg valno# into a single 1328e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// value number, eliminating a copy. 1339790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 1348e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1359790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// hasOtherReachingDefs - Return true if there are definitions of IntB 1368e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// other than BValNo val# that can reach uses of AValno val# of IntA. 1379790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 1388e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen VNInfo *AValNo, VNInfo *BValNo); 1398e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1409790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 1418e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// If the source value number is defined by a commutable instruction and 1428e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// its other operand is coalesced to the copy dest register, see if we 1438e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// can transform the copy into a noop by commuting the definition. 1449790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 1458e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1469790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// reMaterializeTrivialDef - If the source of a copy is defined by a 1478e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// trivial computation, replace the copy by rematerialize the definition. 14867ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen bool reMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, 14967ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen MachineInstr *CopyMI); 1508e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 15134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen /// canJoinPhys - Return true if a physreg copy should be joined. 15234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen bool canJoinPhys(CoalescerPair &CP); 1538e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1549790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 1558e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// update the subregister number if it is not zero. If DstReg is a 1568e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// physical register and the existing subregister number of the def / use 1578e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// being updated is not zero, make sure to set it to the correct physical 1588e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// subregister. 159ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 1608e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1618e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// eliminateUndefCopy - Handle copies of undef values. 1628e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 1638e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1648e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen public: 1658e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen static char ID; // Class identification, replacement for typeinfo 1668e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterCoalescer() : MachineFunctionPass(ID) { 1678e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 1688e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen } 1698e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1708e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 1718e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1728e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void releaseMemory(); 1738e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1748e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// runOnMachineFunction - pass entry point 1758e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 1768e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1778e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// print - Implement the dump method. 1788e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void print(raw_ostream &O, const Module* = 0) const; 1798e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen }; 1808e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen} /// end anonymous namespace 1818e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1828dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trickchar &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 18327215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesen 1845b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 1855b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 186655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 187655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 188655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 189655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 190655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 1915b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 1925b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 193655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1942c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greenechar RegisterCoalescer::ID = 0; 1952c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 19600258d17cd7152237141648d26e1b096cf0e882bRafael Espindolastatic unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) { 19740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!a) return b; 19840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!b) return a; 19900258d17cd7152237141648d26e1b096cf0e882bRafael Espindola return tri.composeSubRegIndices(a, b); 20040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 20140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 20200258d17cd7152237141648d26e1b096cf0e882bRafael Espindolastatic bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 20300258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &Src, unsigned &Dst, 20400258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &SrcSub, unsigned &DstSub) { 205273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 206273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 207273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen DstSub = MI->getOperand(0).getSubReg(); 208273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Src = MI->getOperand(1).getReg(); 209273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen SrcSub = MI->getOperand(1).getSubReg(); 2105c00e077952d14899c3fc26709c7b2dfd36d0209Jakob Stoklund Olesen } else if (MI->isSubregToReg()) { 21140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 21200258d17cd7152237141648d26e1b096cf0e882bRafael Espindola DstSub = compose(tri, MI->getOperand(0).getSubReg(), 21300258d17cd7152237141648d26e1b096cf0e882bRafael Espindola MI->getOperand(3).getImm()); 21440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Src = MI->getOperand(2).getReg(); 21540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = MI->getOperand(2).getSubReg(); 21604c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } else 21740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 21840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 21940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 22040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 22140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::setRegisters(const MachineInstr *MI) { 22294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcReg = DstReg = 0; 22394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx = DstIdx = 0; 224c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen NewRC = 0; 225c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = CrossClass = false; 22640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 22740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 228c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 22940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 230c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Partial = SrcSub || DstSub; 23140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 23240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // If one register is a physreg, it must be Dst. 23340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Src)) { 23440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) 23540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 23640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 23740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 238c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = true; 23940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 24040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 24140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 24240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 24340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 24440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate DstSub on a physreg. 24540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) { 246c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 24740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 24840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = 0; 24940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 25040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 25140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate SrcSub by picking a corresponding Dst superregister. 25240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 253c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 25440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 25540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 25640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else if (!MRI.getRegClass(Src)->contains(Dst)) { 25740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 25840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 25940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 26040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Both registers are virtual. 261defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 262defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 26340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 2648df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // Both registers have subreg indices. 2658df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub && DstSub) { 266ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Copies between different sub-registers are never coalescable. 267ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (Src == Dst && SrcSub != DstSub) 268ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen return false; 269ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen 270defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 27194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx, DstIdx); 272defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen if (!NewRC) 2738df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 27494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else if (DstSub) { 27594b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // SrcReg will be merged with a sub-register of DstReg. 27694b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx = DstSub; 27794b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 27894b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else if (SrcSub) { 27994b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // DstReg will be merged with a sub-register of SrcReg. 28094b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen DstIdx = SrcSub; 28194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 28294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else { 28394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // This is a straight copy without sub-registers. 28494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 2858df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen } 28640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 28794b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // The combined constraint may be impossible to satisfy. 28894b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (!NewRC) 28994b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen return false; 29094b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen 29194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // Prefer SrcReg to be a sub-register of DstReg. 29294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // FIXME: Coalescer should support subregs symmetrically. 29394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (DstIdx && !SrcIdx) { 29440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 29594b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen std::swap(SrcIdx, DstIdx); 29694b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen Flipped = !Flipped; 29740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 29840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 299c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen CrossClass = NewRC != DstRC || NewRC != SrcRC; 30040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 30140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Check our invariants 30240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 30340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 30440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen "Cannot have a physical SubIdx"); 305c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SrcReg = Src; 306c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DstReg = Dst; 30740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 30840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 30940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 31040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::flip() { 31194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 31240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 313c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen std::swap(SrcReg, DstReg); 31494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen std::swap(SrcIdx, DstIdx); 315c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = !Flipped; 31640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 31740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 31840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 31940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 32040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!MI) 32140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 32240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 323c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 32440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 32540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 326c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Find the virtual register that is SrcReg. 327c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Dst == SrcReg) { 32840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 32940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 330c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen } else if (Src != SrcReg) { 33140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 33240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 33340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 334c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Now check that Dst matches DstReg. 335c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 33640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 33740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 33894b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 33940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // DstSub could be set for a physreg from INSERT_SUBREG. 34040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 341c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 34240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Full copy of Src. 34340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!SrcSub) 344c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return DstReg == Dst; 34540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // This is a partial register copy. Check that the parts match. 346c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return TRI.getSubReg(DstReg, SrcSub) == Dst; 34740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 348c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // DstReg is virtual. 349c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (DstReg != Dst) 35040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 35140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Registers match, do the subregisters line up? 35294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen return compose(TRI, SrcIdx, SrcSub) == compose(TRI, DstIdx, DstSub); 35340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 35440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 35540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 3565b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 357655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.setPreservesCFG(); 358655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<AliasAnalysis>(); 359655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveIntervals>(); 360655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveIntervals>(); 361655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveDebugVariables>(); 362655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveDebugVariables>(); 363655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<SlotIndexes>(); 364655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<MachineLoopInfo>(); 365655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<MachineLoopInfo>(); 366655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(MachineDominatorsID); 367655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineFunctionPass::getAnalysisUsage(AU); 368655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 369655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 370bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesenvoid RegisterCoalescer::eliminateDeadDefs() { 371bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> NewRegs; 372bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 373bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen} 374bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 375bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen// Callback from eliminateDeadDefs(). 376bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesenvoid RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 377bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // MI may be in WorkList. Make sure we don't visit it. 378bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.insert(MI); 379bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen} 380bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 3819790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being the source and IntB being the dest, thus this defines a value number 383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// in IntB. If the source value number (in IntA) is defined by a copy from B, 384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// see if we can merge these two pieces of B into a single value number, 385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// eliminating a copy. For example: 386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = B0 388655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 389655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 390655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 391655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 392655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// value number to be replaced with B0 (which simplifies the B liveinterval). 393655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 3969790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 3979790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 398141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen assert(!CP.isPartial() && "This doesn't work for partial copies."); 3990984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen assert(!CP.isPhys() && "This doesn't work for physreg copies."); 400141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen 401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 402c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 403655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 404c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 4052debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 406655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 407655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 408655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BLR == IntB.end()) return false; 411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = BLR->valno; 412655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 413655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the location that B is defined at. Two options: either this value has 414655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // an unknown definition point or it is defined at CopyIdx. If unknown, we 415655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // can't process it. 4163b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (BValNo->def != CopyIdx) return false; 417655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 418655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 4192debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 420655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 421655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live range might not exist after fun with physreg coalescing. 422655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR == IntA.end()) return false; 423655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo = ALR->valno; 424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 425655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If AValNo is defined as a copy from IntB, we can potentially process this. 426655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the instruction that defines this value number. 4273b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 4283b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!CP.isCoalescable(ACopyMI)) 429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the LiveRange in IntB that this value number starts with. 432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ValLR = 433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 434655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR == IntB.end()) 435655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 437655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure that the end of the live range is inside the same block as 438655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI. 439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *ValLREndInst = 440c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 441655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 442655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 444655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we now know that ValLR ends in the same block that the CopyMI 445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live-range starts. If there are no intervening live ranges between them in 446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // IntB, we can merge them. 447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR+1 != BLR) return false; 448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 449b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We are about to delete CopyMI, so need to remove it as the 'instruction 453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // that defines this value #'. Update the valnum with the new defining 454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instruction #. 4553b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen BValNo->def = FillerStart; 456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we can merge them. We need to insert a new liverange: 458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // [ValLR.end, BLR.begin) of either value number, then we merge the 459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // two value numbers. 460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, merge "B1" into the same value number as "B0". 463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BValNo != ValLR->valno) { 464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If B1 is killed by a PHI, then the merged live range must also be killed 465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // by the same PHI, as B0 and B1 can not overlap. 466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool HasPHIKill = BValNo->hasPHIKill(); 467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.MergeValueNumberInto(BValNo, ValLR->valno); 468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (HasPHIKill) 469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLR->valno->setHasPHIKill(true); 470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 471b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << " result = " << IntB << '\n'); 472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the source instruction was killing the source register before the 474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, unset the isKill marker given the live range has been extended. 475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UIdx != -1) { 477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLREndInst->getOperand(UIdx).setIsKill(false); 478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 4798dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 4803b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // Rewrite the copy. If the copy instruction was killing the destination 4813b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // register before the merge, find the last use and trim the live range. That 4823b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // will also add the isKill marker. 483141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR->end == CopyIdx) 485c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&IntA); 486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numExtends; 488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 490655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 4919790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// hasOtherReachingDefs - Return true if there are definitions of IntB 4929b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen/// other than BValNo val# that can reach uses of AValno val# of IntA. 4939790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 4949790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen LiveInterval &IntB, 4959790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *AValNo, 4969790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *BValNo) { 497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 498655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 4999b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AI->valno != AValNo) continue; 500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::Ranges::iterator BI = 501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI != IntB.ranges.begin()) 503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola --BI; 504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->valno == BValNo) 506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start <= AI->start && BI->end > AI->start) 508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start > AI->start && BI->start < AI->end) 510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5169790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// IntA being the source and IntB being the dest, thus this defines a value 518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// number in IntB. If the source value number (in IntA) is defined by a 519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// commutable instruction and its other operand is coalesced to the copy dest 520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// register, see if we can transform the copy into a noop by commuting the 521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// definition. For example, 522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = op A2 B0<kill> 524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op A3 <- more uses 528655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ==> 530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 531655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B2 = op B0 A2<kill> 532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = B2 <- now an identify copy 534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op B2 <- more uses 536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 5399790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 5409790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 5410984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen assert (!CP.isPhys()); 542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5432debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 546c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 548c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 5533b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!BValNo || BValNo->def != CopyIdx) 554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 5592debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(AValNo && "COPY source not live"); 561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5629b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen // If other defs can reach uses of this def, then it's not safe to perform 5639b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen // the optimization. 5649b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 566c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 5695a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isCommutable()) 570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If DefMI is a two-address instruction then commuting it will change the 572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // destination register. 573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefIdx != -1); 575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UseOpIdx; 576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Op1, Op2, NewDstIdx; 579c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Op1 == UseOpIdx) 582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op2; 583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (Op2 == UseOpIdx) 584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op1; 585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewReg = NewDstMO.getReg(); 590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewReg != IntB.reg || !NewDstMO.isKill()) 591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure there are no other definitions of IntB that would reach the 594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // uses which the new definition can reach. 5959790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If some of the uses of IntA.reg is already coalesced away, return false. 599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // It's not possible to determine whether it's safe to perform the coalescing. 600b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick for (MachineRegisterInfo::use_nodbg_iterator UI = 601c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->use_nodbg_begin(IntA.reg), 602c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 604c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 605655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 60656366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (ULR == IntA.end() || ULR->valno != AValNo) 607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 60856366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen // If this use is tied to a def, we can't rewrite the register. 60956366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 6139790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << *DefMI); 615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // At this point we have decided that it is legal to do this 617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // transformation. Start by commuting the instruction. 618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = DefMI->getParent(); 619c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *NewMI = TII->commuteInstruction(DefMI); 620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!NewMI) 621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TargetRegisterInfo::isVirtualRegister(IntB.reg) && 624c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 625655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewMI != DefMI) { 627c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 6287c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MachineBasicBlock::iterator Pos = DefMI; 6297c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMI); 630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->erase(DefMI); 631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->getOperand(OpIdx).setIsKill(); 634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A = or A, B 637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // B = A 639655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 640655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // C = A<kill> 641655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 642655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // = B 643655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 644655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update uses of IntA of the specific Val# with IntB. 645c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 646c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_end(); UI != UE;) { 647655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &UseMO = UI.getOperand(); 648655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 649655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++UI; 650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isDebugValue()) { 651655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME These don't have an instruction index. Not clear we have enough 652655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // info to decide whether to do this replacement or not. For now do it. 653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 654655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 6562debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 657655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 658655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end() || ULR->valno != AValNo) 659655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 661c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMO.substPhysReg(NewReg, *TRI); 662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 663655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 664655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI == CopyMI) 665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isCopy()) 667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 668655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->getOperand(0).getReg() != IntB.reg || 669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getSubReg()) 670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This copy will become a noop. If it's defining a new val#, merge it into 673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo. 6742debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = UseIdx.getRegSlot(); 675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DVNI) 677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DVNI->def == DefIdx); 680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 681ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen ErasedInstrs.insert(UseMI); 682ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(UseMI); 683ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen UseMI->eraseFromParent(); 684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 686655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // is updated. 688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = BValNo; 689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->def = AValNo->def; 690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 693655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 694655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 695655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 697655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntA.removeValNo(AValNo); 698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 699655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCommutes; 700655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 701655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 702655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 7039790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 704655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// computation, replace the copy by rematerialize the definition. 7059790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt, 7069790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen unsigned DstReg, 7079790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 7082debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 710655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(SrcLR != SrcInt.end() && "Live range not found!"); 711655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = SrcLR->valno; 7124ea24e993f179113a9bb76ee152cc490e738c936Jakob Stoklund Olesen if (ValNo->isPHIDef() || ValNo->isUnused()) 713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 714c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 715655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 716655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefMI && "Defining instruction disappeared"); 7185a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isAsCheapAsAMove()) 719655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 720c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->isTriviallyReMaterializable(DefMI, AA)) 721655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 722655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SawStore = false; 723c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!DefMI->isSafeToMove(TII, AA, SawStore)) 724655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 7255a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng const MCInstrDesc &MCID = DefMI->getDesc(); 726e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getNumDefs() != 1) 727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isImplicitDef()) { 729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure the copy destination register class fits the instruction 730655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // definition register class. The mismatch can happen as a result of earlier 731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // extract_subreg, insert_subreg, subreg_to_reg coalescing. 732397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 734c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (MRI->getRegClass(DstReg) != RC) 735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (!RC->contains(DstReg)) 737655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 738655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = CopyMI->getParent(); 741655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock::iterator MII = 742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola llvm::next(MachineBasicBlock::iterator(CopyMI)); 7436e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 744655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = prior(MII); 745655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 746eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 747eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // We need to remember these so we can add intervals once we insert 748eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI into SlotIndexes. 749eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SmallVector<unsigned, 4> NewMIImplDefs; 750eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = NewMI->getDesc().getNumOperands(), 751eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames e = NewMI->getNumOperands(); i != e; ++i) { 752eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames MachineOperand &MO = NewMI->getOperand(i); 753eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames if (MO.isReg()) { 754275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 755275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 756eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames NewMIImplDefs.push_back(MO.getReg()); 757eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 758eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 759eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI may have implicit operands, transfer them over to the newly 761655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerialized instruction. And update implicit def interval valnos. 762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = CopyMI->getDesc().getNumOperands(), 763655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola e = CopyMI->getNumOperands(); i != e; ++i) { 764655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = CopyMI->getOperand(i); 765275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (MO.isReg()) { 766275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isImplicit() && "No explicit operands after implict operands."); 767275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames // Discard VReg implicit defs. 768275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 769275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames NewMI->addOperand(MO); 770275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 771275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 772655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 773655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 774c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 775eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 776eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 777eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 77871b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen unsigned Reg = NewMIImplDefs[i]; 77971b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 78071b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen if (LiveInterval *LI = LIS->getCachedRegUnit(*Units)) 78171b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 782eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 783eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 784655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyMI->eraseFromParent(); 785bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.insert(CopyMI); 786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "Remat: " << *NewMI); 787655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++NumReMats; 788655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 789655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The source interval can become smaller because we removed a use. 7901dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen LIS->shrinkToUses(&SrcInt, &DeadDefs); 7911dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen if (!DeadDefs.empty()) 7921dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen eliminateDeadDefs(); 793655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 794655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 795655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 796655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 797e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 798e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// values, it only removes local variables. When we have a copy like: 799e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 800e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// %vreg1 = COPY %vreg2<undef> 801e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 802e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// We delete the copy and remove the corresponding value number from %vreg1. 803e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// Any uses of that value number are marked as <undef>. 804e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesenbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 805e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen const CoalescerPair &CP) { 806c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 807c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 808e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (SrcInt->liveAt(Idx)) 809e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 810c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 811e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 812e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 813e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 814e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // No intervals are live-in to CopyMI - it is undef. 815e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (CP.isFlipped()) 816e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt = SrcInt; 817e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen SrcInt = 0; 818e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8192debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 820e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen assert(DeadVNI && "No value defined in DstInt"); 821e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt->removeValNo(DeadVNI); 822e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 823e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // Find new undef uses. 824e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator 825c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 826e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen I != E; ++I) { 827e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 828e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 829e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 830e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 831c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(MI); 832e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 833e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 834e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MO.setIsUndef(true); 835e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 836e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 837e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return true; 838e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen} 839e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8409790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 841655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// update the subregister number if it is not zero. If DstReg is a 842655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// physical register and the existing subregister number of the def / use 843655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being updated is not zero, make sure to set it to the correct physical 844655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// subregister. 845ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesenvoid RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 846ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned DstReg, 847ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned SubIdx) { 848ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 849324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 850655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 851655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update LiveDebugVariables. 852c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV->renameRegister(SrcReg, DstReg, SubIdx); 853655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 854c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 855655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = I.skipInstruction();) { 856655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned,8> Ops; 857655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Reads, Writes; 858655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 859655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 86007a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // If SrcReg wasn't read, it may still be the case that DstReg is live-in 86107a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // because SrcReg is a sub-register. 862324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen if (DstInt && !Reads && SubIdx) 863324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 86407a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen 865655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Replace SrcReg with DstReg in all UseMI operands. 866655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 867655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = UseMI->getOperand(Ops[i]); 868655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 86907a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // Adjust <undef> flags in case of sub-register joins. We don't want to 87007a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // turn a full def into a read-modify-write sub-register def and vice 87107a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // versa. 872ec096b492549d625e4be608fcaea265b96dabc03Jakob Stoklund Olesen if (SubIdx && MO.isDef()) 87307a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen MO.setIsUndef(!Reads); 874b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen 875655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) 876c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substPhysReg(DstReg, *TRI); 877655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 878c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substVirtReg(DstReg, SubIdx, *TRI); 879655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 880655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 881655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 882655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tupdated: "; 883655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isDebugValue()) 884c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 885655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << *UseMI; 886655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 887655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 888655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 889655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 89034a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen/// canJoinPhys - Return true if a copy involving a physreg should be joined. 89134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesenbool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { 892655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Always join simple intervals that are defined by a single copy from a 893655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// reserved register. This doesn't increase register pressure, so it is 894655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// always beneficial. 89534a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (!RegClassInfo.isReserved(CP.getDstReg())) { 89634a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 897655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 898655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 899655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 90034a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 90134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (CP.isFlipped() && JoinVInt.containsOneValue()) 90234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return true; 903655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 90434a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 90534a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return false; 906655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 907655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 9089790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 909655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// which are the src/dst of the copy instruction CopyMI. This returns true 910655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// if the copy was successfully coalesced away. If it is not currently 911655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// possible to coalesce this interval, but it may be possible if other 912655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// things get coalesced, then it returns true by reference in 'Again'. 9139790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 914655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 915655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = false; 916c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 917655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 918a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair CP(*TRI); 919655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.setRegisters(CopyMI)) { 920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tNot coalescable.\n"); 921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 922655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 923655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 924bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Dead code elimination. This really should be handled by MachineDCE, but 925bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // sometimes dead copies slip through, and we can't generate invalid live 926bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // ranges. 927bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 928bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy is dead.\n"); 929bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.push_back(CopyMI); 930bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen eliminateDeadDefs(); 931bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen return true; 932bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 933bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 934e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Eliminate undefs. 935e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 936e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 9373662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9383662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 940655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 941655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 942e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Coalesced copies are normally removed immediately, but transformations 943e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // like removeCopyByCommutingDef() can inadvertently create identity copies. 944e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // When that happens, just join the values and remove the copy. 945e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (CP.getSrcReg() == CP.getDstReg()) { 946e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 947e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 948e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 949e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (VNInfo *DefVNI = LRQ.valueDefined()) { 950e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen VNInfo *ReadVNI = LRQ.valueIn(); 951e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI && "No value before copy and no <undef> flag."); 952e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 953e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LI.MergeValueNumberInto(DefVNI, ReadVNI); 954e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 955e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen } 9563662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9573662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 958e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen return true; 959e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 960e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 961655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Enforce policies. 962655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 963ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 964ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 965ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << '\n'); 96634a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (!canJoinPhys(CP)) { 967655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Before giving up coalescing, if definition of source is defined by 968655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // trivial computation, try rematerializing it. 969655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 97067ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 9716e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 972655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 973655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 974655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 975655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 97640a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen DEBUG({ 977ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 978ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with "; 979ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx() && CP.getSrcIdx()) 980ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getDstReg()) << " in " 981ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 982ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getSrcReg()) << " in " 983ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 984ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen else 985ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 986ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 98740a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen }); 988655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 989655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When possible, let DstReg be the larger interval. 990ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 991c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.getDstReg()).ranges.size()) 992655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.flip(); 993655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 994655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 995655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, attempt to join these two intervals. On failure, this returns false. 996655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, if one of the intervals being joined is a physreg, this method 997655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // always canonicalizes DstInt to be it. The output "SrcInt" will not have 998655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been modified, so we can use this information below to update aliases. 9999790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (!joinIntervals(CP)) { 1000655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing failed. 1001655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1002655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If definition of source is defined by trivial computation, try 1003655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerializing it. 1004655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 100567ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 10066e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1007655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1008655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1009655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we can eliminate the copy without merging the live ranges, do so now. 10100984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen if (!CP.isPartial() && !CP.isPhys()) { 10119790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (adjustCopiesBackFrom(CP, CopyMI) || 10129790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen removeCopyByCommutingDef(CP, CopyMI)) { 1013ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 1014ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen CopyMI->eraseFromParent(); 1015655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tTrivial!\n"); 1016655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1017655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1018655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1019655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1020655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, we are unable to join the intervals. 1021655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tInterference!\n"); 1022655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1023655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1024655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1025655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1026655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing to a virtual register that is of a sub-register class of the 1027655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // other. Make sure the resulting register is set to the right register class. 1028655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1029655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCrossRCs; 1030c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1031655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1032655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 103303c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register copies can ease the register class constraints. 103403c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Make sure we attempt to inflate the register class of DstReg. 103503c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 103603c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.push_back(CP.getDstReg()); 103703c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen 10387ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // CopyMI has been erased by joinIntervals at this point. Remove it from 10397ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 10407ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // to the work list. This keeps ErasedInstrs from growing needlessly. 10417ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen ErasedInstrs.erase(CopyMI); 1042655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1043ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Rewrite all SrcReg operands to DstReg. 1044ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Also update DstReg operands to include DstIdx if it is set. 1045ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx()) 1046ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1047ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1048655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1049e02a17c4efb843b8627f3d819c62f88a7f2fb457Lang Hames // SrcReg is guaranteed to be the register whose live interval that is 1050655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // being merged. 1051c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(CP.getSrcReg()); 1052655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1053655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update regalloc hint. 1054c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1055655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 105604ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen DEBUG({ 105704ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI); 105804ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen if (!CP.isPhys()) 105904ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << LIS->getInterval(CP.getDstReg()); 106004ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << '\n'; 106104ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen }); 1062655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1063655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numJoins; 1064655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1065655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1066655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 106792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen/// Attempt joining with a reserved physreg. 106892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesenbool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 106992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isPhys() && "Must be a physreg copy"); 107092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register"); 107192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1072b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1073b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 107492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 107592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isFlipped() && RHS.containsOneValue() && 107692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen "Invalid join with reserved register"); 107792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 107892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Optimization for reserved registers like ESP. We can only merge with a 107992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 108092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // The live range of the reserved register will look like a set of dead defs 108192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // - we don't properly track the live range of reserved registers. 108292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 108392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Deny any overlapping intervals. This depends on all the reserved 108492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live ranges to look like dead defs. 1085241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1086241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1087241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1088241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen return false; 108992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen } 1090241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen 109192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Skip any value computations, we are not adding new values to the 109292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved register. Also skip merging the live ranges, the reserved 109392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live range doesn't need to be accurate as long as all the 109492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // defs are there. 1095857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1096857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // We don't track kills for reserved registers. 1097857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen MRI->clearKillFlags(CP.getSrcReg()); 1098857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 109992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen return true; 110092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen} 110192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1102655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1103655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// compute what the resultant value numbers for each value in the input two 1104655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ranges will be. This is complicated by copies between the two which can 1105655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// and will commonly cause multiple value numbers to be merged into one. 1106655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1107655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// VN is the value number that we're trying to resolve. InstDefiningValue 1108655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// keeps track of the new InstDefiningValue assignment for the result 1109655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1110655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// whether a value in this or other is a copy from the opposite set. 1111655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1112655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// already been assigned. 1113655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1114655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1115655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// contains the value number the copy is from. 1116655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1117655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic unsigned ComputeUltimateVN(VNInfo *VNI, 1118655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> &NewVNInfo, 1119655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1120655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1121655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &ThisValNoAssignments, 1122655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &OtherValNoAssignments) { 1123655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1124655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1125655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the VN has already been computed, just return it. 1126655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ThisValNoAssignments[VN] >= 0) 1127655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN]; 1128655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1129655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1130655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this val is not a copy from the other val, then it must be a new value 1131655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // number in the destination. 1132655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1133655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I == ThisFromOther.end()) { 1134655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1135655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1136655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1137655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *OtherValNo = I->second; 1138655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1139655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, this *is* a copy from the RHS. If the other side has already 1140655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been computed, return it. 1141655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (OtherValNoAssignments[OtherValNo->id] >= 0) 1142655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1143655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1144655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Mark this value number as currently being computed, then ask what the 1145655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ultimate value # of the other value is. 1146655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ThisValNoAssignments[VN] = -2; 1147655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UltimateVN = 1148655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1149655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola OtherValNoAssignments, ThisValNoAssignments); 1150655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = UltimateVN; 1151655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1152655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 11530c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11540c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// Find out if we have something like 11550c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 11560c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = X 11570c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// if so, we can pretend this is actually 11580c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 11590c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = A 11600c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// which allows us to coalesce A and B. 11618f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola// VNI is the definition of B. LR is the life range of A that includes 11620c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// the slot just before B. If we return true, we add "B = X" to DupCopies. 1163b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick// This implies that A dominates B. 11641c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindolastatic bool RegistersDefinedFromSameValue(LiveIntervals &li, 11651c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola const TargetRegisterInfo &tri, 11668f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola CoalescerPair &CP, 11678f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola VNInfo *VNI, 1168e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI, 11690c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> &DupCopies) { 11700c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // FIXME: This is very conservative. For example, we don't handle 11710c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // physical registers. 11720c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11733b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = li.getInstructionFromIndex(VNI->def); 11748f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola 11753b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!MI || !MI->isFullCopy() || CP.isPartial() || CP.isPhys()) 11760c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11770c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11781c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola unsigned Dst = MI->getOperand(0).getReg(); 11791c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola unsigned Src = MI->getOperand(1).getReg(); 11801c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola 11810c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(Src) || 11820c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola !TargetRegisterInfo::isVirtualRegister(Dst)) 11830c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11840c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11850c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned A = CP.getDstReg(); 11860c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned B = CP.getSrcReg(); 11870c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11880c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (B == Dst) 11890c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola std::swap(A, B); 11900c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola assert(Dst == A); 11910c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1192e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen const MachineInstr *OtherMI = li.getInstructionFromIndex(OtherVNI->def); 11930c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11943b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!OtherMI || !OtherMI->isFullCopy()) 11950c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11960c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11970c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned OtherDst = OtherMI->getOperand(0).getReg(); 11980c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 11990c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12000c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(OtherSrc) || 12010c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola !TargetRegisterInfo::isVirtualRegister(OtherDst)) 12020c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 12030c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12040c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola assert(OtherDst == B); 12050c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12060c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (Src != OtherSrc) 12070c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 12080c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1209a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola // If the copies use two different value numbers of X, we cannot merge 1210a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola // A and B. 121165268575c419a890052a446d28329f9e81302a05Rafael Espindola LiveInterval &SrcInt = li.getInterval(Src); 1212b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick // getVNInfoBefore returns NULL for undef copies. In this case, the 1213b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick // optimization is still safe. 1214e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen if (SrcInt.getVNInfoBefore(OtherVNI->def) != SrcInt.getVNInfoBefore(VNI->def)) 1215a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola return false; 1216a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola 12170c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola DupCopies.push_back(MI); 12180c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12190c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return true; 12200c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola} 12210c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12229790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinIntervals - Attempt to join these two intervals. On failure, this 1223655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// returns false. 12249790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 122592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Handle physreg joins separately. 122634a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (CP.isPhys()) 122734a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return joinReservedPhysReg(CP); 1228655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 122992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1230b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1231b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 123292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1233655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Compute the final value assignment, assuming that the live ranges can be 1234655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // coalesced. 1235655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> LHSValNoAssignments; 1236655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> RHSValNoAssignments; 1237655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1238655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1239655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> NewVNInfo; 1240655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 12410c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> DupCopies; 12427ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> DeadCopies; 12430c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1244c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 1245b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tLHS = " << PrintReg(CP.getDstReg(), TRI) << ' ' << LHS 1246b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 1247655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1248ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Loop over the value numbers of the LHS, seeing if any are defined from 1249ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // the RHS. 1250ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1251ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames i != e; ++i) { 1252ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames VNInfo *VNI = *i; 12533b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef()) 12543b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen continue; 12553b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 12563b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen assert(MI && "Missing def"); 12573b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!MI->isCopyLike()) // Src not defined by a copy? 1258ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1259ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1260ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Figure out the value # from the RHS. 1261e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI = RHS.getVNInfoBefore(VNI->def); 1262ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // The copy could be to an aliased physreg. 1263e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen if (!OtherVNI) 1264e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen continue; 1265ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1266ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // DstReg is known to be a register in the LHS interval. If the src is 1267ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // from the RHS interval, we can use its value #. 1268f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen if (CP.isCoalescable(MI)) 1269f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DeadCopies.push_back(MI); 1270f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1271f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DupCopies)) 1272ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1273ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1274e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen LHSValsDefinedFromRHS[VNI] = OtherVNI; 1275ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames } 1276ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1277ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Loop over the value numbers of the RHS, seeing if any are defined from 1278ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // the LHS. 1279ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1280ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames i != e; ++i) { 1281ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames VNInfo *VNI = *i; 12823b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef()) 12833b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen continue; 12843b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 12853b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen assert(MI && "Missing def"); 12863b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!MI->isCopyLike()) // Src not defined by a copy? 1287ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1288ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1289ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Figure out the value # from the LHS. 1290e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI = LHS.getVNInfoBefore(VNI->def); 1291ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // The copy could be to an aliased physreg. 1292e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen if (!OtherVNI) 1293e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen continue; 1294ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1295ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // DstReg is known to be a register in the RHS interval. If the src is 1296ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // from the LHS interval, we can use its value #. 1297f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen if (CP.isCoalescable(MI)) 1298f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DeadCopies.push_back(MI); 1299f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1300f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DupCopies)) 1301ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1302ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1303e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen RHSValsDefinedFromLHS[VNI] = OtherVNI; 1304ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames } 1305655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1306655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1307655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1308655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1309655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1310655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1311655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1312655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1313655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1314655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1315655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1316655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1317655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1318655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments, RHSValNoAssignments); 1319655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1320655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1321655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1322655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1323655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1324655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1325655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1326655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this value number isn't a copy from the LHS, it's a new number. 1327655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1328655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1329655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1330655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1331655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1332655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1333655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1334655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1335655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments, LHSValNoAssignments); 1336655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1337655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1338655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1339655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // interval lists to see if these intervals are coalescable. 1340655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator I = LHS.begin(); 1341655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator IE = LHS.end(); 1342655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator J = RHS.begin(); 1343655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator JE = RHS.end(); 1344655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1345857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Collect interval end points that will no longer be kills. 1346857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen SmallVector<MachineInstr*, 8> LHSOldKills; 1347857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen SmallVector<MachineInstr*, 8> RHSOldKills; 1348857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1349655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Skip ahead until the first place of potential sharing. 1350655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != IE && J != JE) { 1351655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1352655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I = std::upper_bound(I, IE, J->start); 1353655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != LHS.begin()) --I; 1354655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (J->start < I->start) { 1355655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola J = std::upper_bound(J, JE, I->start); 1356655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (J != RHS.begin()) --J; 1357655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1358655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1359655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1360655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (I != IE && J != JE) { 1361655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Determine if these two live ranges overlap. 1362655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, check value # info to determine if they are really different. 1363a991ea5f7f2df661dc1ad7bd230d3a401dfb6411Jakob Stoklund Olesen if (I->end > J->start && J->end > I->start) { 1364655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the live range overlap will map to the same value number in the 1365655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // result liverange, we can still coalesce them. If not, we can't. 1366655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[I->valno->id] != 1367655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[J->valno->id]) 1368655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1369857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1370857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Extended live ranges should no longer be killed. 1371857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (!I->end.isBlock() && I->end < J->end) 1372857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (MachineInstr *MI = LIS->getInstructionFromIndex(I->end)) 1373857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen LHSOldKills.push_back(MI); 1374857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (!J->end.isBlock() && J->end < I->end) 1375857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (MachineInstr *MI = LIS->getInstructionFromIndex(J->end)) 1376857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen RHSOldKills.push_back(MI); 1377655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1378655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1379655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->end < J->end) 1380655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++I; 1381655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++J; 1383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 1387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 1388655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1389655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned LHSValID = LHSValNoAssignments[VNI->id]; 1390655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1391655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[LHSValID]->setHasPHIKill(true); 1392655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1393655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 1396655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 1397655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1398655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned RHSValID = RHSValNoAssignments[VNI->id]; 1399655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1400655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[RHSValID]->setHasPHIKill(true); 1401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1402655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1403857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Clear kill flags where live ranges are extended. 1404857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen while (!LHSOldKills.empty()) 1405857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen LHSOldKills.pop_back_val()->clearRegisterKills(LHS.reg, TRI); 1406857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen while (!RHSOldKills.empty()) 1407857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen RHSOldKills.pop_back_val()->clearRegisterKills(RHS.reg, TRI); 1408857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments.empty()) 1410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.push_back(-1); 1411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments.empty()) 1412655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.push_back(-1); 1413655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 14147ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // Now erase all the redundant copies. 14157ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen for (unsigned i = 0, e = DeadCopies.size(); i != e; ++i) { 14167ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen MachineInstr *MI = DeadCopies[i]; 14177ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen if (!ErasedInstrs.insert(MI)) 14187ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen continue; 1419067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen DEBUG(dbgs() << "\t\terased:\t" << LIS->getInstructionIndex(MI) 1420067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen << '\t' << *MI); 14217ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 14227ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen MI->eraseFromParent(); 14237ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen } 14247ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen 142565268575c419a890052a446d28329f9e81302a05Rafael Espindola SmallVector<unsigned, 8> SourceRegisters; 14260c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 14270c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola E = DupCopies.end(); I != E; ++I) { 14280c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola MachineInstr *MI = *I; 1429067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen if (!ErasedInstrs.insert(MI)) 1430067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen continue; 14310c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 14320c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // We have pretended that the assignment to B in 14330c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 14340c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // B = X 14350c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // was actually a copy from A. Now that we decided to coalesce A and B, 14360c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // transform the code into 14370c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 14380c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned Src = MI->getOperand(1).getReg(); 143965268575c419a890052a446d28329f9e81302a05Rafael Espindola SourceRegisters.push_back(Src); 1440ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 1441ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen MI->eraseFromParent(); 14420c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola } 14430c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 144465268575c419a890052a446d28329f9e81302a05Rafael Espindola // If B = X was the last use of X in a liverange, we have to shrink it now 144565268575c419a890052a446d28329f9e81302a05Rafael Espindola // that B = X is gone. 144665268575c419a890052a446d28329f9e81302a05Rafael Espindola for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 144765268575c419a890052a446d28329f9e81302a05Rafael Espindola E = SourceRegisters.end(); I != E; ++I) { 1448c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&LIS->getInterval(*I)); 144965268575c419a890052a446d28329f9e81302a05Rafael Espindola } 145065268575c419a890052a446d28329f9e81302a05Rafael Espindola 1451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we get here, we know that we can coalesce the live ranges. Ask the 1452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // intervals to coalesce themselves now. 1453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1454c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI); 1455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolanamespace { 1459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DepthMBBCompare - Comparison predicate that sort first based on the loop 1460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // depth of the basic block (the unsigned), and then on the MBB number. 1461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola struct DepthMBBCompare { 1462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Deeper loops first 1465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHS.first != RHS.first) 1466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.first > RHS.first; 1467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Prefer blocks that are more connected in the CFG. This takes care of 1469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the most difficult copies first while intervals are short. 1470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (cl != cr) 1473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return cl > cr; 1474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // As a last resort, sort by block number. 1476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.second->getNumber() < RHS.second->getNumber(); 1477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }; 1479655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1481b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Try joining WorkList copies starting from index From. 1482b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Null out any successful joins. 1483b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesenbool RegisterCoalescer::copyCoalesceWorkList(unsigned From) { 1484b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen assert(From <= WorkList.size() && "Out of range"); 1485b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Progress = false; 1486b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen for (unsigned i = From, e = WorkList.size(); i != e; ++i) { 1487b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (!WorkList[i]) 1488b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen continue; 1489bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Skip instruction pointers that have already been erased, for example by 1490bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // dead code elimination. 1491bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (ErasedInstrs.erase(WorkList[i])) { 1492bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen WorkList[i] = 0; 1493bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen continue; 1494bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 1495b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Again = false; 1496b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Success = joinCopy(WorkList[i], Again); 1497b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen Progress |= Success; 1498b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (Success || !Again) 1499b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList[i] = 0; 1500b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen } 1501b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen return Progress; 1502b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen} 1503b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 15049790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid 1505b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund OlesenRegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 1506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << MBB->getName() << ":\n"); 1507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1508846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // Collect all copy-like instructions in MBB. Don't start coalescing anything 1509846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // yet, it might invalidate the iterator. 1510b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen const unsigned PrevSize = WorkList.size(); 1511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1512846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen MII != E; ++MII) 1513846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen if (MII->isCopyLike()) 1514b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.push_back(MII); 1515b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 1516b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // Try coalescing the collected copies immediately, and remove the nulls. 1517b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // This prevents the WorkList from getting too large since most copies are 1518b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // joinable on the first attempt. 1519b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (copyCoalesceWorkList(PrevSize)) 1520b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 1521b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen (MachineInstr*)0), WorkList.end()); 1522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15249790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid RegisterCoalescer::joinAllIntervals() { 1525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1526b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen assert(WorkList.empty() && "Old data still around."); 1527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1528c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Loops->empty()) { 1529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If there are no loops in the function, join intervals in function order. 1530c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 1531655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I) 1532b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen copyCoalesceInMBB(I); 1533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, join intervals in inner loops before other intervals. 1535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Unfortunately we can't just iterate over loop hierarchy here because 1536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // there may be more MBB's than BB's. Collect MBB's for sorting. 1537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join intervals in the function prolog first. We want to join physical 1539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers with virtual registers before the intervals got too long. 1540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1541c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 1542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = I; 1543c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 1544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Sort by loop depth. 1547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Finally, join intervals in loop nest order. 1550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1551b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen copyCoalesceInMBB(MBBs[i].second); 1552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Joining intervals can allow other intervals to be joined. Iteratively join 1555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // until we make no progress. 1556b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen while (copyCoalesceWorkList()) 1557b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /* empty */ ; 1558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15605b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::releaseMemory() { 1561bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.clear(); 1562b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.clear(); 1563bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.clear(); 156403c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.clear(); 1565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15675b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1568c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF = &fn; 1569c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI = &fn.getRegInfo(); 1570c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TM = &fn.getTarget(); 1571c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 1572c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TII = TM->getInstrInfo(); 1573c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 1574c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV = &getAnalysis<LiveDebugVariables>(); 1575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AA = &getAnalysis<AliasAnalysis>(); 1576c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "********** Function: " 1580c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen << ((Value*)MF->getFunction())->getName() << '\n'); 1581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1583c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "Before register coalescing"); 1584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RegClassInfo.runOnMachineFunction(fn); 1586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join (coalesce) intervals if requested. 1588b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen if (EnableJoining) 15899790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen joinAllIntervals(); 1590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15914a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // After deleting a lot of copies, register classes may be less constrained. 159203c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 15934a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // DPR inflation. 15944a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 15954a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 15964a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.end()); 15974a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 15984a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 15994a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen unsigned Reg = InflateRegs[i]; 16004a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(Reg)) 16014a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen continue; 16024a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->recomputeRegClass(Reg, *TM)) { 16034a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 16044a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << '\n'); 16054a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen ++NumInflated; 16064a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 16074a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 16084a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 1609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dump()); 1610c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(LDV->dump()); 1611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1612c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "After register coalescing"); 1613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// print - Implement the dump method. 16175b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1618c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->print(O, m); 1619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1620