RegisterCoalescer.cpp revision 2344abc939b29ab80bbd247995a0ceb2efa5938b
12c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 22c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 32c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// The LLVM Compiler Infrastructure 42c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 72c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 82c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 92c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 102c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// This file implements the generic RegisterCoalescer interface which 112c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// is used as the common interface used by all clients and 122c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// implementations of register coalescing. 132c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene// 142c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene//===----------------------------------------------------------------------===// 152c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 164281e20aab7f1fe1b35b31c9237ad89c20937e02Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 17fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 18655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "LiveDebugVariables.h" 198e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen#include "VirtRegMap.h" 20655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 21655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Pass.h" 22655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Value.h" 23bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/OwningPtr.h" 24bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/STLExtras.h" 25bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/SmallSet.h" 26bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 27bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Analysis/AliasAnalysis.h" 282c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/LiveIntervalAnalysis.h" 30bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/LiveRangeEdit.h" 31655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineFrameInfo.h" 32655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineInstr.h" 33bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/MachineInstr.h" 34655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineLoopInfo.h" 35655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineRegisterInfo.h" 36bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 37655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/Passes.h" 381525260b3e50cc578939ef41b60609689eecfdd2Andrew Trick#include "llvm/CodeGen/RegisterClassInfo.h" 39655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/CommandLine.h" 40655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/Debug.h" 41655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/ErrorHandling.h" 42655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/raw_ostream.h" 43bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 44bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 45bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetMachine.h" 46bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetOptions.h" 47bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen#include "llvm/Target/TargetRegisterInfo.h" 48ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick#include "llvm/Target/TargetSubtargetInfo.h" 49655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <algorithm> 50655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <cmath> 512c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greeneusing namespace llvm; 522c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 53655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numJoins , "Number of interval joins performed"); 54655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 55655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCommutes , "Number of instruction commuting performed"); 56655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numExtends , "Number of copies extended"); 57655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(NumReMats , "Number of instructions re-materialized"); 584a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund OlesenSTATISTIC(NumInflated , "Number of register classes inflated"); 59d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund OlesenSTATISTIC(NumLaneConflicts, "Number of dead lane conflicts tested"); 60d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund OlesenSTATISTIC(NumLaneResolves, "Number of dead lane conflicts resolved"); 61655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 62655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 63655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnableJoining("join-liveintervals", 64655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Coalesce copies (default=true)"), 65655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(true)); 66655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 673c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// Temporary flag to test critical edge unsplitting. 68ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trickstatic cl::opt<cl::boolOrDefault> 693c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew TrickEnableJoinSplits("join-splitedges", 70ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick cl::desc("Coalesce copies on split edges (default=subtarget)"), 71ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick cl::init(cl::BOU_UNSET), cl::Hidden); 723c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 73265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick// Temporary flag to test global copy optimization. 74ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trickstatic cl::opt<cl::boolOrDefault> 75265058d9239e6867d06dc8aa40db5f33390abd17Andrew TrickEnableGlobalCopies("join-globalcopies", 76ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick cl::desc("Coalesce copies that span blocks (default=subtarget)"), 77ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick cl::init(cl::BOU_UNSET), cl::Hidden); 78265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 79655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 80655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaVerifyCoalescing("verify-coalescing", 81655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Verify machine instrs before and after register coalescing"), 82655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::Hidden); 83655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 848e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesennamespace { 85bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen class RegisterCoalescer : public MachineFunctionPass, 86bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen private LiveRangeEdit::Delegate { 87c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineFunction* MF; 88c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineRegisterInfo* MRI; 89c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetMachine* TM; 90c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetRegisterInfo* TRI; 91c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const TargetInstrInfo* TII; 92c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveIntervals *LIS; 93c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveDebugVariables *LDV; 94c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen const MachineLoopInfo* Loops; 958e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen AliasAnalysis *AA; 968e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterClassInfo RegClassInfo; 978e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 98ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick /// \brief True if the coalescer should aggressively coalesce global copies 99ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick /// in favor of keeping local copies. 100ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick bool JoinGlobalCopies; 101ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 102ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick /// \brief True if the coalescer should aggressively coalesce fall-thru 103ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick /// blocks exclusively containing copies. 104ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick bool JoinSplitEdges; 105ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 106b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// WorkList - Copy instructions yet to be coalesced. 107b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> WorkList; 108265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick SmallVector<MachineInstr*, 8> LocalWorkList; 109b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 110bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// ErasedInstrs - Set of instruction pointers that have been erased, and 111bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// that may be present in WorkList. 112bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallPtrSet<MachineInstr*, 8> ErasedInstrs; 113bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 114bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// Dead instructions that are about to be deleted. 115bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallVector<MachineInstr*, 8> DeadDefs; 116bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 11703c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen /// Virtual registers to be considered for register class inflation. 11803c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen SmallVector<unsigned, 8> InflateRegs; 11903c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen 120bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// Recursively eliminate dead defs in DeadDefs. 121bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen void eliminateDeadDefs(); 122bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 123bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen /// LiveRangeEdit callback. 124bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen void LRE_WillEraseInstruction(MachineInstr *MI); 125bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 126265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick /// coalesceLocals - coalesce the LocalWorkList. 127265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick void coalesceLocals(); 128265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 1299790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinAllIntervals - join compatible live intervals 1309790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen void joinAllIntervals(); 1318e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1329790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// copyCoalesceInMBB - Coalesce copies in the specified MBB, putting 133b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /// copies that cannot yet be coalesced into WorkList. 134b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen void copyCoalesceInMBB(MachineBasicBlock *MBB); 135b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 136265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick /// copyCoalesceWorkList - Try to coalesce all copies in CurrList. Return 137265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick /// true if any progress was made. 138265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick bool copyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList); 1398e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1409790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 1418e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// which are the src/dst of the copy instruction CopyMI. This returns 1428e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// true if the copy was successfully coalesced away. If it is not 1438e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// currently possible to coalesce this interval, but it may be possible if 1448e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// other things get coalesced, then it returns true by reference in 1458e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// 'Again'. 1469790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool joinCopy(MachineInstr *TheCopy, bool &Again); 1478e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1489790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// joinIntervals - Attempt to join these two intervals. On failure, this 1498e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// returns false. The output "SrcInt" will not have been modified, so we 1508e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// can use this information below to update aliases. 1519790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool joinIntervals(CoalescerPair &CP); 1528e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 153c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Attempt joining two virtual registers. Return true on success. 154c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen bool joinVirtRegs(CoalescerPair &CP); 155c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 15692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen /// Attempt joining with a reserved physreg. 15792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen bool joinReservedPhysReg(CoalescerPair &CP); 15892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1599790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// adjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 1608e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// the source value number is defined by a copy from the destination reg 1618e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// see if we can merge these two destination reg valno# into a single 1628e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// value number, eliminating a copy. 1639790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool adjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 1648e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1659790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// hasOtherReachingDefs - Return true if there are definitions of IntB 1668e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// other than BValNo val# that can reach uses of AValno val# of IntA. 1679790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool hasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 1688e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen VNInfo *AValNo, VNInfo *BValNo); 1698e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1709790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// removeCopyByCommutingDef - We found a non-trivially-coalescable copy. 1718e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// If the source value number is defined by a commutable instruction and 1728e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// its other operand is coalesced to the copy dest register, see if we 1738e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// can transform the copy into a noop by commuting the definition. 1749790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen bool removeCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 1758e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1769790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// reMaterializeTrivialDef - If the source of a copy is defined by a 1778e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// trivial computation, replace the copy by rematerialize the definition. 17867ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen bool reMaterializeTrivialDef(LiveInterval &SrcInt, unsigned DstReg, 17967ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen MachineInstr *CopyMI); 1808e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 18134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen /// canJoinPhys - Return true if a physreg copy should be joined. 18234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen bool canJoinPhys(CoalescerPair &CP); 1838e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1849790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen /// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 1858e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// update the subregister number if it is not zero. If DstReg is a 1868e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// physical register and the existing subregister number of the def / use 1878e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// being updated is not zero, make sure to set it to the correct physical 1888e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// subregister. 189ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen void updateRegDefsUses(unsigned SrcReg, unsigned DstReg, unsigned SubIdx); 1908e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1918e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// eliminateUndefCopy - Handle copies of undef values. 1928e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 1938e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 1948e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen public: 1958e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen static char ID; // Class identification, replacement for typeinfo 1968e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen RegisterCoalescer() : MachineFunctionPass(ID) { 1978e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 1988e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen } 1998e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 2008e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void getAnalysisUsage(AnalysisUsage &AU) const; 2018e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 2028e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void releaseMemory(); 2038e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 2048e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// runOnMachineFunction - pass entry point 2058e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual bool runOnMachineFunction(MachineFunction&); 2068e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 2078e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen /// print - Implement the dump method. 2088e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen virtual void print(raw_ostream &O, const Module* = 0) const; 2098e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen }; 2108e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen} /// end anonymous namespace 2118e0cca6945ec09bad0decf34ecd832f7e84dc7f1Jakob Stoklund Olesen 2128dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trickchar &llvm::RegisterCoalescerID = RegisterCoalescer::ID; 21327215676c7114132a0374f7b5c9ea73d9354d329Jakob Stoklund Olesen 2145b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 2155b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 216655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 217655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 218655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 219655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 220655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 2215b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 2225b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 223655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2242c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greenechar RegisterCoalescer::ID = 0; 2252c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 22600258d17cd7152237141648d26e1b096cf0e882bRafael Espindolastatic bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 22700258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &Src, unsigned &Dst, 22800258d17cd7152237141648d26e1b096cf0e882bRafael Espindola unsigned &SrcSub, unsigned &DstSub) { 229273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 230273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 231273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen DstSub = MI->getOperand(0).getSubReg(); 232273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Src = MI->getOperand(1).getReg(); 233273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen SrcSub = MI->getOperand(1).getSubReg(); 2345c00e077952d14899c3fc26709c7b2dfd36d0209Jakob Stoklund Olesen } else if (MI->isSubregToReg()) { 23540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 23621caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen DstSub = tri.composeSubRegIndices(MI->getOperand(0).getSubReg(), 23721caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen MI->getOperand(3).getImm()); 23840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Src = MI->getOperand(2).getReg(); 23940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = MI->getOperand(2).getSubReg(); 24004c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } else 24140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 24240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 24340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 24440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 2453c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// Return true if this block should be vacated by the coalescer to eliminate 2463c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// branches. The important cases to handle in the coalescer are critical edges 2473c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// split during phi elimination which contain only copies. Simple blocks that 2483c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// contain non-branches should also be vacated, but this can be handled by an 2493c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick// earlier pass similar to early if-conversion. 2503c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trickstatic bool isSplitEdge(const MachineBasicBlock *MBB) { 2513c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 2523c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick return false; 2533c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 2543c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick for (MachineBasicBlock::const_iterator MII = MBB->begin(), E = MBB->end(); 2553c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick MII != E; ++MII) { 2562344abc939b29ab80bbd247995a0ceb2efa5938bAndrew Trick if (!MII->isCopyLike() && !MII->isUnconditionalBranch()) 25743736c7cfaea3b0c3e2660b9cd5c01e306f7c0dfAndrew Trick return false; 2583c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick } 2593c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick return true; 2603c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick} 2613c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 26240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::setRegisters(const MachineInstr *MI) { 26394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcReg = DstReg = 0; 26494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx = DstIdx = 0; 265c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen NewRC = 0; 266c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = CrossClass = false; 26740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 26840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 269c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 27040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 271c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Partial = SrcSub || DstSub; 27240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 27340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // If one register is a physreg, it must be Dst. 27440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Src)) { 27540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) 27640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 27740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 27840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 279c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = true; 28040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 28140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 28240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 28340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 28440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 28540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate DstSub on a physreg. 28640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) { 287c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 28840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 28940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = 0; 29040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 29140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 29240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate SrcSub by picking a corresponding Dst superregister. 29340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 294c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 29540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 29640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 29740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else if (!MRI.getRegClass(Src)->contains(Dst)) { 29840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 29940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 30040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 30140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Both registers are virtual. 302defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 303defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 30440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 3058df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // Both registers have subreg indices. 3068df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub && DstSub) { 307ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Copies between different sub-registers are never coalescable. 308ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (Src == Dst && SrcSub != DstSub) 309ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen return false; 310ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen 311defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen NewRC = TRI.getCommonSuperRegClass(SrcRC, SrcSub, DstRC, DstSub, 31294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx, DstIdx); 313defa0afa146f4c2370fe126b7860d6d57cf20909Jakob Stoklund Olesen if (!NewRC) 3148df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 31594b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else if (DstSub) { 31694b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // SrcReg will be merged with a sub-register of DstReg. 31794b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen SrcIdx = DstSub; 31894b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 31994b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else if (SrcSub) { 32094b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // DstReg will be merged with a sub-register of SrcReg. 32194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen DstIdx = SrcSub; 32294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getMatchingSuperRegClass(SrcRC, DstRC, SrcSub); 32394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen } else { 32494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // This is a straight copy without sub-registers. 32594b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 3268df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen } 32740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 32894b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // The combined constraint may be impossible to satisfy. 32994b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (!NewRC) 33094b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen return false; 33194b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen 33294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // Prefer SrcReg to be a sub-register of DstReg. 33394b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen // FIXME: Coalescer should support subregs symmetrically. 33494b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (DstIdx && !SrcIdx) { 33540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 33694b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen std::swap(SrcIdx, DstIdx); 33794b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen Flipped = !Flipped; 33840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 33940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 340c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen CrossClass = NewRC != DstRC || NewRC != SrcRC; 34140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 34240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Check our invariants 34340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 34440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 34540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen "Cannot have a physical SubIdx"); 346c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SrcReg = Src; 347c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DstReg = Dst; 34840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 34940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 35040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 35140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::flip() { 35294b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(DstReg)) 35340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 354c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen std::swap(SrcReg, DstReg); 35594b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen std::swap(SrcIdx, DstIdx); 356c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Flipped = !Flipped; 35740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 35840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 35940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 36040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 36140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!MI) 36240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 36340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 364c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 36540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 36640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 367c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Find the virtual register that is SrcReg. 368c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (Dst == SrcReg) { 36940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 37040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 371c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen } else if (Src != SrcReg) { 37240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 37340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 37440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 375c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // Now check that Dst matches DstReg. 376c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 37740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 37840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 37994b62ac5f3b2732251f164ee6feab2dd1a4b967fJakob Stoklund Olesen assert(!DstIdx && !SrcIdx && "Inconsistent CoalescerPair state."); 38040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // DstSub could be set for a physreg from INSERT_SUBREG. 38140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 382c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Dst = TRI.getSubReg(Dst, DstSub); 38340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Full copy of Src. 38440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!SrcSub) 385c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return DstReg == Dst; 38640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // This is a partial register copy. Check that the parts match. 387c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen return TRI.getSubReg(DstReg, SrcSub) == Dst; 38840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 389c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen // DstReg is virtual. 390c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (DstReg != Dst) 39140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 39240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Registers match, do the subregisters line up? 39321caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen return TRI.composeSubRegIndices(SrcIdx, SrcSub) == 39421caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen TRI.composeSubRegIndices(DstIdx, DstSub); 39540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 39640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 39740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 3985b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 399655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.setPreservesCFG(); 400655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<AliasAnalysis>(); 401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveIntervals>(); 402655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveIntervals>(); 403655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveDebugVariables>(); 404655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveDebugVariables>(); 405655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<SlotIndexes>(); 406655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<MachineLoopInfo>(); 407655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<MachineLoopInfo>(); 408655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(MachineDominatorsID); 409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineFunctionPass::getAnalysisUsage(AU); 410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 412bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesenvoid RegisterCoalescer::eliminateDeadDefs() { 413bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen SmallVector<LiveInterval*, 8> NewRegs; 414bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen LiveRangeEdit(0, NewRegs, *MF, *LIS, 0, this).eliminateDeadDefs(DeadDefs); 415bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen} 416bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 417bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen// Callback from eliminateDeadDefs(). 418bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesenvoid RegisterCoalescer::LRE_WillEraseInstruction(MachineInstr *MI) { 419bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // MI may be in WorkList. Make sure we don't visit it. 420bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.insert(MI); 421bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen} 422bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 4239790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// adjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being the source and IntB being the dest, thus this defines a value number 425655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// in IntB. If the source value number (in IntA) is defined by a copy from B, 426655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// see if we can merge these two pieces of B into a single value number, 427655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// eliminating a copy. For example: 428655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = B0 430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 434655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// value number to be replaced with B0 (which simplifies the B liveinterval). 435655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 437655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 4389790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::adjustCopiesBackFrom(const CoalescerPair &CP, 4399790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 440141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen assert(!CP.isPartial() && "This doesn't work for partial copies."); 4410984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen assert(!CP.isPhys() && "This doesn't work for physreg copies."); 442141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen 443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 444c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 446c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 4472debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BLR == IntB.end()) return false; 453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = BLR->valno; 454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the location that B is defined at. Two options: either this value has 456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // an unknown definition point or it is defined at CopyIdx. If unknown, we 457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // can't process it. 4583b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (BValNo->def != CopyIdx) return false; 459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 4612debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyUseIdx = CopyIdx.getRegSlot(true); 462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live range might not exist after fun with physreg coalescing. 464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR == IntA.end()) return false; 465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo = ALR->valno; 466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If AValNo is defined as a copy from IntB, we can potentially process this. 468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the instruction that defines this value number. 4693b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen MachineInstr *ACopyMI = LIS->getInstructionFromIndex(AValNo->def); 470573303e62a913ec881fde3434d7babed0bd4da33Jakob Stoklund Olesen // Don't allow any partial copies, even if isCoalescable() allows them. 471573303e62a913ec881fde3434d7babed0bd4da33Jakob Stoklund Olesen if (!CP.isCoalescable(ACopyMI) || !ACopyMI->isFullCopy()) 472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the LiveRange in IntB that this value number starts with. 475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ValLR = 476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR == IntB.end()) 478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 479655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure that the end of the live range is inside the same block as 481655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI. 482655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *ValLREndInst = 483c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 485655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we now know that ValLR ends in the same block that the CopyMI 488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live-range starts. If there are no intervening live ranges between them in 489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // IntB, we can merge them. 490655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR+1 != BLR) return false; 491655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 492b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "Extending: " << PrintReg(IntB.reg, TRI)); 493655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 495655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We are about to delete CopyMI, so need to remove it as the 'instruction 496655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // that defines this value #'. Update the valnum with the new defining 497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instruction #. 4983b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen BValNo->def = FillerStart; 499655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we can merge them. We need to insert a new liverange: 501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // [ValLR.end, BLR.begin) of either value number, then we merge the 502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // two value numbers. 503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, merge "B1" into the same value number as "B0". 506bf60aa9db5953dd99c561dfa9323b1e3293a5a85Jakob Stoklund Olesen if (BValNo != ValLR->valno) 507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.MergeValueNumberInto(BValNo, ValLR->valno); 508b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << " result = " << IntB << '\n'); 509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the source instruction was killing the source register before the 511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, unset the isKill marker given the live range has been extended. 512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UIdx != -1) { 514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLREndInst->getOperand(UIdx).setIsKill(false); 515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 5168dd26253f54247e77e5accfdd70e7b4bf27b39c2Andrew Trick 5173b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // Rewrite the copy. If the copy instruction was killing the destination 5183b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // register before the merge, find the last use and trim the live range. That 5193b0714d993a37c722603f7cbfab71848a99e91cdLang Hames // will also add the isKill marker. 520141aea9cff95b8df8ca89fb757dc44ee37a3d8dfJakob Stoklund Olesen CopyMI->substituteRegister(IntA.reg, IntB.reg, 0, *TRI); 521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR->end == CopyIdx) 522c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->shrinkToUses(&IntA); 523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numExtends; 525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5289790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// hasOtherReachingDefs - Return true if there are definitions of IntB 5299b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen/// other than BValNo val# that can reach uses of AValno val# of IntA. 5309790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::hasOtherReachingDefs(LiveInterval &IntA, 5319790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen LiveInterval &IntB, 5329790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *AValNo, 5339790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen VNInfo *BValNo) { 5340ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen // If AValNo has PHI kills, conservatively assume that IntB defs can reach 5350ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen // the PHI values. 5360ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen if (LIS->hasPHIKill(IntA, AValNo)) 5370ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen return true; 5380ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen 539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 5419b82d50d209adf915d3c7f871dc82cb73349db80Jakob Stoklund Olesen if (AI->valno != AValNo) continue; 542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::Ranges::iterator BI = 543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI != IntB.ranges.begin()) 545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola --BI; 546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->valno == BValNo) 548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start <= AI->start && BI->end > AI->start) 550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start > AI->start && BI->start < AI->end) 552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5589790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// removeCopyByCommutingDef - We found a non-trivially-coalescable copy with 559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// IntA being the source and IntB being the dest, thus this defines a value 560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// number in IntB. If the source value number (in IntA) is defined by a 561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// commutable instruction and its other operand is coalesced to the copy dest 562655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// register, see if we can transform the copy into a noop by commuting the 563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// definition. For example, 564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = op A2 B0<kill> 566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op A3 <- more uses 570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ==> 572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B2 = op B0 A2<kill> 574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = B2 <- now an identify copy 576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op B2 <- more uses 578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 5819790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::removeCopyByCommutingDef(const CoalescerPair &CP, 5829790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 5830984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen assert (!CP.isPhys()); 584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 5852debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(); 586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 588c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 590c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 5953b1088a2cc15a39c7a7b8dd95a56143f1dda6863Jakob Stoklund Olesen if (!BValNo || BValNo->def != CopyIdx) 596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 600655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 6012debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getRegSlot(true)); 602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(AValNo && "COPY source not live"); 6030ab7103e06ee1da7bde5b196a68be77ab49a005dJakob Stoklund Olesen if (AValNo->isPHIDef() || AValNo->isUnused()) 604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 605c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 6085a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isCommutable()) 609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If DefMI is a two-address instruction then commuting it will change the 611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // destination register. 612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefIdx != -1); 614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UseOpIdx; 615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Op1, Op2, NewDstIdx; 618c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Op1 == UseOpIdx) 621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op2; 622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (Op2 == UseOpIdx) 623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op1; 624655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 625655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 628655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewReg = NewDstMO.getReg(); 629ab9baf7ff4b58b3905bccad68c8d2ab59ea4202bJakob Stoklund Olesen if (NewReg != IntB.reg || !LiveRangeQuery(IntB, AValNo->def).isKill()) 630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure there are no other definitions of IntB that would reach the 633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // uses which the new definition can reach. 6349790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (hasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If some of the uses of IntA.reg is already coalesced away, return false. 638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // It's not possible to determine whether it's safe to perform the coalescing. 639b1afbac64b7c4c06959350acc175fb3552012f57Andrew Trick for (MachineRegisterInfo::use_nodbg_iterator UI = 640c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->use_nodbg_begin(IntA.reg), 641c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 642655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 643c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 644655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 64556366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (ULR == IntA.end() || ULR->valno != AValNo) 646655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 64756366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen // If this use is tied to a def, we can't rewrite the register. 64856366601765c1ff43f8796c271a818f8c272af27Jakob Stoklund Olesen if (UseMI->isRegTiedToDefOperand(UI.getOperandNo())) 649655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 651655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 6529790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen DEBUG(dbgs() << "\tremoveCopyByCommutingDef: " << AValNo->def << '\t' 653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << *DefMI); 654655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // At this point we have decided that it is legal to do this 656655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // transformation. Start by commuting the instruction. 657655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = DefMI->getParent(); 658c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *NewMI = TII->commuteInstruction(DefMI); 659655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!NewMI) 660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 661655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TargetRegisterInfo::isVirtualRegister(IntB.reg) && 663c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 664655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewMI != DefMI) { 666c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 6677c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MachineBasicBlock::iterator Pos = DefMI; 6687c2a4a30e0e16762c75adacebd05ec9fcbccf16bEvan Cheng MBB->insert(Pos, NewMI); 669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->erase(DefMI); 670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->getOperand(OpIdx).setIsKill(); 673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A = or A, B 676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // B = A 678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // C = A<kill> 680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 681655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // = B 682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update uses of IntA of the specific Val# with IntB. 684c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 685c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UE = MRI->use_end(); UI != UE;) { 686655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &UseMO = UI.getOperand(); 687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++UI; 689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isDebugValue()) { 690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME These don't have an instruction index. Not clear we have enough 691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // info to decide whether to do this replacement or not. For now do it. 692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 693655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 694655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 6952debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getRegSlot(true); 696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 697655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end() || ULR->valno != AValNo) 698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 69934af6f597b09c13fba7d3a1960c0810cfc30beffJakob Stoklund Olesen // Kill flags are no longer accurate. They are recomputed after RA. 70034af6f597b09c13fba7d3a1960c0810cfc30beffJakob Stoklund Olesen UseMO.setIsKill(false); 701655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 702c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen UseMO.substPhysReg(NewReg, *TRI); 703655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 704655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 705655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI == CopyMI) 706655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 707655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isCopy()) 708655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->getOperand(0).getReg() != IntB.reg || 710655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getSubReg()) 711655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 712655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This copy will become a noop. If it's defining a new val#, merge it into 714655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo. 7152debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex DefIdx = UseIdx.getRegSlot(); 716655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DVNI) 718655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 719655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 720655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DVNI->def == DefIdx); 721655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 722ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen ErasedInstrs.insert(UseMI); 723ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(UseMI); 724ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen UseMI->eraseFromParent(); 725655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 726655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // is updated. 729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = BValNo; 730655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->def = AValNo->def; 731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 732655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 734655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 737655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 738655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntA.removeValNo(AValNo); 739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCommutes; 741655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 743655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 7449790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// reMaterializeTrivialDef - If the source of a copy is defined by a trivial 745655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// computation, replace the copy by rematerialize the definition. 7469790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::reMaterializeTrivialDef(LiveInterval &SrcInt, 7479790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen unsigned DstReg, 7489790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen MachineInstr *CopyMI) { 7492debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getRegSlot(true); 750655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 751655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(SrcLR != SrcInt.end() && "Live range not found!"); 752655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = SrcLR->valno; 7534ea24e993f179113a9bb76ee152cc490e738c936Jakob Stoklund Olesen if (ValNo->isPHIDef() || ValNo->isUnused()) 754655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 755c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 756655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 757655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 758655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefMI && "Defining instruction disappeared"); 7595a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng if (!DefMI->isAsCheapAsAMove()) 760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 761c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!TII->isTriviallyReMaterializable(DefMI, AA)) 762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 763655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SawStore = false; 764c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (!DefMI->isSafeToMove(TII, AA, SawStore)) 765655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 7665a96b3dad2f634c9081c8b2b6c2575441dc5a2bdEvan Cheng const MCInstrDesc &MCID = DefMI->getDesc(); 767e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getNumDefs() != 1) 768655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 769655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isImplicitDef()) { 770655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure the copy destination register class fits the instruction 771655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // definition register class. The mismatch can happen as a result of earlier 772655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // extract_subreg, insert_subreg, subreg_to_reg coalescing. 773397fc4874efe9c17e737d4c5c50bd19dc3bf27f5Jakob Stoklund Olesen const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI, *MF); 774655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 775c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen if (MRI->getRegClass(DstReg) != RC) 776655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 777655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (!RC->contains(DstReg)) 778655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 779655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 780655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 781655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = CopyMI->getParent(); 782655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock::iterator MII = 783655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola llvm::next(MachineBasicBlock::iterator(CopyMI)); 7846e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 785655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = prior(MII); 786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 787eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI may have dead implicit defs (E.g. EFLAGS for MOV<bits>r0 on X86). 788eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // We need to remember these so we can add intervals once we insert 789eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames // NewMI into SlotIndexes. 790eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SmallVector<unsigned, 4> NewMIImplDefs; 791eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = NewMI->getDesc().getNumOperands(), 792eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames e = NewMI->getNumOperands(); i != e; ++i) { 793eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames MachineOperand &MO = NewMI->getOperand(i); 794eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames if (MO.isReg()) { 795275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isDef() && MO.isImplicit() && MO.isDead() && 796275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames TargetRegisterInfo::isPhysicalRegister(MO.getReg())); 797eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames NewMIImplDefs.push_back(MO.getReg()); 798eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 799eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 800eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 801655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI may have implicit operands, transfer them over to the newly 802655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerialized instruction. And update implicit def interval valnos. 803655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = CopyMI->getDesc().getNumOperands(), 804655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola e = CopyMI->getNumOperands(); i != e; ++i) { 805655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = CopyMI->getOperand(i); 806275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (MO.isReg()) { 807275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames assert(MO.isImplicit() && "No explicit operands after implict operands."); 808275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames // Discard VReg implicit defs. 809275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames if (TargetRegisterInfo::isPhysicalRegister(MO.getReg())) { 810275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames NewMI->addOperand(MO); 811275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 812275ff9bb17698a5eee613c20eca31b4835ae60dbLang Hames } 813655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 814655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 815c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 816eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 817eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames SlotIndex NewMIIdx = LIS->getInstructionIndex(NewMI); 818eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames for (unsigned i = 0, e = NewMIImplDefs.size(); i != e; ++i) { 81971b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen unsigned Reg = NewMIImplDefs[i]; 82071b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units) 82171b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen if (LiveInterval *LI = LIS->getCachedRegUnit(*Units)) 82271b49cb5c73ba912f2fab30f35ed1e43c35a2139Jakob Stoklund Olesen LI->createDeadDef(NewMIIdx.getRegSlot(), LIS->getVNInfoAllocator()); 823eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames } 824eec68e7ffa22d489562a58299cd2fc6f089b893bLang Hames 825655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyMI->eraseFromParent(); 826bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.insert(CopyMI); 827655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "Remat: " << *NewMI); 828655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++NumReMats; 829655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 830655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The source interval can become smaller because we removed a use. 8311dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen LIS->shrinkToUses(&SrcInt, &DeadDefs); 8321dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen if (!DeadDefs.empty()) 8331dc6d7cbb5affee14a2fc5e7269616f3b7b4b6faJakob Stoklund Olesen eliminateDeadDefs(); 834655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 835655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 836655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 837655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 838e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 839e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// values, it only removes local variables. When we have a copy like: 840e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 841e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// %vreg1 = COPY %vreg2<undef> 842e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// 843e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// We delete the copy and remove the corresponding value number from %vreg1. 844e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen/// Any uses of that value number are marked as <undef>. 845e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesenbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 846e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen const CoalescerPair &CP) { 847c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 848c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 849e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (SrcInt->liveAt(Idx)) 850e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 851c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 852e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 853e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return false; 854e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 855e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // No intervals are live-in to CopyMI - it is undef. 856e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (CP.isFlipped()) 857e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt = SrcInt; 858e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen SrcInt = 0; 859e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8602debd48ca790ac01be6e12e094fdf4fdcadc8364Jakob Stoklund Olesen VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getRegSlot()); 861e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen assert(DeadVNI && "No value defined in DstInt"); 862e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DstInt->removeValNo(DeadVNI); 863e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 864e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen // Find new undef uses. 865e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen for (MachineRegisterInfo::reg_nodbg_iterator 866c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 867e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen I != E; ++I) { 868e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineOperand &MO = I.getOperand(); 869e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (MO.isDef() || MO.isUndef()) 870e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 871e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MachineInstr *MI = MO.getParent(); 872c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen SlotIndex Idx = LIS->getInstructionIndex(MI); 873e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen if (DstInt->liveAt(Idx)) 874e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen continue; 875e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen MO.setIsUndef(true); 876e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 877e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 878e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen return true; 879e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen} 880e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 8819790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// updateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 882655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// update the subregister number if it is not zero. If DstReg is a 883655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// physical register and the existing subregister number of the def / use 884655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being updated is not zero, make sure to set it to the correct physical 885655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// subregister. 886ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesenvoid RegisterCoalescer::updateRegDefsUses(unsigned SrcReg, 887ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned DstReg, 888ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen unsigned SubIdx) { 889ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 890324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen LiveInterval *DstInt = DstIsPhys ? 0 : &LIS->getInterval(DstReg); 891655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 892655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update LiveDebugVariables. 893c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV->renameRegister(SrcReg, DstReg, SubIdx); 894655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 895c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 896655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = I.skipInstruction();) { 897655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned,8> Ops; 898655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Reads, Writes; 899655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 900655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 90107a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // If SrcReg wasn't read, it may still be the case that DstReg is live-in 90207a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // because SrcReg is a sub-register. 903324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen if (DstInt && !Reads && SubIdx) 904324143d888a83511b6e022b4c541b18cc7773886Jakob Stoklund Olesen Reads = DstInt->liveAt(LIS->getInstructionIndex(UseMI)); 90507a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen 906655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Replace SrcReg with DstReg in all UseMI operands. 907655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 908655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = UseMI->getOperand(Ops[i]); 909655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 91007a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // Adjust <undef> flags in case of sub-register joins. We don't want to 91107a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // turn a full def into a read-modify-write sub-register def and vice 91207a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen // versa. 913ec096b492549d625e4be608fcaea265b96dabc03Jakob Stoklund Olesen if (SubIdx && MO.isDef()) 91407a267faec7bd77fdece44f242cb4270120e0ef2Jakob Stoklund Olesen MO.setIsUndef(!Reads); 915b077cf338bd85a6a7397ec88d65278f02f0ed06fJakob Stoklund Olesen 916655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) 917c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substPhysReg(DstReg, *TRI); 918655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 919c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MO.substVirtReg(DstReg, SubIdx, *TRI); 920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 922655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 923655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tupdated: "; 924655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isDebugValue()) 925c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 926655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << *UseMI; 927655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 928655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 929655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 930655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 93134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen/// canJoinPhys - Return true if a copy involving a physreg should be joined. 93234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesenbool RegisterCoalescer::canJoinPhys(CoalescerPair &CP) { 933655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Always join simple intervals that are defined by a single copy from a 934655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// reserved register. This doesn't increase register pressure, so it is 935655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// always beneficial. 93614d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen if (!MRI->isReserved(CP.getDstReg())) { 93734a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCan only merge into reserved registers.\n"); 938655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 940655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 94134a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 94234a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (CP.isFlipped() && JoinVInt.containsOneValue()) 94334a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return true; 944655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 94534a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen DEBUG(dbgs() << "\tCannot join defs into reserved register.\n"); 94634a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen return false; 947655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 948655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 9499790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 950655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// which are the src/dst of the copy instruction CopyMI. This returns true 951655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// if the copy was successfully coalesced away. If it is not currently 952655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// possible to coalesce this interval, but it may be possible if other 953655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// things get coalesced, then it returns true by reference in 'Again'. 9549790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinCopy(MachineInstr *CopyMI, bool &Again) { 955655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 956655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = false; 957c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 958655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 959a7542d5f870c5d98960d1676e23ac1d1d975d7e5Benjamin Kramer CoalescerPair CP(*TRI); 960655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.setRegisters(CopyMI)) { 961655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tNot coalescable.\n"); 962655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 963655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 964655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 965bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Dead code elimination. This really should be handled by MachineDCE, but 966bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // sometimes dead copies slip through, and we can't generate invalid live 967bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // ranges. 968bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen if (!CP.isPhys() && CopyMI->allDefsAreDead()) { 969bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy is dead.\n"); 970bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.push_back(CopyMI); 971bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen eliminateDeadDefs(); 972bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen return true; 973bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 974bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen 975e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Eliminate undefs. 976e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 977e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 9783662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9793662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 980655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 981655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 982655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 983e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // Coalesced copies are normally removed immediately, but transformations 984e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // like removeCopyByCommutingDef() can inadvertently create identity copies. 985e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen // When that happens, just join the values and remove the copy. 986e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (CP.getSrcReg() == CP.getDstReg()) { 987e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveInterval &LI = LIS->getInterval(CP.getSrcReg()); 988e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tCopy already coalesced: " << LI << '\n'); 989e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(CopyMI)); 990e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen if (VNInfo *DefVNI = LRQ.valueDefined()) { 991e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen VNInfo *ReadVNI = LRQ.valueIn(); 992e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI && "No value before copy and no <undef> flag."); 993e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen assert(ReadVNI != DefVNI && "Cannot read and define the same value."); 994e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen LI.MergeValueNumberInto(DefVNI, ReadVNI); 995e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen DEBUG(dbgs() << "\tMerged values: " << LI << '\n'); 996e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen } 9973662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 9983662f0d492533435c30969118fd025f6bed46654Jakob Stoklund Olesen CopyMI->eraseFromParent(); 999e3b548219ff47b1384aa7325ebbe21c795c19974Jakob Stoklund Olesen return true; 1000e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen } 1001e4709777e38b58b856cf8395e071a3326d50a402Jakob Stoklund Olesen 1002655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Enforce policies. 1003655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1004ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 1005ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) 1006ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << '\n'); 100734a18775a402f269425b5d79efe385fe122cc64dJakob Stoklund Olesen if (!canJoinPhys(CP)) { 1008655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Before giving up coalescing, if definition of source is defined by 1009655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // trivial computation, try rematerializing it. 1010655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 101167ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 10126e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1013655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1014655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1015655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1016655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 101740a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen DEBUG({ 1018ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << "\tConsidering merging to " << CP.getNewRC()->getName() 1019ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << " with "; 1020ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx() && CP.getSrcIdx()) 1021ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getDstReg()) << " in " 1022ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getDstIdx()) << " and " 1023ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getSrcReg()) << " in " 1024ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << TRI->getSubRegIndexName(CP.getSrcIdx()) << '\n'; 1025ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen else 1026ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen dbgs() << PrintReg(CP.getSrcReg(), TRI) << " in " 1027ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen << PrintReg(CP.getDstReg(), TRI, CP.getSrcIdx()) << '\n'; 102840a2b653e165b5afc2f612b4b3edbb54a7b5eb59Jakob Stoklund Olesen }); 1029655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1030655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When possible, let DstReg be the larger interval. 1031ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (!CP.isPartial() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 1032c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->getInterval(CP.getDstReg()).ranges.size()) 1033655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.flip(); 1034655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1035655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1036655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, attempt to join these two intervals. On failure, this returns false. 1037655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, if one of the intervals being joined is a physreg, this method 1038655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1039655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been modified, so we can use this information below to update aliases. 10409790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (!joinIntervals(CP)) { 1041655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing failed. 1042655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1043655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If definition of source is defined by trivial computation, try 1044655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerializing it. 1045655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 104667ccb29cec06c85210f334cfbdae144460170cd3Jakob Stoklund Olesen reMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), 10476e39290baf236020f130d8695f7624004706bb08Jakob Stoklund Olesen CP.getDstReg(), CopyMI)) 1048655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1049655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1050655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we can eliminate the copy without merging the live ranges, do so now. 10510984461dfb329c8e43ca70e264f56cd39bbae573Jakob Stoklund Olesen if (!CP.isPartial() && !CP.isPhys()) { 10529790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen if (adjustCopiesBackFrom(CP, CopyMI) || 10539790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen removeCopyByCommutingDef(CP, CopyMI)) { 1054ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 1055ccce1233a27e9527cfb68cbced311351332a3a4eJakob Stoklund Olesen CopyMI->eraseFromParent(); 1056655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tTrivial!\n"); 1057655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1058655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1059655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1060655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1061655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, we are unable to join the intervals. 1062655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tInterference!\n"); 1063655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1064655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1065655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1066655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1067655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing to a virtual register that is of a sub-register class of the 1068655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // other. Make sure the resulting register is set to the right register class. 1069655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1070655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCrossRCs; 1071c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 1072655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1073655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 107403c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register copies can ease the register class constraints. 107503c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Make sure we attempt to inflate the register class of DstReg. 107603c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen if (!CP.isPhys() && RegClassInfo.isProperSubClass(CP.getNewRC())) 107703c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.push_back(CP.getDstReg()); 107803c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen 10797ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // CopyMI has been erased by joinIntervals at this point. Remove it from 10807ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // ErasedInstrs since copyCoalesceWorkList() won't add a successful join back 10817ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen // to the work list. This keeps ErasedInstrs from growing needlessly. 10827ebed91fddbcd259d03c4b438719ac1ce2a4fc87Jakob Stoklund Olesen ErasedInstrs.erase(CopyMI); 1083655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1084ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Rewrite all SrcReg operands to DstReg. 1085ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen // Also update DstReg operands to include DstIdx if it is set. 1086ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen if (CP.getDstIdx()) 1087ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getDstReg(), CP.getDstReg(), CP.getDstIdx()); 1088ceacd6da8c31106333952f6dc4fd6e6aa98312f1Jakob Stoklund Olesen updateRegDefsUses(CP.getSrcReg(), CP.getDstReg(), CP.getSrcIdx()); 1089655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1090e02a17c4efb843b8627f3d819c62f88a7f2fb457Lang Hames // SrcReg is guaranteed to be the register whose live interval that is 1091655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // being merged. 1092c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->removeInterval(CP.getSrcReg()); 1093655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1094655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update regalloc hint. 1095c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 1096655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 109704ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen DEBUG({ 109804ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << "\tJoined. Result = " << PrintReg(CP.getDstReg(), TRI); 109904ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen if (!CP.isPhys()) 110004ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << LIS->getInterval(CP.getDstReg()); 110104ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen dbgs() << '\n'; 110204ce06dc4c9dff4ff7a8b97079e3cbb7b60da3abJakob Stoklund Olesen }); 1103655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1104655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numJoins; 1105655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1106655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1107655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 110892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen/// Attempt joining with a reserved physreg. 110992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesenbool RegisterCoalescer::joinReservedPhysReg(CoalescerPair &CP) { 111092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isPhys() && "Must be a physreg copy"); 111114d1dd95c7c969e07defebb6fe65df2fae1b30cfJakob Stoklund Olesen assert(MRI->isReserved(CP.getDstReg()) && "Not a reserved register"); 111292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1113b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1114b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen << '\n'); 111592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 111692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen assert(CP.isFlipped() && RHS.containsOneValue() && 111792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen "Invalid join with reserved register"); 111892ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 111992ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Optimization for reserved registers like ESP. We can only merge with a 112092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved physreg if RHS has a single value that is a copy of CP.DstReg(). 112192ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // The live range of the reserved register will look like a set of dead defs 112292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // - we don't properly track the live range of reserved registers. 112392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 112492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Deny any overlapping intervals. This depends on all the reserved 112592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live ranges to look like dead defs. 1126241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen for (MCRegUnitIterator UI(CP.getDstReg(), TRI); UI.isValid(); ++UI) 1127241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen if (RHS.overlaps(LIS->getRegUnit(*UI))) { 1128241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tInterference: " << PrintRegUnit(*UI, TRI) << '\n'); 1129241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen return false; 113092ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen } 1131241d0209a765c97c684b120527e185f17723f650Jakob Stoklund Olesen 113292ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // Skip any value computations, we are not adding new values to the 113392ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // reserved register. Also skip merging the live ranges, the reserved 113492ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // register live range doesn't need to be accurate as long as all the 113592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen // defs are there. 1136857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 1137e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen // Delete the identity copy. 1138e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen MachineInstr *CopyMI = MRI->getVRegDef(RHS.reg); 1139e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(CopyMI); 1140e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen CopyMI->eraseFromParent(); 1141e744ac49f4cf878e2b34dba26964f04fb0415fa3Jakob Stoklund Olesen 1142857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen // We don't track kills for reserved registers. 1143857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen MRI->clearKillFlags(CP.getSrcReg()); 1144857ed2260403f2cbfe702e83da283b78e341707eJakob Stoklund Olesen 114592ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen return true; 114692ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen} 114792ff7cae7c5a6ce236549516119a9e0b2e71fda0Jakob Stoklund Olesen 1148c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1149c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// Interference checking and interval joining 1150c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen//===----------------------------------------------------------------------===// 1151c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1152c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// In the easiest case, the two live ranges being joined are disjoint, and 1153c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// there is no interference to consider. It is quite common, though, to have 1154c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// overlapping live ranges, and we need to check if the interference can be 1155c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// resolved. 1156c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1157c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// The live range of a single SSA value forms a sub-tree of the dominator tree. 1158c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// This means that two SSA values overlap if and only if the def of one value 1159c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// is contained in the live range of the other value. As a special case, the 1160c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// overlapping values can be defined at the same index. 1161c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1162c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// The interference from an overlapping def can be resolved in these cases: 1163c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1164c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1. Coalescable copies. The value is defined by a copy that would become an 1165c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// identity copy after joining SrcReg and DstReg. The copy instruction will 1166c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// be removed, and the value will be merged with the source value. 1167c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1168c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// There can be several copies back and forth, causing many values to be 1169c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// merged into one. We compute a list of ultimate values in the joined live 1170c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// range as well as a mappings from the old value numbers. 1171c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1172c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 2. IMPLICIT_DEF. This instruction is only inserted to ensure all PHI 1173c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// predecessors have a live out value. It doesn't cause real interference, 1174c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// and can be merged into the value it overlaps. Like a coalescable copy, it 1175c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// can be erased after joining. 1176c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1177c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 3. Copy of external value. The overlapping def may be a copy of a value that 1178c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// is already in the other register. This is like a coalescable copy, but 1179c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// the live range of the source register must be trimmed after erasing the 1180c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// copy instruction: 1181c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1182c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %src = COPY %ext 1183c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %dst = COPY %ext <-- Remove this COPY, trim the live range of %ext. 1184c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1185c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 4. Clobbering undefined lanes. Vector registers are sometimes built by 1186c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// defining one lane at a time: 1187c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1188c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %dst:ssub0<def,read-undef> = FOO 1189c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %src = BAR 1190c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %dst:ssub1<def> = COPY %src 1191c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1192c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// The live range of %src overlaps the %dst value defined by FOO, but 1193c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// merging %src into %dst:ssub1 is only going to clobber the ssub1 lane 1194c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// which was undef anyway. 1195c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1196c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// The value mapping is more complicated in this case. The final live range 1197c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// will have different value numbers for both FOO and BAR, but there is no 1198c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// simple mapping from old to new values. It may even be necessary to add 1199c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// new PHI values. 1200c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1201c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 5. Clobbering dead lanes. A def may clobber a lane of a vector register that 1202c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// is live, but never read. This can happen because we don't compute 1203c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// individual live ranges per lane. 1204c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1205c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %dst<def> = FOO 1206c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %src = BAR 1207c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// %dst:ssub1<def> = COPY %src 1208c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// 1209c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// This kind of interference is only resolved locally. If the clobbered 1210c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen// lane value escapes the block, the join is aborted. 1211c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1212c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesennamespace { 1213c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Track information about values in a single virtual register about to be 1214c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// joined. Objects of this class are always created in pairs - one for each 1215c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// side of the CoalescerPair. 1216c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenclass JoinVals { 1217c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveInterval &LI; 1218c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1219c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Location of this register in the final joined register. 1220c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Either CP.DstIdx or CP.SrcIdx. 1221c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned SubIdx; 1222c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1223c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Values that will be present in the final live range. 1224c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVectorImpl<VNInfo*> &NewVNInfo; 1225c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1226c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen const CoalescerPair &CP; 1227c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveIntervals *LIS; 1228c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SlotIndexes *Indexes; 1229c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen const TargetRegisterInfo *TRI; 1230c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1231c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Value number assignments. Maps value numbers in LI to entries in NewVNInfo. 1232c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This is suitable for passing to LiveInterval::join(). 1233c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVector<int, 8> Assignments; 1234c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1235c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Conflict resolution for overlapping values. 1236c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen enum ConflictResolution { 1237c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // No overlap, simply keep this value. 1238c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Keep, 1239c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1240c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Merge this value into OtherVNI and erase the defining instruction. 1241c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Used for IMPLICIT_DEF, coalescable copies, and copies from external 1242c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // values. 1243c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Erase, 1244c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1245c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Merge this value into OtherVNI but keep the defining instruction. 1246c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This is for the special case where OtherVNI is defined by the same 1247c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // instruction. 1248c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Merge, 1249c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1250c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Keep this value, and have it replace OtherVNI where possible. This 1251c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // complicates value mapping since OtherVNI maps to two different values 1252c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // before and after this def. 1253c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Used when clobbering undefined or dead lanes. 1254c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Replace, 1255c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1256c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Unresolved conflict. Visit later when all values have been mapped. 1257c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Unresolved, 1258c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1259c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Unresolvable conflict. Abort the join. 1260c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen CR_Impossible 1261c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen }; 1262c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1263c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Per-value info for LI. The lane bit masks are all relative to the final 1264c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // joined register, so they can be compared directly between SrcReg and 1265c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // DstReg. 1266c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen struct Val { 1267c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen ConflictResolution Resolution; 1268c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1269c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Lanes written by this def, 0 for unanalyzed values. 1270c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned WriteLanes; 1271c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1272c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Lanes with defined values in this register. Other lanes are undef and 1273c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // safe to clobber. 1274c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned ValidLanes; 1275c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1276c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Value in LI being redefined by this def. 1277c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen VNInfo *RedefVNI; 1278c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1279c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Value in the other live range that overlaps this def, if any. 1280c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen VNInfo *OtherVNI; 1281c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1282795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // Is this value an IMPLICIT_DEF? 1283795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen bool IsImplicitDef; 1284795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen 12852df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // True when the live range of this value will be pruned because of an 12862df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // overlapping CR_Replace value in the other live range. 12872df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen bool Pruned; 12882df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen 12892df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // True once Pruned above has been computed. 12902df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen bool PrunedComputed; 12912df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen 1292c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Val() : Resolution(CR_Keep), WriteLanes(0), ValidLanes(0), 1293795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen RedefVNI(0), OtherVNI(0), IsImplicitDef(false), Pruned(false), 1294795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen PrunedComputed(false) {} 1295c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1296c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen bool isAnalyzed() const { return WriteLanes != 0; } 1297c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen }; 1298c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1299c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // One entry per value number in LI. 1300c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVector<Val, 8> Vals; 1301c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1302c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned computeWriteLanes(const MachineInstr *DefMI, bool &Redef); 1303c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen VNInfo *stripCopies(VNInfo *VNI); 1304c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen ConflictResolution analyzeValue(unsigned ValNo, JoinVals &Other); 1305c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen void computeAssignment(unsigned ValNo, JoinVals &Other); 1306d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen bool taintExtent(unsigned, unsigned, JoinVals&, 1307d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen SmallVectorImpl<std::pair<SlotIndex, unsigned> >&); 1308d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen bool usesLanes(MachineInstr *MI, unsigned, unsigned, unsigned); 13092df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen bool isPrunedValue(unsigned ValNo, JoinVals &Other); 1310c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1311c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenpublic: 1312c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen JoinVals(LiveInterval &li, unsigned subIdx, 1313c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVectorImpl<VNInfo*> &newVNInfo, 1314c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen const CoalescerPair &cp, 1315c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveIntervals *lis, 1316c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen const TargetRegisterInfo *tri) 1317c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen : LI(li), SubIdx(subIdx), NewVNInfo(newVNInfo), CP(cp), LIS(lis), 1318c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Indexes(LIS->getSlotIndexes()), TRI(tri), 1319c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Assignments(LI.getNumValNums(), -1), Vals(LI.getNumValNums()) 1320c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen {} 1321c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1322c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Analyze defs in LI and compute a value mapping in NewVNInfo. 1323c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Returns false if any conflicts were impossible to resolve. 1324c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen bool mapValues(JoinVals &Other); 1325c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1326c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Try to resolve conflicts that require all values to be mapped. 1327c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Returns false if any conflicts were impossible to resolve. 1328c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen bool resolveConflicts(JoinVals &Other); 1329c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 133087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen /// Prune the live range of values in Other.LI where they would conflict with 133187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen /// CR_Replace values in LI. Collect end points for restoring the live range 133287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen /// after joining. 133387f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen void pruneValues(JoinVals &Other, SmallVectorImpl<SlotIndex> &EndPoints); 133487f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 1335c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Erase any machine instructions that have been coalesced away. 1336c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Add erased instructions to ErasedInstrs. 1337c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Add foreign virtual registers to ShrinkRegs if their live range ended at 1338c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// the erased instrs. 1339c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen void eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1340c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVectorImpl<unsigned> &ShrinkRegs); 1341c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1342c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen /// Get the value assignments suitable for passing to LiveInterval::join. 134356acf63e35440068935bca999d19a81f76e876d6Jakob Stoklund Olesen const int *getAssignments() const { return Assignments.data(); } 1344c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen}; 1345c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} // end anonymous namespace 1346c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1347c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Compute the bitmask of lanes actually written by DefMI. 1348c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Set Redef if there are any partial register definitions that depend on the 1349c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// previous value of the register. 1350c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenunsigned JoinVals::computeWriteLanes(const MachineInstr *DefMI, bool &Redef) { 1351c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned L = 0; 1352c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen for (ConstMIOperands MO(DefMI); MO.isValid(); ++MO) { 1353c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!MO->isReg() || MO->getReg() != LI.reg || !MO->isDef()) 1354c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen continue; 135521caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen L |= TRI->getSubRegIndexLaneMask( 135621caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen TRI->composeSubRegIndices(SubIdx, MO->getSubReg())); 1357c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (MO->readsReg()) 1358c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Redef = true; 1359c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1360c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return L; 1361c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1362c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1363c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Find the ultimate value that VNI was copied from. 1364c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund OlesenVNInfo *JoinVals::stripCopies(VNInfo *VNI) { 1365c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen while (!VNI->isPHIDef()) { 1366c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen MachineInstr *MI = Indexes->getInstructionFromIndex(VNI->def); 1367c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(MI && "No defining instruction"); 1368c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!MI->isFullCopy()) 1369c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen break; 1370c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen unsigned Reg = MI->getOperand(1).getReg(); 1371c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!TargetRegisterInfo::isVirtualRegister(Reg)) 1372c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen break; 1373c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveRangeQuery LRQ(LIS->getInterval(Reg), VNI->def); 1374c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!LRQ.valueIn()) 1375c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen break; 1376c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen VNI = LRQ.valueIn(); 1377c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1378c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return VNI; 1379c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1380c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1381c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Analyze ValNo in this live range, and set all fields of Vals[ValNo]. 1382c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Return a conflict resolution when possible, but leave the hard cases as 1383c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// CR_Unresolved. 1384c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Recursively calls computeAssignment() on this and Other, guaranteeing that 1385c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// both OtherVNI and RedefVNI have been analyzed and mapped before returning. 1386c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// The recursion always goes upwards in the dominator tree, making loops 1387c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// impossible. 1388c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund OlesenJoinVals::ConflictResolution 1389c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund OlesenJoinVals::analyzeValue(unsigned ValNo, JoinVals &Other) { 1390c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Val &V = Vals[ValNo]; 1391c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(!V.isAnalyzed() && "Value has already been analyzed!"); 1392c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(ValNo); 1393c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (VNI->isUnused()) { 1394c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.WriteLanes = ~0u; 1395c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Keep; 1396c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1397c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1398c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Get the instruction defining this value, compute the lanes written. 1399c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen const MachineInstr *DefMI = 0; 1400c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (VNI->isPHIDef()) { 1401c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Conservatively assume that all lanes in a PHI are valid. 1402c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.ValidLanes = V.WriteLanes = TRI->getSubRegIndexLaneMask(SubIdx); 1403c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } else { 1404c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen DefMI = Indexes->getInstructionFromIndex(VNI->def); 1405c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen bool Redef = false; 1406c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.ValidLanes = V.WriteLanes = computeWriteLanes(DefMI, Redef); 1407c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1408c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // If this is a read-modify-write instruction, there may be more valid 1409c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // lanes than the ones written by this instruction. 1410c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This only covers partial redef operands. DefMI may have normal use 1411c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // operands reading the register. They don't contribute valid lanes. 1412c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1413c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This adds ssub1 to the set of valid lanes in %src: 1414c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1415c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // %src:ssub1<def> = FOO 1416c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1417c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This leaves only ssub1 valid, making any other lanes undef: 1418c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1419c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // %src:ssub1<def,read-undef> = FOO %src:ssub2 1420c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1421c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // The <read-undef> flag on the def operand means that old lane values are 1422c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // not important. 1423c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (Redef) { 1424c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.RedefVNI = LiveRangeQuery(LI, VNI->def).valueIn(); 1425c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(V.RedefVNI && "Instruction is reading nonexistent value"); 1426c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen computeAssignment(V.RedefVNI->id, Other); 1427c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.ValidLanes |= Vals[V.RedefVNI->id].ValidLanes; 1428c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1429c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1430c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // An IMPLICIT_DEF writes undef values. 1431795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen if (DefMI->isImplicitDef()) { 1432795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen V.IsImplicitDef = true; 1433c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.ValidLanes &= ~V.WriteLanes; 1434795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen } 1435c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1436c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1437c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Find the value in Other that overlaps VNI->def, if any. 1438c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveRangeQuery OtherLRQ(Other.LI, VNI->def); 1439c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1440c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // It is possible that both values are defined by the same instruction, or 1441c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // the values are PHIs defined in the same block. When that happens, the two 1442c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // values should be merged into one, but not into any preceding value. 1443c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // The first value defined or visited gets CR_Keep, the other gets CR_Merge. 1444c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (VNInfo *OtherVNI = OtherLRQ.valueDefined()) { 1445c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(SlotIndex::isSameInstr(VNI->def, OtherVNI->def) && "Broken LRQ"); 1446c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1447c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // One value stays, the other is merged. Keep the earlier one, or the first 1448c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // one we see. 1449c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (OtherVNI->def < VNI->def) 1450c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Other.computeAssignment(OtherVNI->id, *this); 1451c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen else if (VNI->def < OtherVNI->def && OtherLRQ.valueIn()) { 1452c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This is an early-clobber def overlapping a live-in value in the other 1453c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // register. Not mergeable. 1454c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.OtherVNI = OtherLRQ.valueIn(); 1455c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Impossible; 1456c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1457c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.OtherVNI = OtherVNI; 1458c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Val &OtherV = Other.Vals[OtherVNI->id]; 1459c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Keep this value, check for conflicts when analyzing OtherVNI. 1460c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!OtherV.isAnalyzed()) 1461c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Keep; 1462e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen // Both sides have been analyzed now. 1463e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen // Allow overlapping PHI values. Any real interference would show up in a 1464e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen // predecessor, the PHI itself can't introduce any conflicts. 1465e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen if (VNI->isPHIDef()) 1466e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen return CR_Merge; 1467c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (V.ValidLanes & OtherV.ValidLanes) 1468d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Overlapping lanes can't be resolved. 1469d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return CR_Impossible; 1470c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen else 1471c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Merge; 1472c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1473c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1474c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // No simultaneous def. Is Other live at the def? 1475c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen V.OtherVNI = OtherLRQ.valueIn(); 1476c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!V.OtherVNI) 1477c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // No overlap, no conflict. 1478c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Keep; 1479c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1480c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(!SlotIndex::isSameInstr(VNI->def, V.OtherVNI->def) && "Broken LRQ"); 1481c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1482c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // We have overlapping values, or possibly a kill of Other. 1483c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Recursively compute assignments up the dominator tree. 1484c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Other.computeAssignment(V.OtherVNI->id, *this); 148587f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1486c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1487e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen // Allow overlapping PHI values. Any real interference would show up in a 1488e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen // predecessor, the PHI itself can't introduce any conflicts. 1489c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (VNI->isPHIDef()) 1490e6e2d8cd90ceb5190aa646dc06584027f7d492d0Jakob Stoklund Olesen return CR_Replace; 1491c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1492c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Check for simple erasable conflicts. 1493c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (DefMI->isImplicitDef()) 1494c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Erase; 1495c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1496c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Include the non-conflict where DefMI is a coalescable copy that kills 1497c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // OtherVNI. We still want the copy erased and value numbers merged. 1498c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (CP.isCoalescable(DefMI)) { 1499c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Some of the lanes copied from OtherVNI may be undef, making them undef 1500c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // here too. 150187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen V.ValidLanes &= ~V.WriteLanes | OtherV.ValidLanes; 1502c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Erase; 1503c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1504c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1505c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This may not be a real conflict if DefMI simply kills Other and defines 1506c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // VNI. 1507c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (OtherLRQ.isKill() && OtherLRQ.endPoint() <= VNI->def) 1508c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Keep; 1509c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1510c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Handle the case where VNI and OtherVNI can be proven to be identical: 1511c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1512c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // %other = COPY %ext 1513c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // %this = COPY %ext <-- Erase this copy 1514c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // 1515c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (DefMI->isFullCopy() && !CP.isPartial() && 1516c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen stripCopies(VNI) == stripCopies(V.OtherVNI)) 1517c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return CR_Erase; 1518c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 151987f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // If the lanes written by this instruction were all undef in OtherVNI, it is 152087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // still safe to join the live ranges. This can't be done with a simple value 152187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // mapping, though - OtherVNI will map to multiple values: 152287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 152387f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 1 %dst:ssub0 = FOO <-- OtherVNI 152487f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 2 %src = BAR <-- VNI 152587f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 3 %dst:ssub1 = COPY %src<kill> <-- Eliminate this copy. 152687f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 4 BAZ %dst<kill> 152787f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 5 QUUX %src<kill> 152887f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // 152987f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // Here OtherVNI will map to itself in [1;2), but to VNI in [2;5). CR_Replace 153087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // handles this complex value mapping. 153187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen if ((V.WriteLanes & OtherV.ValidLanes) == 0) 153287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen return CR_Replace; 153387f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 1534163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // If the other live range is killed by DefMI and the live ranges are still 1535163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // overlapping, it must be because we're looking at an early clobber def: 1536163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // 1537163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // %dst<def,early-clobber> = ASM %src<kill> 1538163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // 1539163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // In this case, it is illegal to merge the two live ranges since the early 1540163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // clobber def would clobber %src before it was read. 1541163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen if (OtherLRQ.isKill()) { 1542163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen // This case where the def doesn't overlap the kill is handled above. 1543163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen assert(VNI->def.isEarlyClobber() && 1544163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen "Only early clobber defs can overlap a kill"); 1545163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen return CR_Impossible; 1546163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen } 1547163f67f4d98aab114cb9b04efd086f54f7688d0cJakob Stoklund Olesen 1548d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // VNI is clobbering live lanes in OtherVNI, but there is still the 1549d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // possibility that no instructions actually read the clobbered lanes. 1550d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // If we're clobbering all the lanes in OtherVNI, at least one must be read. 1551d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Otherwise Other.LI wouldn't be live here. 1552d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if ((TRI->getSubRegIndexLaneMask(Other.SubIdx) & ~V.WriteLanes) == 0) 1553d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return CR_Impossible; 1554d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1555d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // We need to verify that no instructions are reading the clobbered lanes. To 1556d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // save compile time, we'll only check that locally. Don't allow the tainted 1557d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // value to escape the basic block. 1558d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1559d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (OtherLRQ.endPoint() >= Indexes->getMBBEndIdx(MBB)) 1560d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return CR_Impossible; 1561d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1562d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // There are still some things that could go wrong besides clobbered lanes 1563d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // being read, for example OtherVNI may be only partially redefined in MBB, 1564d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // and some clobbered lanes could escape the block. Save this analysis for 1565d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // resolveConflicts() when all values have been mapped. We need to know 1566d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // RedefVNI and WriteLanes for any later defs in MBB, and we can't compute 1567d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // that now - the recursive analyzeValue() calls must go upwards in the 1568d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // dominator tree. 1569d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return CR_Unresolved; 1570c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1571c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1572c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// Compute the value assignment for ValNo in LI. 1573c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// This may be called recursively by analyzeValue(), but never for a ValNo on 1574c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen/// the stack. 1575c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenvoid JoinVals::computeAssignment(unsigned ValNo, JoinVals &Other) { 1576c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Val &V = Vals[ValNo]; 1577c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (V.isAnalyzed()) { 1578c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Recursion should always move up the dominator tree, so ValNo is not 1579c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // supposed to reappear before it has been assigned. 1580c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(Assignments[ValNo] != -1 && "Bad recursion?"); 1581c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return; 1582c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1583c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen switch ((V.Resolution = analyzeValue(ValNo, Other))) { 1584c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen case CR_Erase: 1585c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen case CR_Merge: 1586c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Merge this ValNo into OtherVNI. 1587c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(V.OtherVNI && "OtherVNI not assigned, can't merge."); 1588c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen assert(Other.Vals[V.OtherVNI->id].isAnalyzed() && "Missing recursion"); 1589c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Assignments[ValNo] = Other.Assignments[V.OtherVNI->id]; 1590c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen DEBUG(dbgs() << "\t\tmerge " << PrintReg(LI.reg) << ':' << ValNo << '@' 1591c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << LI.getValNumInfo(ValNo)->def << " into " 1592c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << PrintReg(Other.LI.reg) << ':' << V.OtherVNI->id << '@' 1593c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << V.OtherVNI->def << " --> @" 1594c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << NewVNInfo[Assignments[ValNo]]->def << '\n'); 1595c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen break; 15962df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Replace: 15972df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Unresolved: 15982df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // The other value is going to be pruned if this join is successful. 15992df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen assert(V.OtherVNI && "OtherVNI not assigned, can't prune"); 16002df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen Other.Vals[V.OtherVNI->id].Pruned = true; 16012df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // Fall through. 1602c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen default: 1603c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // This value number needs to go in the final joined live range. 1604c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen Assignments[ValNo] = NewVNInfo.size(); 1605c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen NewVNInfo.push_back(LI.getValNumInfo(ValNo)); 1606c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen break; 1607c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1608c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1609c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1610c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenbool JoinVals::mapValues(JoinVals &Other) { 1611c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1612c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen computeAssignment(i, Other); 1613c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (Vals[i].Resolution == CR_Impossible) { 1614c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen DEBUG(dbgs() << "\t\tinterference at " << PrintReg(LI.reg) << ':' << i 1615c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << '@' << LI.getValNumInfo(i)->def << '\n'); 1616c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return false; 1617c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1618c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1619c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return true; 1620c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1621c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1622d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// Assuming ValNo is going to clobber some valid lanes in Other.LI, compute 1623d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// the extent of the tainted lanes in the block. 1624d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 1625d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// Multiple values in Other.LI can be affected since partial redefinitions can 1626d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// preserve previously tainted lanes. 1627d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 1628d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 1 %dst = VLOAD <-- Define all lanes in %dst 1629d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 2 %src = FOO <-- ValNo to be joined with %dst:ssub0 1630d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 3 %dst:ssub1 = BAR <-- Partial redef doesn't clear taint in ssub0 1631d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 4 %dst:ssub0 = COPY %src <-- Conflict resolved, ssub0 wasn't read 1632d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 1633d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// For each ValNo in Other that is affected, add an (EndIndex, TaintedLanes) 1634d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// entry to TaintedVals. 1635d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// 1636d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// Returns false if the tainted lanes extend beyond the basic block. 1637d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesenbool JoinVals:: 1638d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund OlesentaintExtent(unsigned ValNo, unsigned TaintedLanes, JoinVals &Other, 1639d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen SmallVectorImpl<std::pair<SlotIndex, unsigned> > &TaintExtent) { 1640d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(ValNo); 1641d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1642d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen SlotIndex MBBEnd = Indexes->getMBBEndIdx(MBB); 1643d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1644d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Scan Other.LI from VNI.def to MBBEnd. 1645d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen LiveInterval::iterator OtherI = Other.LI.find(VNI->def); 1646d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(OtherI != Other.LI.end() && "No conflict?"); 1647d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen do { 1648d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // OtherI is pointing to a tainted value. Abort the join if the tainted 1649d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // lanes escape the block. 1650d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen SlotIndex End = OtherI->end; 1651d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (End >= MBBEnd) { 1652d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen DEBUG(dbgs() << "\t\ttaints global " << PrintReg(Other.LI.reg) << ':' 1653d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen << OtherI->valno->id << '@' << OtherI->start << '\n'); 1654d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return false; 1655d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1656d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen DEBUG(dbgs() << "\t\ttaints local " << PrintReg(Other.LI.reg) << ':' 1657d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen << OtherI->valno->id << '@' << OtherI->start 1658d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen << " to " << End << '\n'); 1659d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // A dead def is not a problem. 1660d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (End.isDead()) 1661d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen break; 1662d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen TaintExtent.push_back(std::make_pair(End, TaintedLanes)); 1663d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1664d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Check for another def in the MBB. 1665d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (++OtherI == Other.LI.end() || OtherI->start >= MBBEnd) 1666d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen break; 1667d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1668d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Lanes written by the new def are no longer tainted. 1669d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen const Val &OV = Other.Vals[OtherI->valno->id]; 1670d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen TaintedLanes &= ~OV.WriteLanes; 1671d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (!OV.RedefVNI) 1672d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen break; 1673d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } while (TaintedLanes); 1674d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return true; 1675d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen} 1676d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1677d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// Return true if MI uses any of the given Lanes from Reg. 1678d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen/// This does not include partial redefinitions of Reg. 1679d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesenbool JoinVals::usesLanes(MachineInstr *MI, unsigned Reg, unsigned SubIdx, 1680d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen unsigned Lanes) { 1681d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (MI->isDebugValue()) 1682d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return false; 1683d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen for (ConstMIOperands MO(MI); MO.isValid(); ++MO) { 1684d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (!MO->isReg() || MO->isDef() || MO->getReg() != Reg) 1685d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen continue; 1686d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (!MO->readsReg()) 1687d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen continue; 168821caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen if (Lanes & TRI->getSubRegIndexLaneMask( 168921caa9ef03e3f2d4e860c8fc3cd53015c42934bfJakob Stoklund Olesen TRI->composeSubRegIndices(SubIdx, MO->getSubReg()))) 1690d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return true; 1691d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1692d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return false; 1693d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen} 1694d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1695c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenbool JoinVals::resolveConflicts(JoinVals &Other) { 1696c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1697d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen Val &V = Vals[i]; 1698d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert (V.Resolution != CR_Impossible && "Unresolvable conflict"); 1699d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (V.Resolution != CR_Unresolved) 1700c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen continue; 1701c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen DEBUG(dbgs() << "\t\tconflict at " << PrintReg(LI.reg) << ':' << i 1702c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << '@' << LI.getValNumInfo(i)->def << '\n'); 1703d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen ++NumLaneConflicts; 1704d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(V.OtherVNI && "Inconsistent conflict resolution."); 1705d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen VNInfo *VNI = LI.getValNumInfo(i); 1706d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen const Val &OtherV = Other.Vals[V.OtherVNI->id]; 1707d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1708d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // VNI is known to clobber some lanes in OtherVNI. If we go ahead with the 1709d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // join, those lanes will be tainted with a wrong value. Get the extent of 1710d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // the tainted lanes. 1711d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen unsigned TaintedLanes = V.WriteLanes & OtherV.ValidLanes; 1712d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen SmallVector<std::pair<SlotIndex, unsigned>, 8> TaintExtent; 1713d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (!taintExtent(i, TaintedLanes, Other, TaintExtent)) 1714d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Tainted lanes would extend beyond the basic block. 1715d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return false; 1716d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1717d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(!TaintExtent.empty() && "There should be at least one conflict."); 1718d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1719d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // Now look at the instructions from VNI->def to TaintExtent (inclusive). 1720d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MachineBasicBlock *MBB = Indexes->getMBBFromIndex(VNI->def); 1721d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MachineBasicBlock::iterator MI = MBB->begin(); 1722d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (!VNI->isPHIDef()) { 1723d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MI = Indexes->getInstructionFromIndex(VNI->def); 1724d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // No need to check the instruction defining VNI for reads. 1725d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen ++MI; 1726d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1727d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(!SlotIndex::isSameInstr(VNI->def, TaintExtent.front().first) && 1728d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen "Interference ends on VNI->def. Should have been handled earlier"); 1729d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen MachineInstr *LastMI = 1730d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen Indexes->getInstructionFromIndex(TaintExtent.front().first); 1731d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(LastMI && "Range must end at a proper instruction"); 1732d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen unsigned TaintNum = 0; 1733d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen for(;;) { 1734d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(MI != MBB->end() && "Bad LastMI"); 1735d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (usesLanes(MI, Other.LI.reg, Other.SubIdx, TaintedLanes)) { 1736d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen DEBUG(dbgs() << "\t\ttainted lanes used by: " << *MI); 1737d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen return false; 1738d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1739d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // LastMI is the last instruction to use the current value. 1740d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (&*MI == LastMI) { 1741d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen if (++TaintNum == TaintExtent.size()) 1742d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen break; 1743d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen LastMI = Indexes->getInstructionFromIndex(TaintExtent[TaintNum].first); 1744d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen assert(LastMI && "Range must end at a proper instruction"); 1745d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen TaintedLanes = TaintExtent[TaintNum].second; 1746d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1747d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen ++MI; 1748d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen } 1749d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen 1750d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen // The tainted lanes are unused. 1751d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen V.Resolution = CR_Replace; 1752d40d4c34f72d1eda3cd9ba0f3dbf2d43b726f06cJakob Stoklund Olesen ++NumLaneResolves; 1753c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1754c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return true; 1755c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1756c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 17572df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// Determine if ValNo is a copy of a value number in LI or Other.LI that will 17582df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// be pruned: 17592df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// 17602df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// %dst = COPY %src 17612df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// %src = COPY %dst <-- This value to be pruned. 17622df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// %dst = COPY %src <-- This value is a copy of a pruned value. 17632df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen// 17642df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesenbool JoinVals::isPrunedValue(unsigned ValNo, JoinVals &Other) { 17652df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen Val &V = Vals[ValNo]; 17662df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen if (V.Pruned || V.PrunedComputed) 17672df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen return V.Pruned; 17682df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen 17692df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen if (V.Resolution != CR_Erase && V.Resolution != CR_Merge) 17702df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen return V.Pruned; 17712df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen 17722df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // Follow copies up the dominator tree and check if any intermediate value 17732df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // has been pruned. 17742df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen V.PrunedComputed = true; 17752df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen V.Pruned = Other.isPrunedValue(V.OtherVNI->id, *this); 17762df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen return V.Pruned; 17772df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen} 17782df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen 177987f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesenvoid JoinVals::pruneValues(JoinVals &Other, 178087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen SmallVectorImpl<SlotIndex> &EndPoints) { 178187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 178287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen SlotIndex Def = LI.getValNumInfo(i)->def; 17832df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen switch (Vals[i].Resolution) { 17842df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Keep: 17852df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen break; 1786795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen case CR_Replace: { 17872df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // This value takes precedence over the value in Other.LI. 17882df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen LIS->pruneValue(&Other.LI, Def, &EndPoints); 1789795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // Check if we're replacing an IMPLICIT_DEF value. The IMPLICIT_DEF 1790795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // instructions are only inserted to provide a live-out value for PHI 1791795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // predecessors, so the instruction should simply go away once its value 1792795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // has been replaced. 1793795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen Val &OtherV = Other.Vals[Vals[i].OtherVNI->id]; 1794795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen bool EraseImpDef = OtherV.IsImplicitDef && OtherV.Resolution == CR_Keep; 1795d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen if (!Def.isBlock()) { 1796795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // Remove <def,read-undef> flags. This def is now a partial redef. 1797d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen // Also remove <def,dead> flags since the joined live range will 1798d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen // continue past this instruction. 179983ef63efced9a957fe370134314645d2188c7203Jakob Stoklund Olesen for (MIOperands MO(Indexes->getInstructionFromIndex(Def)); 180083ef63efced9a957fe370134314645d2188c7203Jakob Stoklund Olesen MO.isValid(); ++MO) 1801d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen if (MO->isReg() && MO->isDef() && MO->getReg() == LI.reg) { 1802d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen MO->setIsUndef(EraseImpDef); 1803d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen MO->setIsDead(false); 1804d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen } 1805795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // This value will reach instructions below, but we need to make sure 1806795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // the live range also reaches the instruction at Def. 1807d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen if (!EraseImpDef) 1808d86296a4aea7ebac9c8ef8ba92642b64545dec95Jakob Stoklund Olesen EndPoints.push_back(Def); 180927cb347d0e765175efb2c4d388bcbba84cf1b95eJakob Stoklund Olesen } 18102df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tpruned " << PrintReg(Other.LI.reg) << " at " << Def 18112df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen << ": " << Other.LI << '\n'); 18122df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen break; 1813795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen } 18142df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Erase: 18152df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Merge: 18162df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen if (isPrunedValue(i, Other)) { 18172df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // This value is ultimately a copy of a pruned value in LI or Other.LI. 18182df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // We can no longer trust the value mapping computed by 18192df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // computeAssignment(), the value that was originally copied could have 18202df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen // been replaced. 18212df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen LIS->pruneValue(&LI, Def, &EndPoints); 18222df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tpruned all of " << PrintReg(LI.reg) << " at " 18232df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen << Def << ": " << LI << '\n'); 18242df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen } 18252df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen break; 18262df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Unresolved: 18272df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen case CR_Impossible: 18282df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen llvm_unreachable("Unresolved conflicts"); 18292df8ac84ae8317b6a96f19bbc984d2bd02cff087Jakob Stoklund Olesen } 183087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen } 183187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen} 183287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 1833c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenvoid JoinVals::eraseInstrs(SmallPtrSet<MachineInstr*, 8> &ErasedInstrs, 1834c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVectorImpl<unsigned> &ShrinkRegs) { 1835c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen for (unsigned i = 0, e = LI.getNumValNums(); i != e; ++i) { 1836795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // Get the def location before markUnused() below invalidates it. 1837c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SlotIndex Def = LI.getValNumInfo(i)->def; 1838795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen switch (Vals[i].Resolution) { 1839795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen case CR_Keep: 1840795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // If an IMPLICIT_DEF value is pruned, it doesn't serve a purpose any 1841795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // longer. The IMPLICIT_DEF instructions are only inserted by 1842795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // PHIElimination to guarantee that all PHI predecessors have a value. 1843795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen if (!Vals[i].IsImplicitDef || !Vals[i].Pruned) 1844795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen break; 1845795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // Remove value number i from LI. Note that this VNInfo is still present 1846795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // in NewVNInfo, so it will appear as an unused value number in the final 1847795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // joined interval. 1848795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen LI.getValNumInfo(i)->markUnused(); 1849795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen LI.removeValNo(LI.getValNumInfo(i)); 1850795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen DEBUG(dbgs() << "\t\tremoved " << i << '@' << Def << ": " << LI << '\n'); 1851795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen // FALL THROUGH. 1852795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen 1853795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen case CR_Erase: { 1854795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen MachineInstr *MI = Indexes->getInstructionFromIndex(Def); 1855795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen assert(MI && "No instruction to erase"); 1856795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen if (MI->isCopy()) { 1857795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen unsigned Reg = MI->getOperand(1).getReg(); 1858795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen if (TargetRegisterInfo::isVirtualRegister(Reg) && 1859795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen Reg != CP.getSrcReg() && Reg != CP.getDstReg()) 1860795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen ShrinkRegs.push_back(Reg); 1861795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen } 1862795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen ErasedInstrs.insert(MI); 1863795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen DEBUG(dbgs() << "\t\terased:\t" << Def << '\t' << *MI); 1864795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen LIS->RemoveMachineInstrFromMaps(MI); 1865795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen MI->eraseFromParent(); 1866795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen break; 1867795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen } 1868795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen default: 1869795f951c6d5c60a10ffc8e0fdfa22b7c3b499f35Jakob Stoklund Olesen break; 1870c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1871c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen } 1872c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1873c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1874c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesenbool RegisterCoalescer::joinVirtRegs(CoalescerPair &CP) { 1875c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVector<VNInfo*, 16> NewVNInfo; 1876c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 1877c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LiveInterval &LHS = LIS->getInterval(CP.getDstReg()); 1878c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen JoinVals RHSVals(RHS, CP.getSrcIdx(), NewVNInfo, CP, LIS, TRI); 1879c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen JoinVals LHSVals(LHS, CP.getDstIdx(), NewVNInfo, CP, LIS, TRI); 1880c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1881c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen DEBUG(dbgs() << "\t\tRHS = " << PrintReg(CP.getSrcReg()) << ' ' << RHS 1882c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << "\n\t\tLHS = " << PrintReg(CP.getDstReg()) << ' ' << LHS 1883c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen << '\n'); 1884c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1885c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // First compute NewVNInfo and the simple value mappings. 1886c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Detect impossible conflicts early. 1887c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!LHSVals.mapValues(RHSVals) || !RHSVals.mapValues(LHSVals)) 1888c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return false; 1889c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1890c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Some conflicts can only be resolved after all values have been mapped. 1891c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen if (!LHSVals.resolveConflicts(RHSVals) || !RHSVals.resolveConflicts(LHSVals)) 1892c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return false; 1893c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1894c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // All clear, the live ranges can be merged. 1895c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 189687f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // The merging algorithm in LiveInterval::join() can't handle conflicting 189787f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // value mappings, so we need to remove any live ranges that overlap a 189887f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // CR_Replace resolution. Collect a set of end points that can be used to 189987f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // restore the live range after joining. 190087f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen SmallVector<SlotIndex, 8> EndPoints; 190187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen LHSVals.pruneValues(RHSVals, EndPoints); 190287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen RHSVals.pruneValues(LHSVals, EndPoints); 190387f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 1904c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Erase COPY and IMPLICIT_DEF instructions. This may cause some external 1905c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // registers to require trimming. 1906c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen SmallVector<unsigned, 8> ShrinkRegs; 1907c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1908c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen RHSVals.eraseInstrs(ErasedInstrs, ShrinkRegs); 1909c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen while (!ShrinkRegs.empty()) 1910c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LIS->shrinkToUses(&LIS->getInterval(ShrinkRegs.pop_back_val())); 1911c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1912c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Join RHS into LHS. 1913c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen LHS.join(RHS, LHSVals.getAssignments(), RHSVals.getAssignments(), NewVNInfo, 1914c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen MRI); 1915c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 1916c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Kill flags are going to be wrong if the live ranges were overlapping. 1917c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // Eventually, we should simply clear all kill flags when computing live 1918c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen // ranges. They are reinserted after register allocation. 1919c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen MRI->clearKillFlags(LHS.reg); 1920c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen MRI->clearKillFlags(RHS.reg); 192187f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 192287f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen if (EndPoints.empty()) 192387f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen return true; 192487f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen 192587f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // Recompute the parts of the live range we had to remove because of 192687f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen // CR_Replace conflicts. 192787f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen DEBUG(dbgs() << "\t\trestoring liveness to " << EndPoints.size() 192887f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen << " points: " << LHS << '\n'); 192987f7864c6d81ae134335b8271ac12c937c81dffcJakob Stoklund Olesen LIS->extendToIndices(&LHS, EndPoints); 1930c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen return true; 1931c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen} 1932c722ae7a2b470e544ce570692ef3b109449d69ecJakob Stoklund Olesen 19339790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen/// joinIntervals - Attempt to join these two intervals. On failure, this 1934655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// returns false. 19359790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenbool RegisterCoalescer::joinIntervals(CoalescerPair &CP) { 1936cdcdfd2cab67366b1debbe36bf46c29f7fecda67Jakob Stoklund Olesen return CP.isPhys() ? joinReservedPhysReg(CP) : joinVirtRegs(CP); 1937655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1938655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolanamespace { 19403c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick // Information concerning MBB coalescing priority. 19413c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick struct MBBPriorityInfo { 19423c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick MachineBasicBlock *MBB; 19433c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick unsigned Depth; 19443c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick bool IsSplit; 19453c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 19463c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick MBBPriorityInfo(MachineBasicBlock *mbb, unsigned depth, bool issplit) 19473c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick : MBB(mbb), Depth(depth), IsSplit(issplit) {} 19483c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick }; 19493c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 19503c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick // MBBPriorityCompare - Comparison predicate that sorts first based on the 19513c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick // loop depth of the basic block (the unsigned), and then on the MBB number. 1952265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // 1953265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // EnableGlobalCopies assumes that the primary sort key is loop depth. 19543c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick struct MBBPriorityCompare { 1955ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick bool JoinSplitEdges; 1956ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 1957ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick MBBPriorityCompare(bool joinsplits): JoinSplitEdges(joinsplits) {} 1958ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 19593c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick bool operator()(const MBBPriorityInfo &LHS, 19603c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick const MBBPriorityInfo &RHS) const { 1961655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Deeper loops first 19623c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick if (LHS.Depth != RHS.Depth) 19633c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick return LHS.Depth > RHS.Depth; 19643c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick 19653c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick // Try to unsplit critical edges next. 1966ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick if (JoinSplitEdges && LHS.IsSplit != RHS.IsSplit) 19673c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick return LHS.IsSplit; 1968655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1969655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Prefer blocks that are more connected in the CFG. This takes care of 1970655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the most difficult copies first while intervals are short. 19713c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick unsigned cl = LHS.MBB->pred_size() + LHS.MBB->succ_size(); 19723c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick unsigned cr = RHS.MBB->pred_size() + RHS.MBB->succ_size(); 1973655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (cl != cr) 1974655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return cl > cr; 1975655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1976655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // As a last resort, sort by block number. 19773c9e55867e2c8ae7a9e528bce865ebfa963f30a9Andrew Trick return LHS.MBB->getNumber() < RHS.MBB->getNumber(); 1978655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1979655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }; 1980655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1981655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1982265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick/// \returns true if the given copy uses or defines a local live range. 1983265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trickstatic bool isLocalCopy(MachineInstr *Copy, const LiveIntervals *LIS) { 1984265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (!Copy->isCopy()) 1985265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick return false; 1986265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 1987265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick unsigned SrcReg = Copy->getOperand(1).getReg(); 1988265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick unsigned DstReg = Copy->getOperand(0).getReg(); 1989265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (TargetRegisterInfo::isPhysicalRegister(SrcReg) 1990265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick || TargetRegisterInfo::isPhysicalRegister(DstReg)) 1991265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick return false; 1992265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 1993265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick return LIS->intervalIsInOneMBB(LIS->getInterval(SrcReg)) 1994265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick || LIS->intervalIsInOneMBB(LIS->getInterval(DstReg)); 1995265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick} 1996265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 1997b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Try joining WorkList copies starting from index From. 1998b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen// Null out any successful joins. 1999265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trickbool RegisterCoalescer:: 2000265058d9239e6867d06dc8aa40db5f33390abd17Andrew TrickcopyCoalesceWorkList(MutableArrayRef<MachineInstr*> CurrList) { 2001b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Progress = false; 2002265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick for (unsigned i = 0, e = CurrList.size(); i != e; ++i) { 2003265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (!CurrList[i]) 2004b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen continue; 2005bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // Skip instruction pointers that have already been erased, for example by 2006bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen // dead code elimination. 2007265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (ErasedInstrs.erase(CurrList[i])) { 2008265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick CurrList[i] = 0; 2009bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen continue; 2010bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen } 2011b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen bool Again = false; 2012265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick bool Success = joinCopy(CurrList[i], Again); 2013b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen Progress |= Success; 2014b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen if (Success || !Again) 2015265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick CurrList[i] = 0; 2016b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen } 2017b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen return Progress; 2018b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen} 2019b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen 20209790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid 2021b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund OlesenRegisterCoalescer::copyCoalesceInMBB(MachineBasicBlock *MBB) { 2022655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << MBB->getName() << ":\n"); 2023655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2024846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // Collect all copy-like instructions in MBB. Don't start coalescing anything 2025846b183a9ed2999d3f35c7c6b54a5796c0660b9eJakob Stoklund Olesen // yet, it might invalidate the iterator. 2026b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen const unsigned PrevSize = WorkList.size(); 2027ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick if (JoinGlobalCopies) { 2028265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // Coalesce copies bottom-up to coalesce local defs before local uses. They 2029265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // are not inherently easier to resolve, but slightly preferable until we 2030265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // have local live range splitting. In particular this is required by 2031265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // cmp+jmp macro fusion. 2032265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick for (MachineBasicBlock::reverse_iterator 2033265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick MII = MBB->rbegin(), E = MBB->rend(); MII != E; ++MII) { 2034265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (!MII->isCopyLike()) 2035265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick continue; 2036265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (isLocalCopy(&(*MII), LIS)) 2037265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick LocalWorkList.push_back(&(*MII)); 2038265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick else 2039265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick WorkList.push_back(&(*MII)); 2040265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick } 2041265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick } 2042265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick else { 2043265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 2044265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick MII != E; ++MII) 2045265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (MII->isCopyLike()) 2046265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick WorkList.push_back(MII); 2047265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick } 2048b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // Try coalescing the collected copies immediately, and remove the nulls. 2049b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // This prevents the WorkList from getting too large since most copies are 2050b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen // joinable on the first attempt. 2051265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick MutableArrayRef<MachineInstr*> 2052265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick CurrList(WorkList.begin() + PrevSize, WorkList.end()); 2053265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (copyCoalesceWorkList(CurrList)) 2054b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.erase(std::remove(WorkList.begin() + PrevSize, WorkList.end(), 2055b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen (MachineInstr*)0), WorkList.end()); 2056655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 2057655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2058265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trickvoid RegisterCoalescer::coalesceLocals() { 2059265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick copyCoalesceWorkList(LocalWorkList); 2060265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick for (unsigned j = 0, je = LocalWorkList.size(); j != je; ++j) { 2061265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick if (LocalWorkList[j]) 2062265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick WorkList.push_back(LocalWorkList[j]); 2063265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick } 2064265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick LocalWorkList.clear(); 2065265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick} 2066265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick 20679790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesenvoid RegisterCoalescer::joinAllIntervals() { 2068655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 2069265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick assert(WorkList.empty() && LocalWorkList.empty() && "Old data still around."); 2070655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2071f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick std::vector<MBBPriorityInfo> MBBs; 2072f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 2073f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick MachineBasicBlock *MBB = I; 2074f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick MBBs.push_back(MBBPriorityInfo(MBB, Loops->getLoopDepth(MBB), 2075f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick isSplitEdge(MBB))); 2076655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 2077ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick std::sort(MBBs.begin(), MBBs.end(), MBBPriorityCompare(JoinSplitEdges)); 2078f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick 2079f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick // Coalesce intervals in MBB priority order. 2080265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick unsigned CurrDepth = UINT_MAX; 2081265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick for (unsigned i = 0, e = MBBs.size(); i != e; ++i) { 2082265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick // Try coalescing the collected local copies for deeper loops. 2083ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick if (JoinGlobalCopies && MBBs[i].Depth < CurrDepth) 2084265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick coalesceLocals(); 2085f546ac5f9bdedc7d1ae49238c65a93201d0e4f05Andrew Trick copyCoalesceInMBB(MBBs[i].MBB); 2086265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick } 2087265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick coalesceLocals(); 2088655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2089655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Joining intervals can allow other intervals to be joined. Iteratively join 2090655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // until we make no progress. 2091265058d9239e6867d06dc8aa40db5f33390abd17Andrew Trick while (copyCoalesceWorkList(WorkList)) 2092b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen /* empty */ ; 2093655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 2094655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 20955b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::releaseMemory() { 2096bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen ErasedInstrs.clear(); 2097b3776d33cfaba3fc48acccf166d2bd4871ee51c7Jakob Stoklund Olesen WorkList.clear(); 2098bd6f44a3a2a1404721bcbb67edf92b8480a3e655Jakob Stoklund Olesen DeadDefs.clear(); 209903c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen InflateRegs.clear(); 2100655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 2101655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 21025b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 2103c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF = &fn; 2104c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MRI = &fn.getRegInfo(); 2105c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TM = &fn.getTarget(); 2106c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TRI = TM->getRegisterInfo(); 2107c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen TII = TM->getInstrInfo(); 2108c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 2109c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LDV = &getAnalysis<LiveDebugVariables>(); 2110655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AA = &getAnalysis<AliasAnalysis>(); 2111c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen Loops = &getAnalysis<MachineLoopInfo>(); 2112655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2113ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick const TargetSubtargetInfo &ST = TM->getSubtarget<TargetSubtargetInfo>(); 2114ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick if (EnableGlobalCopies == cl::BOU_UNSET) 2115ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick JoinGlobalCopies = ST.enableMachineScheduler(); 2116ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick else 2117ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick JoinGlobalCopies = (EnableGlobalCopies == cl::BOU_TRUE); 2118ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 2119ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick if (EnableJoinSplits == cl::BOU_UNSET) 2120ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick JoinSplitEdges = ST.enableMachineScheduler(); 2121ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick else 2122ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick JoinSplitEdges = (EnableJoinSplits == cl::BOU_TRUE); 2123ad1cc1d1bfc0accd3f1af5c02ac367ff46a4bfdfAndrew Trick 2124655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 2125986d76d7b3844b9a2f3d01a48975952749267a93David Blaikie << "********** Function: " << MF->getName() << '\n'); 2126655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2127655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 2128c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "Before register coalescing"); 2129655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2130655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RegClassInfo.runOnMachineFunction(fn); 2131655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2132655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join (coalesce) intervals if requested. 2133b77ec7d26405125fa5685370af5f17fcc9edbecdJakob Stoklund Olesen if (EnableJoining) 21349790266eeae86b2d763d0760f239ab90bc1de84aJakob Stoklund Olesen joinAllIntervals(); 2135655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 21364a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // After deleting a lot of copies, register classes may be less constrained. 213703c8383324da4fe42fae4e5685072a782935644dJakob Stoklund Olesen // Removing sub-register operands may allow GR32_ABCD -> GR32 and DPR_VFP2 -> 21384a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen // DPR inflation. 21394a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 21404a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 21414a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen InflateRegs.end()); 21424a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 21434a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 21444a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen unsigned Reg = InflateRegs[i]; 21454a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->reg_nodbg_empty(Reg)) 21464a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen continue; 21474a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen if (MRI->recomputeRegClass(Reg, *TM)) { 21484a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 21494a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen << MRI->getRegClass(Reg)->getName() << '\n'); 21504a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen ++NumInflated; 21514a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 21524a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen } 21534a74b3b933e2944ff313dc5d24da6f9e8ec4c1c4Jakob Stoklund Olesen 2154655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dump()); 2155c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen DEBUG(LDV->dump()); 2156655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 2157c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen MF->verify(this, "After register coalescing"); 2158655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 2159655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 2160655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2161655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// print - Implement the dump method. 21625b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 2163c19e6dd64fe4fa825c8d79e1d097e301c66eaf72Jakob Stoklund Olesen LIS->print(O, m); 2164655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 2165