18879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen//===-- LiveRegMatrix.cpp - Track register interference -------------------===// 28879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// 38879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 48879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// 58879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 68879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 78879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// 88879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 98879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// 108879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// This file defines the LiveRegMatrix analysis pass. 118879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen// 128879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 138879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 148879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen#define DEBUG_TYPE "regalloc" 15d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/LiveRegMatrix.h" 1645c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen#include "RegisterCoalescer.h" 178879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen#include "llvm/ADT/Statistic.h" 188879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/MachineRegisterInfo.h" 201ead68d769f27f6d68d4aaeffe4199fa2cacbc95Jakob Stoklund Olesen#include "llvm/CodeGen/VirtRegMap.h" 218879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen#include "llvm/Support/Debug.h" 228879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen#include "llvm/Support/raw_ostream.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 258879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 268879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenusing namespace llvm; 278879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 288879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenSTATISTIC(NumAssigned , "Number of registers assigned"); 298879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenSTATISTIC(NumUnassigned , "Number of registers unassigned"); 308879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 318879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenchar LiveRegMatrix::ID = 0; 328879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenINITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 338879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen "Live Register Matrix", false, false) 348879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 358879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 368879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenINITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 378879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen "Live Register Matrix", false, false) 388879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 398879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenLiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 408879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 418879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 428879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenvoid LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 438879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen AU.setPreservesAll(); 448879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen AU.addRequiredTransitive<LiveIntervals>(); 458879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen AU.addRequiredTransitive<VirtRegMap>(); 468879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen MachineFunctionPass::getAnalysisUsage(AU); 478879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 488879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 498879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenbool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 508879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen TRI = MF.getTarget().getRegisterInfo(); 518879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen MRI = &MF.getRegInfo(); 528879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen LIS = &getAnalysis<LiveIntervals>(); 538879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen VRM = &getAnalysis<VirtRegMap>(); 548879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 558879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen unsigned NumRegUnits = TRI->getNumRegUnits(); 568879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (NumRegUnits != Matrix.size()) 578879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 588879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Matrix.init(LIUAlloc, NumRegUnits); 598879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 608879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Make sure no stale queries get reused. 618879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen invalidateVirtRegs(); 628879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return false; 638879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 648879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 658879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenvoid LiveRegMatrix::releaseMemory() { 668879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 678879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Matrix[i].clear(); 688879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Queries[i].clear(); 698879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen } 708879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 718879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 728879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenvoid LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 738879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 748879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen << " to " << PrintReg(PhysReg, TRI) << ':'); 758879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 768879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 778879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen MRI->setPhysRegUsed(PhysReg); 788879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 798879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 808879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Matrix[*Units].unify(VirtReg); 818879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen } 828879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen ++NumAssigned; 838879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 848879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 858879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 868879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenvoid LiveRegMatrix::unassign(LiveInterval &VirtReg) { 878879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen unsigned PhysReg = VRM->getPhys(VirtReg.reg); 888879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 898879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen << " from " << PrintReg(PhysReg, TRI) << ':'); 908879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen VRM->clearVirt(VirtReg.reg); 918879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 928879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 938879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Matrix[*Units].extract(VirtReg); 948879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen } 958879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen ++NumUnassigned; 968879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen DEBUG(dbgs() << '\n'); 978879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 988879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 998879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenbool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 1008879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen unsigned PhysReg) { 1018879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Check if the cached information is valid. 1028879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // The same BitVector can be reused for all PhysRegs. 1038879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // We could cache multiple VirtRegs if it becomes necessary. 1048879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 1058879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen RegMaskVirtReg = VirtReg.reg; 1068879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen RegMaskTag = UserTag; 1078879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen RegMaskUsable.clear(); 1088879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 1098879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen } 1108879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1118879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // The BitVector is indexed by PhysReg, not register unit. 1128879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Regmask interference is more fine grained than regunits. 1138879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 114eb06b0b6aa627c6698471d4df71570f080fb3c5cJakob Stoklund Olesen return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 1158879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 1168879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1178879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesenbool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 1188879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen unsigned PhysReg) { 1198879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (VirtReg.empty()) 1208879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return false; 12145c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 1228879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 12345c5c57179e8b4938042431f8e12c9bfad67b3c8Jakob Stoklund Olesen if (VirtReg.overlaps(LIS->getRegUnit(*Units), CP, *LIS->getSlotIndexes())) 1248879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return true; 1258879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return false; 1268879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 1278879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1288879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenLiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 1298879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen unsigned RegUnit) { 1308879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen LiveIntervalUnion::Query &Q = Queries[RegUnit]; 1318879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 1328879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return Q; 1338879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 1348879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1358879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenLiveRegMatrix::InterferenceKind 1368879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund OlesenLiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 1378879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (VirtReg.empty()) 1388879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return IK_Free; 1398879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1408879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Regmask interference is the fastest check. 1418879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (checkRegMaskInterference(VirtReg, PhysReg)) 1428879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return IK_RegMask; 1438879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1448879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Check for fixed interference. 1458879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (checkRegUnitInterference(VirtReg, PhysReg)) 1468879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return IK_RegUnit; 1478879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1488879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen // Check the matrix for virtual register interference. 1498879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 1508879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen if (query(VirtReg, *Units).checkInterference()) 1518879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return IK_VirtReg; 1528879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen 1538879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen return IK_Free; 1548879480ed708ffa51d23f423ec316763c7cb9577Jakob Stoklund Olesen} 155