RegisterCoalescer.cpp revision e744ac49f4cf878e2b34dba26964f04fb0415fa3
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". 463bf60aa9db5953dd99c561dfa9323b1e3293a5a85Jakob Stoklund Olesen if (BValNo != ValLR->valno) 464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.MergeValueNumberInto(BValNo, ValLR->valno); 465b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << " result = " << IntB << '\n'); 466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the source instruction was killing the source register before the 468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, unset the isKill marker given the live range has been extended. 469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UIdx != -1) { 471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLREndInst->getOperand(UIdx).setIsKill(false); 472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 4738dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 4743b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // Rewrite the copy. If the copy instruction was killing the destination 4753b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // register before the merge, find the last use and trim the live range. That 4763b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // will also add the isKill marker. 477141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR->end == CopyIdx) 479c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&IntA); 480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 481655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numExtends; 482655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 483655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 4859790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// hasOtherReachingDefs - Return true if there are definitions of IntB 4869b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen/// other than BValNo val# that can reach uses of AValno val# of IntA. 4879790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 4889790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen LiveInterval &IntB, 4899790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *AValNo, 4909790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *BValNo) { 4910ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen // If AValNo has PHI kills, conservatively assume that IntB defs can reach 4920ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen // the PHI values. 4930ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen if (LIS->hasPHIKill(IntA, AValNo)) 4940ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen return true; 4950ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen 496655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 4989b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AI->valno != AValNo) continue; 499655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::Ranges::iterator BI = 500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI != IntB.ranges.begin()) 502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola --BI; 503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->valno == BValNo) 505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start <= AI->start && BI->end > AI->start) 507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start > AI->start && BI->start < AI->end) 509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5159790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 516655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// IntA being the source and IntB being the dest, thus this defines a value 517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// number in IntB. If the source value number (in IntA) is defined by a 518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// commutable instruction and its other operand is coalesced to the copy dest 519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// register, see if we can transform the copy into a noop by commuting the 520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// definition. For example, 521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = op A2 B0<kill> 523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op A3 <- more uses 527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 528655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ==> 529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B2 = op B0 A2<kill> 531655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = B2 <- now an identify copy 533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op B2 <- more uses 535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 5389790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 5399790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 5400984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen assert (!CP.isPhys()); 541655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5422debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 545c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 547c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 5523b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!BValNo || BValNo->def != CopyIdx) 553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 5582debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(AValNo && "COPY source not live"); 5600ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen if (AValNo->isPHIDef() || AValNo->isUnused()) 561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 562c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 5655a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isCommutable()) 566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If DefMI is a two-address instruction then commuting it will change the 568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // destination register. 569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefIdx != -1); 571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UseOpIdx; 572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Op1, Op2, NewDstIdx; 575c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Op1 == UseOpIdx) 578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op2; 579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (Op2 == UseOpIdx) 580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op1; 581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewReg = NewDstMO.getReg(); 586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewReg != IntB.reg || !NewDstMO.isKill()) 587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure there are no other definitions of IntB that would reach the 590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // uses which the new definition can reach. 5919790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If some of the uses of IntA.reg is already coalesced away, return false. 595655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // It's not possible to determine whether it's safe to perform the coalescing. 596b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick for (MachineRegisterInfo::use_nodbg_iterator UI = 597c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->use_nodbg_begin(IntA.reg), 598c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 600c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 60256366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (ULR == IntA.end() || ULR->valno != AValNo) 603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 60456366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen // If this use is tied to a def, we can't rewrite the register. 60556366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 608655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 6099790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << *DefMI); 611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // At this point we have decided that it is legal to do this 613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // transformation. Start by commuting the instruction. 614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = DefMI->getParent(); 615c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *NewMI = TII->commuteInstruction(DefMI); 616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!NewMI) 617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TargetRegisterInfo::isVirtualRegister(IntB.reg) && 620c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewMI != DefMI) { 623c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 6247c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MachineBasicBlock::iterator Pos = DefMI; 6257c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMI); 626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->erase(DefMI); 627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 628655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 629655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->getOperand(OpIdx).setIsKill(); 630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A = or A, B 633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // B = A 635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // C = A<kill> 637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // = B 639655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 640655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update uses of IntA of the specific Val# with IntB. 641c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 642c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_end(); UI != UE;) { 643655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &UseMO = UI.getOperand(); 644655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 645655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++UI; 646655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isDebugValue()) { 647655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME These don't have an instruction index. Not clear we have enough 648655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // info to decide whether to do this replacement or not. For now do it. 649655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 651655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 6522debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 654655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end() || ULR->valno != AValNo) 655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 65634af6f597b09c13fba7d3a1960c0810cfc30beffJakob Stoklund Olesen // Kill flags are no longer accurate. They are recomputed after RA. 65734af6f597b09c13fba7d3a1960c0810cfc30beffJakob Stoklund Olesen UseMO.setIsKill(false); 658655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 659c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMO.substPhysReg(NewReg, *TRI); 660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 661655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI == CopyMI) 663655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 664655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isCopy()) 665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->getOperand(0).getReg() != IntB.reg || 667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getSubReg()) 668655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This copy will become a noop. If it's defining a new val#, merge it into 671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo. 6722debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = UseIdx.getRegSlot(); 673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DVNI) 675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DVNI->def == DefIdx); 678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 679ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen ErasedInstrs.insert(UseMI); 680ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(UseMI); 681ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen UseMI->eraseFromParent(); 682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // is updated. 686655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = BValNo; 687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->def = AValNo->def; 688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 693655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 694655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 695655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntA.removeValNo(AValNo); 696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 697655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCommutes; 698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 699655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 700655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 7019790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 702655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// computation, replace the copy by rematerialize the definition. 7039790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt, 7049790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen unsigned DstReg, 7059790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 7062debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 707655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 708655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(SrcLR != SrcInt.end() && "Live range not found!"); 709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = SrcLR->valno; 7104ea24e993f179113a9bb76ee152cc490e738c936Jakob Stoklund Olesen if (ValNo->isPHIDef() || ValNo->isUnused()) 711655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 712c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 714655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 715655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefMI && "Defining instruction disappeared"); 7165a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isAsCheapAsAMove()) 717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 718c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->isTriviallyReMaterializable(DefMI, AA)) 719655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 720655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SawStore = false; 721c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!DefMI->isSafeToMove(TII, AA, SawStore)) 722655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 7235a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng const MCInstrDesc &MCID = DefMI->getDesc(); 724e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getNumDefs() != 1) 725655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 726655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isImplicitDef()) { 727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure the copy destination register class fits the instruction 728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // definition register class. The mismatch can happen as a result of earlier 729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // extract_subreg, insert_subreg, subreg_to_reg coalescing. 730397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 732c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (MRI->getRegClass(DstReg) != RC) 733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 734655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (!RC->contains(DstReg)) 735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 737655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 738655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = CopyMI->getParent(); 739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock::iterator MII = 740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola llvm::next(MachineBasicBlock::iterator(CopyMI)); 7416e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = prior(MII); 743655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 744eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 745eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // We need to remember these so we can add intervals once we insert 746eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI into SlotIndexes. 747eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SmallVector<unsigned, 4> NewMIImplDefs; 748eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = NewMI->getDesc().getNumOperands(), 749eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames e = NewMI->getNumOperands(); i != e; ++i) { 750eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames MachineOperand &MO = NewMI->getOperand(i); 751eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames if (MO.isReg()) { 752275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 753275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 754eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames NewMIImplDefs.push_back(MO.getReg()); 755eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 756eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 757eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 758655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI may have implicit operands, transfer them over to the newly 759655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerialized instruction. And update implicit def interval valnos. 760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = CopyMI->getDesc().getNumOperands(), 761655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola e = CopyMI->getNumOperands(); i != e; ++i) { 762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = CopyMI->getOperand(i); 763275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (MO.isReg()) { 764275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isImplicit() && "No explicit operands after implict operands."); 765275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames // Discard VReg implicit defs. 766275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 767275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames NewMI->addOperand(MO); 768275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 769275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 770655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 771655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 772c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 773eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 774eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 775eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 77671b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen unsigned Reg = NewMIImplDefs[i]; 77771b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 77871b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen if (LiveInterval *LI = LIS->getCachedRegUnit(*Units)) 77971b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 780eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 781eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 782655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyMI->eraseFromParent(); 783bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.insert(CopyMI); 784655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "Remat: " << *NewMI); 785655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++NumReMats; 786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 787655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The source interval can become smaller because we removed a use. 7881dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen LIS->shrinkToUses(&SrcInt, &DeadDefs); 7891dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen if (!DeadDefs.empty()) 7901dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen eliminateDeadDefs(); 791655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 792655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 793655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 794655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 795e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 796e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// values, it only removes local variables. When we have a copy like: 797e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 798e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// %vreg1 = COPY %vreg2<undef> 799e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 800e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// We delete the copy and remove the corresponding value number from %vreg1. 801e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// Any uses of that value number are marked as <undef>. 802e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesenbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 803e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen const CoalescerPair &CP) { 804c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 805c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 806e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (SrcInt->liveAt(Idx)) 807e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 808c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 809e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 810e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 811e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 812e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // No intervals are live-in to CopyMI - it is undef. 813e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (CP.isFlipped()) 814e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt = SrcInt; 815e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen SrcInt = 0; 816e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8172debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 818e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen assert(DeadVNI && "No value defined in DstInt"); 819e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt->removeValNo(DeadVNI); 820e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 821e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // Find new undef uses. 822e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator 823c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 824e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen I != E; ++I) { 825e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 826e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 827e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 828e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 829c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(MI); 830e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 831e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 832e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MO.setIsUndef(true); 833e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 834e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 835e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return true; 836e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen} 837e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8389790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 839655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// update the subregister number if it is not zero. If DstReg is a 840655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// physical register and the existing subregister number of the def / use 841655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being updated is not zero, make sure to set it to the correct physical 842655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// subregister. 843ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesenvoid RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 844ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned DstReg, 845ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned SubIdx) { 846ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 847324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 848655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 849655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update LiveDebugVariables. 850c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV->renameRegister(SrcReg, DstReg, SubIdx); 851655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 852c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 853655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = I.skipInstruction();) { 854655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned,8> Ops; 855655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Reads, Writes; 856655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 857655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 85807a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // If SrcReg wasn't read, it may still be the case that DstReg is live-in 85907a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // because SrcReg is a sub-register. 860324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen if (DstInt && !Reads && SubIdx) 861324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 86207a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen 863655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Replace SrcReg with DstReg in all UseMI operands. 864655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 865655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = UseMI->getOperand(Ops[i]); 866655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 86707a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // Adjust <undef> flags in case of sub-register joins. We don't want to 86807a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // turn a full def into a read-modify-write sub-register def and vice 86907a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // versa. 870ec096b492549d625e4be608fcaea265b96dabc03Jakob Stoklund Olesen if (SubIdx && MO.isDef()) 87107a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen MO.setIsUndef(!Reads); 872b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen 873655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) 874c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substPhysReg(DstReg, *TRI); 875655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 876c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substVirtReg(DstReg, SubIdx, *TRI); 877655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 878655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 879655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 880655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tupdated: "; 881655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isDebugValue()) 882c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 883655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << *UseMI; 884655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 885655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 886655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 887655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 88834a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen/// canJoinPhys - Return true if a copy involving a physreg should be joined. 88934a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesenbool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { 890655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Always join simple intervals that are defined by a single copy from a 891655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// reserved register. This doesn't increase register pressure, so it is 892655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// always beneficial. 89334a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (!RegClassInfo.isReserved(CP.getDstReg())) { 89434a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 895655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 896655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 897655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 89834a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 89934a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (CP.isFlipped() && JoinVInt.containsOneValue()) 90034a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return true; 901655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 90234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 90334a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return false; 904655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 905655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 9069790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 907655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// which are the src/dst of the copy instruction CopyMI. This returns true 908655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// if the copy was successfully coalesced away. If it is not currently 909655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// possible to coalesce this interval, but it may be possible if other 910655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// things get coalesced, then it returns true by reference in 'Again'. 9119790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 912655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 913655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = false; 914c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 915655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 916a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair CP(*TRI); 917655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.setRegisters(CopyMI)) { 918655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tNot coalescable.\n"); 919655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 922bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Dead code elimination. This really should be handled by MachineDCE, but 923bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // sometimes dead copies slip through, and we can't generate invalid live 924bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // ranges. 925bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 926bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy is dead.\n"); 927bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.push_back(CopyMI); 928bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen eliminateDeadDefs(); 929bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen return true; 930bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 931bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 932e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Eliminate undefs. 933e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 934e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 9353662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9363662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 937655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 938655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 940e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Coalesced copies are normally removed immediately, but transformations 941e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // like removeCopyByCommutingDef() can inadvertently create identity copies. 942e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // When that happens, just join the values and remove the copy. 943e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (CP.getSrcReg() == CP.getDstReg()) { 944e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 945e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 946e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 947e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (VNInfo *DefVNI = LRQ.valueDefined()) { 948e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen VNInfo *ReadVNI = LRQ.valueIn(); 949e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI && "No value before copy and no <undef> flag."); 950e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 951e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LI.MergeValueNumberInto(DefVNI, ReadVNI); 952e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 953e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen } 9543662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9553662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 956e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen return true; 957e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 958e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 959655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Enforce policies. 960655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 961ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 962ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 963ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << '\n'); 96434a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (!canJoinPhys(CP)) { 965655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Before giving up coalescing, if definition of source is defined by 966655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // trivial computation, try rematerializing it. 967655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 96867ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 9696e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 970655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 971655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 972655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 973655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 97440a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen DEBUG({ 975ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 976ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with "; 977ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx() && CP.getSrcIdx()) 978ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getDstReg()) << " in " 979ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 980ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getSrcReg()) << " in " 981ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 982ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen else 983ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 984ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 98540a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen }); 986655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 987655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When possible, let DstReg be the larger interval. 988ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 989c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.getDstReg()).ranges.size()) 990655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.flip(); 991655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 992655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 993655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, attempt to join these two intervals. On failure, this returns false. 994655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, if one of the intervals being joined is a physreg, this method 995655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // always canonicalizes DstInt to be it. The output "SrcInt" will not have 996655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been modified, so we can use this information below to update aliases. 9979790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (!joinIntervals(CP)) { 998655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing failed. 999655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1000655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If definition of source is defined by trivial computation, try 1001655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerializing it. 1002655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 100367ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 10046e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1005655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1006655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1007655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we can eliminate the copy without merging the live ranges, do so now. 10080984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen if (!CP.isPartial() && !CP.isPhys()) { 10099790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (adjustCopiesBackFrom(CP, CopyMI) || 10109790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen removeCopyByCommutingDef(CP, CopyMI)) { 1011ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 1012ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen CopyMI->eraseFromParent(); 1013655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tTrivial!\n"); 1014655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1015655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1016655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1017655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1018655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, we are unable to join the intervals. 1019655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tInterference!\n"); 1020655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1021655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1022655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1023655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1024655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing to a virtual register that is of a sub-register class of the 1025655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // other. Make sure the resulting register is set to the right register class. 1026655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1027655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCrossRCs; 1028c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1029655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1030655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 103103c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register copies can ease the register class constraints. 103203c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Make sure we attempt to inflate the register class of DstReg. 103303c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 103403c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.push_back(CP.getDstReg()); 103503c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen 10367ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // CopyMI has been erased by joinIntervals at this point. Remove it from 10377ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 10387ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // to the work list. This keeps ErasedInstrs from growing needlessly. 10397ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen ErasedInstrs.erase(CopyMI); 1040655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1041ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Rewrite all SrcReg operands to DstReg. 1042ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Also update DstReg operands to include DstIdx if it is set. 1043ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx()) 1044ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1045ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1046655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1047e02a17c4efb843b8627f3d819c62f88a7f2fb457Lang Hames // SrcReg is guaranteed to be the register whose live interval that is 1048655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // being merged. 1049c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(CP.getSrcReg()); 1050655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1051655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update regalloc hint. 1052c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1053655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 105404ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen DEBUG({ 105504ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI); 105604ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen if (!CP.isPhys()) 105704ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << LIS->getInterval(CP.getDstReg()); 105804ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << '\n'; 105904ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen }); 1060655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1061655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numJoins; 1062655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1063655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1064655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 106592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen/// Attempt joining with a reserved physreg. 106692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesenbool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 106792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isPhys() && "Must be a physreg copy"); 106892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(RegClassInfo.isReserved(CP.getDstReg()) && "Not a reserved register"); 106992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1070b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1071b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 107292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 107392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isFlipped() && RHS.containsOneValue() && 107492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen "Invalid join with reserved register"); 107592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 107692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Optimization for reserved registers like ESP. We can only merge with a 107792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 107892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // The live range of the reserved register will look like a set of dead defs 107992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // - we don't properly track the live range of reserved registers. 108092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 108192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Deny any overlapping intervals. This depends on all the reserved 108292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live ranges to look like dead defs. 1083241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1084241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1085241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1086241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen return false; 108792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen } 1088241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen 108992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Skip any value computations, we are not adding new values to the 109092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved register. Also skip merging the live ranges, the reserved 109192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live range doesn't need to be accurate as long as all the 109292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // defs are there. 1093857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1094e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen // Delete the identity copy. 1095e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1096e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 1097e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen CopyMI->eraseFromParent(); 1098e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen 1099857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // We don't track kills for reserved registers. 1100857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen MRI->clearKillFlags(CP.getSrcReg()); 1101857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 110292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen return true; 110392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen} 110492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1105655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1106655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// compute what the resultant value numbers for each value in the input two 1107655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ranges will be. This is complicated by copies between the two which can 1108655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// and will commonly cause multiple value numbers to be merged into one. 1109655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1110655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// VN is the value number that we're trying to resolve. InstDefiningValue 1111655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// keeps track of the new InstDefiningValue assignment for the result 1112655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1113655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// whether a value in this or other is a copy from the opposite set. 1114655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1115655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// already been assigned. 1116655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1117655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1118655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// contains the value number the copy is from. 1119655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1120655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic unsigned ComputeUltimateVN(VNInfo *VNI, 1121655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> &NewVNInfo, 1122655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1123655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1124655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &ThisValNoAssignments, 1125655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &OtherValNoAssignments) { 1126655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1127655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1128655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the VN has already been computed, just return it. 1129655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ThisValNoAssignments[VN] >= 0) 1130655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN]; 1131655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1132655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1133655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this val is not a copy from the other val, then it must be a new value 1134655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // number in the destination. 1135655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1136655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I == ThisFromOther.end()) { 1137655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1138655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1139655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1140655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *OtherValNo = I->second; 1141655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1142655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, this *is* a copy from the RHS. If the other side has already 1143655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been computed, return it. 1144655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (OtherValNoAssignments[OtherValNo->id] >= 0) 1145655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1146655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1147655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Mark this value number as currently being computed, then ask what the 1148655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ultimate value # of the other value is. 1149655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ThisValNoAssignments[VN] = -2; 1150655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UltimateVN = 1151655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1152655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola OtherValNoAssignments, ThisValNoAssignments); 1153655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = UltimateVN; 1154655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1155655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 11560c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11570c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// Find out if we have something like 11580c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 11590c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = X 11600c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// if so, we can pretend this is actually 11610c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 11620c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = A 11630c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// which allows us to coalesce A and B. 11648f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola// VNI is the definition of B. LR is the life range of A that includes 11650c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// the slot just before B. If we return true, we add "B = X" to DupCopies. 1166b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick// This implies that A dominates B. 11671c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindolastatic bool RegistersDefinedFromSameValue(LiveIntervals &li, 11681c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola const TargetRegisterInfo &tri, 11698f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola CoalescerPair &CP, 11708f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola VNInfo *VNI, 1171e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI, 11720c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> &DupCopies) { 11730c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // FIXME: This is very conservative. For example, we don't handle 11740c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // physical registers. 11750c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11763b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = li.getInstructionFromIndex(VNI->def); 11778f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola 1178682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!MI || CP.isPartial() || CP.isPhys()) 11790c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11800c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11819c3d5a70f40f9e7bb90f3cb8ec1d87cff6e3f0aeRafael Espindola unsigned A = CP.getDstReg(); 11829c3d5a70f40f9e7bb90f3cb8ec1d87cff6e3f0aeRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(A)) 11830c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11840c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 11850c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned B = CP.getSrcReg(); 11869c3d5a70f40f9e7bb90f3cb8ec1d87cff6e3f0aeRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(B)) 11879c3d5a70f40f9e7bb90f3cb8ec1d87cff6e3f0aeRafael Espindola return false; 11880c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1189682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola MachineInstr *OtherMI = li.getInstructionFromIndex(OtherVNI->def); 1190682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!OtherMI) 11910c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 11920c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1193682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (MI->isImplicitDef()) { 1194682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola DupCopies.push_back(MI); 1195682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return true; 1196682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola } else { 1197682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!MI->isFullCopy()) 1198682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 1199682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola unsigned Src = MI->getOperand(1).getReg(); 1200682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!TargetRegisterInfo::isVirtualRegister(Src)) 1201682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 1202682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!OtherMI->isFullCopy()) 1203682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 1204682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 1205682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!TargetRegisterInfo::isVirtualRegister(OtherSrc)) 1206682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 12070c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1208682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (Src != OtherSrc) 1209682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 1210a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola 1211682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // If the copies use two different value numbers of X, we cannot merge 1212682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // A and B. 1213682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola LiveInterval &SrcInt = li.getInterval(Src); 1214682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // getVNInfoBefore returns NULL for undef copies. In this case, the 1215682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // optimization is still safe. 1216682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (SrcInt.getVNInfoBefore(OtherVNI->def) != 1217682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola SrcInt.getVNInfoBefore(VNI->def)) 1218682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return false; 12190c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1220682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola DupCopies.push_back(MI); 1221682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola return true; 1222682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola } 12230c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola} 12240c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 12259790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinIntervals - Attempt to join these two intervals. On failure, this 1226655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// returns false. 12279790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 122892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Handle physreg joins separately. 122934a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (CP.isPhys()) 123034a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return joinReservedPhysReg(CP); 1231655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 123292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1233b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1234b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 123592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1236655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Compute the final value assignment, assuming that the live ranges can be 1237655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // coalesced. 1238655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> LHSValNoAssignments; 1239655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> RHSValNoAssignments; 1240655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1241655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1242655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> NewVNInfo; 1243655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 12440c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> DupCopies; 12457ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> DeadCopies; 12460c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1247c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 1248b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tLHS = " << PrintReg(CP.getDstReg(), TRI) << ' ' << LHS 1249b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 1250655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1251ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Loop over the value numbers of the LHS, seeing if any are defined from 1252ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // the RHS. 1253ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1254ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames i != e; ++i) { 1255ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames VNInfo *VNI = *i; 12563b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef()) 12573b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen continue; 12583b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 12593b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen assert(MI && "Missing def"); 1260682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!MI->isCopyLike() && !MI->isImplicitDef()) // Src not defined by a copy? 1261ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1262ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1263ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Figure out the value # from the RHS. 1264e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI = RHS.getVNInfoBefore(VNI->def); 1265ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // The copy could be to an aliased physreg. 1266e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen if (!OtherVNI) 1267e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen continue; 1268ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1269ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // DstReg is known to be a register in the LHS interval. If the src is 1270ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // from the RHS interval, we can use its value #. 1271f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen if (CP.isCoalescable(MI)) 1272f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DeadCopies.push_back(MI); 1273f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1274f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DupCopies)) 1275ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1276ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1277e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen LHSValsDefinedFromRHS[VNI] = OtherVNI; 1278ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames } 1279ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1280ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Loop over the value numbers of the RHS, seeing if any are defined from 1281ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // the LHS. 1282ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1283ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames i != e; ++i) { 1284ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames VNInfo *VNI = *i; 12853b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (VNI->isUnused() || VNI->isPHIDef()) 12863b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen continue; 12873b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *MI = LIS->getInstructionFromIndex(VNI->def); 12883b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen assert(MI && "Missing def"); 1289682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!MI->isCopyLike() && !MI->isImplicitDef()) // Src not defined by a copy? 1290ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1291ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1292ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // Figure out the value # from the LHS. 1293e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen VNInfo *OtherVNI = LHS.getVNInfoBefore(VNI->def); 1294ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // The copy could be to an aliased physreg. 1295e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen if (!OtherVNI) 1296e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen continue; 1297ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1298ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // DstReg is known to be a register in the RHS interval. If the src is 1299ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames // from the LHS interval, we can use its value #. 1300f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen if (CP.isCoalescable(MI)) 1301f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DeadCopies.push_back(MI); 1302f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen else if (!RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, OtherVNI, 1303f0bf8b401827b58ec171c9d994c46d7f810a3e17Jakob Stoklund Olesen DupCopies)) 1304ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames continue; 1305ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames 1306e1b93d2e86a3396b1b1d3d761f0335b17c5f54b8Jakob Stoklund Olesen RHSValsDefinedFromLHS[VNI] = OtherVNI; 1307ff21bb53ae9496b0e24d0ea0cb392fae1d49128bLang Hames } 1308655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1309655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1310655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1311655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1312655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1313655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1314655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1315655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1316655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1317655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1318655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1319655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1320655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1321655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments, RHSValNoAssignments); 1322655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1323655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1324655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1325655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1326655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1327655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1328655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1329655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this value number isn't a copy from the LHS, it's a new number. 1330655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1331655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1332655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1333655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1334655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1335655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1336655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1337655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1338655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments, LHSValNoAssignments); 1339655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1340655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1341655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1342655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // interval lists to see if these intervals are coalescable. 1343655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator I = LHS.begin(); 1344655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator IE = LHS.end(); 1345655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator J = RHS.begin(); 1346655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator JE = RHS.end(); 1347655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1348857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Collect interval end points that will no longer be kills. 1349857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen SmallVector<MachineInstr*, 8> LHSOldKills; 1350857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen SmallVector<MachineInstr*, 8> RHSOldKills; 1351857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1352655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Skip ahead until the first place of potential sharing. 1353655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != IE && J != JE) { 1354655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1355655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I = std::upper_bound(I, IE, J->start); 1356655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != LHS.begin()) --I; 1357655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (J->start < I->start) { 1358655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola J = std::upper_bound(J, JE, I->start); 1359655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (J != RHS.begin()) --J; 1360655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1361655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1362655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1363655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (I != IE && J != JE) { 1364655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Determine if these two live ranges overlap. 1365655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, check value # info to determine if they are really different. 1366a991ea5f7f2df661dc1ad7bd230d3a401dfb6411Jakob Stoklund Olesen if (I->end > J->start && J->end > I->start) { 1367655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the live range overlap will map to the same value number in the 1368655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // result liverange, we can still coalesce them. If not, we can't. 1369655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[I->valno->id] != 1370655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[J->valno->id]) 1371655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1372857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1373857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Extended live ranges should no longer be killed. 1374857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (!I->end.isBlock() && I->end < J->end) 1375857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (MachineInstr *MI = LIS->getInstructionFromIndex(I->end)) 1376857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen LHSOldKills.push_back(MI); 1377857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (!J->end.isBlock() && J->end < I->end) 1378857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen if (MachineInstr *MI = LIS->getInstructionFromIndex(J->end)) 1379857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen RHSOldKills.push_back(MI); 1380655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1381655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->end < J->end) 1383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++I; 1384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++J; 1386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1388857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // Clear kill flags where live ranges are extended. 1389857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen while (!LHSOldKills.empty()) 1390857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen LHSOldKills.pop_back_val()->clearRegisterKills(LHS.reg, TRI); 1391857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen while (!RHSOldKills.empty()) 1392857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen RHSOldKills.pop_back_val()->clearRegisterKills(RHS.reg, TRI); 1393857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments.empty()) 1395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.push_back(-1); 1396655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments.empty()) 1397655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.push_back(-1); 1398655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 13997ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // Now erase all the redundant copies. 14007ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen for (unsigned i = 0, e = DeadCopies.size(); i != e; ++i) { 14017ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen MachineInstr *MI = DeadCopies[i]; 14027ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen if (!ErasedInstrs.insert(MI)) 14037ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen continue; 1404067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen DEBUG(dbgs() << "\t\terased:\t" << LIS->getInstructionIndex(MI) 1405067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen << '\t' << *MI); 14067ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 14077ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen MI->eraseFromParent(); 14087ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen } 14097ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen 141065268575c419a890052a446d28329f9e81302a05Rafael Espindola SmallVector<unsigned, 8> SourceRegisters; 14110c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 14120c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola E = DupCopies.end(); I != E; ++I) { 14130c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola MachineInstr *MI = *I; 1414067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen if (!ErasedInstrs.insert(MI)) 1415067fcb4087a2c816f6536907b9918165e5b00b33Jakob Stoklund Olesen continue; 14160c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1417682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // If MI is a copy, then we have pretended that the assignment to B in 14180c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 14190c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // B = X 14200c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // was actually a copy from A. Now that we decided to coalesce A and B, 14210c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // transform the code into 14220c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 1423682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola // In the case of the implicit_def, we just have to remove it. 1424682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola if (!MI->isImplicitDef()) { 1425682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola unsigned Src = MI->getOperand(1).getReg(); 1426682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola SourceRegisters.push_back(Src); 1427682e8d05c7def2b82edc354abf1d38df607d39c8Rafael Espindola } 1428ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 1429ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen MI->eraseFromParent(); 14300c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola } 14310c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 143265268575c419a890052a446d28329f9e81302a05Rafael Espindola // If B = X was the last use of X in a liverange, we have to shrink it now 143365268575c419a890052a446d28329f9e81302a05Rafael Espindola // that B = X is gone. 143465268575c419a890052a446d28329f9e81302a05Rafael Espindola for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 143565268575c419a890052a446d28329f9e81302a05Rafael Espindola E = SourceRegisters.end(); I != E; ++I) { 1436c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&LIS->getInterval(*I)); 143765268575c419a890052a446d28329f9e81302a05Rafael Espindola } 143865268575c419a890052a446d28329f9e81302a05Rafael Espindola 1439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we get here, we know that we can coalesce the live ranges. Ask the 1440655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // intervals to coalesce themselves now. 1441655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1442c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI); 1443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1444655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolanamespace { 1447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DepthMBBCompare - Comparison predicate that sort first based on the loop 1448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // depth of the basic block (the unsigned), and then on the MBB number. 1449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola struct DepthMBBCompare { 1450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Deeper loops first 1453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHS.first != RHS.first) 1454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.first > RHS.first; 1455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Prefer blocks that are more connected in the CFG. This takes care of 1457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the most difficult copies first while intervals are short. 1458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (cl != cr) 1461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return cl > cr; 1462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // As a last resort, sort by block number. 1464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.second->getNumber() < RHS.second->getNumber(); 1465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }; 1467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1469b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Try joining WorkList copies starting from index From. 1470b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Null out any successful joins. 1471b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesenbool RegisterCoalescer::copyCoalesceWorkList(unsigned From) { 1472b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen assert(From <= WorkList.size() && "Out of range"); 1473b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Progress = false; 1474b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen for (unsigned i = From, e = WorkList.size(); i != e; ++i) { 1475b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (!WorkList[i]) 1476b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen continue; 1477bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Skip instruction pointers that have already been erased, for example by 1478bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // dead code elimination. 1479bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (ErasedInstrs.erase(WorkList[i])) { 1480bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen WorkList[i] = 0; 1481bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen continue; 1482bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 1483b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Again = false; 1484b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Success = joinCopy(WorkList[i], Again); 1485b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen Progress |= Success; 1486b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (Success || !Again) 1487b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList[i] = 0; 1488b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen } 1489b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen return Progress; 1490b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen} 1491b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 14929790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid 1493b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund OlesenRegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 1494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << MBB->getName() << ":\n"); 1495655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1496846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // Collect all copy-like instructions in MBB. Don't start coalescing anything 1497846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // yet, it might invalidate the iterator. 1498b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen const unsigned PrevSize = WorkList.size(); 1499655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1500846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen MII != E; ++MII) 1501846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen if (MII->isCopyLike()) 1502b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.push_back(MII); 1503b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 1504b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // Try coalescing the collected copies immediately, and remove the nulls. 1505b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // This prevents the WorkList from getting too large since most copies are 1506b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // joinable on the first attempt. 1507b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (copyCoalesceWorkList(PrevSize)) 1508b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 1509b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen (MachineInstr*)0), WorkList.end()); 1510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15129790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid RegisterCoalescer::joinAllIntervals() { 1513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1514b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen assert(WorkList.empty() && "Old data still around."); 1515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1516c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Loops->empty()) { 1517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If there are no loops in the function, join intervals in function order. 1518c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 1519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I) 1520b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen copyCoalesceInMBB(I); 1521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, join intervals in inner loops before other intervals. 1523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Unfortunately we can't just iterate over loop hierarchy here because 1524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // there may be more MBB's than BB's. Collect MBB's for sorting. 1525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join intervals in the function prolog first. We want to join physical 1527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers with virtual registers before the intervals got too long. 1528655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1529c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 1530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = I; 1531c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 1532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Sort by loop depth. 1535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Finally, join intervals in loop nest order. 1538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1539b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen copyCoalesceInMBB(MBBs[i].second); 1540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1541655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Joining intervals can allow other intervals to be joined. Iteratively join 1543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // until we make no progress. 1544b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen while (copyCoalesceWorkList()) 1545b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /* empty */ ; 1546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15485b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::releaseMemory() { 1549bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.clear(); 1550b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.clear(); 1551bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.clear(); 155203c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.clear(); 1553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15555b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1556c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF = &fn; 1557c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI = &fn.getRegInfo(); 1558c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TM = &fn.getTarget(); 1559c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 1560c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TII = TM->getInstrInfo(); 1561c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 1562c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV = &getAnalysis<LiveDebugVariables>(); 1563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AA = &getAnalysis<AliasAnalysis>(); 1564c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "********** Function: " 1568c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen << ((Value*)MF->getFunction())->getName() << '\n'); 1569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1571c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "Before register coalescing"); 1572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RegClassInfo.runOnMachineFunction(fn); 1574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join (coalesce) intervals if requested. 1576b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen if (EnableJoining) 15779790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen joinAllIntervals(); 1578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15794a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // After deleting a lot of copies, register classes may be less constrained. 158003c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 15814a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // DPR inflation. 15824a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 15834a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 15844a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.end()); 15854a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 15864a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 15874a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen unsigned Reg = InflateRegs[i]; 15884a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(Reg)) 15894a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen continue; 15904a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->recomputeRegClass(Reg, *TM)) { 15914a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 15924a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << '\n'); 15934a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen ++NumInflated; 15944a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 15954a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 15964a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 1597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dump()); 1598c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(LDV->dump()); 1599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1600c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "After register coalescing"); 1601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// print - Implement the dump method. 16055b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1606c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->print(O, m); 1607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1608