RegisterCoalescer.cpp revision 4281e20aab7f1fe1b35b31c9237ad89c20937e02
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 "RegisterClassInfo.h" 208e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen#include "VirtRegMap.h" 21655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 22655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Pass.h" 23655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Value.h" 242c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveIntervalAnalysis.h" 252c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/MachineInstr.h" 2640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 286f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 29655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Analysis/AliasAnalysis.h" 31655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineFrameInfo.h" 32655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineInstr.h" 33655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineLoopInfo.h" 34655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineRegisterInfo.h" 35655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/Passes.h" 36655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetInstrInfo.h" 37655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetMachine.h" 38655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetOptions.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" 43655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/OwningPtr.h" 44655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/SmallSet.h" 45655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/Statistic.h" 46655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/STLExtras.h" 47655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <algorithm> 48655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <cmath> 492c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greeneusing namespace llvm; 502c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 51655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numJoins , "Number of interval joins performed"); 52655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 53655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCommutes , "Number of instruction commuting performed"); 54655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numExtends , "Number of copies extended"); 55655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(NumReMats , "Number of instructions re-materialized"); 56655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 57655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numAborts , "Number of times interval joining aborted"); 584a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund OlesenSTATISTIC(NumInflated , "Number of register classes inflated"); 59655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 60655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 61655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnableJoining("join-liveintervals", 62655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Coalesce copies (default=true)"), 63655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(true)); 64655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 65655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 66655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaDisableCrossClassJoin("disable-cross-class-join", 67655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Avoid coalescing cross register class copies"), 68655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(false), cl::Hidden); 69655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 70655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 71655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnablePhysicalJoin("join-physregs", 72655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Join physical register copies"), 73655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(false), cl::Hidden); 74655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 75655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 76655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaVerifyCoalescing("verify-coalescing", 77655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Verify machine instrs before and after register coalescing"), 78655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::Hidden); 79655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 808e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesennamespace { 818e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen class RegisterCoalescer : public MachineFunctionPass { 82c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineFunction* MF; 83c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineRegisterInfo* MRI; 84c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetMachine* TM; 85c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterInfo* TRI; 86c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetInstrInfo* TII; 87c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveIntervals *LIS; 88c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveDebugVariables *LDV; 89c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const MachineLoopInfo* Loops; 908e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen AliasAnalysis *AA; 918e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterClassInfo RegClassInfo; 928e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 938e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// JoinedCopies - Keep track of copies eliminated due to coalescing. 948e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// 958e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 32> JoinedCopies; 968e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 978e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// ReMatCopies - Keep track of copies eliminated due to remat. 988e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// 998e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 32> ReMatCopies; 1008e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1018e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// ReMatDefs - Keep track of definition instructions which have 1028e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// been remat'ed. 1038e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 8> ReMatDefs; 1048e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1058e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// joinIntervals - join compatible live intervals 1068e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen void joinIntervals(); 1078e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1088e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting 1098e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// copies that cannot yet be coalesced into the "TryAgain" list. 1108e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen void CopyCoalesceInMBB(MachineBasicBlock *MBB, 1118e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen std::vector<MachineInstr*> &TryAgain); 1128e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1138e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob 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'. 1198e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool JoinCopy(MachineInstr *TheCopy, bool &Again); 1208e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1218e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob 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. 1248e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool JoinIntervals(CoalescerPair &CP); 1258e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1268e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 1278e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// the source value number is defined by a copy from the destination reg 1288e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// see if we can merge these two destination reg valno# into a single 1298e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// value number, eliminating a copy. 1308e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool AdjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 1318e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1328e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// HasOtherReachingDefs - Return true if there are definitions of IntB 1338e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// other than BValNo val# that can reach uses of AValno val# of IntA. 1348e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool HasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 1358e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen VNInfo *AValNo, VNInfo *BValNo); 1368e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1378e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy. 1388e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// If the source value number is defined by a commutable instruction and 1398e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// its other operand is coalesced to the copy dest register, see if we 1408e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// can transform the copy into a noop by commuting the definition. 1418e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 1428e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1438e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// ReMaterializeTrivialDef - If the source of a copy is defined by a 1448e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// trivial computation, replace the copy by rematerialize the definition. 1458e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// If PreserveSrcInt is true, make sure SrcInt is valid after the call. 1468e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool ReMaterializeTrivialDef(LiveInterval &SrcInt, bool PreserveSrcInt, 1476e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen unsigned DstReg, MachineInstr *CopyMI); 1488e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1498e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// shouldJoinPhys - Return true if a physreg copy should be joined. 1508e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool shouldJoinPhys(CoalescerPair &CP); 1518e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1528f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper /// isWinToJoinCrossClass - Return true if it's profitable to coalesce 1538f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper /// two virtual registers from different register classes. 1548f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper bool isWinToJoinCrossClass(unsigned SrcReg, 1558f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned DstReg, 1568f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *SrcRC, 1578f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *DstRC, 1588f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *NewRC); 1598f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper 1608e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 1618e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// update the subregister number if it is not zero. If DstReg is a 1628e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// physical register and the existing subregister number of the def / use 1638e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// being updated is not zero, make sure to set it to the correct physical 1648e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// subregister. 1658e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen void UpdateRegDefsUses(const CoalescerPair &CP); 1668e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1678e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// RemoveDeadDef - If a def of a live interval is now determined dead, 1688e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// remove the val# it defines. If the live interval becomes empty, remove 1698e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// it as well. 1708e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool RemoveDeadDef(LiveInterval &li, MachineInstr *DefMI); 1718e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1728e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// RemoveCopyFlag - If DstReg is no longer defined by CopyMI, clear the 1738e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// VNInfo copy flag for DstReg and all aliases. 1748e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen void RemoveCopyFlag(unsigned DstReg, const MachineInstr *CopyMI); 1758e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1768e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// markAsJoined - Remember that CopyMI has already been joined. 1778e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen void markAsJoined(MachineInstr *CopyMI); 1788e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1798e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// eliminateUndefCopy - Handle copies of undef values. 1808e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 1818e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1828e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen public: 1838e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen static char ID; // Class identification, replacement for typeinfo 1848e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterCoalescer() : MachineFunctionPass(ID) { 1858e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 1868e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen } 1878e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1888e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 1898e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1908e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void releaseMemory(); 1918e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1928e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// runOnMachineFunction - pass entry point 1938e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 1948e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1958e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// print - Implement the dump method. 1968e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void print(raw_ostream &O, const Module* = 0) const; 1978e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen }; 1988e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen} /// end anonymous namespace 1998e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 20027215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesenchar &llvm::RegisterCoalescerPassID = RegisterCoalescer::ID; 20127215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesen 2025b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 2035b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 204655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 205655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 206655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 207655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 208655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 209655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(PHIElimination) 210655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 211655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 2125b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 2135b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 214655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2152c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greenechar RegisterCoalescer::ID = 0; 2162c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 21700258d17cd7152237141648d26e1b096cf0e882bRafael Espindolastatic unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) { 21840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!a) return b; 21940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!b) return a; 22000258d17cd7152237141648d26e1b096cf0e882bRafael Espindola return tri.composeSubRegIndices(a, b); 22140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 22240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 22300258d17cd7152237141648d26e1b096cf0e882bRafael Espindolastatic bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 22400258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &Src, unsigned &Dst, 22500258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &SrcSub, unsigned &DstSub) { 226273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 227273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 228273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen DstSub = MI->getOperand(0).getSubReg(); 229273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Src = MI->getOperand(1).getReg(); 230273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen SrcSub = MI->getOperand(1).getSubReg(); 2315c00e077952d14899c3fc26709c7b2dfd36d0209Jakob Stoklund Olesen } else if (MI->isSubregToReg()) { 23240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 23300258d17cd7152237141648d26e1b096cf0e882bRafael Espindola DstSub = compose(tri, MI->getOperand(0).getSubReg(), 23400258d17cd7152237141648d26e1b096cf0e882bRafael Espindola MI->getOperand(3).getImm()); 23540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Src = MI->getOperand(2).getReg(); 23640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = MI->getOperand(2).getSubReg(); 23704c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } else 23840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 23940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 24040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 24140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 24240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::setRegisters(const MachineInstr *MI) { 243c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SrcReg = DstReg = SubIdx = 0; 244c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen NewRC = 0; 245c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = CrossClass = false; 24640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 24740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 248c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 24940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 250c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Partial = SrcSub || DstSub; 25140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 25240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // If one register is a physreg, it must be Dst. 25340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Src)) { 25440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) 25540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 25640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 25740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 258c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = true; 25940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 26040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 26140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 26240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 26340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 26440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate DstSub on a physreg. 26540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) { 266c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 26740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 26840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = 0; 26940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 27040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 27140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate SrcSub by picking a corresponding Dst superregister. 27240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 273c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 27440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 27540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 27640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else if (!MRI.getRegClass(Src)->contains(Dst)) { 27740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 27840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 27940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 28040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Both registers are virtual. 28140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 2828df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // Both registers have subreg indices. 2838df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub && DstSub) { 2848df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // For now we only handle the case of identical indices in commensurate 2858df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // registers: Dreg:ssub_1 + Dreg:ssub_1 -> Dreg 2868df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // FIXME: Handle Qreg:ssub_3 + Dreg:ssub_1 as QReg:dsub_1 + Dreg. 2878df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub != DstSub) 2888df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 2898df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 2908df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 291e27e1ca3c90b69e78242c98a669337f84ccded7fJakob Stoklund Olesen if (!TRI.getCommonSubClass(DstRC, SrcRC)) 2928df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 29340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = DstSub = 0; 2948df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen } 29540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 29640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // There can be no SrcSub. 29740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 29840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 29940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = SrcSub; 30040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 301c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen assert(!Flipped && "Unexpected flip"); 302c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = true; 30340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 30440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 30540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Find the new register class. 30640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 30740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 30840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 309c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 31040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen else 311e27e1ca3c90b69e78242c98a669337f84ccded7fJakob Stoklund Olesen NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 312c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!NewRC) 31340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 314c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen CrossClass = NewRC != DstRC || NewRC != SrcRC; 31540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 31640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Check our invariants 31740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 31840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 31940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen "Cannot have a physical SubIdx"); 320c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SrcReg = Src; 321c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DstReg = Dst; 322c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SubIdx = DstSub; 32340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 32440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 32540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 32640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::flip() { 327c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (SubIdx || TargetRegisterInfo::isPhysicalRegister(DstReg)) 32840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 329c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen std::swap(SrcReg, DstReg); 330c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = !Flipped; 33140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 33240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 33340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 33440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 33540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!MI) 33640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 33740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 338c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 33940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 34040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 341c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Find the virtual register that is SrcReg. 342c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Dst == SrcReg) { 34340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 34440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 345c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen } else if (Src != SrcReg) { 34640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 34740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 34840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 349c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Now check that Dst matches DstReg. 350c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 35140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 35240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 353c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen assert(!SubIdx && "Inconsistent CoalescerPair state."); 35440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // DstSub could be set for a physreg from INSERT_SUBREG. 35540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 356c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 35740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Full copy of Src. 35840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!SrcSub) 359c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return DstReg == Dst; 36040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // This is a partial register copy. Check that the parts match. 361c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return TRI.getSubReg(DstReg, SrcSub) == Dst; 36240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 363c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // DstReg is virtual. 364c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (DstReg != Dst) 36540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 36640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Registers match, do the subregisters line up? 367c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return compose(TRI, SubIdx, SrcSub) == DstSub; 36840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 36940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 37040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 3715b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 372655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.setPreservesCFG(); 373655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<AliasAnalysis>(); 374655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveIntervals>(); 375655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveIntervals>(); 376655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveDebugVariables>(); 377655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveDebugVariables>(); 378655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<SlotIndexes>(); 379655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<MachineLoopInfo>(); 380655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<MachineLoopInfo>(); 381655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(MachineDominatorsID); 382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(StrongPHIEliminationID); 383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(PHIEliminationID); 384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(TwoAddressInstructionPassID); 385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineFunctionPass::getAnalysisUsage(AU); 386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 3885b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::markAsJoined(MachineInstr *CopyMI) { 389655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Joined copies are not deleted immediately, but kept in JoinedCopies. 390655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola JoinedCopies.insert(CopyMI); 391655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 392655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Mark all register operands of CopyMI as <undef> so they won't affect dead 393655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// code elimination. 394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineInstr::mop_iterator I = CopyMI->operands_begin(), 395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = CopyMI->operands_end(); I != E; ++I) 396655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->isReg()) 397655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I->setIsUndef(true); 398655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 399655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 400655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being the source and IntB being the dest, thus this defines a value number 402655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// in IntB. If the source value number (in IntA) is defined by a copy from B, 403655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// see if we can merge these two pieces of B into a single value number, 404655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// eliminating a copy. For example: 405655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 406655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = B0 407655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 408655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// value number to be replaced with B0 (which simplifies the B liveinterval). 412655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 413655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 414655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 4155b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::AdjustCopiesBackFrom(const CoalescerPair &CP, 416655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 417655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Bail if there is no dst interval - can happen when merging physical subreg 418655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // operations. 419c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(CP.getDstReg())) 420655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 421655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 422655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 423c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 425c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 4262debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 427655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 428655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BLR == IntB.end()) return false; 432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = BLR->valno; 433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 434655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the location that B is defined at. Two options: either this value has 435655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // an unknown definition point or it is defined at CopyIdx. If unknown, we 436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // can't process it. 437655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!BValNo->isDefByCopy()) return false; 438655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 440655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 4412debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 442655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live range might not exist after fun with physreg coalescing. 444655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR == IntA.end()) return false; 445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo = ALR->valno; 446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If it's re-defined by an early clobber somewhere in the live range, then 447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. 448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // See PR3149: 449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 172 %ECX<def> = MOV32rr %reg1039<kill> 450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 180 INLINEASM <es:subl $5,$1 451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, 452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %EAX<kill>, 453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 188 %EAX<def> = MOV32rr %EAX<kill> 455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 196 %ECX<def> = MOV32rr %ECX<kill> 456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 204 %ECX<def> = MOV32rr %ECX<kill> 457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 212 %EAX<def> = MOV32rr %EAX<kill> 458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 220 %EAX<def> = MOV32rr %EAX 459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 228 %reg1039<def> = MOV32rr %ECX<kill> 460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The early clobber operand ties ECX input to the ECX def. 461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live interval of ECX is represented as this: 463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) 464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The coalescer has no idea there was a def in the middle of [174,230]. 465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AValNo->hasRedefByEC()) 466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If AValNo is defined as a copy from IntB, we can potentially process this. 469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the instruction that defines this value number. 470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isCoalescable(AValNo->getCopy())) 471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the LiveRange in IntB that this value number starts with. 474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ValLR = 475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR == IntB.end()) 477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 479655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure that the end of the live range is inside the same block as 480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI. 481655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *ValLREndInst = 482c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 483655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 485655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we now know that ValLR ends in the same block that the CopyMI 487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live-range starts. If there are no intervening live ranges between them in 488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // IntB, we can merge them. 489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR+1 != BLR) return false; 490655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 491655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If a live interval is a physical register, conservatively check if any 492655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // of its aliases is overlapping the live interval of the virtual register. 493655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, do not coalesce. 494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 495c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 496c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(*AS) && IntA.overlaps(LIS->getInterval(*AS))) { 497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 498655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterfere with alias "; 499c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(*AS).print(dbgs(), TRI); 500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "Extending: "; 507c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen IntB.print(dbgs(), TRI); 508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We are about to delete CopyMI, so need to remove it as the 'instruction 512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // that defines this value #'. Update the valnum with the new defining 513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instruction #. 514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo->def = FillerStart; 515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo->setCopy(0); 516655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we can merge them. We need to insert a new liverange: 518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // [ValLR.end, BLR.begin) of either value number, then we merge the 519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // two value numbers. 520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the IntB live range is assigned to a physical register, and if that 523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // physreg has sub-registers, update their live intervals as well. 524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 525c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned *SR = TRI->getSubRegisters(IntB.reg); *SR; ++SR) { 526c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(*SR)) 527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 528c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &SRLI = LIS->getInterval(*SR); 529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SRLI.addRange(LiveRange(FillerStart, FillerEnd, 530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SRLI.getNextValue(FillerStart, 0, 531c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getVNInfoAllocator()))); 532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, merge "B1" into the same value number as "B0". 536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BValNo != ValLR->valno) { 537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If B1 is killed by a PHI, then the merged live range must also be killed 538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // by the same PHI, as B0 and B1 can not overlap. 539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool HasPHIKill = BValNo->hasPHIKill(); 540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.MergeValueNumberInto(BValNo, ValLR->valno); 541655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (HasPHIKill) 542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLR->valno->setHasPHIKill(true); 543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << " result = "; 546c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen IntB.print(dbgs(), TRI); 547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the source instruction was killing the source register before the 551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, unset the isKill marker given the live range has been extended. 552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UIdx != -1) { 554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLREndInst->getOperand(UIdx).setIsKill(false); 555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the copy instruction was killing the destination register before the 558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, find the last use and trim the live range. That will also add the 559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // isKill marker. 560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR->end == CopyIdx) 561c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&IntA); 562655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numExtends; 564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// HasOtherReachingDefs - Return true if there are definitions of IntB 5689b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen/// other than BValNo val# that can reach uses of AValno val# of IntA. 5695b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::HasOtherReachingDefs(LiveInterval &IntA, 5709b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen LiveInterval &IntB, 5719b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen VNInfo *AValNo, 5729b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen VNInfo *BValNo) { 573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 5759b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AI->valno != AValNo) continue; 576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::Ranges::iterator BI = 577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI != IntB.ranges.begin()) 579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola --BI; 580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->valno == BValNo) 582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start <= AI->start && BI->end > AI->start) 584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start > AI->start && BI->start < AI->end) 586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with 593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// IntA being the source and IntB being the dest, thus this defines a value 594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// number in IntB. If the source value number (in IntA) is defined by a 595655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// commutable instruction and its other operand is coalesced to the copy dest 596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// register, see if we can transform the copy into a noop by commuting the 597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// definition. For example, 598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = op A2 B0<kill> 600655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op A3 <- more uses 604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 605655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ==> 606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B2 = op B0 A2<kill> 608655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = B2 <- now an identify copy 610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op B2 <- more uses 612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 6155b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::RemoveCopyByCommutingDef(const CoalescerPair &CP, 616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME: For now, only eliminate the copy by commuting its def when the 618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // source register is a virtual register. We want to guard against cases 619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // where the copy is a back edge copy and commuting the def lengthen the 620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live interval of the source register to the entire loop. 621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys() && CP.isFlipped()) 622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 624655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Bail if there is no dst interval. 625c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(CP.getDstReg())) 626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 6282debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 629655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 631c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 633c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!BValNo || !BValNo->isDefByCopy()) 639655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 640655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 641655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 642655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 643655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 6442debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 645655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(AValNo && "COPY source not live"); 646655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 6479b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen // If other defs can reach uses of this def, then it's not safe to perform 6489b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen // the optimization. 6499b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 651c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 652655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 6545a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isCommutable()) 655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 656655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If DefMI is a two-address instruction then commuting it will change the 657655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // destination register. 658655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 659655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefIdx != -1); 660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UseOpIdx; 661655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 663655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Op1, Op2, NewDstIdx; 664c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Op1 == UseOpIdx) 667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op2; 668655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (Op2 == UseOpIdx) 669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op1; 670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewReg = NewDstMO.getReg(); 675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewReg != IntB.reg || !NewDstMO.isKill()) 676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure there are no other definitions of IntB that would reach the 679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // uses which the new definition can reach. 680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 681655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Abort if the aliases of IntB.reg have values that are not simply the 684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // clobbers from the superreg. 685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) 686c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 687c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(*AS) && 688c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen HasOtherReachingDefs(IntA, LIS->getInterval(*AS), AValNo, 0)) 689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If some of the uses of IntA.reg is already coalesced away, return false. 692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // It's not possible to determine whether it's safe to perform the coalescing. 693b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick for (MachineRegisterInfo::use_nodbg_iterator UI = 694c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->use_nodbg_begin(IntA.reg), 695c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 697c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 699655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end()) 700655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 701655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR->valno == AValNo && JoinedCopies.count(UseMI)) 702655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 703655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 704655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 705655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tRemoveCopyByCommutingDef: " << AValNo->def << '\t' 706655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << *DefMI); 707655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 708655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // At this point we have decided that it is legal to do this 709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // transformation. Start by commuting the instruction. 710655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = DefMI->getParent(); 711c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *NewMI = TII->commuteInstruction(DefMI); 712655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!NewMI) 713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 714655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 715655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TargetRegisterInfo::isVirtualRegister(IntB.reg) && 716c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 718655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewMI != DefMI) { 719c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 7207c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MachineBasicBlock::iterator Pos = DefMI; 7217c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMI); 722655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->erase(DefMI); 723655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 724655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 725655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->getOperand(OpIdx).setIsKill(); 726655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A = or A, B 729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 730655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // B = A 731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 732655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // C = A<kill> 733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 734655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // = B 735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update uses of IntA of the specific Val# with IntB. 737c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 738c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_end(); UI != UE;) { 739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &UseMO = UI.getOperand(); 740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 741655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++UI; 742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(UseMI)) 743655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 744655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isDebugValue()) { 745655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME These don't have an instruction index. Not clear we have enough 746655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // info to decide whether to do this replacement or not. For now do it. 747655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 748655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 749655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 7502debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 751655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 752655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end() || ULR->valno != AValNo) 753655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 754655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 755c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMO.substPhysReg(NewReg, *TRI); 756655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 757655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 758655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI == CopyMI) 759655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isCopy()) 761655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->getOperand(0).getReg() != IntB.reg || 763655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getSubReg()) 764655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 765655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 766655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This copy will become a noop. If it's defining a new val#, merge it into 767655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo. 7682debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = UseIdx.getRegSlot(); 769655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 770655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DVNI) 771655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 772655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 773655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DVNI->def == DefIdx); 774655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 775655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(UseMI); 776655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 777655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 778655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 779655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // is updated. 780655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = BValNo; 781655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->def = AValNo->def; 782655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->setCopy(0); 783655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 784655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 785655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 787655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 788655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 789655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 790655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntA.removeValNo(AValNo); 791655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 792655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCommutes; 793655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 794655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 795655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 796655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial 797655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// computation, replace the copy by rematerialize the definition. 7985b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::ReMaterializeTrivialDef(LiveInterval &SrcInt, 799655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool preserveSrcInt, 800655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstReg, 801655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 8022debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 803655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 804655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(SrcLR != SrcInt.end() && "Live range not found!"); 805655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = SrcLR->valno; 8064ea24e993f179113a9bb76ee152cc490e738c936Jakob Stoklund Olesen if (ValNo->isPHIDef() || ValNo->isUnused()) 807655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 808c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 809655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 810655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 811655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefMI && "Defining instruction disappeared"); 8125a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isAsCheapAsAMove()) 813655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 814c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->isTriviallyReMaterializable(DefMI, AA)) 815655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 816655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SawStore = false; 817c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!DefMI->isSafeToMove(TII, AA, SawStore)) 818655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 8195a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng const MCInstrDesc &MCID = DefMI->getDesc(); 820e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getNumDefs() != 1) 821655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 822655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isImplicitDef()) { 823655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure the copy destination register class fits the instruction 824655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // definition register class. The mismatch can happen as a result of earlier 825655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // extract_subreg, insert_subreg, subreg_to_reg coalescing. 826c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI); 827655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 828c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (MRI->getRegClass(DstReg) != RC) 829655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 830655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (!RC->contains(DstReg)) 831655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 832655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 833655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 834655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyFlag(DstReg, CopyMI); 835655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 836655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = CopyMI->getParent(); 837655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock::iterator MII = 838655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola llvm::next(MachineBasicBlock::iterator(CopyMI)); 8396e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 840655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = prior(MII); 841655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 842655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI may have implicit operands, transfer them over to the newly 843655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerialized instruction. And update implicit def interval valnos. 844655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = CopyMI->getDesc().getNumOperands(), 845655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola e = CopyMI->getNumOperands(); i != e; ++i) { 846655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = CopyMI->getOperand(i); 847655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isReg() && MO.isImplicit()) 848655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->addOperand(MO); 849655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isDef()) 850655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyFlag(MO.getReg(), CopyMI); 851655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 852655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 853655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->copyImplicitOps(CopyMI); 854c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 855655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyMI->eraseFromParent(); 856655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatCopies.insert(CopyMI); 857655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatDefs.insert(DefMI); 858655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "Remat: " << *NewMI); 859655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++NumReMats; 860655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 861655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The source interval can become smaller because we removed a use. 862655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (preserveSrcInt) 863c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&SrcInt); 864655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 865655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 866655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 867655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 868e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 869e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// values, it only removes local variables. When we have a copy like: 870e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 871e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// %vreg1 = COPY %vreg2<undef> 872e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 873e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// We delete the copy and remove the corresponding value number from %vreg1. 874e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// Any uses of that value number are marked as <undef>. 875e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesenbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 876e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen const CoalescerPair &CP) { 877c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 878c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 879e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (SrcInt->liveAt(Idx)) 880e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 881c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 882e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 883e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 884e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 885e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // No intervals are live-in to CopyMI - it is undef. 886e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (CP.isFlipped()) 887e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt = SrcInt; 888e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen SrcInt = 0; 889e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8902debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 891e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen assert(DeadVNI && "No value defined in DstInt"); 892e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt->removeValNo(DeadVNI); 893e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 894e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // Find new undef uses. 895e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator 896c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 897e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen I != E; ++I) { 898e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 899e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 900e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 901e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 902c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(MI); 903e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 904e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 905e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MO.setIsUndef(true); 906e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 907e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 908e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return true; 909e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen} 910e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 911655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 912655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// update the subregister number if it is not zero. If DstReg is a 913655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// physical register and the existing subregister number of the def / use 914655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being updated is not zero, make sure to set it to the correct physical 915655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// subregister. 916655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolavoid 9175b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaRegisterCoalescer::UpdateRegDefsUses(const CoalescerPair &CP) { 918655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DstIsPhys = CP.isPhys(); 919655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg = CP.getSrcReg(); 920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstReg = CP.getDstReg(); 921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SubIdx = CP.getSubIdx(); 922655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 923655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update LiveDebugVariables. 924c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV->renameRegister(SrcReg, DstReg, SubIdx); 925655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 926c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 927655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = I.skipInstruction();) { 928655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A PhysReg copy that won't be coalesced can perhaps be rematerialized 929655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instead. 930655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) { 9318040e064346cc3b78dece7d8ac50593a1c834c46Jakob Stoklund Olesen if (UseMI->isFullCopy() && 932655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(1).getReg() == SrcReg && 933655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getReg() != SrcReg && 934655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getReg() != DstReg && 935655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !JoinedCopies.count(UseMI) && 936c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen ReMaterializeTrivialDef(LIS->getInterval(SrcReg), false, 9376e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen UseMI->getOperand(0).getReg(), UseMI)) 938655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 940655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 941655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned,8> Ops; 942655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Reads, Writes; 943655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 944655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Kills = false, Deads = false; 945655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 946655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Replace SrcReg with DstReg in all UseMI operands. 947655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 948655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = UseMI->getOperand(Ops[i]); 949655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Kills |= MO.isKill(); 950655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Deads |= MO.isDead(); 951655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 952b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen // Make sure we don't create read-modify-write defs accidentally. We 953b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen // assume here that a SrcReg def cannot be joined into a live DstReg. If 954b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen // RegisterCoalescer starts tracking partially live registers, we will 955b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen // need to check the actual LiveInterval to determine if DstReg is live 956b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen // here. 957b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen if (SubIdx && !Reads) 958b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen MO.setIsUndef(); 959b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen 960655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) 961c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substPhysReg(DstReg, *TRI); 962655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 963c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substVirtReg(DstReg, SubIdx, *TRI); 964655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 965655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 966655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This instruction is a copy that will be removed. 967655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(UseMI)) 968655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 969655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 970655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (SubIdx) { 971655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If UseMI was a simple SrcReg def, make sure we didn't turn it into a 972655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // read-modify-write of DstReg. 973655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Deads) 974c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMI->addRegisterDead(DstReg, TRI); 975655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (!Reads && Writes) 976c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMI->addRegisterDefined(DstReg, TRI); 977655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 978655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Kill flags apply to the whole physical register. 979655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys && Kills) 980c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMI->addRegisterKilled(DstReg, TRI); 981655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 982655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 983655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 984655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tupdated: "; 985655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isDebugValue()) 986c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 987655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << *UseMI; 988655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 989655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 990655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 991655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 992655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// removeIntervalIfEmpty - Check if the live interval of a physical register 993655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// is empty, if so remove it and also remove the empty intervals of its 994655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// sub-registers. Return true if live interval is removed. 995c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesenstatic bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *LIS, 996c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterInfo *TRI) { 997655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li.empty()) { 998655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(li.reg)) 999c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned* SR = TRI->getSubRegisters(li.reg); *SR; ++SR) { 1000c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(*SR)) 1001655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1002c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &sli = LIS->getInterval(*SR); 1003655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (sli.empty()) 1004c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(*SR); 1005655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1006c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(li.reg); 1007655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1008655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1009655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1010655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1011655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1012655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// RemoveDeadDef - If a def of a live interval is now determined dead, remove 1013655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// the val# it defines. If the live interval becomes empty, remove it as well. 10145b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::RemoveDeadDef(LiveInterval &li, 1015655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *DefMI) { 10162debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = LIS->getInstructionIndex(DefMI).getRegSlot(); 1017655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); 1018655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DefIdx != MLR->valno->def) 1019655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1020655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li.removeValNo(MLR->valno); 1021c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return removeIntervalIfEmpty(li, LIS, TRI); 1022655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1023655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 10245b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::RemoveCopyFlag(unsigned DstReg, 1025655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const MachineInstr *CopyMI) { 10262debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 1027c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(DstReg)) { 1028c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(DstReg); 1029655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 1030655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LR->valno->def == DefIdx) 1031655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LR->valno->setCopy(0); 1032655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1033655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TargetRegisterInfo::isPhysicalRegister(DstReg)) 1034655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return; 1035c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned* AS = TRI->getAliasSet(DstReg); *AS; ++AS) { 1036c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(*AS)) 1037655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1038c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(*AS); 1039655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 1040655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LR->valno->def == DefIdx) 1041655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LR->valno->setCopy(0); 1042655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1043655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1044655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1045655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// shouldJoinPhys - Return true if a copy involving a physreg should be joined. 1046655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// We need to be careful about coalescing a source physical register with a 1047655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// virtual register. Once the coalescing is done, it cannot be broken and these 1048655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// are not spillable! If the destination interval uses are far away, think 1049655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// twice about coalescing them! 10505b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::shouldJoinPhys(CoalescerPair &CP) { 1051c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen bool Allocatable = LIS->isAllocatable(CP.getDstReg()); 1052c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 1053655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1054655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Always join simple intervals that are defined by a single copy from a 1055655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// reserved register. This doesn't increase register pressure, so it is 1056655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// always beneficial. 1057655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Allocatable && CP.isFlipped() && JoinVInt.containsOneValue()) 1058655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1059655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1060655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!EnablePhysicalJoin) { 1061655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tPhysreg joins disabled.\n"); 1062655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1063655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1064655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1065655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Only coalesce to allocatable physreg, we don't want to risk modifying 1066655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // reserved registers. 1067655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Allocatable) { 1068655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n"); 1069655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 1070655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1071655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1072655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Don't join with physregs that have a ridiculous number of live 1073655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ranges. The data structure performance is really bad when that 1074655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // happens. 1075c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(CP.getDstReg()) && 1076c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.getDstReg()).ranges.size() > 1000) { 1077655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numAborts; 1078655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() 1079655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "\tPhysical register live interval too complicated, abort!\n"); 1080655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1081655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1082655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1083655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME: Why are we skipping this test for partial copies? 1084655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CodeGen/X86/phys_subreg_coalesce-3.ll needs it. 1085655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isPartial()) { 1086c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterClass *RC = MRI->getRegClass(CP.getSrcReg()); 1087655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Threshold = RegClassInfo.getNumAllocatableRegs(RC) * 2; 1088c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen unsigned Length = LIS->getApproximateInstructionCount(JoinVInt); 1089655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Length > Threshold) { 1090655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numAborts; 1091655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n"); 1092655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1093655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1094655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1095655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1096655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1097655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 10988f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper/// isWinToJoinCrossClass - Return true if it's profitable to coalesce 10998f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper/// two virtual registers from different register classes. 11008f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooperbool 11018f391d9330e1a4ed66e72ceac28ed70814f05623Pete CooperRegisterCoalescer::isWinToJoinCrossClass(unsigned SrcReg, 11028f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned DstReg, 11038f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *SrcRC, 11048f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *DstRC, 11058f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const TargetRegisterClass *NewRC) { 11068f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned NewRCCount = RegClassInfo.getNumAllocatableRegs(NewRC); 11078f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // This heuristics is good enough in practice, but it's obviously not *right*. 11088f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // 4 is a magic number that works well enough for x86, ARM, etc. It filter 11098f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // out all but the most restrictive register classes. 11108f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (NewRCCount > 4 || 11118f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // Early exit if the function is fairly small, coalesce aggressively if 11128f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // that's the case. For really special register classes with 3 or 11138f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // fewer registers, be a bit more careful. 11148f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper (LIS->getFuncInstructionCount() / NewRCCount) < 8) 11158f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return true; 11168f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper LiveInterval &SrcInt = LIS->getInterval(SrcReg); 11178f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper LiveInterval &DstInt = LIS->getInterval(DstReg); 11188f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned SrcSize = LIS->getApproximateInstructionCount(SrcInt); 11198f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned DstSize = LIS->getApproximateInstructionCount(DstInt); 11208f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper 11218f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // Coalesce aggressively if the intervals are small compared to the number of 11228f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // registers in the new class. The number 4 is fairly arbitrary, chosen to be 11238f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // less aggressive than the 8 used for the whole function size. 11248f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper const unsigned ThresSize = 4 * NewRCCount; 11258f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (SrcSize <= ThresSize && DstSize <= ThresSize) 11268f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return true; 11278f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper 11288f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper // Estimate *register use density*. If it doubles or more, abort. 11298f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned SrcUses = std::distance(MRI->use_nodbg_begin(SrcReg), 11308f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper MRI->use_nodbg_end()); 11318f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned DstUses = std::distance(MRI->use_nodbg_begin(DstReg), 11328f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper MRI->use_nodbg_end()); 11338f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned NewUses = SrcUses + DstUses; 11348f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned NewSize = SrcSize + DstSize; 11358f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (SrcRC != NewRC && SrcSize > ThresSize) { 11368f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned SrcRCCount = RegClassInfo.getNumAllocatableRegs(SrcRC); 11378f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount) 11388f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return false; 11398f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper } 11408f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (DstRC != NewRC && DstSize > ThresSize) { 11418f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper unsigned DstRCCount = RegClassInfo.getNumAllocatableRegs(DstRC); 11428f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount) 11438f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return false; 11448f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper } 11458f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return true; 11468f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper} 11478f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper 1148655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1149655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1150655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// which are the src/dst of the copy instruction CopyMI. This returns true 1151655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// if the copy was successfully coalesced away. If it is not currently 1152655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// possible to coalesce this interval, but it may be possible if other 1153655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// things get coalesced, then it returns true by reference in 'Again'. 11545b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::JoinCopy(MachineInstr *CopyMI, bool &Again) { 1155655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1156655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = false; 1157655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) 1158655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Already done. 1159655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1160c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 1161655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1162c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen CoalescerPair CP(*TII, *TRI); 1163655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.setRegisters(CopyMI)) { 1164655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tNot coalescable.\n"); 1165655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1166655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1167655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1168655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If they are already joined we continue. 1169655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.getSrcReg() == CP.getDstReg()) { 1170655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1171655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCopy already coalesced.\n"); 1172655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 1173655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1174655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1175e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // Eliminate undefs. 1176e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 1177e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen markAsJoined(CopyMI); 1178e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 1179e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; // Not coalescable. 1180e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 1181e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 1182c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1183c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSubIdx()) 1184655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "\n"); 1185655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1186655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Enforce policies. 1187655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1188655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!shouldJoinPhys(CP)) { 1189655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Before giving up coalescing, if definition of source is defined by 1190655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // trivial computation, try rematerializing it. 1191655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 1192c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen ReMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), true, 11936e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1194655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1195655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1196655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1197655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1198655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Avoid constraining virtual register regclass too much. 1199655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1200655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCross-class to " << CP.getNewRC()->getName() << ".\n"); 1201655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DisableCrossClassJoin) { 1202655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCross-class joins disabled.\n"); 1203655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1204655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 12058f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(), 12068f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper MRI->getRegClass(CP.getSrcReg()), 12078f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper MRI->getRegClass(CP.getDstReg()), 12088f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper CP.getNewRC())) { 12098f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper DEBUG(dbgs() << "\tAvoid coalescing to constrained register class.\n"); 12108f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper Again = true; // May be possible to coalesce later. 12118f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper return false; 12128f391d9330e1a4ed66e72ceac28ed70814f05623Pete Cooper } 1213655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1214655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1215655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When possible, let DstReg be the larger interval. 1216c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!CP.getSubIdx() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1217c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.getDstReg()).ranges.size()) 1218655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.flip(); 1219655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1220655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1221655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, attempt to join these two intervals. On failure, this returns false. 1222655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, if one of the intervals being joined is a physreg, this method 1223655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1224655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been modified, so we can use this information below to update aliases. 1225655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinIntervals(CP)) { 1226655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing failed. 1227655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1228655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If definition of source is defined by trivial computation, try 1229655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerializing it. 1230655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 1231c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen ReMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), true, 12326e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1233655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1234655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1235655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we can eliminate the copy without merging the live ranges, do so now. 1236655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isPartial()) { 1237655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AdjustCopiesBackFrom(CP, CopyMI) || 1238655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyByCommutingDef(CP, CopyMI)) { 1239655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1240655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tTrivial!\n"); 1241655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1242655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1243655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1244655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1245655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, we are unable to join the intervals. 1246655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tInterference!\n"); 1247655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1248655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1249655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1250655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1251655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing to a virtual register that is of a sub-register class of the 1252655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // other. Make sure the resulting register is set to the right register class. 1253655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1254655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCrossRCs; 1255c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1256655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1257655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1258655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Remember to delete the copy instruction. 1259655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1260655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1261655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UpdateRegDefsUses(CP); 1262655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1263655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we have extended the live range of a physical register, make sure we 1264655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // update live-in lists as well. 1265655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1266655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineBasicBlock*, 16> BlockSeq; 1267655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the 1268655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ranges for this, and they are preserved. 1269c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &SrcInt = LIS->getInterval(CP.getSrcReg()); 1270655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end(); 1271655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I ) { 1272c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->findLiveInMBBs(I->start, I->end, BlockSeq); 1273655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) { 1274655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock &block = *BlockSeq[idx]; 1275655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!block.isLiveIn(CP.getDstReg())) 1276655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola block.addLiveIn(CP.getDstReg()); 1277655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1278655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BlockSeq.clear(); 1279655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1280655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1281655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1282655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // SrcReg is guarateed to be the register whose live interval that is 1283655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // being merged. 1284c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(CP.getSrcReg()); 1285655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1286655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update regalloc hint. 1287c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1288655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1289655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1290c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &DstInt = LIS->getInterval(CP.getDstReg()); 1291655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\tJoined. Result = "; 1292c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DstInt.print(dbgs(), TRI); 1293655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 1294655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1295655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1296655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numJoins; 1297655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1298655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1299655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1300655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1301655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// compute what the resultant value numbers for each value in the input two 1302655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ranges will be. This is complicated by copies between the two which can 1303655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// and will commonly cause multiple value numbers to be merged into one. 1304655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1305655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// VN is the value number that we're trying to resolve. InstDefiningValue 1306655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// keeps track of the new InstDefiningValue assignment for the result 1307655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1308655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// whether a value in this or other is a copy from the opposite set. 1309655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1310655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// already been assigned. 1311655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1312655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1313655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// contains the value number the copy is from. 1314655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1315655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic unsigned ComputeUltimateVN(VNInfo *VNI, 1316655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> &NewVNInfo, 1317655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1318655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1319655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &ThisValNoAssignments, 1320655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &OtherValNoAssignments) { 1321655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1322655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1323655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the VN has already been computed, just return it. 1324655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ThisValNoAssignments[VN] >= 0) 1325655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN]; 1326655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1327655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1328655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this val is not a copy from the other val, then it must be a new value 1329655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // number in the destination. 1330655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1331655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I == ThisFromOther.end()) { 1332655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1333655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1334655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1335655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *OtherValNo = I->second; 1336655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1337655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, this *is* a copy from the RHS. If the other side has already 1338655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been computed, return it. 1339655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (OtherValNoAssignments[OtherValNo->id] >= 0) 1340655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1341655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1342655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Mark this value number as currently being computed, then ask what the 1343655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ultimate value # of the other value is. 1344655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ThisValNoAssignments[VN] = -2; 1345655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UltimateVN = 1346655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1347655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola OtherValNoAssignments, ThisValNoAssignments); 1348655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = UltimateVN; 1349655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1350655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 13510c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13520c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// Find out if we have something like 13530c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 13540c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = X 13550c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// if so, we can pretend this is actually 13560c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// A = X 13570c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// B = A 13580c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// which allows us to coalesce A and B. 13598f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola// VNI is the definition of B. LR is the life range of A that includes 13600c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola// the slot just before B. If we return true, we add "B = X" to DupCopies. 1361b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick// This implies that A dominates B. 13621c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindolastatic bool RegistersDefinedFromSameValue(LiveIntervals &li, 13631c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola const TargetRegisterInfo &tri, 13648f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola CoalescerPair &CP, 13658f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola VNInfo *VNI, 13660c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola LiveRange *LR, 13670c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> &DupCopies) { 13680c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // FIXME: This is very conservative. For example, we don't handle 13690c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // physical registers. 13700c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13718f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola MachineInstr *MI = VNI->getCopy(); 13728f1bdac3eba0e065c8ebe2a9c671e299c1fc6797Rafael Espindola 13730c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!MI->isFullCopy() || CP.isPartial() || CP.isPhys()) 13740c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 13750c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13761c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola unsigned Dst = MI->getOperand(0).getReg(); 13771c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola unsigned Src = MI->getOperand(1).getReg(); 13781c8b97cbc03e0e1966d244a27b55e74bde35671eRafael Espindola 13790c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(Src) || 13800c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola !TargetRegisterInfo::isVirtualRegister(Dst)) 13810c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 13820c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13830c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned A = CP.getDstReg(); 13840c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned B = CP.getSrcReg(); 13850c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13860c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (B == Dst) 13870c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola std::swap(A, B); 13880c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola assert(Dst == A); 13890c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13900c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola VNInfo *Other = LR->valno; 13910c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!Other->isDefByCopy()) 13920c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 13930c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola const MachineInstr *OtherMI = Other->getCopy(); 13940c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13950c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!OtherMI->isFullCopy()) 13960c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 13970c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 13980c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned OtherDst = OtherMI->getOperand(0).getReg(); 13990c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 14000c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 14010c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!TargetRegisterInfo::isVirtualRegister(OtherSrc) || 14020c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola !TargetRegisterInfo::isVirtualRegister(OtherDst)) 14030c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 14040c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 14050c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola assert(OtherDst == B); 14060c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 14070c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (Src != OtherSrc) 14080c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return false; 14090c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1410a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola // If the copies use two different value numbers of X, we cannot merge 1411a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola // A and B. 141265268575c419a890052a446d28329f9e81302a05Rafael Espindola LiveInterval &SrcInt = li.getInterval(Src); 1413b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick // getVNInfoBefore returns NULL for undef copies. In this case, the 1414b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick // optimization is still safe. 1415b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick if (SrcInt.getVNInfoBefore(Other->def) != SrcInt.getVNInfoBefore(VNI->def)) 1416a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola return false; 1417a9badd250cac2e5090eb950bb0456c37ee6c8f7aRafael Espindola 14180c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola DupCopies.push_back(MI); 14190c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 14200c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola return true; 14210c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola} 14220c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1423655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// JoinIntervals - Attempt to join these two intervals. On failure, this 1424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// returns false. 14255b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::JoinIntervals(CoalescerPair &CP) { 1426c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1427c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), TRI); dbgs() << "\n"; }); 1428655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If a live interval is a physical register, check for interference with any 1430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // aliases. The interference check implemented here is a bit more conservative 1431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // than the full interfeence check below. We allow overlapping live ranges 1432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // only when one is a copy of the other. 1433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1434c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned *AS = TRI->getAliasSet(CP.getDstReg()); *AS; ++AS){ 1435c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->hasInterval(*AS)) 1436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1437c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const LiveInterval &LHS = LIS->getInterval(*AS); 1438655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator LI = LHS.begin(); 1439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::const_iterator RI = RHS.begin(), RE = RHS.end(); 1440655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RI != RE; ++RI) { 1441655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LI = std::lower_bound(LI, LHS.end(), RI->start); 1442655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Does LHS have an overlapping live range starting before RI? 1443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if ((LI != LHS.begin() && LI[-1].end > RI->start) && 1444655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola (RI->start != RI->valno->def || 1445c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !CP.isCoalescable(LIS->getInstructionFromIndex(RI->start)))) { 1446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterference from alias: "; 1448c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LHS.print(dbgs(), TRI); 1449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n\t\tOverlap at " << RI->start << " and no copy.\n"; 1450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Check that LHS ranges beginning in this range are copies. 1455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; LI != LHS.end() && LI->start < RI->end; ++LI) { 1456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LI->start != LI->valno->def || 1457c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !CP.isCoalescable(LIS->getInstructionFromIndex(LI->start))) { 1458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterference from alias: "; 1460c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LHS.print(dbgs(), TRI); 1461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n\t\tDef at " << LI->start << " is not a copy.\n"; 1462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Compute the final value assignment, assuming that the live ranges can be 1471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // coalesced. 1472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> LHSValNoAssignments; 1473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> RHSValNoAssignments; 1474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> NewVNInfo; 1477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 14780c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola SmallVector<MachineInstr*, 8> DupCopies; 14790c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1480c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 1481c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), TRI); dbgs() << "\n"; }); 1482655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1483655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Loop over the value numbers of the LHS, seeing if any are defined from 1484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the RHS. 1485655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 1489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1490655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1491655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Never join with a register that has EarlyClobber redefs. 1492655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasRedefByEC()) 1493655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 149515e96be3c70ab2e4a50c505c2b90e4ce1095dbd6Rafael Espindola // Figure out the value # from the RHS. 149615e96be3c70ab2e4a50c505c2b90e4ce1095dbd6Rafael Espindola LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 149715e96be3c70ab2e4a50c505c2b90e4ce1095dbd6Rafael Espindola // The copy could be to an aliased physreg. 149815e96be3c70ab2e4a50c505c2b90e4ce1095dbd6Rafael Espindola if (!lr) continue; 14990c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 15000c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // DstReg is known to be a register in the LHS interval. If the src is 15010c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // from the RHS interval, we can use its value #. 15020c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola MachineInstr *MI = VNI->getCopy(); 15030c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!CP.isCoalescable(MI) && 1504c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, lr, DupCopies)) 15050c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola continue; 15060c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS[VNI] = lr->valno; 1508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Loop over the value numbers of the RHS, seeing if any are defined from 1511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the LHS. 1512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 1516655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Never join with a register that has EarlyClobber redefs. 1519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasRedefByEC()) 1520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Figure out the value # from the LHS. 1523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 1524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The copy could be to an aliased physreg. 1525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!lr) continue; 15260c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 15270c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // DstReg is known to be a register in the RHS interval. If the src is 15280c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // from the LHS interval, we can use its value #. 15290c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola MachineInstr *MI = VNI->getCopy(); 15300c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola if (!CP.isCoalescable(MI) && 1531c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, lr, DupCopies)) 15320c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola continue; 15330c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 1534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS[VNI] = lr->valno; 1535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1541655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments, RHSValNoAssignments); 1550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this value number isn't a copy from the LHS, it's a new number. 1558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1562655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments, LHSValNoAssignments); 1567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // interval lists to see if these intervals are coalescable. 1571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator I = LHS.begin(); 1572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator IE = LHS.end(); 1573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator J = RHS.begin(); 1574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator JE = RHS.end(); 1575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Skip ahead until the first place of potential sharing. 1577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != IE && J != JE) { 1578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I = std::upper_bound(I, IE, J->start); 1580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != LHS.begin()) --I; 1581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (J->start < I->start) { 1582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola J = std::upper_bound(J, JE, I->start); 1583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (J != RHS.begin()) --J; 1584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (I != IE && J != JE) { 1588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Determine if these two live ranges overlap. 1589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Overlaps; 1590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Overlaps = I->end > J->start; 1592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Overlaps = J->end > I->start; 1594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1595655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, check value # info to determine if they are really different. 1597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Overlaps) { 1598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the live range overlap will map to the same value number in the 1599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // result liverange, we can still coalesce them. If not, we can't. 1600655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[I->valno->id] != 1601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[J->valno->id]) 1602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If it's re-defined by an early clobber somewhere in the live range, 1604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // then conservatively abort coalescing. 1605655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC()) 1606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1608655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->end < J->end) 1610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++I; 1611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++J; 1613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 1617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 1618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned LHSValID = LHSValNoAssignments[VNI->id]; 1620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[LHSValID]->setHasPHIKill(true); 1622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1624655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1625655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 1626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 1627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1628655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned RHSValID = RHSValNoAssignments[VNI->id]; 1629655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[RHSValID]->setHasPHIKill(true); 1631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments.empty()) 1634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.push_back(-1); 1635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments.empty()) 1636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.push_back(-1); 1637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 163865268575c419a890052a446d28329f9e81302a05Rafael Espindola SmallVector<unsigned, 8> SourceRegisters; 16390c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 16400c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola E = DupCopies.end(); I != E; ++I) { 16410c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola MachineInstr *MI = *I; 16420c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 16430c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // We have pretended that the assignment to B in 16440c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 16450c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // B = X 16460c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // was actually a copy from A. Now that we decided to coalesce A and B, 16470c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // transform the code into 16480c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // A = X 16490c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // X = X 16500c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola // and mark the X as coalesced to keep the illusion. 16510c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola unsigned Src = MI->getOperand(1).getReg(); 165265268575c419a890052a446d28329f9e81302a05Rafael Espindola SourceRegisters.push_back(Src); 1653c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MI->getOperand(0).substVirtReg(Src, 0, *TRI); 16540c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 16550c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola markAsJoined(MI); 16560c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola } 16570c13e9471a4aa32207923d84c0990eeb9bb898abRafael Espindola 165865268575c419a890052a446d28329f9e81302a05Rafael Espindola // If B = X was the last use of X in a liverange, we have to shrink it now 165965268575c419a890052a446d28329f9e81302a05Rafael Espindola // that B = X is gone. 166065268575c419a890052a446d28329f9e81302a05Rafael Espindola for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 166165268575c419a890052a446d28329f9e81302a05Rafael Espindola E = SourceRegisters.end(); I != E; ++I) { 1662c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&LIS->getInterval(*I)); 166365268575c419a890052a446d28329f9e81302a05Rafael Espindola } 166465268575c419a890052a446d28329f9e81302a05Rafael Espindola 1665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we get here, we know that we can coalesce the live ranges. Ask the 1666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // intervals to coalesce themselves now. 1667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1668c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI); 1669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolanamespace { 1673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DepthMBBCompare - Comparison predicate that sort first based on the loop 1674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // depth of the basic block (the unsigned), and then on the MBB number. 1675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola struct DepthMBBCompare { 1676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Deeper loops first 1679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHS.first != RHS.first) 1680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.first > RHS.first; 1681655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Prefer blocks that are more connected in the CFG. This takes care of 1683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the most difficult copies first while intervals are short. 1684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1686655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (cl != cr) 1687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return cl > cr; 1688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // As a last resort, sort by block number. 1690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.second->getNumber() < RHS.second->getNumber(); 1691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }; 1693655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1694655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 16955b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::CopyCoalesceInMBB(MachineBasicBlock *MBB, 1696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<MachineInstr*> &TryAgain) { 1697655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << MBB->getName() << ":\n"); 1698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1699655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> VirtCopies; 1700655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> PhysCopies; 1701655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> ImpDefCopies; 1702655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1703655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MII != E;) { 1704655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *Inst = MII++; 1705655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1706655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this isn't a copy nor a extract_subreg, we can't join intervals. 1707655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg, DstReg; 1708655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Inst->isCopy()) { 1709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstReg = Inst->getOperand(0).getReg(); 1710655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SrcReg = Inst->getOperand(1).getReg(); 1711655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (Inst->isSubregToReg()) { 1712655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstReg = Inst->getOperand(0).getReg(); 1713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SrcReg = Inst->getOperand(2).getReg(); 1714655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else 1715655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1716655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 1718655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 1719c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(SrcReg) && LIS->getInterval(SrcReg).empty()) 1720655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ImpDefCopies.push_back(Inst); 1721655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (SrcIsPhys || DstIsPhys) 1722655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola PhysCopies.push_back(Inst); 1723655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1724655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VirtCopies.push_back(Inst); 1725655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1726655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Try coalescing implicit copies and insert_subreg <undef> first, 1728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // followed by copies to / from physical registers, then finally copies 1729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // from virtual registers to virtual registers. 1730655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) { 1731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = ImpDefCopies[i]; 1732655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1734655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1737655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { 1738655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = PhysCopies[i]; 1739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1741655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1743655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1744655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { 1745655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = VirtCopies[i]; 1746655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1747655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1748655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1749655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1750655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1751655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1752655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 17535b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::joinIntervals() { 1754655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1755655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1756655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<MachineInstr*> TryAgainList; 1757c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Loops->empty()) { 1758655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If there are no loops in the function, join intervals in function order. 1759c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 1760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I) 1761655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyCoalesceInMBB(I, TryAgainList); 1762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1763655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, join intervals in inner loops before other intervals. 1764655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Unfortunately we can't just iterate over loop hierarchy here because 1765655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // there may be more MBB's than BB's. Collect MBB's for sorting. 1766655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1767655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join intervals in the function prolog first. We want to join physical 1768655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers with virtual registers before the intervals got too long. 1769655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1770c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 1771655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = I; 1772c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 1773655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1774655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1775655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Sort by loop depth. 1776655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1777655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1778655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Finally, join intervals in loop nest order. 1779655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1780655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyCoalesceInMBB(MBBs[i].second, TryAgainList); 1781655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1782655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1783655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Joining intervals can allow other intervals to be joined. Iteratively join 1784655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // until we make no progress. 1785655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool ProgressMade = true; 1786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (ProgressMade) { 1787655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ProgressMade = false; 1788655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1789655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 1790655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *&TheCopy = TryAgainList[i]; 1791655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TheCopy) 1792655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1793655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1794655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1795655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Success = JoinCopy(TheCopy, Again); 1796655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Success || !Again) { 1797655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TheCopy= 0; // Mark this one as done. 1798655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ProgressMade = true; 1799655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1800655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1801655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1802655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1803655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 18045b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::releaseMemory() { 1805655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola JoinedCopies.clear(); 1806655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatCopies.clear(); 1807655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatDefs.clear(); 1808655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1809655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 18105b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1811c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF = &fn; 1812c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI = &fn.getRegInfo(); 1813c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TM = &fn.getTarget(); 1814c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 1815c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TII = TM->getInstrInfo(); 1816c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 1817c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV = &getAnalysis<LiveDebugVariables>(); 1818655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AA = &getAnalysis<AliasAnalysis>(); 1819c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 1820655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1821655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1822655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "********** Function: " 1823c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen << ((Value*)MF->getFunction())->getName() << '\n'); 1824655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1825655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1826c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "Before register coalescing"); 1827655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1828655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RegClassInfo.runOnMachineFunction(fn); 1829655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1830655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join (coalesce) intervals if requested. 1831655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (EnableJoining) { 1832655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola joinIntervals(); 1833655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1834655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "********** INTERVALS POST JOINING **********\n"; 1835c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); 1836655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I){ 1837c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen I->second->print(dbgs(), TRI); 1838655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 1839655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1840655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1841655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1842655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1843655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Perform a final pass over the instructions and compute spill weights 1844655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // and remove identity moves. 18454a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen SmallVector<unsigned, 4> DeadDefs, InflateRegs; 1846c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineFunction::iterator mbbi = MF->begin(), mbbe = MF->end(); 1847655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mbbi != mbbe; ++mbbi) { 1848655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock* mbb = mbbi; 1849655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1850655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii != mie; ) { 1851655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *MI = mii; 1852655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(MI)) { 1853655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Delete all coalesced copies. 1854655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DoDelete = true; 1855655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(MI->isCopyLike() && "Unrecognized copy instruction"); 1856655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg(); 18574a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen unsigned DstReg = MI->getOperand(0).getReg(); 18584a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 18594a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // Collect candidates for register class inflation. 18604a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(SrcReg) && 18614a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen RegClassInfo.isProperSubClass(MRI->getRegClass(SrcReg))) 18624a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.push_back(SrcReg); 18634a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(DstReg) && 18644a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen RegClassInfo.isProperSubClass(MRI->getRegClass(DstReg))) 18654a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.push_back(DstReg); 18664a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 1867655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(SrcReg) && 1868655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->getNumOperands() > 2) 1869655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Do not delete extract_subreg, insert_subreg of physical 1870655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers unless the definition is dead. e.g. 1871655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1 1872655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // or else the scavenger may complain. LowerSubregs will 1873655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // delete them later. 1874655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DoDelete = false; 1875655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1876655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MI->allDefsAreDead()) { 1877655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(SrcReg) && 1878c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->hasInterval(SrcReg)) 1879c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&LIS->getInterval(SrcReg)); 1880655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DoDelete = true; 1881655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1882655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DoDelete) { 1883655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We need the instruction to adjust liveness, so make it a KILL. 1884655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MI->isSubregToReg()) { 1885655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->RemoveOperand(3); 1886655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->RemoveOperand(1); 1887655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1888c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MI->setDesc(TII->get(TargetOpcode::KILL)); 1889655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = llvm::next(mii); 1890655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1891c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 1892655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = mbbi->erase(mii); 1893655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numPeep; 1894655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1895655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1896655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1897655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1898655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Now check if this is a remat'ed def instruction which is now dead. 1899655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ReMatDefs.count(MI)) { 1900655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool isDead = true; 1901655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1902655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const MachineOperand &MO = MI->getOperand(i); 1903655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!MO.isReg()) 1904655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1905655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Reg = MO.getReg(); 1906655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Reg) 1907655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 19084a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg)) { 1909655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.push_back(Reg); 19104a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // Remat may also enable register class inflation. 19114a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (RegClassInfo.isProperSubClass(MRI->getRegClass(Reg))) 19124a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.push_back(Reg); 19134a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 1914655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isDead()) 1915655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1916655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(Reg) || 1917c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !MRI->use_nodbg_empty(Reg)) { 1918655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola isDead = false; 1919655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola break; 1920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1922655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (isDead) { 1923655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (!DeadDefs.empty()) { 1924655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DeadDef = DeadDefs.back(); 1925655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.pop_back(); 1926c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen RemoveDeadDef(LIS->getInterval(DeadDef), MI); 1927655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1928c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(mii); 1929655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = mbbi->erase(mii); 1930655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1931655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else 1932655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.clear(); 1933655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1934655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1935655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++mii; 1936655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1937655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Check for now unnecessary kill flags. 1938c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->isNotInMIMap(MI)) continue; 19392debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = LIS->getInstructionIndex(MI).getRegSlot(); 1940655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1941655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = MI->getOperand(i); 1942655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!MO.isReg() || !MO.isKill()) continue; 1943655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned reg = MO.getReg(); 1944c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!reg || !LIS->hasInterval(reg)) continue; 1945c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!LIS->getInterval(reg).killedAt(DefIdx)) { 1946655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MO.setIsKill(false); 1947655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1948655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1949655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When leaving a kill flag on a physreg, check if any subregs should 1950655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // remain alive. 1951655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TargetRegisterInfo::isPhysicalRegister(reg)) 1952655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1953c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (const unsigned *SR = TRI->getSubRegisters(reg); 1954655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned S = *SR; ++SR) 1955c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (LIS->hasInterval(S) && LIS->getInterval(S).liveAt(DefIdx)) 1956c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MI->addRegisterDefined(S, TRI); 1957655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1958655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1959655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1960655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 19614a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // After deleting a lot of copies, register classes may be less constrained. 19624a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // Removing sub-register opreands may alow GR32_ABCD -> GR32 and DPR_VFP2 -> 19634a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // DPR inflation. 19644a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 19654a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 19664a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.end()); 19674a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 19684a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 19694a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen unsigned Reg = InflateRegs[i]; 19704a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(Reg)) 19714a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen continue; 19724a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->recomputeRegClass(Reg, *TM)) { 19734a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 19744a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << '\n'); 19754a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen ++NumInflated; 19764a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 19774a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 19784a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 1979655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dump()); 1980c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(LDV->dump()); 1981655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1982c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "After register coalescing"); 1983655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1984655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1985655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1986655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// print - Implement the dump method. 19875b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1988c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->print(O, m); 1989655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1990