RegisterCoalescer.cpp revision 5b220213bfe9c37c2bb41a7ae0804e06a14f1007
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 16655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#define DEBUG_TYPE "regcoalescing" 17fdf16ca44f130afe80c57481d0c08130aa08cc09Rafael Espindola#include "RegisterCoalescer.h" 18655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "VirtRegMap.h" 19655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "LiveDebugVariables.h" 20655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 21655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Pass.h" 22655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Value.h" 232c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/LiveIntervalAnalysis.h" 242c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene#include "llvm/CodeGen/MachineInstr.h" 2540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen#include "llvm/CodeGen/MachineRegisterInfo.h" 2640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen#include "llvm/Target/TargetInstrInfo.h" 276f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 28655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/LiveIntervalAnalysis.h" 29655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Analysis/AliasAnalysis.h" 30655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineFrameInfo.h" 31655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineInstr.h" 32655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineLoopInfo.h" 33655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/MachineRegisterInfo.h" 34655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/CodeGen/Passes.h" 35655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetInstrInfo.h" 36655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetMachine.h" 37655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Target/TargetOptions.h" 38655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/CommandLine.h" 39655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/Debug.h" 40655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/ErrorHandling.h" 41655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/Support/raw_ostream.h" 42655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/OwningPtr.h" 43655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/SmallSet.h" 44655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/Statistic.h" 45655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include "llvm/ADT/STLExtras.h" 46655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <algorithm> 47655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola#include <cmath> 482c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greeneusing namespace llvm; 492c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 50655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numJoins , "Number of interval joins performed"); 51655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 52655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numCommutes , "Number of instruction commuting performed"); 53655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numExtends , "Number of copies extended"); 54655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(NumReMats , "Number of instructions re-materialized"); 55655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 56655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaSTATISTIC(numAborts , "Number of times interval joining aborted"); 57655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 58655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 59655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnableJoining("join-liveintervals", 60655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Coalesce copies (default=true)"), 61655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(true)); 62655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 63655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 64655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaDisableCrossClassJoin("disable-cross-class-join", 65655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Avoid coalescing cross register class copies"), 66655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(false), cl::Hidden); 67655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 68655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 69655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaEnablePhysicalJoin("join-physregs", 70655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Join physical register copies"), 71655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::init(false), cl::Hidden); 72655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 73655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic cl::opt<bool> 74655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaVerifyCoalescing("verify-coalescing", 75655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::desc("Verify machine instrs before and after register coalescing"), 76655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola cl::Hidden); 77655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 785b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 795b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 80655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 81655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 82655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 83655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 84655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 85655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(PHIElimination) 86655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 87655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael EspindolaINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 885b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 895b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola "Simple Register Coalescing", false, false) 90655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 912c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greenechar RegisterCoalescer::ID = 0; 922c17c4d8d9f232f0329786ad9abee976bc0f3d27David Greene 9340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenunsigned CoalescerPair::compose(unsigned a, unsigned b) const { 9440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!a) return b; 9540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!b) return a; 9640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return tri_.composeSubRegIndices(a, b); 9740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 9840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 9940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::isMoveInstr(const MachineInstr *MI, 10040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned &Src, unsigned &Dst, 10140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned &SrcSub, unsigned &DstSub) const { 102273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen if (MI->isCopy()) { 103273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 104273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen DstSub = MI->getOperand(0).getSubReg(); 105273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen Src = MI->getOperand(1).getReg(); 106273f7e42994a5bce0614d04d96dbfdf05fd652e5Jakob Stoklund Olesen SrcSub = MI->getOperand(1).getSubReg(); 1075c00e077952d14899c3fc26709c7b2dfd36d0209Jakob Stoklund Olesen } else if (MI->isSubregToReg()) { 10840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = MI->getOperand(0).getReg(); 10940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = compose(MI->getOperand(0).getSubReg(), MI->getOperand(3).getImm()); 11040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Src = MI->getOperand(2).getReg(); 11140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = MI->getOperand(2).getSubReg(); 11204c528a0c86ddf3d6a70681f72e1b2ec07b0b53aJakob Stoklund Olesen } else 11340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 11440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 11540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 11640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 11740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::setRegisters(const MachineInstr *MI) { 11840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen srcReg_ = dstReg_ = subIdx_ = 0; 11940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen newRC_ = 0; 1208df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen flipped_ = crossClass_ = false; 12140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 12240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 12340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!isMoveInstr(MI, Src, Dst, SrcSub, DstSub)) 12440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 12540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen partial_ = SrcSub || DstSub; 12640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 12740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // If one register is a physreg, it must be Dst. 12840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Src)) { 12940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) 13040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 13140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 13240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 13340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen flipped_ = true; 13440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 13540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 13640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 13740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 13840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 13940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate DstSub on a physreg. 14040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) { 14140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = tri_.getSubReg(Dst, DstSub); 14240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 14340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = 0; 14440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 14540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 14640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Eliminate SrcSub by picking a corresponding Dst superregister. 14740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 14840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = tri_.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 14940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!Dst) return false; 15040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 15140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else if (!MRI.getRegClass(Src)->contains(Dst)) { 15240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 15340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 15440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 15540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Both registers are virtual. 15640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 1578df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // Both registers have subreg indices. 1588df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub && DstSub) { 1598df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // For now we only handle the case of identical indices in commensurate 1608df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // registers: Dreg:ssub_1 + Dreg:ssub_1 -> Dreg 1618df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen // FIXME: Handle Qreg:ssub_3 + Dreg:ssub_1 as QReg:dsub_1 + Dreg. 1628df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (SrcSub != DstSub) 1638df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 1648df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 1658df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 1668df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen if (!getCommonSubClass(DstRC, SrcRC)) 1678df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen return false; 16840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = DstSub = 0; 1698df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen } 17040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 17140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // There can be no SrcSub. 17240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (SrcSub) { 17340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 17440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen DstSub = SrcSub; 17540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen SrcSub = 0; 17640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!flipped_ && "Unexpected flip"); 17740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen flipped_ = true; 17840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 17940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 18040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Find the new register class. 18140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 18240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 18340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 18440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen newRC_ = tri_.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 18540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen else 18640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen newRC_ = getCommonSubClass(DstRC, SrcRC); 18740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!newRC_) 18840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 1898df08017d81ef3749acdc3234e3f33c15a6d0defJakob Stoklund Olesen crossClass_ = newRC_ != DstRC || newRC_ != SrcRC; 19040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 19140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Check our invariants 19240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 19340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 19440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen "Cannot have a physical SubIdx"); 19540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen srcReg_ = Src; 19640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen dstReg_ = Dst; 19740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen subIdx_ = DstSub; 19840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 19940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 20040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 20140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::flip() { 20240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (subIdx_ || TargetRegisterInfo::isPhysicalRegister(dstReg_)) 20340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 20440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(srcReg_, dstReg_); 20540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen flipped_ = !flipped_; 20640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return true; 20740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 20840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 20940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesenbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 21040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!MI) 21140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 21240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen unsigned Src, Dst, SrcSub, DstSub; 21340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!isMoveInstr(MI, Src, Dst, SrcSub, DstSub)) 21440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 21540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 21640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Find the virtual register that is srcReg_. 21740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (Dst == srcReg_) { 21840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(Src, Dst); 21940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen std::swap(SrcSub, DstSub); 22040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else if (Src != srcReg_) { 22140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 22240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 22340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 22440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Now check that Dst matches dstReg_. 22540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (TargetRegisterInfo::isPhysicalRegister(dstReg_)) { 22640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 22740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 22840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen assert(!subIdx_ && "Inconsistent CoalescerPair state."); 22940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // DstSub could be set for a physreg from INSERT_SUBREG. 23040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (DstSub) 23140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen Dst = tri_.getSubReg(Dst, DstSub); 23240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Full copy of Src. 23340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (!SrcSub) 23440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return dstReg_ == Dst; 23540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // This is a partial register copy. Check that the parts match. 23640d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return tri_.getSubReg(dstReg_, SrcSub) == Dst; 23740d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } else { 23840d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // dstReg_ is virtual. 23940d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen if (dstReg_ != Dst) 24040d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return false; 24140d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen // Registers match, do the subregisters line up? 24240d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen return compose(subIdx_, SrcSub) == DstSub; 24340d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen } 24440d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen} 24540d07bbebbe73914af28be1bdab169ce8333adcaJakob Stoklund Olesen 2465b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 247655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.setPreservesCFG(); 248655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<AliasAnalysis>(); 249655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveIntervals>(); 250655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveIntervals>(); 251655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<LiveDebugVariables>(); 252655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<LiveDebugVariables>(); 253655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<SlotIndexes>(); 254655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addRequired<MachineLoopInfo>(); 255655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreserved<MachineLoopInfo>(); 256655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(MachineDominatorsID); 257655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(StrongPHIEliminationID); 258655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(PHIEliminationID); 259655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AU.addPreservedID(TwoAddressInstructionPassID); 260655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineFunctionPass::getAnalysisUsage(AU); 261655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 262655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 2635b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::markAsJoined(MachineInstr *CopyMI) { 264655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Joined copies are not deleted immediately, but kept in JoinedCopies. 265655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola JoinedCopies.insert(CopyMI); 266655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 267655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Mark all register operands of CopyMI as <undef> so they won't affect dead 268655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// code elimination. 269655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineInstr::mop_iterator I = CopyMI->operands_begin(), 270655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = CopyMI->operands_end(); I != E; ++I) 271655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->isReg()) 272655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I->setIsUndef(true); 273655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 274655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 275655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 276655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being the source and IntB being the dest, thus this defines a value number 277655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// in IntB. If the source value number (in IntA) is defined by a copy from B, 278655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// see if we can merge these two pieces of B into a single value number, 279655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// eliminating a copy. For example: 280655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 281655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = B0 282655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 283655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 284655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 285655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 286655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// value number to be replaced with B0 (which simplifies the B liveinterval). 287655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 288655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 289655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 2905b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::AdjustCopiesBackFrom(const CoalescerPair &CP, 291655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 292655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Bail if there is no dst interval - can happen when merging physical subreg 293655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // operations. 294655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(CP.getDstReg())) 295655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 296655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 297655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 298655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 299655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 300655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 301655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex(); 302655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 303655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 304655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 305655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 306655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BLR == IntB.end()) return false; 307655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = BLR->valno; 308655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 309655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the location that B is defined at. Two options: either this value has 310655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // an unknown definition point or it is defined at CopyIdx. If unknown, we 311655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // can't process it. 312655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!BValNo->isDefByCopy()) return false; 313655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 314655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 315655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 316655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex CopyUseIdx = CopyIdx.getUseIndex(); 317655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 318655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live range might not exist after fun with physreg coalescing. 319655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR == IntA.end()) return false; 320655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo = ALR->valno; 321655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If it's re-defined by an early clobber somewhere in the live range, then 322655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. 323655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // See PR3149: 324655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 172 %ECX<def> = MOV32rr %reg1039<kill> 325655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 180 INLINEASM <es:subl $5,$1 326655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, 327655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %EAX<kill>, 328655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 329655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 188 %EAX<def> = MOV32rr %EAX<kill> 330655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 196 %ECX<def> = MOV32rr %ECX<kill> 331655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 204 %ECX<def> = MOV32rr %ECX<kill> 332655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 212 %EAX<def> = MOV32rr %EAX<kill> 333655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 220 %EAX<def> = MOV32rr %EAX 334655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 228 %reg1039<def> = MOV32rr %ECX<kill> 335655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The early clobber operand ties ECX input to the ECX def. 336655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 337655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The live interval of ECX is represented as this: 338655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) 339655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The coalescer has no idea there was a def in the middle of [174,230]. 340655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AValNo->hasRedefByEC()) 341655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 342655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 343655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If AValNo is defined as a copy from IntB, we can potentially process this. 344655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the instruction that defines this value number. 345655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isCoalescable(AValNo->getCopy())) 346655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 347655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 348655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Get the LiveRange in IntB that this value number starts with. 349655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ValLR = 350655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 351655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR == IntB.end()) 352655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 353655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 354655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure that the end of the live range is inside the same block as 355655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI. 356655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *ValLREndInst = 357655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInstructionFromIndex(ValLR->end.getPrevSlot()); 358655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 359655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 360655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 361655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we now know that ValLR ends in the same block that the CopyMI 362655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live-range starts. If there are no intervening live ranges between them in 363655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // IntB, we can merge them. 364655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValLR+1 != BLR) return false; 365655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 366655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If a live interval is a physical register, conservatively check if any 367655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // of its aliases is overlapping the live interval of the virtual register. 368655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, do not coalesce. 369655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 370655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned *AS = tri_->getAliasSet(IntB.reg); *AS; ++AS) 371655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(*AS) && IntA.overlaps(li_->getInterval(*AS))) { 372655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 373655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterfere with alias "; 374655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(*AS).print(dbgs(), tri_); 375655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 376655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 377655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 378655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 379655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 380655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 381655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "Extending: "; 382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.print(dbgs(), tri_); 383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We are about to delete CopyMI, so need to remove it as the 'instruction 387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // that defines this value #'. Update the valnum with the new defining 388655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instruction #. 389655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo->def = FillerStart; 390655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo->setCopy(0); 391655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 392655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, we can merge them. We need to insert a new liverange: 393655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // [ValLR.end, BLR.begin) of either value number, then we merge the 394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // two value numbers. 395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 396655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 397655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the IntB live range is assigned to a physical register, and if that 398655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // physreg has sub-registers, update their live intervals as well. 399655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 400655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned *SR = tri_->getSubRegisters(IntB.reg); *SR; ++SR) { 401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(*SR)) 402655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 403655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &SRLI = li_->getInterval(*SR); 404655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SRLI.addRange(LiveRange(FillerStart, FillerEnd, 405655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SRLI.getNextValue(FillerStart, 0, 406655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getVNInfoAllocator()))); 407655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 408655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, merge "B1" into the same value number as "B0". 411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BValNo != ValLR->valno) { 412655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If B1 is killed by a PHI, then the merged live range must also be killed 413655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // by the same PHI, as B0 and B1 can not overlap. 414655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool HasPHIKill = BValNo->hasPHIKill(); 415655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.MergeValueNumberInto(BValNo, ValLR->valno); 416655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (HasPHIKill) 417655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLR->valno->setHasPHIKill(true); 418655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 419655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 420655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << " result = "; 421655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.print(dbgs(), tri_); 422655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 423655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 425655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the source instruction was killing the source register before the 426655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, unset the isKill marker given the live range has been extended. 427655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 428655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UIdx != -1) { 429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValLREndInst->getOperand(UIdx).setIsKill(false); 430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the copy instruction was killing the destination register before the 433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // merge, find the last use and trim the live range. That will also add the 434655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // isKill marker. 435655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ALR->end == CopyIdx) 436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->shrinkToUses(&IntA); 437655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 438655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numExtends; 439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 440655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 441655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 442655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// HasOtherReachingDefs - Return true if there are definitions of IntB 443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// other than BValNo val# that can reach uses of AValno val# of IntA. 4445b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::HasOtherReachingDefs(LiveInterval &IntA, 445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB, 446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo, 447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo) { 448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::Ranges::iterator BI = 452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI != IntB.ranges.begin()) 454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola --BI; 455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->valno == BValNo) 457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start <= AI->start && BI->end > AI->start) 459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (BI->start > AI->start && BI->start < AI->end) 461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with 468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// IntA being the source and IntB being the dest, thus this defines a value 469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// number in IntB. If the source value number (in IntA) is defined by a 470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// commutable instruction and its other operand is coalesced to the copy dest 471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// register, see if we can transform the copy into a noop by commuting the 472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// definition. For example, 473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// A3 = op A2 B0<kill> 475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = A3 <- this copy 477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op A3 <- more uses 479655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ==> 481655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 482655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B2 = op B0 A2<kill> 483655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 484655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// B1 = B2 <- now an identify copy 485655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ... 486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// = op B2 <- more uses 487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// This returns true if an interval was modified. 489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 4905b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::RemoveCopyByCommutingDef(const CoalescerPair &CP, 491655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 492655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME: For now, only eliminate the copy by commuting its def when the 493655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // source register is a virtual register. We want to guard against cases 494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // where the copy is a back edge copy and commuting the def lengthen the 495655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // live interval of the source register to the entire loop. 496655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys() && CP.isFlipped()) 497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 498655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 499655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Bail if there is no dst interval. 500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(CP.getDstReg())) 501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getDefIndex(); 504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntA = 506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &IntB = 508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo is a value number in B that is defined by a copy from A. 'B3' in 511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the example above. 512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!BValNo || !BValNo->isDefByCopy()) 514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 516655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // AValNo is the value number in A that defines the copy, A3 in the example. 519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getUseIndex()); 520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(AValNo && "COPY source not live"); 521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If other defs can reach uses of this def, then it's not safe to perform 523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the optimization. 524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *DefMI = li_->getInstructionFromIndex(AValNo->def); 527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 528655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetInstrDesc &TID = DefMI->getDesc(); 530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TID.isCommutable()) 531655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If DefMI is a two-address instruction then commuting it will change the 533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // destination register. 534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 535655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefIdx != -1); 536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UseOpIdx; 537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Op1, Op2, NewDstIdx; 540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!tii_->findCommutedOpIndices(DefMI, Op1, Op2)) 541655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Op1 == UseOpIdx) 543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op2; 544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (Op2 == UseOpIdx) 545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewDstIdx = Op1; 546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewReg = NewDstMO.getReg(); 551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewReg != IntB.reg || !NewDstMO.isKill()) 552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure there are no other definitions of IntB that would reach the 555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // uses which the new definition can reach. 556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Abort if the aliases of IntB.reg have values that are not simply the 560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // clobbers from the superreg. 561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) 562655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned *AS = tri_->getAliasSet(IntB.reg); *AS; ++AS) 563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(*AS) && 564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola HasOtherReachingDefs(IntA, li_->getInterval(*AS), AValNo, 0)) 565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If some of the uses of IntA.reg is already coalesced away, return false. 568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // It's not possible to determine whether it's safe to perform the coalescing. 569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineRegisterInfo::use_nodbg_iterator UI = 570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->use_nodbg_begin(IntA.reg), 571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UE = mri_->use_nodbg_end(); UI != UE; ++UI) { 572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex UseIdx = li_->getInstructionIndex(UseMI); 574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end()) 576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR->valno == AValNo && JoinedCopies.count(UseMI)) 578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tRemoveCopyByCommutingDef: " << AValNo->def << '\t' 582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << *DefMI); 583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // At this point we have decided that it is legal to do this 585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // transformation. Start by commuting the instruction. 586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = DefMI->getParent(); 587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = tii_->commuteInstruction(DefMI); 588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!NewMI) 589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TargetRegisterInfo::isVirtualRegister(IntB.reg) && 592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !mri_->constrainRegClass(IntB.reg, mri_->getRegClass(IntA.reg))) 593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewMI != DefMI) { 595655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->ReplaceMachineInstrInMaps(DefMI, NewMI); 596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->insert(DefMI, NewMI); 597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBB->erase(DefMI); 598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 600655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->getOperand(OpIdx).setIsKill(); 601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A = or A, B 604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 605655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // B = A 606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // C = A<kill> 608655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ... 609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // = B 610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update uses of IntA of the specific Val# with IntB. 612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineRegisterInfo::use_iterator UI = mri_->use_begin(IntA.reg), 613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UE = mri_->use_end(); UI != UE;) { 614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &UseMO = UI.getOperand(); 615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = &*UI; 616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++UI; 617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(UseMI)) 618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isDebugValue()) { 620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME These don't have an instruction index. Not clear we have enough 621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // info to decide whether to do this replacement or not. For now do it. 622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 624655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 625655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex UseIdx = li_->getInstructionIndex(UseMI).getUseIndex(); 626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ULR == IntA.end() || ULR->valno != AValNo) 628655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 629655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.substPhysReg(NewReg, *tri_); 631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMO.setReg(NewReg); 633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI == CopyMI) 634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isCopy()) 636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->getOperand(0).getReg() != IntB.reg || 638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getSubReg()) 639655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 640655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 641655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This copy will become a noop. If it's defining a new val#, merge it into 642655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // BValNo. 643655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex DefIdx = UseIdx.getDefIndex(); 644655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 645655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DVNI) 646655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 647655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 648655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DVNI->def == DefIdx); 649655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(UseMI); 651655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 652655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 654655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // is updated. 655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = BValNo; 656655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->def = AValNo->def; 657655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ValNo->setCopy(0); 658655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 659655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AI != AE; ++AI) { 660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AI->valno != AValNo) continue; 661655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 663655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 664655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola IntA.removeValNo(AValNo); 666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCommutes; 668655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial 672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// computation, replace the copy by rematerialize the definition. 6735b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::ReMaterializeTrivialDef(LiveInterval &SrcInt, 674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool preserveSrcInt, 675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstReg, 676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstSubIdx, 677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *CopyMI) { 678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex CopyIdx = li_->getInstructionIndex(CopyMI).getUseIndex(); 679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(SrcLR != SrcInt.end() && "Live range not found!"); 681655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *ValNo = SrcLR->valno; 682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If other defs can reach uses of this def, then it's not safe to perform 683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the optimization. 684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ValNo->isPHIDef() || ValNo->isUnused() || ValNo->hasPHIKill()) 685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 686655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *DefMI = li_->getInstructionFromIndex(ValNo->def); 687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI) 688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(DefMI && "Defining instruction disappeared"); 690655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetInstrDesc &TID = DefMI->getDesc(); 691655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TID.isAsCheapAsAMove()) 692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 693655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!tii_->isTriviallyReMaterializable(DefMI, AA)) 694655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 695655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SawStore = false; 696655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isSafeToMove(tii_, AA, SawStore)) 697655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 698655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TID.getNumDefs() != 1) 699655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 700655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DefMI->isImplicitDef()) { 701655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Make sure the copy destination register class fits the instruction 702655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // definition register class. The mismatch can happen as a result of earlier 703655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // extract_subreg, insert_subreg, subreg_to_reg coalescing. 704655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *RC = TID.OpInfo[0].getRegClass(tri_); 705655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 706655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (mri_->getRegClass(DstReg) != RC) 707655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 708655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (!RC->contains(DstReg)) 709655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 710655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 711655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 712655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If destination register has a sub-register index on it, make sure it 713655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // matches the instruction register class. 714655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstSubIdx) { 715655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetInstrDesc &TID = DefMI->getDesc(); 716655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TID.getNumDefs() != 1) 717655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 718655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *DstRC = mri_->getRegClass(DstReg); 719655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *DstSubRC = 720655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstRC->getSubRegisterRegClass(DstSubIdx); 721655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *DefRC = TID.OpInfo[0].getRegClass(tri_); 722655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DefRC == DstRC) 723655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstSubIdx = 0; 724655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (DefRC != DstSubRC) 725655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 726655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 727655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 728655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyFlag(DstReg, CopyMI); 729655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 730655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = CopyMI->getParent(); 731655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock::iterator MII = 732655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola llvm::next(MachineBasicBlock::iterator(CopyMI)); 733655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tii_->reMaterialize(*MBB, MII, DstReg, DstSubIdx, DefMI, *tri_); 734655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *NewMI = prior(MII); 735655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 736655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CopyMI may have implicit operands, transfer them over to the newly 737655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerialized instruction. And update implicit def interval valnos. 738655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = CopyMI->getDesc().getNumOperands(), 739655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola e = CopyMI->getNumOperands(); i != e; ++i) { 740655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = CopyMI->getOperand(i); 741655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isReg() && MO.isImplicit()) 742655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->addOperand(MO); 743655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isDef()) 744655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyFlag(MO.getReg(), CopyMI); 745655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 746655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 747655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewMI->copyImplicitOps(CopyMI); 748655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->ReplaceMachineInstrInMaps(CopyMI, NewMI); 749655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyMI->eraseFromParent(); 750655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatCopies.insert(CopyMI); 751655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatDefs.insert(DefMI); 752655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "Remat: " << *NewMI); 753655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++NumReMats; 754655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 755655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The source interval can become smaller because we removed a use. 756655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (preserveSrcInt) 757655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->shrinkToUses(&SrcInt); 758655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 759655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 760655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 761655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 762655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 763655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// update the subregister number if it is not zero. If DstReg is a 764655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// physical register and the existing subregister number of the def / use 765655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// being updated is not zero, make sure to set it to the correct physical 766655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// subregister. 767655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolavoid 7685b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaRegisterCoalescer::UpdateRegDefsUses(const CoalescerPair &CP) { 769655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DstIsPhys = CP.isPhys(); 770655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg = CP.getSrcReg(); 771655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstReg = CP.getDstReg(); 772655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SubIdx = CP.getSubIdx(); 773655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 774655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update LiveDebugVariables. 775655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ldv_->renameRegister(SrcReg, DstReg, SubIdx); 776655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 777655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(SrcReg); 778655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *UseMI = I.skipInstruction();) { 779655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // A PhysReg copy that won't be coalesced can perhaps be rematerialized 780655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // instead. 781655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) { 782655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (UseMI->isCopy() && 783655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !UseMI->getOperand(1).getSubReg() && 784655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !UseMI->getOperand(0).getSubReg() && 785655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(1).getReg() == SrcReg && 786655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getReg() != SrcReg && 787655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getReg() != DstReg && 788655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !JoinedCopies.count(UseMI) && 789655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMaterializeTrivialDef(li_->getInterval(SrcReg), false, 790655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->getOperand(0).getReg(), 0, UseMI)) 791655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 792655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 793655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 794655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned,8> Ops; 795655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Reads, Writes; 796655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 797655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Kills = false, Deads = false; 798655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 799655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Replace SrcReg with DstReg in all UseMI operands. 800655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 801655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = UseMI->getOperand(Ops[i]); 802655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Kills |= MO.isKill(); 803655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Deads |= MO.isDead(); 804655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 805655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys) 806655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MO.substPhysReg(DstReg, *tri_); 807655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 808655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MO.substVirtReg(DstReg, SubIdx, *tri_); 809655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 810655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 811655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This instruction is a copy that will be removed. 812655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(UseMI)) 813655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 814655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 815655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (SubIdx) { 816655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If UseMI was a simple SrcReg def, make sure we didn't turn it into a 817655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // read-modify-write of DstReg. 818655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Deads) 819655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->addRegisterDead(DstReg, tri_); 820655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (!Reads && Writes) 821655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->addRegisterDefined(DstReg, tri_); 822655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 823655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Kill flags apply to the whole physical register. 824655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstIsPhys && Kills) 825655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UseMI->addRegisterKilled(DstReg, tri_); 826655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 827655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 828655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 829655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tupdated: "; 830655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!UseMI->isDebugValue()) 831655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << li_->getInstructionIndex(UseMI) << "\t"; 832655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << *UseMI; 833655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 834655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 835655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 836655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 837655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// removeIntervalIfEmpty - Check if the live interval of a physical register 838655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// is empty, if so remove it and also remove the empty intervals of its 839655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// sub-registers. Return true if live interval is removed. 840655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *li_, 841655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterInfo *tri_) { 842655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li.empty()) { 843655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(li.reg)) 844655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned* SR = tri_->getSubRegisters(li.reg); *SR; ++SR) { 845655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(*SR)) 846655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 847655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &sli = li_->getInterval(*SR); 848655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (sli.empty()) 849655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->removeInterval(*SR); 850655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 851655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->removeInterval(li.reg); 852655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 853655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 854655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 855655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 856655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 857655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// RemoveDeadDef - If a def of a live interval is now determined dead, remove 858655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// the val# it defines. If the live interval becomes empty, remove it as well. 8595b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::RemoveDeadDef(LiveInterval &li, 860655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *DefMI) { 861655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex DefIdx = li_->getInstructionIndex(DefMI).getDefIndex(); 862655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); 863655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DefIdx != MLR->valno->def) 864655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 865655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li.removeValNo(MLR->valno); 866655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return removeIntervalIfEmpty(li, li_, tri_); 867655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 868655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 8695b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::RemoveCopyFlag(unsigned DstReg, 870655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const MachineInstr *CopyMI) { 871655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex DefIdx = li_->getInstructionIndex(CopyMI).getDefIndex(); 872655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(DstReg)) { 873655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &LI = li_->getInterval(DstReg); 874655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 875655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LR->valno->def == DefIdx) 876655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LR->valno->setCopy(0); 877655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 878655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TargetRegisterInfo::isPhysicalRegister(DstReg)) 879655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return; 880655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned* AS = tri_->getAliasSet(DstReg); *AS; ++AS) { 881655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(*AS)) 882655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 883655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &LI = li_->getInterval(*AS); 884655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 885655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LR->valno->def == DefIdx) 886655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LR->valno->setCopy(0); 887655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 888655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 889655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 890655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// shouldJoinPhys - Return true if a copy involving a physreg should be joined. 891655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// We need to be careful about coalescing a source physical register with a 892655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// virtual register. Once the coalescing is done, it cannot be broken and these 893655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// are not spillable! If the destination interval uses are far away, think 894655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// twice about coalescing them! 8955b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::shouldJoinPhys(CoalescerPair &CP) { 896655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Allocatable = li_->isAllocatable(CP.getDstReg()); 897655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &JoinVInt = li_->getInterval(CP.getSrcReg()); 898655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 899655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// Always join simple intervals that are defined by a single copy from a 900655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// reserved register. This doesn't increase register pressure, so it is 901655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola /// always beneficial. 902655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Allocatable && CP.isFlipped() && JoinVInt.containsOneValue()) 903655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 904655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 905655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!EnablePhysicalJoin) { 906655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tPhysreg joins disabled.\n"); 907655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 908655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 909655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 910655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Only coalesce to allocatable physreg, we don't want to risk modifying 911655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // reserved registers. 912655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Allocatable) { 913655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n"); 914655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 915655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 916655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 917655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Don't join with physregs that have a ridiculous number of live 918655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ranges. The data structure performance is really bad when that 919655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // happens. 920655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(CP.getDstReg()) && 921655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.getDstReg()).ranges.size() > 1000) { 922655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numAborts; 923655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() 924655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "\tPhysical register live interval too complicated, abort!\n"); 925655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 926655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 927655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 928655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // FIXME: Why are we skipping this test for partial copies? 929655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // CodeGen/X86/phys_subreg_coalesce-3.ll needs it. 930655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isPartial()) { 931655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *RC = mri_->getRegClass(CP.getSrcReg()); 932655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Threshold = RegClassInfo.getNumAllocatableRegs(RC) * 2; 933655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Length = li_->getApproximateInstructionCount(JoinVInt); 934655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Length > Threshold) { 935655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numAborts; 936655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n"); 937655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 938655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 939655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 940655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 941655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 942655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 943655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// isWinToJoinCrossClass - Return true if it's profitable to coalesce 944655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// two virtual registers from different register classes. 945655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolabool 9465b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaRegisterCoalescer::isWinToJoinCrossClass(unsigned SrcReg, 9475b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola unsigned DstReg, 948655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *SrcRC, 949655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *DstRC, 950655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const TargetRegisterClass *NewRC) { 951655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewRCCount = RegClassInfo.getNumAllocatableRegs(NewRC); 952655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // This heuristics is good enough in practice, but it's obviously not *right*. 953655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // 4 is a magic number that works well enough for x86, ARM, etc. It filter 954655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // out all but the most restrictive register classes. 955655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewRCCount > 4 || 956655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Early exit if the function is fairly small, coalesce aggressively if 957655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // that's the case. For really special register classes with 3 or 958655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // fewer registers, be a bit more careful. 959655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola (li_->getFuncInstructionCount() / NewRCCount) < 8) 960655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 961655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &SrcInt = li_->getInterval(SrcReg); 962655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &DstInt = li_->getInterval(DstReg); 963655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcSize = li_->getApproximateInstructionCount(SrcInt); 964655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstSize = li_->getApproximateInstructionCount(DstInt); 965655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 966655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalesce aggressively if the intervals are small compared to the number of 967655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers in the new class. The number 4 is fairly arbitrary, chosen to be 968655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // less aggressive than the 8 used for the whole function size. 969655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const unsigned ThresSize = 4 * NewRCCount; 970655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (SrcSize <= ThresSize && DstSize <= ThresSize) 971655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 972655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 973655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Estimate *register use density*. If it doubles or more, abort. 974655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcUses = std::distance(mri_->use_nodbg_begin(SrcReg), 975655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->use_nodbg_end()); 976655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstUses = std::distance(mri_->use_nodbg_begin(DstReg), 977655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->use_nodbg_end()); 978655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewUses = SrcUses + DstUses; 979655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned NewSize = SrcSize + DstSize; 980655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (SrcRC != NewRC && SrcSize > ThresSize) { 981655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcRCCount = RegClassInfo.getNumAllocatableRegs(SrcRC); 982655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount) 983655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 984655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 985655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DstRC != NewRC && DstSize > ThresSize) { 986655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DstRCCount = RegClassInfo.getNumAllocatableRegs(DstRC); 987655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount) 988655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 989655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 990655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 991655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 992655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 993655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 994655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 995655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// which are the src/dst of the copy instruction CopyMI. This returns true 996655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// if the copy was successfully coalesced away. If it is not currently 997655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// possible to coalesce this interval, but it may be possible if other 998655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// things get coalesced, then it returns true by reference in 'Again'. 9995b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::JoinCopy(MachineInstr *CopyMI, bool &Again) { 1000655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1001655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = false; 1002655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) 1003655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Already done. 1004655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1005655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << li_->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 1006655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1007655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CoalescerPair CP(*tii_, *tri_); 1008655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.setRegisters(CopyMI)) { 1009655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tNot coalescable.\n"); 1010655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1011655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1012655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1013655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If they are already joined we continue. 1014655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.getSrcReg() == CP.getDstReg()) { 1015655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1016655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCopy already coalesced.\n"); 1017655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; // Not coalescable. 1018655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1019655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1020655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), tri_) 1021655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << " with " << PrintReg(CP.getDstReg(), tri_, CP.getSubIdx()) 1022655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "\n"); 1023655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1024655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Enforce policies. 1025655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1026655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!shouldJoinPhys(CP)) { 1027655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Before giving up coalescing, if definition of source is defined by 1028655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // trivial computation, try rematerializing it. 1029655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 1030655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMaterializeTrivialDef(li_->getInterval(CP.getSrcReg()), true, 1031655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.getDstReg(), 0, CopyMI)) 1032655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1033655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1034655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1035655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1036655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Avoid constraining virtual register regclass too much. 1037655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1038655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCross-class to " << CP.getNewRC()->getName() << ".\n"); 1039655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (DisableCrossClassJoin) { 1040655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tCross-class joins disabled.\n"); 1041655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1042655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1043655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(), 1044655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->getRegClass(CP.getSrcReg()), 1045655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->getRegClass(CP.getDstReg()), 1046655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.getNewRC())) { 1047655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tAvoid coalescing to constrained register class.\n"); 1048655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1049655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1050655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1051655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1052655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1053655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When possible, let DstReg be the larger interval. 1054655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.getSubIdx() && li_->getInterval(CP.getSrcReg()).ranges.size() > 1055655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->getInterval(CP.getDstReg()).ranges.size()) 1056655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.flip(); 1057655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1058655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1059655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Okay, attempt to join these two intervals. On failure, this returns false. 1060655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, if one of the intervals being joined is a physreg, this method 1061655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // always canonicalizes DstInt to be it. The output "SrcInt" will not have 1062655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been modified, so we can use this information below to update aliases. 1063655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinIntervals(CP)) { 1064655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing failed. 1065655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1066655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If definition of source is defined by trivial computation, try 1067655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // rematerializing it. 1068655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isFlipped() && 1069655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMaterializeTrivialDef(li_->getInterval(CP.getSrcReg()), true, 1070655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CP.getDstReg(), 0, CopyMI)) 1071655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1072655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1073655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we can eliminate the copy without merging the live ranges, do so now. 1074655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isPartial()) { 1075655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (AdjustCopiesBackFrom(CP, CopyMI) || 1076655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveCopyByCommutingDef(CP, CopyMI)) { 1077655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1078655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tTrivial!\n"); 1079655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1080655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1081655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1082655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1083655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, we are unable to join the intervals. 1084655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "\tInterference!\n"); 1085655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Again = true; // May be possible to coalesce later. 1086655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1087655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1088655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1089655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Coalescing to a virtual register that is of a sub-register class of the 1090655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // other. Make sure the resulting register is set to the right register class. 1091655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isCrossClass()) { 1092655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numCrossRCs; 1093655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_->setRegClass(CP.getDstReg(), CP.getNewRC()); 1094655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1095655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1096655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Remember to delete the copy instruction. 1097655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola markAsJoined(CopyMI); 1098655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1099655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola UpdateRegDefsUses(CP); 1100655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1101655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we have extended the live range of a physical register, make sure we 1102655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // update live-in lists as well. 1103655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1104655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineBasicBlock*, 16> BlockSeq; 1105655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the 1106655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ranges for this, and they are preserved. 1107655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &SrcInt = li_->getInterval(CP.getSrcReg()); 1108655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end(); 1109655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I ) { 1110655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->findLiveInMBBs(I->start, I->end, BlockSeq); 1111655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) { 1112655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock &block = *BlockSeq[idx]; 1113655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!block.isLiveIn(CP.getDstReg())) 1114655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola block.addLiveIn(CP.getDstReg()); 1115655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1116655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola BlockSeq.clear(); 1117655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1118655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1119655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1120655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // SrcReg is guarateed to be the register whose live interval that is 1121655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // being merged. 1122655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->removeInterval(CP.getSrcReg()); 1123655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1124655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update regalloc hint. 1125655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tri_->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *mf_); 1126655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1127655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1128655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &DstInt = li_->getInterval(CP.getDstReg()); 1129655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\tJoined. Result = "; 1130655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstInt.print(dbgs(), tri_); 1131655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 1132655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1133655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1134655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numJoins; 1135655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1136655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1137655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1138655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ComputeUltimateVN - Assuming we are going to join two live intervals, 1139655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// compute what the resultant value numbers for each value in the input two 1140655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ranges will be. This is complicated by copies between the two which can 1141655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// and will commonly cause multiple value numbers to be merged into one. 1142655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1143655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// VN is the value number that we're trying to resolve. InstDefiningValue 1144655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// keeps track of the new InstDefiningValue assignment for the result 1145655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 1146655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// whether a value in this or other is a copy from the opposite set. 1147655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 1148655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// already been assigned. 1149655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1150655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 1151655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// contains the value number the copy is from. 1152655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// 1153655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolastatic unsigned ComputeUltimateVN(VNInfo *VNI, 1154655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> &NewVNInfo, 1155655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 1156655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 1157655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &ThisValNoAssignments, 1158655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> &OtherValNoAssignments) { 1159655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1160655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1161655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the VN has already been computed, just return it. 1162655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ThisValNoAssignments[VN] >= 0) 1163655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN]; 1164655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 1165655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1166655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this val is not a copy from the other val, then it must be a new value 1167655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // number in the destination. 1168655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 1169655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I == ThisFromOther.end()) { 1170655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1171655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 1172655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1173655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *OtherValNo = I->second; 1174655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1175655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, this *is* a copy from the RHS. If the other side has already 1176655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // been computed, return it. 1177655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (OtherValNoAssignments[OtherValNo->id] >= 0) 1178655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 1179655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1180655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Mark this value number as currently being computed, then ask what the 1181655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // ultimate value # of the other value is. 1182655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ThisValNoAssignments[VN] = -2; 1183655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned UltimateVN = 1184655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 1185655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola OtherValNoAssignments, ThisValNoAssignments); 1186655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return ThisValNoAssignments[VN] = UltimateVN; 1187655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1188655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1189655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// JoinIntervals - Attempt to join these two intervals. On failure, this 1190655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// returns false. 11915b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::JoinIntervals(CoalescerPair &CP) { 1192655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &RHS = li_->getInterval(CP.getSrcReg()); 1193655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), tri_); dbgs() << "\n"; }); 1194655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1195655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If a live interval is a physical register, check for interference with any 1196655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // aliases. The interference check implemented here is a bit more conservative 1197655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // than the full interfeence check below. We allow overlapping live ranges 1198655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // only when one is a copy of the other. 1199655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (CP.isPhys()) { 1200655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned *AS = tri_->getAliasSet(CP.getDstReg()); *AS; ++AS){ 1201655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->hasInterval(*AS)) 1202655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1203655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const LiveInterval &LHS = li_->getInterval(*AS); 1204655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator LI = LHS.begin(); 1205655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::const_iterator RI = RHS.begin(), RE = RHS.end(); 1206655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RI != RE; ++RI) { 1207655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LI = std::lower_bound(LI, LHS.end(), RI->start); 1208655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Does LHS have an overlapping live range starting before RI? 1209655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if ((LI != LHS.begin() && LI[-1].end > RI->start) && 1210655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola (RI->start != RI->valno->def || 1211655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !CP.isCoalescable(li_->getInstructionFromIndex(RI->start)))) { 1212655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1213655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterference from alias: "; 1214655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.print(dbgs(), tri_); 1215655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n\t\tOverlap at " << RI->start << " and no copy.\n"; 1216655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1217655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1218655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1219655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1220655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Check that LHS ranges beginning in this range are copies. 1221655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (; LI != LHS.end() && LI->start < RI->end; ++LI) { 1222655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LI->start != LI->valno->def || 1223655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !CP.isCoalescable(li_->getInstructionFromIndex(LI->start))) { 1224655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1225655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\t\tInterference from alias: "; 1226655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.print(dbgs(), tri_); 1227655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n\t\tDef at " << LI->start << " is not a copy.\n"; 1228655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1229655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1230655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1231655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1232655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1233655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1234655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1235655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1236655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Compute the final value assignment, assuming that the live ranges can be 1237655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // coalesced. 1238655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> LHSValNoAssignments; 1239655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<int, 16> RHSValNoAssignments; 1240655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 1241655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 1242655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<VNInfo*, 16> NewVNInfo; 1243655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1244655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval &LHS = li_->getOrCreateInterval(CP.getDstReg()); 1245655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), tri_); dbgs() << "\n"; }); 1246655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1247655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Loop over the value numbers of the LHS, seeing if any are defined from 1248655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the RHS. 1249655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1250655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1251655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1252655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 1253655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1254655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1255655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Never join with a register that has EarlyClobber redefs. 1256655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasRedefByEC()) 1257655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1258655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1259655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DstReg is known to be a register in the LHS interval. If the src is 1260655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // from the RHS interval, we can use its value #. 1261655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isCoalescable(VNI->getCopy())) 1262655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1263655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1264655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Figure out the value # from the RHS. 1265655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 1266655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The copy could be to an aliased physreg. 1267655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!lr) continue; 1268655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS[VNI] = lr->valno; 1269655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1270655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1271655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Loop over the value numbers of the RHS, seeing if any are defined from 1272655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the LHS. 1273655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1274655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1275655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1276655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 1277655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1278655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1279655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Never join with a register that has EarlyClobber redefs. 1280655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasRedefByEC()) 1281655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1282655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1283655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DstReg is known to be a register in the RHS interval. If the src is 1284655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // from the LHS interval, we can use its value #. 1285655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!CP.isCoalescable(VNI->getCopy())) 1286655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1287655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1288655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Figure out the value # from the LHS. 1289655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 1290655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // The copy could be to an aliased physreg. 1291655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!lr) continue; 1292655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS[VNI] = lr->valno; 1293655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1294655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1295655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 1296655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 1297655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 1298655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1299655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 1300655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1301655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1302655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1303655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1304655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1305655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1306655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 1307655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments, RHSValNoAssignments); 1308655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1309655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 1310655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola i != e; ++i) { 1311655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = *i; 1312655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned VN = VNI->id; 1313655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 1314655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1315655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this value number isn't a copy from the LHS, it's a new number. 1316655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 1317655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo.push_back(VNI); 1318655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[VN] = NewVNInfo.size()-1; 1319655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1320655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1321655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1322655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ComputeUltimateVN(VNI, NewVNInfo, 1323655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 1324655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments, LHSValNoAssignments); 1325655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1326655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1327655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Armed with the mappings of LHS/RHS values to ultimate values, walk the 1328655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // interval lists to see if these intervals are coalescable. 1329655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator I = LHS.begin(); 1330655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator IE = LHS.end(); 1331655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator J = RHS.begin(); 1332655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LiveInterval::const_iterator JE = RHS.end(); 1333655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1334655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Skip ahead until the first place of potential sharing. 1335655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != IE && J != JE) { 1336655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1337655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I = std::upper_bound(I, IE, J->start); 1338655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I != LHS.begin()) --I; 1339655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (J->start < I->start) { 1340655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola J = std::upper_bound(J, JE, I->start); 1341655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (J != RHS.begin()) --J; 1342655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1343655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1344655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1345655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (I != IE && J != JE) { 1346655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Determine if these two live ranges overlap. 1347655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Overlaps; 1348655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->start < J->start) { 1349655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Overlaps = I->end > J->start; 1350655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1351655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola Overlaps = J->end > I->start; 1352655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1353655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1354655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If so, check value # info to determine if they are really different. 1355655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Overlaps) { 1356655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If the live range overlap will map to the same value number in the 1357655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // result liverange, we can still coalesce them. If not, we can't. 1358655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments[I->valno->id] != 1359655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments[J->valno->id]) 1360655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1361655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If it's re-defined by an early clobber somewhere in the live range, 1362655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // then conservatively abort coalescing. 1363655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC()) 1364655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return false; 1365655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1366655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1367655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (I->end < J->end) 1368655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++I; 1369655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1370655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++J; 1371655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1372655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1373655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1374655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 1375655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 1376655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1377655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned LHSValID = LHSValNoAssignments[VNI->id]; 1378655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1379655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[LHSValID]->setHasPHIKill(true); 1380655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1381655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1382655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Update kill info. Some live ranges are extended due to copy coalescing. 1383655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 1384655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 1385655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VNInfo *VNI = I->first; 1386655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned RHSValID = RHSValNoAssignments[VNI->id]; 1387655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VNI->hasPHIKill()) 1388655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola NewVNInfo[RHSValID]->setHasPHIKill(true); 1389655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1390655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1391655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHSValNoAssignments.empty()) 1392655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHSValNoAssignments.push_back(-1); 1393655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (RHSValNoAssignments.empty()) 1394655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RHSValNoAssignments.push_back(-1); 1395655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1396655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If we get here, we know that we can coalesce the live ranges. Ask the 1397655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // intervals to coalesce themselves now. 1398655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 1399655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_); 1400655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1401655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1402655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1403655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindolanamespace { 1404655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // DepthMBBCompare - Comparison predicate that sort first based on the loop 1405655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // depth of the basic block (the unsigned), and then on the MBB number. 1406655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola struct DepthMBBCompare { 1407655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 1408655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 1409655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Deeper loops first 1410655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (LHS.first != RHS.first) 1411655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.first > RHS.first; 1412655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1413655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Prefer blocks that are more connected in the CFG. This takes care of 1414655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // the most difficult copies first while intervals are short. 1415655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 1416655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 1417655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (cl != cr) 1418655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return cl > cr; 1419655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1420655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // As a last resort, sort by block number. 1421655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return LHS.second->getNumber() < RHS.second->getNumber(); 1422655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1423655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }; 1424655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1425655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 14265b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::CopyCoalesceInMBB(MachineBasicBlock *MBB, 1427655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<MachineInstr*> &TryAgain) { 1428655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << MBB->getName() << ":\n"); 1429655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1430655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> VirtCopies; 1431655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> PhysCopies; 1432655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<MachineInstr*, 8> ImpDefCopies; 1433655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 1434655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MII != E;) { 1435655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *Inst = MII++; 1436655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1437655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If this isn't a copy nor a extract_subreg, we can't join intervals. 1438655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg, DstReg; 1439655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Inst->isCopy()) { 1440655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstReg = Inst->getOperand(0).getReg(); 1441655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SrcReg = Inst->getOperand(1).getReg(); 1442655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else if (Inst->isSubregToReg()) { 1443655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DstReg = Inst->getOperand(0).getReg(); 1444655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SrcReg = Inst->getOperand(2).getReg(); 1445655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else 1446655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1447655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1448655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 1449655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 1450655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(SrcReg) && li_->getInterval(SrcReg).empty()) 1451655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ImpDefCopies.push_back(Inst); 1452655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else if (SrcIsPhys || DstIsPhys) 1453655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola PhysCopies.push_back(Inst); 1454655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola else 1455655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola VirtCopies.push_back(Inst); 1456655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1457655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1458655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Try coalescing implicit copies and insert_subreg <undef> first, 1459655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // followed by copies to / from physical registers, then finally copies 1460655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // from virtual registers to virtual registers. 1461655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) { 1462655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = ImpDefCopies[i]; 1463655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1464655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1465655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1466655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1467655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1468655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { 1469655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = PhysCopies[i]; 1470655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1471655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1472655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1473655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1474655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1475655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { 1476655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *TheCopy = VirtCopies[i]; 1477655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1478655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!JoinCopy(TheCopy, Again)) 1479655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Again) 1480655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TryAgain.push_back(TheCopy); 1481655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1482655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1483655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 14845b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::joinIntervals() { 1485655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 1486655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1487655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<MachineInstr*> TryAgainList; 1488655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (loopInfo->empty()) { 1489655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // If there are no loops in the function, join intervals in function order. 1490655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineFunction::iterator I = mf_->begin(), E = mf_->end(); 1491655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I) 1492655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyCoalesceInMBB(I, TryAgainList); 1493655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1494655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Otherwise, join intervals in inner loops before other intervals. 1495655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Unfortunately we can't just iterate over loop hierarchy here because 1496655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // there may be more MBB's than BB's. Collect MBB's for sorting. 1497655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1498655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join intervals in the function prolog first. We want to join physical 1499655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers with virtual registers before the intervals got too long. 1500655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 1501655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineFunction::iterator I = mf_->begin(), E = mf_->end();I != E;++I){ 1502655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock *MBB = I; 1503655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MBBs.push_back(std::make_pair(loopInfo->getLoopDepth(MBB), I)); 1504655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1505655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1506655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Sort by loop depth. 1507655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 1508655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1509655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Finally, join intervals in loop nest order. 1510655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 1511655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola CopyCoalesceInMBB(MBBs[i].second, TryAgainList); 1512655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1513655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1514655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Joining intervals can allow other intervals to be joined. Iteratively join 1515655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // until we make no progress. 1516655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool ProgressMade = true; 1517655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (ProgressMade) { 1518655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ProgressMade = false; 1519655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1520655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 1521655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *&TheCopy = TryAgainList[i]; 1522655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TheCopy) 1523655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1524655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1525655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Again = false; 1526655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool Success = JoinCopy(TheCopy, Again); 1527655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (Success || !Again) { 1528655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola TheCopy= 0; // Mark this one as done. 1529655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ProgressMade = true; 1530655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1531655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1532655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1533655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1534655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15355b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::releaseMemory() { 1536655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola JoinedCopies.clear(); 1537655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatCopies.clear(); 1538655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ReMatDefs.clear(); 1539655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1540655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 15415b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolabool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 1542655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mf_ = &fn; 1543655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mri_ = &fn.getRegInfo(); 1544655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tm_ = &fn.getTarget(); 1545655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tri_ = tm_->getRegisterInfo(); 1546655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola tii_ = tm_->getInstrInfo(); 1547655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_ = &getAnalysis<LiveIntervals>(); 1548655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ldv_ = &getAnalysis<LiveDebugVariables>(); 1549655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola AA = &getAnalysis<AliasAnalysis>(); 1550655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola loopInfo = &getAnalysis<MachineLoopInfo>(); 1551655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1552655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 1553655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << "********** Function: " 1554655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola << ((Value*)mf_->getFunction())->getName() << '\n'); 1555655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1556655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1557655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mf_->verify(this, "Before register coalescing"); 1558655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1559655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RegClassInfo.runOnMachineFunction(fn); 1560655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1561655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Join (coalesce) intervals if requested. 1562655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (EnableJoining) { 1563655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola joinIntervals(); 1564655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG({ 1565655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "********** INTERVALS POST JOINING **********\n"; 1566655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (LiveIntervals::iterator I = li_->begin(), E = li_->end(); 1567655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I != E; ++I){ 1568655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola I->second->print(dbgs(), tri_); 1569655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola dbgs() << "\n"; 1570655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1571655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola }); 1572655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1573655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1574655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Perform a final pass over the instructions and compute spill weights 1575655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // and remove identity moves. 1576655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SmallVector<unsigned, 4> DeadDefs; 1577655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineFunction::iterator mbbi = mf_->begin(), mbbe = mf_->end(); 1578655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mbbi != mbbe; ++mbbi) { 1579655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineBasicBlock* mbb = mbbi; 1580655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 1581655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii != mie; ) { 1582655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineInstr *MI = mii; 1583655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (JoinedCopies.count(MI)) { 1584655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Delete all coalesced copies. 1585655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool DoDelete = true; 1586655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola assert(MI->isCopyLike() && "Unrecognized copy instruction"); 1587655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg(); 1588655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(SrcReg) && 1589655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->getNumOperands() > 2) 1590655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Do not delete extract_subreg, insert_subreg of physical 1591655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // registers unless the definition is dead. e.g. 1592655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1 1593655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // or else the scavenger may complain. LowerSubregs will 1594655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // delete them later. 1595655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DoDelete = false; 1596655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1597655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MI->allDefsAreDead()) { 1598655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(SrcReg) && 1599655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->hasInterval(SrcReg)) 1600655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->shrinkToUses(&li_->getInterval(SrcReg)); 1601655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DoDelete = true; 1602655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1603655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!DoDelete) { 1604655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // We need the instruction to adjust liveness, so make it a KILL. 1605655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MI->isSubregToReg()) { 1606655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->RemoveOperand(3); 1607655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->RemoveOperand(1); 1608655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1609655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->setDesc(tii_->get(TargetOpcode::KILL)); 1610655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = llvm::next(mii); 1611655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else { 1612655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->RemoveMachineInstrFromMaps(MI); 1613655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = mbbi->erase(mii); 1614655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++numPeep; 1615655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1616655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1617655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1618655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1619655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Now check if this is a remat'ed def instruction which is now dead. 1620655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (ReMatDefs.count(MI)) { 1621655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola bool isDead = true; 1622655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1623655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola const MachineOperand &MO = MI->getOperand(i); 1624655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!MO.isReg()) 1625655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1626655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned Reg = MO.getReg(); 1627655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!Reg) 1628655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1629655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isVirtualRegister(Reg)) 1630655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.push_back(Reg); 1631655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (MO.isDead()) 1632655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1633655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (TargetRegisterInfo::isPhysicalRegister(Reg) || 1634655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola !mri_->use_nodbg_empty(Reg)) { 1635655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola isDead = false; 1636655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola break; 1637655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1638655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1639655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (isDead) { 1640655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola while (!DeadDefs.empty()) { 1641655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned DeadDef = DeadDefs.back(); 1642655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.pop_back(); 1643655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola RemoveDeadDef(li_->getInterval(DeadDef), MI); 1644655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1645655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->RemoveMachineInstrFromMaps(mii); 1646655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mii = mbbi->erase(mii); 1647655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1648655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } else 1649655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DeadDefs.clear(); 1650655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1651655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1652655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola ++mii; 1653655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1654655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // Check for now unnecessary kill flags. 1655655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->isNotInMIMap(MI)) continue; 1656655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola SlotIndex DefIdx = li_->getInstructionIndex(MI).getDefIndex(); 1657655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 1658655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MachineOperand &MO = MI->getOperand(i); 1659655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!MO.isReg() || !MO.isKill()) continue; 1660655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned reg = MO.getReg(); 1661655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!reg || !li_->hasInterval(reg)) continue; 1662655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!li_->getInterval(reg).killedAt(DefIdx)) { 1663655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MO.setIsKill(false); 1664655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1665655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1666655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // When leaving a kill flag on a physreg, check if any subregs should 1667655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola // remain alive. 1668655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (!TargetRegisterInfo::isPhysicalRegister(reg)) 1669655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola continue; 1670655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola for (const unsigned *SR = tri_->getSubRegisters(reg); 1671655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola unsigned S = *SR; ++SR) 1672655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (li_->hasInterval(S) && li_->getInterval(S).liveAt(DefIdx)) 1673655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola MI->addRegisterDefined(S, tri_); 1674655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1675655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1676655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola } 1677655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1678655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(dump()); 1679655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola DEBUG(ldv_->dump()); 1680655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola if (VerifyCoalescing) 1681655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola mf_->verify(this, "After register coalescing"); 1682655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola return true; 1683655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1684655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 1685655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola/// print - Implement the dump method. 16865b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindolavoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 1687655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola li_->print(O, m); 1688655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1689655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola 16905b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael EspindolaRegisterCoalescer *llvm::createRegisterCoalescer() { 16915b220213bfe9c37c2bb41a7ae0804e06a14f1007Rafael Espindola return new RegisterCoalescer(); 1692655739de7b09dcfecd9f3e5f1734e53ec90a19f3Rafael Espindola} 1693