1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===- RegisterCoalescer.cpp - Generic Register Coalescing Interface -------==// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the generic RegisterCoalescer interface which 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// is used as the common interface used by all clients and 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// implementations of register coalescing. 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 1619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#define DEBUG_TYPE "regcoalescing" 1719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "RegisterCoalescer.h" 1819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "LiveDebugVariables.h" 1919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "RegisterClassInfo.h" 2019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "VirtRegMap.h" 2119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 2219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Pass.h" 2319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Value.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/LiveIntervalAnalysis.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineInstr.h" 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetInstrInfo.h" 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetRegisterInfo.h" 2919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/LiveIntervalAnalysis.h" 3019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Analysis/AliasAnalysis.h" 3119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineFrameInfo.h" 3219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineInstr.h" 3319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineLoopInfo.h" 3419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/MachineRegisterInfo.h" 3519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/CodeGen/Passes.h" 3619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetInstrInfo.h" 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetMachine.h" 3819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Target/TargetOptions.h" 3919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/CommandLine.h" 4019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/Debug.h" 4119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/ErrorHandling.h" 4219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/Support/raw_ostream.h" 4319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/OwningPtr.h" 4419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/SmallSet.h" 4519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/Statistic.h" 4619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include "llvm/ADT/STLExtras.h" 4719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <algorithm> 4819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#include <cmath> 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanusing namespace llvm; 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 5119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numJoins , "Number of interval joins performed"); 5219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numCrossRCs , "Number of cross class joins performed"); 5319bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numCommutes , "Number of instruction commuting performed"); 5419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numExtends , "Number of copies extended"); 5519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumReMats , "Number of instructions re-materialized"); 5619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numPeep , "Number of identity moves eliminated after coalescing"); 5719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(numAborts , "Number of times interval joining aborted"); 5819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanSTATISTIC(NumInflated , "Number of register classes inflated"); 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 6019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> 6119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanEnableJoining("join-liveintervals", 6219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Coalesce copies (default=true)"), 6319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::init(true)); 6419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 6519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> 6619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanDisableCrossClassJoin("disable-cross-class-join", 6719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Avoid coalescing cross register class copies"), 6819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::init(false), cl::Hidden); 6919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> 7119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanEnablePhysicalJoin("join-physregs", 7219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Join physical register copies"), 7319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::init(false), cl::Hidden); 7419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 7519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic cl::opt<bool> 7619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanVerifyCoalescing("verify-coalescing", 7719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::desc("Verify machine instrs before and after register coalescing"), 7819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman cl::Hidden); 7919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 8019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 8119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class RegisterCoalescer : public MachineFunctionPass { 8219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunction* MF; 8319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineRegisterInfo* MRI; 8419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetMachine* TM; 8519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo* TRI; 8619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetInstrInfo* TII; 8719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveIntervals *LIS; 8819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveDebugVariables *LDV; 8919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineLoopInfo* Loops; 9019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AliasAnalysis *AA; 9119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegisterClassInfo RegClassInfo; 9219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// JoinedCopies - Keep track of copies eliminated due to coalescing. 9419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 9519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<MachineInstr*, 32> JoinedCopies; 9619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 9719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ReMatCopies - Keep track of copies eliminated due to remat. 9819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 9919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<MachineInstr*, 32> ReMatCopies; 10019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ReMatDefs - Keep track of definition instructions which have 10219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// been remat'ed. 10319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallPtrSet<MachineInstr*, 8> ReMatDefs; 10419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// joinIntervals - join compatible live intervals 10619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void joinIntervals(); 10719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 10819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// CopyCoalesceInMBB - Coalesce copies in the specified MBB, putting 10919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// copies that cannot yet be coalesced into the "TryAgain" list. 11019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void CopyCoalesceInMBB(MachineBasicBlock *MBB, 11119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<MachineInstr*> &TryAgain); 11219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 11319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 11419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// which are the src/dst of the copy instruction CopyMI. This returns 11519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// true if the copy was successfully coalesced away. If it is not 11619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// currently possible to coalesce this interval, but it may be possible if 11719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// other things get coalesced, then it returns true by reference in 11819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 'Again'. 11919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool JoinCopy(MachineInstr *TheCopy, bool &Again); 12019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// JoinIntervals - Attempt to join these two intervals. On failure, this 12219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// returns false. The output "SrcInt" will not have been modified, so we 12319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can use this information below to update aliases. 12419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool JoinIntervals(CoalescerPair &CP); 12519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 12619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy. If 12719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the source value number is defined by a copy from the destination reg 12819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// see if we can merge these two destination reg valno# into a single 12919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// value number, eliminating a copy. 13019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool AdjustCopiesBackFrom(const CoalescerPair &CP, MachineInstr *CopyMI); 13119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// HasOtherReachingDefs - Return true if there are definitions of IntB 13319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// other than BValNo val# that can reach uses of AValno val# of IntA. 13419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HasOtherReachingDefs(LiveInterval &IntA, LiveInterval &IntB, 13519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *AValNo, VNInfo *BValNo); 13619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 13719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy. 13819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// If the source value number is defined by a commutable instruction and 13919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// its other operand is coalesced to the copy dest register, see if we 14019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// can transform the copy into a noop by commuting the definition. 14119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool RemoveCopyByCommutingDef(const CoalescerPair &CP,MachineInstr *CopyMI); 14219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 14319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// ReMaterializeTrivialDef - If the source of a copy is defined by a 14419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// trivial computation, replace the copy by rematerialize the definition. 14519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// If PreserveSrcInt is true, make sure SrcInt is valid after the call. 14619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool ReMaterializeTrivialDef(LiveInterval &SrcInt, bool PreserveSrcInt, 14719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg, MachineInstr *CopyMI); 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 14919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// shouldJoinPhys - Return true if a physreg copy should be joined. 15019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool shouldJoinPhys(CoalescerPair &CP); 15119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 15219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isWinToJoinCrossClass - Return true if it's profitable to coalesce 15319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// two virtual registers from different register classes. 15419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isWinToJoinCrossClass(unsigned SrcReg, 15519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg, 15619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *SrcRC, 15719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *DstRC, 15819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *NewRC); 15919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 16119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// update the subregister number if it is not zero. If DstReg is a 16219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// physical register and the existing subregister number of the def / use 16319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// being updated is not zero, make sure to set it to the correct physical 16419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// subregister. 16519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void UpdateRegDefsUses(const CoalescerPair &CP); 16619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 16719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// RemoveDeadDef - If a def of a live interval is now determined dead, 16819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// remove the val# it defines. If the live interval becomes empty, remove 16919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// it as well. 17019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool RemoveDeadDef(LiveInterval &li, MachineInstr *DefMI); 17119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// RemoveCopyFlag - If DstReg is no longer defined by CopyMI, clear the 17319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// VNInfo copy flag for DstReg and all aliases. 17419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void RemoveCopyFlag(unsigned DstReg, const MachineInstr *CopyMI); 17519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// markAsJoined - Remember that CopyMI has already been joined. 17719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman void markAsJoined(MachineInstr *CopyMI); 17819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 17919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// eliminateUndefCopy - Handle copies of undef values. 18019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool eliminateUndefCopy(MachineInstr *CopyMI, const CoalescerPair &CP); 18119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman public: 18319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static char ID; // Class identification, replacement for typeinfo 18419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegisterCoalescer() : MachineFunctionPass(ID) { 18519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman initializeRegisterCoalescerPass(*PassRegistry::getPassRegistry()); 18619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 18719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 18819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void getAnalysisUsage(AnalysisUsage &AU) const; 18919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void releaseMemory(); 19119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// runOnMachineFunction - pass entry point 19319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool runOnMachineFunction(MachineFunction&); 19419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 19519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// print - Implement the dump method. 19619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void print(raw_ostream &O, const Module* = 0) const; 19719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 19819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} /// end anonymous namespace 19919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar &llvm::RegisterCoalescerPassID = RegisterCoalescer::ID; 20119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 20219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_BEGIN(RegisterCoalescer, "simple-register-coalescing", 20319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Simple Register Coalescing", false, false) 20419bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 20519bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(LiveDebugVariables) 20619bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(SlotIndexes) 20719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(MachineLoopInfo) 20819bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(StrongPHIElimination) 20919bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(PHIElimination) 21019bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_DEPENDENCY(TwoAddressInstructionPass) 21119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 21219bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanINITIALIZE_PASS_END(RegisterCoalescer, "simple-register-coalescing", 21319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman "Simple Register Coalescing", false, false) 21419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanchar RegisterCoalescer::ID = 0; 21619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 21719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic unsigned compose(const TargetRegisterInfo &tri, unsigned a, unsigned b) { 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!a) return b; 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!b) return a; 22019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return tri.composeSubRegIndices(a, b); 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 22319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool isMoveInstr(const TargetRegisterInfo &tri, const MachineInstr *MI, 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned &Src, unsigned &Dst, 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned &SrcSub, unsigned &DstSub) { 226894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (MI->isCopy()) { 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Dst = MI->getOperand(0).getReg(); 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DstSub = MI->getOperand(0).getSubReg(); 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Src = MI->getOperand(1).getReg(); 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcSub = MI->getOperand(1).getSubReg(); 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (MI->isSubregToReg()) { 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Dst = MI->getOperand(0).getReg(); 23319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstSub = compose(tri, MI->getOperand(0).getSubReg(), 23419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->getOperand(3).getImm()); 235894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Src = MI->getOperand(2).getReg(); 236894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcSub = MI->getOperand(2).getSubReg(); 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CoalescerPair::setRegisters(const MachineInstr *MI) { 24319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcReg = DstReg = SubIdx = 0; 24419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewRC = 0; 24519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Flipped = CrossClass = false; 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Src, Dst, SrcSub, DstSub; 24819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 25019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Partial = SrcSub || DstSub; 251894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 252894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // If one register is a physreg, it must be Dst. 253894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TargetRegisterInfo::isPhysicalRegister(Src)) { 254894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TargetRegisterInfo::isPhysicalRegister(Dst)) 255894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(Src, Dst); 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(SrcSub, DstSub); 25819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Flipped = true; 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const MachineRegisterInfo &MRI = MI->getParent()->getParent()->getRegInfo(); 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (TargetRegisterInfo::isPhysicalRegister(Dst)) { 264894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Eliminate DstSub on a physreg. 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DstSub) { 26619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dst = TRI.getSubReg(Dst, DstSub); 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Dst) return false; 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DstSub = 0; 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Eliminate SrcSub by picking a corresponding Dst superregister. 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcSub) { 27319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dst = TRI.getMatchingSuperReg(Dst, SrcSub, MRI.getRegClass(Src)); 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!Dst) return false; 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcSub = 0; 276894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else if (!MRI.getRegClass(Src)->contains(Dst)) { 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Both registers are virtual. 281894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 282894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Both registers have subreg indices. 283894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcSub && DstSub) { 284894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // For now we only handle the case of identical indices in commensurate 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // registers: Dreg:ssub_1 + Dreg:ssub_1 -> Dreg 286894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // FIXME: Handle Qreg:ssub_3 + Dreg:ssub_1 as QReg:dsub_1 + Dreg. 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcSub != DstSub) 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 29119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TRI.getCommonSubClass(DstRC, SrcRC)) 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcSub = DstSub = 0; 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 295894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 296894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // There can be no SrcSub. 297894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (SrcSub) { 298894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(Src, Dst); 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman DstSub = SrcSub; 300894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SrcSub = 0; 30119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!Flipped && "Unexpected flip"); 30219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Flipped = true; 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Find the new register class. 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *SrcRC = MRI.getRegClass(Src); 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *DstRC = MRI.getRegClass(Dst); 308894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DstSub) 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewRC = TRI.getMatchingSuperRegClass(DstRC, SrcRC, DstSub); 310894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman else 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewRC = TRI.getCommonSubClass(DstRC, SrcRC); 31219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!NewRC) 313894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 31419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CrossClass = NewRC != DstRC || NewRC != SrcRC; 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Check our invariants 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(TargetRegisterInfo::isVirtualRegister(Src) && "Src must be virtual"); 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!(TargetRegisterInfo::isPhysicalRegister(Dst) && DstSub) && 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "Cannot have a physical SubIdx"); 32019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcReg = Src; 32119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstReg = Dst; 32219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SubIdx = DstSub; 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CoalescerPair::flip() { 32719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SubIdx || TargetRegisterInfo::isPhysicalRegister(DstReg)) 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 32919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::swap(SrcReg, DstReg); 33019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Flipped = !Flipped; 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 332894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 333894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 334894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumanbool CoalescerPair::isCoalescable(const MachineInstr *MI) const { 335894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!MI) 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Src, Dst, SrcSub, DstSub; 33819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isMoveInstr(TRI, MI, Src, Dst, SrcSub, DstSub)) 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 34119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find the virtual register that is SrcReg. 34219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Dst == SrcReg) { 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(Src, Dst); 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::swap(SrcSub, DstSub); 34519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (Src != SrcReg) { 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 34919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now check that Dst matches DstReg. 35019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(DstReg)) { 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!TargetRegisterInfo::isPhysicalRegister(Dst)) 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!SubIdx && "Inconsistent CoalescerPair state."); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // DstSub could be set for a physreg from INSERT_SUBREG. 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (DstSub) 35619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Dst = TRI.getSubReg(Dst, DstSub); 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Full copy of Src. 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (!SrcSub) 35919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return DstReg == Dst; 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // This is a partial register copy. Check that the parts match. 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return TRI.getSubReg(DstReg, SrcSub) == Dst; 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } else { 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DstReg is virtual. 36419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstReg != Dst) 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // Registers match, do the subregisters line up? 36719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return compose(TRI, SubIdx, SrcSub) == DstSub; 36819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 37019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::getAnalysisUsage(AnalysisUsage &AU) const { 37219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.setPreservesCFG(); 37319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<AliasAnalysis>(); 37419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<LiveIntervals>(); 37519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreserved<LiveIntervals>(); 37619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<LiveDebugVariables>(); 37719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreserved<LiveDebugVariables>(); 37819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreserved<SlotIndexes>(); 37919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addRequired<MachineLoopInfo>(); 38019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreserved<MachineLoopInfo>(); 38119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(MachineDominatorsID); 38219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(StrongPHIEliminationID); 38319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(PHIEliminationID); 38419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AU.addPreservedID(TwoAddressInstructionPassID); 38519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineFunctionPass::getAnalysisUsage(AU); 38619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 38719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 38819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::markAsJoined(MachineInstr *CopyMI) { 38919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Joined copies are not deleted immediately, but kept in JoinedCopies. 39019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman JoinedCopies.insert(CopyMI); 39119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 39219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Mark all register operands of CopyMI as <undef> so they won't affect dead 39319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// code elimination. 39419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineInstr::mop_iterator I = CopyMI->operands_begin(), 39519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = CopyMI->operands_end(); I != E; ++I) 39619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->isReg()) 39719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->setIsUndef(true); 39819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 39919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 40019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// AdjustCopiesBackFrom - We found a non-trivially-coalescable copy with IntA 40119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// being the source and IntB being the dest, thus this defines a value number 40219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// in IntB. If the source value number (in IntA) is defined by a copy from B, 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// see if we can merge these two pieces of B into a single value number, 40419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// eliminating a copy. For example: 40519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 40619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// A3 = B0 40719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ... 40819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// B1 = A3 <- this copy 40919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 41019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// In this case, B0 can be extended to where the B1 copy lives, allowing the B1 41119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// value number to be replaced with B0 (which simplifies the B liveinterval). 41219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 41319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// This returns true if an interval was modified. 41419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 41519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::AdjustCopiesBackFrom(const CoalescerPair &CP, 41619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *CopyMI) { 41719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bail if there is no dst interval - can happen when merging physical subreg 41819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // operations. 41919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(CP.getDstReg())) 42019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 42119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &IntA = 42319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &IntB = 42519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 42619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getDefIndex(); 42719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // BValNo is a value number in B that is defined by a copy from A. 'B3' in 42919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the example above. 43019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator BLR = IntB.FindLiveRangeContaining(CopyIdx); 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BLR == IntB.end()) return false; 43219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *BValNo = BLR->valno; 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Get the location that B is defined at. Two options: either this value has 43519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // an unknown definition point or it is defined at CopyIdx. If unknown, we 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // can't process it. 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!BValNo->isDefByCopy()) return false; 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 43919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // AValNo is the value number in A that defines the copy, A3 in the example. 44119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex CopyUseIdx = CopyIdx.getUseIndex(); 44219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator ALR = IntA.FindLiveRangeContaining(CopyUseIdx); 44319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The live range might not exist after fun with physreg coalescing. 44419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ALR == IntA.end()) return false; 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *AValNo = ALR->valno; 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it's re-defined by an early clobber somewhere in the live range, then 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // it's not safe to eliminate the copy. FIXME: This is a temporary workaround. 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // See PR3149: 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 172 %ECX<def> = MOV32rr %reg1039<kill> 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 180 INLINEASM <es:subl $5,$1 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // sbbl $3,$0>, 10, %EAX<def>, 14, %ECX<earlyclobber,def>, 9, 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %EAX<kill>, 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 36, <fi#0>, 1, %reg0, 0, 9, %ECX<kill>, 36, <fi#1>, 1, %reg0, 0 45419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 188 %EAX<def> = MOV32rr %EAX<kill> 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 196 %ECX<def> = MOV32rr %ECX<kill> 45619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 204 %ECX<def> = MOV32rr %ECX<kill> 45719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 212 %EAX<def> = MOV32rr %EAX<kill> 45819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 220 %EAX<def> = MOV32rr %EAX 45919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 228 %reg1039<def> = MOV32rr %ECX<kill> 46019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The early clobber operand ties ECX input to the ECX def. 46119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 46219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The live interval of ECX is represented as this: 46319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %reg20,inf = [46,47:1)[174,230:0) 0@174-(230) 1@46-(47) 46419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The coalescer has no idea there was a def in the middle of [174,230]. 46519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AValNo->hasRedefByEC()) 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 46819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If AValNo is defined as a copy from IntB, we can potentially process this. 46919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Get the instruction that defines this value number. 47019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isCoalescable(AValNo->getCopy())) 47119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 47219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Get the LiveRange in IntB that this value number starts with. 47419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator ValLR = 47519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.FindLiveRangeContaining(AValNo->def.getPrevSlot()); 47619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ValLR == IntB.end()) 47719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 47819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 47919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure that the end of the live range is inside the same block as 48019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // CopyMI. 48119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *ValLREndInst = 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInstructionFromIndex(ValLR->end.getPrevSlot()); 48319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!ValLREndInst || ValLREndInst->getParent() != CopyMI->getParent()) 48419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 48519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 48619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, we now know that ValLR ends in the same block that the CopyMI 48719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // live-range starts. If there are no intervening live ranges between them in 48819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // IntB, we can merge them. 48919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ValLR+1 != BLR) return false; 49019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 49119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If a live interval is a physical register, conservatively check if any 49219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // of its aliases is overlapping the live interval of the virtual register. 49319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If so, do not coalesce. 49419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 49519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 49619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(*AS) && IntA.overlaps(LIS->getInterval(*AS))) { 49719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 49819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\t\tInterfere with alias "; 49919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(*AS).print(dbgs(), TRI); 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 50619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "Extending: "; 50719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.print(dbgs(), TRI); 50819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 50919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex FillerStart = ValLR->end, FillerEnd = BLR->start; 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We are about to delete CopyMI, so need to remove it as the 'instruction 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that defines this value #'. Update the valnum with the new defining 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instruction #. 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BValNo->def = FillerStart; 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BValNo->setCopy(0); 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 51719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, we can merge them. We need to insert a new liverange: 51819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // [ValLR.end, BLR.begin) of either value number, then we merge the 51919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // two value numbers. 52019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.addRange(LiveRange(FillerStart, FillerEnd, BValNo)); 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 52219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the IntB live range is assigned to a physical register, and if that 52319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // physreg has sub-registers, update their live intervals as well. 52419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) { 52519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *SR = TRI->getSubRegisters(IntB.reg); *SR; ++SR) { 52619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(*SR)) 52719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 52819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &SRLI = LIS->getInterval(*SR); 52919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SRLI.addRange(LiveRange(FillerStart, FillerEnd, 53019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SRLI.getNextValue(FillerStart, 0, 53119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getVNInfoAllocator()))); 53219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 53419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 53519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, merge "B1" into the same value number as "B0". 53619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BValNo != ValLR->valno) { 53719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If B1 is killed by a PHI, then the merged live range must also be killed 53819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // by the same PHI, as B0 and B1 can not overlap. 53919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HasPHIKill = BValNo->hasPHIKill(); 54019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.MergeValueNumberInto(BValNo, ValLR->valno); 54119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (HasPHIKill) 54219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValLR->valno->setHasPHIKill(true); 54319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 54419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 54519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << " result = "; 54619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.print(dbgs(), TRI); 54719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n"; 54819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 54919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 55019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the source instruction was killing the source register before the 55119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // merge, unset the isKill marker given the live range has been extended. 55219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int UIdx = ValLREndInst->findRegisterUseOperandIdx(IntB.reg, true); 55319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UIdx != -1) { 55419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValLREndInst->getOperand(UIdx).setIsKill(false); 55519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 55619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 55719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the copy instruction was killing the destination register before the 55819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // merge, find the last use and trim the live range. That will also add the 55919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // isKill marker. 56019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ALR->end == CopyIdx) 56119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->shrinkToUses(&IntA); 56219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numExtends; 56419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 56519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 56619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 56719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// HasOtherReachingDefs - Return true if there are definitions of IntB 56819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// other than BValNo val# that can reach uses of AValno val# of IntA. 56919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::HasOtherReachingDefs(LiveInterval &IntA, 57019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &IntB, 57119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *AValNo, 57219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *BValNo) { 57319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 57419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AI != AE; ++AI) { 57519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AI->valno != AValNo) continue; 57619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::Ranges::iterator BI = 57719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::upper_bound(IntB.ranges.begin(), IntB.ranges.end(), AI->start); 57819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI != IntB.ranges.begin()) 57919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman --BI; 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (; BI != IntB.ranges.end() && AI->end >= BI->start; ++BI) { 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->valno == BValNo) 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->start <= AI->start && BI->end > AI->start) 58419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 58519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (BI->start > AI->start && BI->start < AI->end) 58619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 58719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 58819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 58919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 59019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 59119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 59219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// RemoveCopyByCommutingDef - We found a non-trivially-coalescable copy with 59319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// IntA being the source and IntB being the dest, thus this defines a value 59419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// number in IntB. If the source value number (in IntA) is defined by a 59519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// commutable instruction and its other operand is coalesced to the copy dest 59619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// register, see if we can transform the copy into a noop by commuting the 59719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// definition. For example, 59819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 59919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// A3 = op A2 B0<kill> 60019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ... 60119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// B1 = A3 <- this copy 60219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ... 60319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// = op A3 <- more uses 60419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 60519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ==> 60619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 60719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// B2 = op B0 A2<kill> 60819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ... 60919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// B1 = B2 <- now an identify copy 61019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ... 61119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// = op B2 <- more uses 61219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 61319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// This returns true if an interval was modified. 61419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 61519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::RemoveCopyByCommutingDef(const CoalescerPair &CP, 61619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *CopyMI) { 61719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME: For now, only eliminate the copy by commuting its def when the 61819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // source register is a virtual register. We want to guard against cases 61919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // where the copy is a back edge copy and commuting the def lengthen the 62019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // live interval of the source register to the entire loop. 62119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isPhys() && CP.isFlipped()) 62219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 62319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 62419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Bail if there is no dst interval. 62519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(CP.getDstReg())) 62619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 62719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 62819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getDefIndex(); 62919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &IntA = 63119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.isFlipped() ? CP.getDstReg() : CP.getSrcReg()); 63219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &IntB = 63319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.isFlipped() ? CP.getSrcReg() : CP.getDstReg()); 63419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 63519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // BValNo is a value number in B that is defined by a copy from A. 'B3' in 63619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the example above. 63719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *BValNo = IntB.getVNInfoAt(CopyIdx); 63819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!BValNo || !BValNo->isDefByCopy()) 63919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 64019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(BValNo->def == CopyIdx && "Copy doesn't define the value?"); 64219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // AValNo is the value number in A that defines the copy, A3 in the example. 64419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *AValNo = IntA.getVNInfoAt(CopyIdx.getUseIndex()); 64519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(AValNo && "COPY source not live"); 64619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 64719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If other defs can reach uses of this def, then it's not safe to perform 64819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the optimization. 64919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AValNo->isPHIDef() || AValNo->isUnused() || AValNo->hasPHIKill()) 65019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 65119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *DefMI = LIS->getInstructionFromIndex(AValNo->def); 65219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DefMI) 65319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 65419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = DefMI->getDesc(); 65519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MCID.isCommutable()) 65619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 65719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If DefMI is a two-address instruction then commuting it will change the 65819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // destination register. 65919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman int DefIdx = DefMI->findRegisterDefOperandIdx(IntA.reg); 66019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(DefIdx != -1); 66119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned UseOpIdx; 66219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DefMI->isRegTiedToUseOperand(DefIdx, &UseOpIdx)) 66319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 66419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Op1, Op2, NewDstIdx; 66519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TII->findCommutedOpIndices(DefMI, Op1, Op2)) 66619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 66719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Op1 == UseOpIdx) 66819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewDstIdx = Op2; 66919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (Op2 == UseOpIdx) 67019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewDstIdx = Op1; 67119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 67219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 67319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &NewDstMO = DefMI->getOperand(NewDstIdx); 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewReg = NewDstMO.getReg(); 67619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewReg != IntB.reg || !NewDstMO.isKill()) 67719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 67819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 67919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure there are no other definitions of IntB that would reach the 68019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // uses which the new definition can reach. 68119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (HasOtherReachingDefs(IntA, IntB, AValNo, BValNo)) 68219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 68319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 68419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Abort if the aliases of IntB.reg have values that are not simply the 68519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // clobbers from the superreg. 68619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(IntB.reg)) 68719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *AS = TRI->getAliasSet(IntB.reg); *AS; ++AS) 68819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(*AS) && 68919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman HasOtherReachingDefs(IntA, LIS->getInterval(*AS), AValNo, 0)) 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 69119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 69219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If some of the uses of IntA.reg is already coalesced away, return false. 69319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // It's not possible to determine whether it's safe to perform the coalescing. 69419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::use_nodbg_iterator UI = 69519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->use_nodbg_begin(IntA.reg), 69619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UE = MRI->use_nodbg_end(); UI != UE; ++UI) { 69719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *UseMI = &*UI; 69819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex UseIdx = LIS->getInstructionIndex(UseMI); 69919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 70019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ULR == IntA.end()) 70119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 70219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ULR->valno == AValNo && JoinedCopies.count(UseMI)) 70319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 70419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tRemoveCopyByCommutingDef: " << AValNo->def << '\t' 70719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << *DefMI); 70819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 70919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // At this point we have decided that it is legal to do this 71019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // transformation. Start by commuting the instruction. 71119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *MBB = DefMI->getParent(); 71219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *NewMI = TII->commuteInstruction(DefMI); 71319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!NewMI) 71419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 71519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(IntA.reg) && 71619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TargetRegisterInfo::isVirtualRegister(IntB.reg) && 71719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !MRI->constrainRegClass(IntB.reg, MRI->getRegClass(IntA.reg))) 71819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 71919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewMI != DefMI) { 72019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->ReplaceMachineInstrInMaps(DefMI, NewMI); 72119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MBB->insert(DefMI, NewMI); 72219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MBB->erase(DefMI); 72319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 72419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OpIdx = NewMI->findRegisterUseOperandIdx(IntA.reg, false); 72519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewMI->getOperand(OpIdx).setIsKill(); 72619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 72719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If ALR and BLR overlaps and end of BLR extends beyond end of ALR, e.g. 72819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A = or A, B 72919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ... 73019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // B = A 73119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ... 73219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // C = A<kill> 73319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ... 73419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // = B 73519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 73619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update uses of IntA of the specific Val# with IntB. 73719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::use_iterator UI = MRI->use_begin(IntA.reg), 73819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UE = MRI->use_end(); UI != UE;) { 73919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &UseMO = UI.getOperand(); 74019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *UseMI = &*UI; 74119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++UI; 74219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (JoinedCopies.count(UseMI)) 74319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 74419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMI->isDebugValue()) { 74519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME These don't have an instruction index. Not clear we have enough 74619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // info to decide whether to do this replacement or not. For now do it. 74719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMO.setReg(NewReg); 74819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 74919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 75019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex UseIdx = LIS->getInstructionIndex(UseMI).getUseIndex(); 75119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator ULR = IntA.FindLiveRangeContaining(UseIdx); 75219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ULR == IntA.end() || ULR->valno != AValNo) 75319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 75419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(NewReg)) 75519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMO.substPhysReg(NewReg, *TRI); 75619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 75719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMO.setReg(NewReg); 75819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMI == CopyMI) 75919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 76019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!UseMI->isCopy()) 76119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 76219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMI->getOperand(0).getReg() != IntB.reg || 76319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->getOperand(0).getSubReg()) 76419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 76519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 76619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This copy will become a noop. If it's defining a new val#, merge it into 76719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // BValNo. 76819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex DefIdx = UseIdx.getDefIndex(); 76919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *DVNI = IntB.getVNInfoAt(DefIdx); 77019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DVNI) 77119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 77219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\t\tnoop: " << DefIdx << '\t' << *UseMI); 77319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(DVNI->def == DefIdx); 77419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BValNo = IntB.MergeValueNumberInto(BValNo, DVNI); 77519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(UseMI); 77619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 77719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 77819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Extend BValNo by merging in IntA live ranges of AValNo. Val# definition 77919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // is updated. 78019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *ValNo = BValNo; 78119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValNo->def = AValNo->def; 78219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ValNo->setCopy(0); 78319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::iterator AI = IntA.begin(), AE = IntA.end(); 78419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AI != AE; ++AI) { 78519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AI->valno != AValNo) continue; 78619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntB.addRange(LiveRange(AI->start, AI->end, ValNo)); 78719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 78819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\t\textended: " << IntB << '\n'); 78919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman IntA.removeValNo(AValNo); 79119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\t\ttrimmed: " << IntA << '\n'); 79219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numCommutes; 79319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 79419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 79519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 79619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ReMaterializeTrivialDef - If the source of a copy is defined by a trivial 79719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// computation, replace the copy by rematerialize the definition. 79819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::ReMaterializeTrivialDef(LiveInterval &SrcInt, 79919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool preserveSrcInt, 80019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg, 80119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *CopyMI) { 80219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex CopyIdx = LIS->getInstructionIndex(CopyMI).getUseIndex(); 80319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator SrcLR = SrcInt.FindLiveRangeContaining(CopyIdx); 80419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(SrcLR != SrcInt.end() && "Live range not found!"); 80519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *ValNo = SrcLR->valno; 80619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ValNo->isPHIDef() || ValNo->isUnused()) 80719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 80819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *DefMI = LIS->getInstructionFromIndex(ValNo->def); 80919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DefMI) 81019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 81119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(DefMI && "Defining instruction disappeared"); 81219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc &MCID = DefMI->getDesc(); 81319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MCID.isAsCheapAsAMove()) 81419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 81519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TII->isTriviallyReMaterializable(DefMI, AA)) 81619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 81719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool SawStore = false; 81819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DefMI->isSafeToMove(TII, AA, SawStore)) 81919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 82019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MCID.getNumDefs() != 1) 82119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 82219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DefMI->isImplicitDef()) { 82319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure the copy destination register class fits the instruction 82419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // definition register class. The mismatch can happen as a result of earlier 82519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // extract_subreg, insert_subreg, subreg_to_reg coalescing. 82619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *RC = TII->getRegClass(MCID, 0, TRI); 82719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(DstReg)) { 82819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MRI->getRegClass(DstReg) != RC) 82919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 83019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (!RC->contains(DstReg)) 83119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 83219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 83319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RemoveCopyFlag(DstReg, CopyMI); 83519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 83619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *MBB = CopyMI->getParent(); 83719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock::iterator MII = 83819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman llvm::next(MachineBasicBlock::iterator(CopyMI)); 83919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII->reMaterialize(*MBB, MII, DstReg, 0, DefMI, *TRI); 84019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *NewMI = prior(MII); 84119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 84219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // CopyMI may have implicit operands, transfer them over to the newly 84319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // rematerialized instruction. And update implicit def interval valnos. 84419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = CopyMI->getDesc().getNumOperands(), 84519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman e = CopyMI->getNumOperands(); i != e; ++i) { 84619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &MO = CopyMI->getOperand(i); 84719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isReg() && MO.isImplicit()) 84819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewMI->addOperand(MO); 84919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isDef()) 85019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RemoveCopyFlag(MO.getReg(), CopyMI); 85119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 85219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 85319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewMI->copyImplicitOps(CopyMI); 85419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->ReplaceMachineInstrInMaps(CopyMI, NewMI); 85519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CopyMI->eraseFromParent(); 85619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMatCopies.insert(CopyMI); 85719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMatDefs.insert(DefMI); 85819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Remat: " << *NewMI); 85919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumReMats; 86019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 86119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The source interval can become smaller because we removed a use. 86219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (preserveSrcInt) 86319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->shrinkToUses(&SrcInt); 86419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 86519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 86619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 86719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 86819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// eliminateUndefCopy - ProcessImpicitDefs may leave some copies of <undef> 86919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// values, it only removes local variables. When we have a copy like: 87019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 87119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// %vreg1 = COPY %vreg2<undef> 87219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 87319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// We delete the copy and remove the corresponding value number from %vreg1. 87419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// Any uses of that value number are marked as <undef>. 87519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::eliminateUndefCopy(MachineInstr *CopyMI, 87619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const CoalescerPair &CP) { 87719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex Idx = LIS->getInstructionIndex(CopyMI); 87819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval *SrcInt = &LIS->getInterval(CP.getSrcReg()); 87919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SrcInt->liveAt(Idx)) 88019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 88119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval *DstInt = &LIS->getInterval(CP.getDstReg()); 88219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstInt->liveAt(Idx)) 88319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 88419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 88519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // No intervals are live-in to CopyMI - it is undef. 88619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isFlipped()) 88719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstInt = SrcInt; 88819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcInt = 0; 88919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 89019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *DeadVNI = DstInt->getVNInfoAt(Idx.getDefIndex()); 89119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(DeadVNI && "No value defined in DstInt"); 89219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstInt->removeValNo(DeadVNI); 89319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 89419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Find new undef uses. 89519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::reg_nodbg_iterator 89619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I = MRI->reg_nodbg_begin(DstInt->reg), E = MRI->reg_nodbg_end(); 89719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) { 89819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &MO = I.getOperand(); 89919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isDef() || MO.isUndef()) 90019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 90119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = MO.getParent(); 90219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex Idx = LIS->getInstructionIndex(MI); 90319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstInt->liveAt(Idx)) 90419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 90519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.setIsUndef(true); 90619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tnew undef: " << Idx << '\t' << *MI); 90719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 90819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 90919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 91019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 91119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// UpdateRegDefsUses - Replace all defs and uses of SrcReg to DstReg and 91219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// update the subregister number if it is not zero. If DstReg is a 91319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// physical register and the existing subregister number of the def / use 91419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// being updated is not zero, make sure to set it to the correct physical 91519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// subregister. 91619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid 91719bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanRegisterCoalescer::UpdateRegDefsUses(const CoalescerPair &CP) { 91819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool DstIsPhys = CP.isPhys(); 91919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcReg = CP.getSrcReg(); 92019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg = CP.getDstReg(); 92119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SubIdx = CP.getSubIdx(); 92219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 92319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update LiveDebugVariables. 92419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LDV->renameRegister(SrcReg, DstReg, SubIdx); 92519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 92619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineRegisterInfo::reg_iterator I = MRI->reg_begin(SrcReg); 92719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *UseMI = I.skipInstruction();) { 92819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A PhysReg copy that won't be coalesced can perhaps be rematerialized 92919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // instead. 93019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstIsPhys) { 93119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (UseMI->isFullCopy() && 93219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->getOperand(1).getReg() == SrcReg && 93319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->getOperand(0).getReg() != SrcReg && 93419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->getOperand(0).getReg() != DstReg && 93519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !JoinedCopies.count(UseMI) && 93619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMaterializeTrivialDef(LIS->getInterval(SrcReg), false, 93719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->getOperand(0).getReg(), UseMI)) 93819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 93919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 94019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 94119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<unsigned,8> Ops; 94219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Reads, Writes; 94319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman tie(Reads, Writes) = UseMI->readsWritesVirtualRegister(SrcReg, &Ops); 94419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Kills = false, Deads = false; 94519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 94619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Replace SrcReg with DstReg in all UseMI operands. 94719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 94819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &MO = UseMI->getOperand(Ops[i]); 94919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Kills |= MO.isKill(); 95019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Deads |= MO.isDead(); 95119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 95219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Make sure we don't create read-modify-write defs accidentally. We 95319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // assume here that a SrcReg def cannot be joined into a live DstReg. If 95419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // RegisterCoalescer starts tracking partially live registers, we will 95519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // need to check the actual LiveInterval to determine if DstReg is live 95619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // here. 95719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SubIdx && !Reads) 95819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.setIsUndef(); 95919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstIsPhys) 96119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.substPhysReg(DstReg, *TRI); 96219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 96319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.substVirtReg(DstReg, SubIdx, *TRI); 96419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 96519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 96619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This instruction is a copy that will be removed. 96719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (JoinedCopies.count(UseMI)) 96819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 96919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 97019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SubIdx) { 97119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If UseMI was a simple SrcReg def, make sure we didn't turn it into a 97219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // read-modify-write of DstReg. 97319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Deads) 97419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->addRegisterDead(DstReg, TRI); 97519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (!Reads && Writes) 97619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->addRegisterDefined(DstReg, TRI); 97719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 97819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Kill flags apply to the whole physical register. 97919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstIsPhys && Kills) 98019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UseMI->addRegisterKilled(DstReg, TRI); 98119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 98219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 98319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 98419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\t\tupdated: "; 98519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!UseMI->isDebugValue()) 98619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << LIS->getInstructionIndex(UseMI) << "\t"; 98719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << *UseMI; 98819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 98919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 99019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 99119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 99219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// removeIntervalIfEmpty - Check if the live interval of a physical register 99319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// is empty, if so remove it and also remove the empty intervals of its 99419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// sub-registers. Return true if live interval is removed. 99519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool removeIntervalIfEmpty(LiveInterval &li, LiveIntervals *LIS, 99619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo *TRI) { 99719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (li.empty()) { 99819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(li.reg)) 99919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned* SR = TRI->getSubRegisters(li.reg); *SR; ++SR) { 100019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(*SR)) 100119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 100219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &sli = LIS->getInterval(*SR); 100319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (sli.empty()) 100419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->removeInterval(*SR); 100519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 100619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->removeInterval(li.reg); 100719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 100819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 100919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 101019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 101119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 101219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// RemoveDeadDef - If a def of a live interval is now determined dead, remove 101319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// the val# it defines. If the live interval becomes empty, remove it as well. 101419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::RemoveDeadDef(LiveInterval &li, 101519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *DefMI) { 101619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex DefIdx = LIS->getInstructionIndex(DefMI).getDefIndex(); 101719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::iterator MLR = li.FindLiveRangeContaining(DefIdx); 101819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DefIdx != MLR->valno->def) 101919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 102019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman li.removeValNo(MLR->valno); 102119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return removeIntervalIfEmpty(li, LIS, TRI); 102219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 102319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 102419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::RemoveCopyFlag(unsigned DstReg, 102519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineInstr *CopyMI) { 102619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex DefIdx = LIS->getInstructionIndex(CopyMI).getDefIndex(); 102719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(DstReg)) { 102819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &LI = LIS->getInterval(DstReg); 102919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 103019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LR->valno->def == DefIdx) 103119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LR->valno->setCopy(0); 103219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 103319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TargetRegisterInfo::isPhysicalRegister(DstReg)) 103419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return; 103519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned* AS = TRI->getAliasSet(DstReg); *AS; ++AS) { 103619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(*AS)) 103719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 103819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &LI = LIS->getInterval(*AS); 103919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (const LiveRange *LR = LI.getLiveRangeContaining(DefIdx)) 104019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LR->valno->def == DefIdx) 104119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LR->valno->setCopy(0); 104219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 104319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 104419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 104519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// shouldJoinPhys - Return true if a copy involving a physreg should be joined. 104619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// We need to be careful about coalescing a source physical register with a 104719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// virtual register. Once the coalescing is done, it cannot be broken and these 104819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// are not spillable! If the destination interval uses are far away, think 104919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// twice about coalescing them! 105019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::shouldJoinPhys(CoalescerPair &CP) { 105119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Allocatable = LIS->isAllocatable(CP.getDstReg()); 105219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &JoinVInt = LIS->getInterval(CP.getSrcReg()); 105319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 105419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Always join simple intervals that are defined by a single copy from a 105519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// reserved register. This doesn't increase register pressure, so it is 105619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// always beneficial. 105719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Allocatable && CP.isFlipped() && JoinVInt.containsOneValue()) 105819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 105919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 106019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!EnablePhysicalJoin) { 106119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tPhysreg joins disabled.\n"); 106219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 106319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 106419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 106519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Only coalesce to allocatable physreg, we don't want to risk modifying 106619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // reserved registers. 106719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Allocatable) { 106819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tRegister is an unallocatable physreg.\n"); 106919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; // Not coalescable. 107019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 107119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 107219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Don't join with physregs that have a ridiculous number of live 107319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ranges. The data structure performance is really bad when that 107419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // happens. 107519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(CP.getDstReg()) && 107619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.getDstReg()).ranges.size() > 1000) { 107719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numAborts; 107819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() 107919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "\tPhysical register live interval too complicated, abort!\n"); 108019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 108119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 108219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 108319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME: Why are we skipping this test for partial copies? 108419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // CodeGen/X86/phys_subreg_coalesce-3.ll needs it. 108519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isPartial()) { 108619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *RC = MRI->getRegClass(CP.getSrcReg()); 108719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Threshold = RegClassInfo.getNumAllocatableRegs(RC) * 2; 108819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Length = LIS->getApproximateInstructionCount(JoinVInt); 108919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Length > Threshold) { 109019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numAborts; 109119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tMay tie down a physical register, abort!\n"); 109219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 109319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 1094894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 109519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 1096894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 1097894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 109819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// isWinToJoinCrossClass - Return true if it's profitable to coalesce 109919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// two virtual registers from different register classes. 110019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool 110119bac1e08be200c31efd26f0f5fd144c9b3eefd3John BaumanRegisterCoalescer::isWinToJoinCrossClass(unsigned SrcReg, 110219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg, 110319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *SrcRC, 110419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *DstRC, 110519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterClass *NewRC) { 110619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewRCCount = RegClassInfo.getNumAllocatableRegs(NewRC); 110719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // This heuristics is good enough in practice, but it's obviously not *right*. 110819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // 4 is a magic number that works well enough for x86, ARM, etc. It filter 110919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // out all but the most restrictive register classes. 111019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewRCCount > 4 || 111119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Early exit if the function is fairly small, coalesce aggressively if 111219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that's the case. For really special register classes with 3 or 111319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // fewer registers, be a bit more careful. 111419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (LIS->getFuncInstructionCount() / NewRCCount) < 8) 111519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 111619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &SrcInt = LIS->getInterval(SrcReg); 111719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &DstInt = LIS->getInterval(DstReg); 111819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcSize = LIS->getApproximateInstructionCount(SrcInt); 111919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstSize = LIS->getApproximateInstructionCount(DstInt); 112019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalesce aggressively if the intervals are small compared to the number of 112219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // registers in the new class. The number 4 is fairly arbitrary, chosen to be 112319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // less aggressive than the 8 used for the whole function size. 112419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const unsigned ThresSize = 4 * NewRCCount; 112519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SrcSize <= ThresSize && DstSize <= ThresSize) 112619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 112719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 112819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Estimate *register use density*. If it doubles or more, abort. 112919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcUses = std::distance(MRI->use_nodbg_begin(SrcReg), 113019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->use_nodbg_end()); 113119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstUses = std::distance(MRI->use_nodbg_begin(DstReg), 113219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->use_nodbg_end()); 113319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewUses = SrcUses + DstUses; 113419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned NewSize = SrcSize + DstSize; 113519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SrcRC != NewRC && SrcSize > ThresSize) { 113619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcRCCount = RegClassInfo.getNumAllocatableRegs(SrcRC); 113719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewUses*SrcSize*SrcRCCount > 2*SrcUses*NewSize*NewRCCount) 113819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 113919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 114019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DstRC != NewRC && DstSize > ThresSize) { 114119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstRCCount = RegClassInfo.getNumAllocatableRegs(DstRC); 114219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewUses*DstSize*DstRCCount > 2*DstUses*NewSize*NewRCCount) 114319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 114419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 114519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 114619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 114719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 114819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 114919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// JoinCopy - Attempt to join intervals corresponding to SrcReg/DstReg, 115019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// which are the src/dst of the copy instruction CopyMI. This returns true 115119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// if the copy was successfully coalesced away. If it is not currently 115219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// possible to coalesce this interval, but it may be possible if other 115319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// things get coalesced, then it returns true by reference in 'Again'. 115419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::JoinCopy(MachineInstr *CopyMI, bool &Again) { 115519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 115619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Again = false; 115719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (JoinedCopies.count(CopyMI) || ReMatCopies.count(CopyMI)) 115819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; // Already done. 115919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 116019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << LIS->getInstructionIndex(CopyMI) << '\t' << *CopyMI); 116119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 116219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CoalescerPair CP(*TII, *TRI); 116319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.setRegisters(CopyMI)) { 116419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tNot coalescable.\n"); 116519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 116619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 116719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 116819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If they are already joined we continue. 116919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.getSrcReg() == CP.getDstReg()) { 117019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(CopyMI); 117119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tCopy already coalesced.\n"); 117219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; // Not coalescable. 117319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 117419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 117519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Eliminate undefs. 117619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isPhys() && eliminateUndefCopy(CopyMI, CP)) { 117719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(CopyMI); 117819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tEliminated copy of <undef> value.\n"); 117919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; // Not coalescable. 118019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 118119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 118219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tConsidering merging " << PrintReg(CP.getSrcReg(), TRI) 118319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << " with " << PrintReg(CP.getDstReg(), TRI, CP.getSubIdx()) 118419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "\n"); 118519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 118619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Enforce policies. 118719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isPhys()) { 118819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!shouldJoinPhys(CP)) { 118919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Before giving up coalescing, if definition of source is defined by 119019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // trivial computation, try rematerializing it. 119119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isFlipped() && 119219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), true, 119319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CP.getDstReg(), CopyMI)) 119419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 119519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 119619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 119719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 119819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Avoid constraining virtual register regclass too much. 119919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isCrossClass()) { 120019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tCross-class to " << CP.getNewRC()->getName() << ".\n"); 120119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (DisableCrossClassJoin) { 120219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tCross-class joins disabled.\n"); 120319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 120419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 120519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isWinToJoinCrossClass(CP.getSrcReg(), CP.getDstReg(), 120619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->getRegClass(CP.getSrcReg()), 120719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->getRegClass(CP.getDstReg()), 120819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CP.getNewRC())) { 120919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tAvoid coalescing to constrained register class.\n"); 121019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Again = true; // May be possible to coalesce later. 121119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 121219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 121319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 121419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 121519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When possible, let DstReg be the larger interval. 121619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.getSubIdx() && LIS->getInterval(CP.getSrcReg()).ranges.size() > 121719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->getInterval(CP.getDstReg()).ranges.size()) 121819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CP.flip(); 121919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 122019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 122119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Okay, attempt to join these two intervals. On failure, this returns false. 122219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, if one of the intervals being joined is a physreg, this method 122319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // always canonicalizes DstInt to be it. The output "SrcInt" will not have 122419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // been modified, so we can use this information below to update aliases. 122519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!JoinIntervals(CP)) { 122619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalescing failed. 122719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 122819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If definition of source is defined by trivial computation, try 122919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // rematerializing it. 123019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isFlipped() && 123119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMaterializeTrivialDef(LIS->getInterval(CP.getSrcReg()), true, 123219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CP.getDstReg(), CopyMI)) 123319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 123419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 123519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we can eliminate the copy without merging the live ranges, do so now. 123619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isPartial()) { 123719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (AdjustCopiesBackFrom(CP, CopyMI) || 123819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RemoveCopyByCommutingDef(CP, CopyMI)) { 123919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(CopyMI); 124019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tTrivial!\n"); 124119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 124219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 124319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 124419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 124519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, we are unable to join the intervals. 124619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "\tInterference!\n"); 124719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Again = true; // May be possible to coalesce later. 124819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 124919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 125019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 125119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Coalescing to a virtual register that is of a sub-register class of the 125219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // other. Make sure the resulting register is set to the right register class. 125319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isCrossClass()) { 125419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numCrossRCs; 125519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI->setRegClass(CP.getDstReg(), CP.getNewRC()); 125619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 125719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 125819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Remember to delete the copy instruction. 125919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(CopyMI); 126019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 126119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman UpdateRegDefsUses(CP); 126219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 126319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we have extended the live range of a physical register, make sure we 126419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // update live-in lists as well. 126519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isPhys()) { 126619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineBasicBlock*, 16> BlockSeq; 126719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // JoinIntervals invalidates the VNInfos in SrcInt, but we only need the 126819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ranges for this, and they are preserved. 126919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &SrcInt = LIS->getInterval(CP.getSrcReg()); 127019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::const_iterator I = SrcInt.begin(), E = SrcInt.end(); 127119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I ) { 127219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->findLiveInMBBs(I->start, I->end, BlockSeq); 127319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned idx = 0, size = BlockSeq.size(); idx != size; ++idx) { 127419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock &block = *BlockSeq[idx]; 127519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!block.isLiveIn(CP.getDstReg())) 127619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman block.addLiveIn(CP.getDstReg()); 127719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 127819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman BlockSeq.clear(); 127919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 128019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 128119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // SrcReg is guarateed to be the register whose live interval that is 128319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // being merged. 128419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->removeInterval(CP.getSrcReg()); 128519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update regalloc hint. 128719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI->UpdateRegAllocHint(CP.getSrcReg(), CP.getDstReg(), *MF); 128819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 128919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 129019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &DstInt = LIS->getInterval(CP.getDstReg()); 129119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\tJoined. Result = "; 129219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstInt.print(dbgs(), TRI); 129319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n"; 129419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 129519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 129619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numJoins; 129719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 129819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 129919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 130019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ComputeUltimateVN - Assuming we are going to join two live intervals, 130119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// compute what the resultant value numbers for each value in the input two 130219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ranges will be. This is complicated by copies between the two which can 130319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// and will commonly cause multiple value numbers to be merged into one. 130419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 130519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// VN is the value number that we're trying to resolve. InstDefiningValue 130619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// keeps track of the new InstDefiningValue assignment for the result 130719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// LiveInterval. ThisFromOther/OtherFromThis are sets that keep track of 130819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// whether a value in this or other is a copy from the opposite set. 130919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ThisValNoAssignments/OtherValNoAssignments keep track of value #'s that have 131019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// already been assigned. 131119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 131219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// ThisFromOther[x] - If x is defined as a copy from the other interval, this 131319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// contains the value number the copy is from. 131419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// 131519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic unsigned ComputeUltimateVN(VNInfo *VNI, 131619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<VNInfo*, 16> &NewVNInfo, 131719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<VNInfo*, VNInfo*> &ThisFromOther, 131819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<VNInfo*, VNInfo*> &OtherFromThis, 131919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<int, 16> &ThisValNoAssignments, 132019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<int, 16> &OtherValNoAssignments) { 132119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned VN = VNI->id; 132219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 132319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the VN has already been computed, just return it. 132419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ThisValNoAssignments[VN] >= 0) 132519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ThisValNoAssignments[VN]; 132619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(ThisValNoAssignments[VN] != -2 && "Cyclic value numbers"); 132719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 132819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this val is not a copy from the other val, then it must be a new value 132919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // number in the destination. 133019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<VNInfo*, VNInfo*>::iterator I = ThisFromOther.find(VNI); 133119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I == ThisFromOther.end()) { 133219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewVNInfo.push_back(VNI); 133319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ThisValNoAssignments[VN] = NewVNInfo.size()-1; 133419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 133519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *OtherValNo = I->second; 133619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 133719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, this *is* a copy from the RHS. If the other side has already 133819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // been computed, return it. 133919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (OtherValNoAssignments[OtherValNo->id] >= 0) 134019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ThisValNoAssignments[VN] = OtherValNoAssignments[OtherValNo->id]; 134119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 134219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Mark this value number as currently being computed, then ask what the 134319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // ultimate value # of the other value is. 134419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ThisValNoAssignments[VN] = -2; 134519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned UltimateVN = 134619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ComputeUltimateVN(OtherValNo, NewVNInfo, OtherFromThis, ThisFromOther, 134719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman OtherValNoAssignments, ThisValNoAssignments); 134819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return ThisValNoAssignments[VN] = UltimateVN; 134919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 135019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 135119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 135219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// Find out if we have something like 135319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A = X 135419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// B = X 135519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// if so, we can pretend this is actually 135619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// A = X 135719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// B = A 135819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// which allows us to coalesce A and B. 135919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// VNI is the definition of B. LR is the life range of A that includes 136019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// the slot just before B. If we return true, we add "B = X" to DupCopies. 136119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman// This implies that A dominates B. 136219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanstatic bool RegistersDefinedFromSameValue(LiveIntervals &li, 136319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const TargetRegisterInfo &tri, 136419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CoalescerPair &CP, 136519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI, 136619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *LR, 136719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> &DupCopies) { 136819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // FIXME: This is very conservative. For example, we don't handle 136919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // physical registers. 137019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = VNI->getCopy(); 137219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MI->isFullCopy() || CP.isPartial() || CP.isPhys()) 137419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 137519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Dst = MI->getOperand(0).getReg(); 137719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Src = MI->getOperand(1).getReg(); 137819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 137919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TargetRegisterInfo::isVirtualRegister(Src) || 138019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !TargetRegisterInfo::isVirtualRegister(Dst)) 138119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 138219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 138319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned A = CP.getDstReg(); 138419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned B = CP.getSrcReg(); 138519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 138619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (B == Dst) 138719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::swap(A, B); 138819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(Dst == A); 138919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 139019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *Other = LR->valno; 139119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Other->isDefByCopy()) 139219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 139319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineInstr *OtherMI = Other->getCopy(); 139419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 139519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!OtherMI->isFullCopy()) 139619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 139719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 139819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OtherDst = OtherMI->getOperand(0).getReg(); 139919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned OtherSrc = OtherMI->getOperand(1).getReg(); 140019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 140119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TargetRegisterInfo::isVirtualRegister(OtherSrc) || 140219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !TargetRegisterInfo::isVirtualRegister(OtherDst)) 140319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 140419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 140519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(OtherDst == B); 140619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 140719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Src != OtherSrc) 140819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 140919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 141019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the copies use two different value numbers of X, we cannot merge 141119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A and B. 141219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &SrcInt = li.getInterval(Src); 141319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // getVNInfoBefore returns NULL for undef copies. In this case, the 141419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // optimization is still safe. 141519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SrcInt.getVNInfoBefore(Other->def) != SrcInt.getVNInfoBefore(VNI->def)) 141619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 141719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 141819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DupCopies.push_back(MI); 141919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 142019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 142119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 142219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 142319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// JoinIntervals - Attempt to join these two intervals. On failure, this 142419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// returns false. 142519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::JoinIntervals(CoalescerPair &CP) { 142619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &RHS = LIS->getInterval(CP.getSrcReg()); 142719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ dbgs() << "\t\tRHS = "; RHS.print(dbgs(), TRI); dbgs() << "\n"; }); 142819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 142919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If a live interval is a physical register, check for interference with any 143019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // aliases. The interference check implemented here is a bit more conservative 143119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // than the full interfeence check below. We allow overlapping live ranges 143219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // only when one is a copy of the other. 143319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (CP.isPhys()) { 143419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *AS = TRI->getAliasSet(CP.getDstReg()); *AS; ++AS){ 143519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->hasInterval(*AS)) 143619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 143719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const LiveInterval &LHS = LIS->getInterval(*AS); 143819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::const_iterator LI = LHS.begin(); 143919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::const_iterator RI = RHS.begin(), RE = RHS.end(); 144019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RI != RE; ++RI) { 144119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LI = std::lower_bound(LI, LHS.end(), RI->start); 144219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Does LHS have an overlapping live range starting before RI? 144319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if ((LI != LHS.begin() && LI[-1].end > RI->start) && 144419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman (RI->start != RI->valno->def || 144519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !CP.isCoalescable(LIS->getInstructionFromIndex(RI->start)))) { 144619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 144719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\t\tInterference from alias: "; 144819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHS.print(dbgs(), TRI); 144919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n\t\tOverlap at " << RI->start << " and no copy.\n"; 145019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 145119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 145219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 145319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 145419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Check that LHS ranges beginning in this range are copies. 145519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (; LI != LHS.end() && LI->start < RI->end; ++LI) { 145619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LI->start != LI->valno->def || 145719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !CP.isCoalescable(LIS->getInstructionFromIndex(LI->start))) { 145819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 145919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\t\tInterference from alias: "; 146019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHS.print(dbgs(), TRI); 146119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n\t\tDef at " << LI->start << " is not a copy.\n"; 146219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 146319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 146419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 146919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 147019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Compute the final value assignment, assuming that the live ranges can be 147119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // coalesced. 147219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<int, 16> LHSValNoAssignments; 147319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<int, 16> RHSValNoAssignments; 147419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<VNInfo*, VNInfo*> LHSValsDefinedFromRHS; 147519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DenseMap<VNInfo*, VNInfo*> RHSValsDefinedFromLHS; 147619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<VNInfo*, 16> NewVNInfo; 147719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 147819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> DupCopies; 147919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 148019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval &LHS = LIS->getOrCreateInterval(CP.getDstReg()); 148119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ dbgs() << "\t\tLHS = "; LHS.print(dbgs(), TRI); dbgs() << "\n"; }); 148219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 148319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Loop over the value numbers of the LHS, seeing if any are defined from 148419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the RHS. 148519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 148619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e; ++i) { 148719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = *i; 148819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 148919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 149019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 149119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Never join with a register that has EarlyClobber redefs. 149219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->hasRedefByEC()) 149319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 149419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 149519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Figure out the value # from the RHS. 149619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *lr = RHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 149719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The copy could be to an aliased physreg. 149819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!lr) continue; 149919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 150019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DstReg is known to be a register in the LHS interval. If the src is 150119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // from the RHS interval, we can use its value #. 150219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = VNI->getCopy(); 150319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isCoalescable(MI) && 150419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, lr, DupCopies)) 150519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 150619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 150719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHSValsDefinedFromRHS[VNI] = lr->valno; 150819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 150919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 151019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Loop over the value numbers of the RHS, seeing if any are defined from 151119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the LHS. 151219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 151319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e; ++i) { 151419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = *i; 151519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->isUnused() || !VNI->isDefByCopy()) // Src not defined by a copy? 151619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 151719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 151819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Never join with a register that has EarlyClobber redefs. 151919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->hasRedefByEC()) 152019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 152119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 152219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Figure out the value # from the LHS. 152319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveRange *lr = LHS.getLiveRangeContaining(VNI->def.getPrevSlot()); 152419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // The copy could be to an aliased physreg. 152519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!lr) continue; 152619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 152719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DstReg is known to be a register in the RHS interval. If the src is 152819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // from the LHS interval, we can use its value #. 152919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = VNI->getCopy(); 153019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!CP.isCoalescable(MI) && 153119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !RegistersDefinedFromSameValue(*LIS, *TRI, CP, VNI, lr, DupCopies)) 153219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 153319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 153419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValsDefinedFromLHS[VNI] = lr->valno; 153519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 153619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 153719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHSValNoAssignments.resize(LHS.getNumValNums(), -1); 153819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValNoAssignments.resize(RHS.getNumValNums(), -1); 153919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewVNInfo.reserve(LHS.getNumValNums() + RHS.getNumValNums()); 154019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 154119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::vni_iterator i = LHS.vni_begin(), e = LHS.vni_end(); 154219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e; ++i) { 154319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = *i; 154419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned VN = VNI->id; 154519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 154619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 154719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ComputeUltimateVN(VNI, NewVNInfo, 154819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHSValsDefinedFromRHS, RHSValsDefinedFromLHS, 154919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHSValNoAssignments, RHSValNoAssignments); 155019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 155119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveInterval::vni_iterator i = RHS.vni_begin(), e = RHS.vni_end(); 155219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman i != e; ++i) { 155319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = *i; 155419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned VN = VNI->id; 155519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RHSValNoAssignments[VN] >= 0 || VNI->isUnused()) 155619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 155719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this value number isn't a copy from the LHS, it's a new number. 155819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RHSValsDefinedFromLHS.find(VNI) == RHSValsDefinedFromLHS.end()) { 155919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewVNInfo.push_back(VNI); 156019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValNoAssignments[VN] = NewVNInfo.size()-1; 156119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 156219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 156319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 156419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ComputeUltimateVN(VNI, NewVNInfo, 156519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValsDefinedFromLHS, LHSValsDefinedFromRHS, 156619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValNoAssignments, LHSValNoAssignments); 156719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 156819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 156919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Armed with the mappings of LHS/RHS values to ultimate values, walk the 157019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // interval lists to see if these intervals are coalescable. 157119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::const_iterator I = LHS.begin(); 157219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::const_iterator IE = LHS.end(); 157319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::const_iterator J = RHS.begin(); 157419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LiveInterval::const_iterator JE = RHS.end(); 157519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 157619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Skip ahead until the first place of potential sharing. 157719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I != IE && J != JE) { 157819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->start < J->start) { 157919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I = std::upper_bound(I, IE, J->start); 158019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I != LHS.begin()) --I; 158119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (J->start < I->start) { 158219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman J = std::upper_bound(J, JE, I->start); 158319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (J != RHS.begin()) --J; 158419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 158519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 158619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 158719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (I != IE && J != JE) { 158819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Determine if these two live ranges overlap. 158919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Overlaps; 159019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->start < J->start) { 159119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Overlaps = I->end > J->start; 159219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 159319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Overlaps = J->end > I->start; 159419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 159519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 159619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If so, check value # info to determine if they are really different. 159719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Overlaps) { 159819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If the live range overlap will map to the same value number in the 159919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // result liverange, we can still coalesce them. If not, we can't. 160019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHSValNoAssignments[I->valno->id] != 160119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValNoAssignments[J->valno->id]) 160219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 160319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If it's re-defined by an early clobber somewhere in the live range, 160419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // then conservatively abort coalescing. 160519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (NewVNInfo[LHSValNoAssignments[I->valno->id]]->hasRedefByEC()) 160619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return false; 160719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 160819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 160919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (I->end < J->end) 161019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++I; 161119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 161219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++J; 161319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 161419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 161519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update kill info. Some live ranges are extended due to copy coalescing. 161619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (DenseMap<VNInfo*, VNInfo*>::iterator I = LHSValsDefinedFromRHS.begin(), 161719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = LHSValsDefinedFromRHS.end(); I != E; ++I) { 161819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = I->first; 161919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned LHSValID = LHSValNoAssignments[VNI->id]; 162019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->hasPHIKill()) 162119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewVNInfo[LHSValID]->setHasPHIKill(true); 162219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 162319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 162419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Update kill info. Some live ranges are extended due to copy coalescing. 162519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (DenseMap<VNInfo*, VNInfo*>::iterator I = RHSValsDefinedFromLHS.begin(), 162619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = RHSValsDefinedFromLHS.end(); I != E; ++I) { 162719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VNInfo *VNI = I->first; 162819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned RHSValID = RHSValNoAssignments[VNI->id]; 162919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VNI->hasPHIKill()) 163019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NewVNInfo[RHSValID]->setHasPHIKill(true); 163119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 163219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 163319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHSValNoAssignments.empty()) 163419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHSValNoAssignments.push_back(-1); 163519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RHSValNoAssignments.empty()) 163619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RHSValNoAssignments.push_back(-1); 163719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 163819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<unsigned, 8> SourceRegisters; 163919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<MachineInstr*, 8>::iterator I = DupCopies.begin(), 164019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = DupCopies.end(); I != E; ++I) { 164119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = *I; 164219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 164319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We have pretended that the assignment to B in 164419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A = X 164519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // B = X 164619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // was actually a copy from A. Now that we decided to coalesce A and B, 164719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // transform the code into 164819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // A = X 164919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // X = X 165019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and mark the X as coalesced to keep the illusion. 165119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Src = MI->getOperand(1).getReg(); 165219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SourceRegisters.push_back(Src); 165319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->getOperand(0).substVirtReg(Src, 0, *TRI); 165419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 165519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman markAsJoined(MI); 165619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 165719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 165819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If B = X was the last use of X in a liverange, we have to shrink it now 165919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // that B = X is gone. 166019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (SmallVector<unsigned, 8>::iterator I = SourceRegisters.begin(), 166119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman E = SourceRegisters.end(); I != E; ++I) { 166219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->shrinkToUses(&LIS->getInterval(*I)); 166319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 166419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 166519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If we get here, we know that we can coalesce the live ranges. Ask the 166619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // intervals to coalesce themselves now. 166719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LHS.join(RHS, &LHSValNoAssignments[0], &RHSValNoAssignments[0], NewVNInfo, 166819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI); 166919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 167019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 167119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 167219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumannamespace { 167319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DepthMBBCompare - Comparison predicate that sort first based on the loop 167419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // depth of the basic block (the unsigned), and then on the MBB number. 167519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct DepthMBBCompare { 167619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman typedef std::pair<unsigned, MachineBasicBlock*> DepthMBBPair; 167719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool operator()(const DepthMBBPair &LHS, const DepthMBBPair &RHS) const { 167819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Deeper loops first 167919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LHS.first != RHS.first) 168019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHS.first > RHS.first; 168119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 168219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Prefer blocks that are more connected in the CFG. This takes care of 168319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // the most difficult copies first while intervals are short. 168419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned cl = LHS.second->pred_size() + LHS.second->succ_size(); 168519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned cr = RHS.second->pred_size() + RHS.second->succ_size(); 168619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (cl != cr) 168719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return cl > cr; 168819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 168919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // As a last resort, sort by block number. 169019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return LHS.second->getNumber() < RHS.second->getNumber(); 169119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 169219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }; 169319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 169419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 169519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::CopyCoalesceInMBB(MachineBasicBlock *MBB, 169619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<MachineInstr*> &TryAgain) { 169719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << MBB->getName() << ":\n"); 169819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 169919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> VirtCopies; 170019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> PhysCopies; 170119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<MachineInstr*, 8> ImpDefCopies; 170219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::iterator MII = MBB->begin(), E = MBB->end(); 170319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MII != E;) { 170419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *Inst = MII++; 170519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 170619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If this isn't a copy nor a extract_subreg, we can't join intervals. 170719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcReg, DstReg; 170819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Inst->isCopy()) { 170919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstReg = Inst->getOperand(0).getReg(); 171019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcReg = Inst->getOperand(1).getReg(); 171119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else if (Inst->isSubregToReg()) { 171219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DstReg = Inst->getOperand(0).getReg(); 171319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SrcReg = Inst->getOperand(2).getReg(); 171419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else 171519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 171619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 171719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool SrcIsPhys = TargetRegisterInfo::isPhysicalRegister(SrcReg); 171819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool DstIsPhys = TargetRegisterInfo::isPhysicalRegister(DstReg); 171919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(SrcReg) && LIS->getInterval(SrcReg).empty()) 172019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ImpDefCopies.push_back(Inst); 172119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else if (SrcIsPhys || DstIsPhys) 172219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman PhysCopies.push_back(Inst); 172319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman else 172419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman VirtCopies.push_back(Inst); 172519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 172619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 172719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Try coalescing implicit copies and insert_subreg <undef> first, 172819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // followed by copies to / from physical registers, then finally copies 172919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // from virtual registers to virtual registers. 173019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = ImpDefCopies.size(); i != e; ++i) { 173119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *TheCopy = ImpDefCopies[i]; 173219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Again = false; 173319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!JoinCopy(TheCopy, Again)) 173419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Again) 173519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TryAgain.push_back(TheCopy); 173619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 173719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = PhysCopies.size(); i != e; ++i) { 173819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *TheCopy = PhysCopies[i]; 173919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Again = false; 174019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!JoinCopy(TheCopy, Again)) 174119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Again) 174219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TryAgain.push_back(TheCopy); 174319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 174419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = VirtCopies.size(); i != e; ++i) { 174519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *TheCopy = VirtCopies[i]; 174619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Again = false; 174719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!JoinCopy(TheCopy, Again)) 174819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Again) 174919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TryAgain.push_back(TheCopy); 175019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 175119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 175219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 175319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::joinIntervals() { 175419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "********** JOINING INTERVALS ***********\n"); 175519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 175619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<MachineInstr*> TryAgainList; 175719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Loops->empty()) { 175819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // If there are no loops in the function, join intervals in function order. 175919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::iterator I = MF->begin(), E = MF->end(); 176019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I) 176119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CopyCoalesceInMBB(I, TryAgainList); 176219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 176319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Otherwise, join intervals in inner loops before other intervals. 176419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Unfortunately we can't just iterate over loop hierarchy here because 176519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // there may be more MBB's than BB's. Collect MBB's for sorting. 176619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 176719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Join intervals in the function prolog first. We want to join physical 176819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // registers with virtual registers before the intervals got too long. 176919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::vector<std::pair<unsigned, MachineBasicBlock*> > MBBs; 177019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::iterator I = MF->begin(), E = MF->end();I != E;++I){ 177119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock *MBB = I; 177219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MBBs.push_back(std::make_pair(Loops->getLoopDepth(MBB), I)); 177319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 177419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 177519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Sort by loop depth. 177619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman std::sort(MBBs.begin(), MBBs.end(), DepthMBBCompare()); 177719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 177819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Finally, join intervals in loop nest order. 177919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = MBBs.size(); i != e; ++i) 178019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CopyCoalesceInMBB(MBBs[i].second, TryAgainList); 178119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 178219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 178319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Joining intervals can allow other intervals to be joined. Iteratively join 178419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // until we make no progress. 178519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool ProgressMade = true; 178619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (ProgressMade) { 178719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ProgressMade = false; 178819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 178919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = TryAgainList.size(); i != e; ++i) { 179019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *&TheCopy = TryAgainList[i]; 179119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TheCopy) 179219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 179319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 179419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Again = false; 179519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool Success = JoinCopy(TheCopy, Again); 179619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (Success || !Again) { 179719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TheCopy= 0; // Mark this one as done. 179819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ProgressMade = true; 179919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 180019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 180119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 180219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 180319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 180419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::releaseMemory() { 180519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman JoinedCopies.clear(); 180619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMatCopies.clear(); 180719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ReMatDefs.clear(); 180819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 180919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 181019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanbool RegisterCoalescer::runOnMachineFunction(MachineFunction &fn) { 181119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MF = &fn; 181219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MRI = &fn.getRegInfo(); 181319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TM = &fn.getTarget(); 181419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TRI = TM->getRegisterInfo(); 181519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman TII = TM->getInstrInfo(); 181619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS = &getAnalysis<LiveIntervals>(); 181719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LDV = &getAnalysis<LiveDebugVariables>(); 181819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman AA = &getAnalysis<AliasAnalysis>(); 181919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman Loops = &getAnalysis<MachineLoopInfo>(); 182019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 182119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "********** SIMPLE REGISTER COALESCING **********\n" 182219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << "********** Function: " 182319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << ((Value*)MF->getFunction())->getName() << '\n'); 182419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 182519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VerifyCoalescing) 182619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MF->verify(this, "Before register coalescing"); 182719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 182819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegClassInfo.runOnMachineFunction(fn); 182919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 183019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Join (coalesce) intervals if requested. 183119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (EnableJoining) { 183219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman joinIntervals(); 183319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG({ 183419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "********** INTERVALS POST JOINING **********\n"; 183519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (LiveIntervals::iterator I = LIS->begin(), E = LIS->end(); 183619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I != E; ++I){ 183719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman I->second->print(dbgs(), TRI); 183819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman dbgs() << "\n"; 183919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 184019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman }); 184119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 184219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 184319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Perform a final pass over the instructions and compute spill weights 184419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // and remove identity moves. 184519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SmallVector<unsigned, 4> DeadDefs, InflateRegs; 184619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineFunction::iterator mbbi = MF->begin(), mbbe = MF->end(); 184719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mbbi != mbbe; ++mbbi) { 184819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineBasicBlock* mbb = mbbi; 184919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (MachineBasicBlock::iterator mii = mbb->begin(), mie = mbb->end(); 185019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mii != mie; ) { 185119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineInstr *MI = mii; 185219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (JoinedCopies.count(MI)) { 185319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Delete all coalesced copies. 185419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool DoDelete = true; 185519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(MI->isCopyLike() && "Unrecognized copy instruction"); 185619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned SrcReg = MI->getOperand(MI->isSubregToReg() ? 2 : 1).getReg(); 185719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DstReg = MI->getOperand(0).getReg(); 185819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 185919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Collect candidates for register class inflation. 186019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(SrcReg) && 186119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegClassInfo.isProperSubClass(MRI->getRegClass(SrcReg))) 186219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InflateRegs.push_back(SrcReg); 186319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(DstReg) && 186419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RegClassInfo.isProperSubClass(MRI->getRegClass(DstReg))) 186519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InflateRegs.push_back(DstReg); 186619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 186719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(SrcReg) && 186819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->getNumOperands() > 2) 186919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Do not delete extract_subreg, insert_subreg of physical 187019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // registers unless the definition is dead. e.g. 187119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // %DO<def> = INSERT_SUBREG %D0<undef>, %S0<kill>, 1 187219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // or else the scavenger may complain. LowerSubregs will 187319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // delete them later. 187419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DoDelete = false; 187519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 187619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MI->allDefsAreDead()) { 187719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(SrcReg) && 187819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->hasInterval(SrcReg)) 187919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->shrinkToUses(&LIS->getInterval(SrcReg)); 188019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DoDelete = true; 188119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 188219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!DoDelete) { 188319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // We need the instruction to adjust liveness, so make it a KILL. 188419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MI->isSubregToReg()) { 188519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->RemoveOperand(3); 188619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->RemoveOperand(1); 188719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 188819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->setDesc(TII->get(TargetOpcode::KILL)); 188919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mii = llvm::next(mii); 189019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else { 189119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->RemoveMachineInstrFromMaps(MI); 189219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mii = mbbi->erase(mii); 189319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++numPeep; 189419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 189519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 189619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 189719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 189819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Now check if this is a remat'ed def instruction which is now dead. 189919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (ReMatDefs.count(MI)) { 190019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isDead = true; 190119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 190219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MachineOperand &MO = MI->getOperand(i); 190319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MO.isReg()) 190419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 190519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Reg = MO.getReg(); 190619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!Reg) 190719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 190819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isVirtualRegister(Reg)) { 190919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DeadDefs.push_back(Reg); 191019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Remat may also enable register class inflation. 191119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (RegClassInfo.isProperSubClass(MRI->getRegClass(Reg))) 191219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InflateRegs.push_back(Reg); 191319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 191419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MO.isDead()) 191519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 191619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (TargetRegisterInfo::isPhysicalRegister(Reg) || 191719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman !MRI->use_nodbg_empty(Reg)) { 191819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isDead = false; 191919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman break; 192019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (isDead) { 192319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman while (!DeadDefs.empty()) { 192419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned DeadDef = DeadDefs.back(); 192519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DeadDefs.pop_back(); 192619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman RemoveDeadDef(LIS->getInterval(DeadDef), MI); 192719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 192819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->RemoveMachineInstrFromMaps(mii); 192919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman mii = mbbi->erase(mii); 193019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 193119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } else 193219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DeadDefs.clear(); 193319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 193419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 193519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++mii; 193619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 193719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Check for now unnecessary kill flags. 193819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->isNotInMIMap(MI)) continue; 193919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SlotIndex DefIdx = LIS->getInstructionIndex(MI).getDefIndex(); 194019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 194119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MachineOperand &MO = MI->getOperand(i); 194219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!MO.isReg() || !MO.isKill()) continue; 194319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned reg = MO.getReg(); 194419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!reg || !LIS->hasInterval(reg)) continue; 194519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!LIS->getInterval(reg).killedAt(DefIdx)) { 194619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MO.setIsKill(false); 194719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 194819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 194919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // When leaving a kill flag on a physreg, check if any subregs should 195019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // remain alive. 195119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!TargetRegisterInfo::isPhysicalRegister(reg)) 195219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 195319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (const unsigned *SR = TRI->getSubRegisters(reg); 195419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned S = *SR; ++SR) 195519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (LIS->hasInterval(S) && LIS->getInterval(S).liveAt(DefIdx)) 195619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MI->addRegisterDefined(S, TRI); 195719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 195819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 195919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 196019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 196119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // After deleting a lot of copies, register classes may be less constrained. 196219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Removing sub-register opreands may alow GR32_ABCD -> GR32 and DPR_VFP2 -> 196319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // DPR inflation. 196419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman array_pod_sort(InflateRegs.begin(), InflateRegs.end()); 196519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InflateRegs.erase(std::unique(InflateRegs.begin(), InflateRegs.end()), 196619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman InflateRegs.end()); 196719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << "Trying to inflate " << InflateRegs.size() << " regs.\n"); 196819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman for (unsigned i = 0, e = InflateRegs.size(); i != e; ++i) { 196919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned Reg = InflateRegs[i]; 197019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MRI->reg_nodbg_empty(Reg)) 197119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman continue; 197219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (MRI->recomputeRegClass(Reg, *TM)) { 197319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dbgs() << PrintReg(Reg) << " inflated to " 197419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman << MRI->getRegClass(Reg)->getName() << '\n'); 197519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman ++NumInflated; 197619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 197719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 197819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 197919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(dump()); 198019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman DEBUG(LDV->dump()); 198119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (VerifyCoalescing) 198219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman MF->verify(this, "After register coalescing"); 198319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 198419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 198519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 198619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman/// print - Implement the dump method. 198719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Baumanvoid RegisterCoalescer::print(raw_ostream &O, const Module* m) const { 198819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman LIS->print(O, m); 198919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman} 1990