1239310Sdim//===-- LiveRegMatrix.cpp - Track register interference -------------------===// 2239310Sdim// 3239310Sdim// The LLVM Compiler Infrastructure 4239310Sdim// 5239310Sdim// This file is distributed under the University of Illinois Open Source 6239310Sdim// License. See LICENSE.TXT for details. 7239310Sdim// 8239310Sdim//===----------------------------------------------------------------------===// 9239310Sdim// 10239310Sdim// This file defines the LiveRegMatrix analysis pass. 11239310Sdim// 12239310Sdim//===----------------------------------------------------------------------===// 13239310Sdim 14239310Sdim#define DEBUG_TYPE "regalloc" 15249423Sdim#include "llvm/CodeGen/LiveRegMatrix.h" 16243830Sdim#include "RegisterCoalescer.h" 17239310Sdim#include "llvm/ADT/Statistic.h" 18249423Sdim#include "llvm/CodeGen/LiveIntervalAnalysis.h" 19239310Sdim#include "llvm/CodeGen/MachineRegisterInfo.h" 20249423Sdim#include "llvm/CodeGen/VirtRegMap.h" 21249423Sdim#include "llvm/Support/Debug.h" 22249423Sdim#include "llvm/Support/raw_ostream.h" 23239310Sdim#include "llvm/Target/TargetMachine.h" 24239310Sdim#include "llvm/Target/TargetRegisterInfo.h" 25239310Sdim 26239310Sdimusing namespace llvm; 27239310Sdim 28239310SdimSTATISTIC(NumAssigned , "Number of registers assigned"); 29239310SdimSTATISTIC(NumUnassigned , "Number of registers unassigned"); 30239310Sdim 31239310Sdimchar LiveRegMatrix::ID = 0; 32239310SdimINITIALIZE_PASS_BEGIN(LiveRegMatrix, "liveregmatrix", 33239310Sdim "Live Register Matrix", false, false) 34239310SdimINITIALIZE_PASS_DEPENDENCY(LiveIntervals) 35239310SdimINITIALIZE_PASS_DEPENDENCY(VirtRegMap) 36239310SdimINITIALIZE_PASS_END(LiveRegMatrix, "liveregmatrix", 37239310Sdim "Live Register Matrix", false, false) 38239310Sdim 39239310SdimLiveRegMatrix::LiveRegMatrix() : MachineFunctionPass(ID), 40239310Sdim UserTag(0), RegMaskTag(0), RegMaskVirtReg(0) {} 41239310Sdim 42239310Sdimvoid LiveRegMatrix::getAnalysisUsage(AnalysisUsage &AU) const { 43239310Sdim AU.setPreservesAll(); 44239310Sdim AU.addRequiredTransitive<LiveIntervals>(); 45239310Sdim AU.addRequiredTransitive<VirtRegMap>(); 46239310Sdim MachineFunctionPass::getAnalysisUsage(AU); 47239310Sdim} 48239310Sdim 49239310Sdimbool LiveRegMatrix::runOnMachineFunction(MachineFunction &MF) { 50239310Sdim TRI = MF.getTarget().getRegisterInfo(); 51239310Sdim MRI = &MF.getRegInfo(); 52239310Sdim LIS = &getAnalysis<LiveIntervals>(); 53239310Sdim VRM = &getAnalysis<VirtRegMap>(); 54239310Sdim 55239310Sdim unsigned NumRegUnits = TRI->getNumRegUnits(); 56239310Sdim if (NumRegUnits != Matrix.size()) 57239310Sdim Queries.reset(new LiveIntervalUnion::Query[NumRegUnits]); 58239310Sdim Matrix.init(LIUAlloc, NumRegUnits); 59239310Sdim 60239310Sdim // Make sure no stale queries get reused. 61239310Sdim invalidateVirtRegs(); 62239310Sdim return false; 63239310Sdim} 64239310Sdim 65239310Sdimvoid LiveRegMatrix::releaseMemory() { 66239310Sdim for (unsigned i = 0, e = Matrix.size(); i != e; ++i) { 67239310Sdim Matrix[i].clear(); 68239310Sdim Queries[i].clear(); 69239310Sdim } 70239310Sdim} 71239310Sdim 72239310Sdimvoid LiveRegMatrix::assign(LiveInterval &VirtReg, unsigned PhysReg) { 73239310Sdim DEBUG(dbgs() << "assigning " << PrintReg(VirtReg.reg, TRI) 74239310Sdim << " to " << PrintReg(PhysReg, TRI) << ':'); 75239310Sdim assert(!VRM->hasPhys(VirtReg.reg) && "Duplicate VirtReg assignment"); 76239310Sdim VRM->assignVirt2Phys(VirtReg.reg, PhysReg); 77239310Sdim MRI->setPhysRegUsed(PhysReg); 78239310Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 79239310Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 80239310Sdim Matrix[*Units].unify(VirtReg); 81239310Sdim } 82239310Sdim ++NumAssigned; 83239310Sdim DEBUG(dbgs() << '\n'); 84239310Sdim} 85239310Sdim 86239310Sdimvoid LiveRegMatrix::unassign(LiveInterval &VirtReg) { 87239310Sdim unsigned PhysReg = VRM->getPhys(VirtReg.reg); 88239310Sdim DEBUG(dbgs() << "unassigning " << PrintReg(VirtReg.reg, TRI) 89239310Sdim << " from " << PrintReg(PhysReg, TRI) << ':'); 90239310Sdim VRM->clearVirt(VirtReg.reg); 91239310Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) { 92239310Sdim DEBUG(dbgs() << ' ' << PrintRegUnit(*Units, TRI)); 93239310Sdim Matrix[*Units].extract(VirtReg); 94239310Sdim } 95239310Sdim ++NumUnassigned; 96239310Sdim DEBUG(dbgs() << '\n'); 97239310Sdim} 98239310Sdim 99239310Sdimbool LiveRegMatrix::checkRegMaskInterference(LiveInterval &VirtReg, 100239310Sdim unsigned PhysReg) { 101239310Sdim // Check if the cached information is valid. 102239310Sdim // The same BitVector can be reused for all PhysRegs. 103239310Sdim // We could cache multiple VirtRegs if it becomes necessary. 104239310Sdim if (RegMaskVirtReg != VirtReg.reg || RegMaskTag != UserTag) { 105239310Sdim RegMaskVirtReg = VirtReg.reg; 106239310Sdim RegMaskTag = UserTag; 107239310Sdim RegMaskUsable.clear(); 108239310Sdim LIS->checkRegMaskInterference(VirtReg, RegMaskUsable); 109239310Sdim } 110239310Sdim 111239310Sdim // The BitVector is indexed by PhysReg, not register unit. 112239310Sdim // Regmask interference is more fine grained than regunits. 113239310Sdim // For example, a Win64 call can clobber %ymm8 yet preserve %xmm8. 114239310Sdim return !RegMaskUsable.empty() && (!PhysReg || !RegMaskUsable.test(PhysReg)); 115239310Sdim} 116239310Sdim 117239310Sdimbool LiveRegMatrix::checkRegUnitInterference(LiveInterval &VirtReg, 118239310Sdim unsigned PhysReg) { 119239310Sdim if (VirtReg.empty()) 120239310Sdim return false; 121243830Sdim CoalescerPair CP(VirtReg.reg, PhysReg, *TRI); 122239310Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 123243830Sdim if (VirtReg.overlaps(LIS->getRegUnit(*Units), CP, *LIS->getSlotIndexes())) 124239310Sdim return true; 125239310Sdim return false; 126239310Sdim} 127239310Sdim 128239310SdimLiveIntervalUnion::Query &LiveRegMatrix::query(LiveInterval &VirtReg, 129239310Sdim unsigned RegUnit) { 130239310Sdim LiveIntervalUnion::Query &Q = Queries[RegUnit]; 131239310Sdim Q.init(UserTag, &VirtReg, &Matrix[RegUnit]); 132239310Sdim return Q; 133239310Sdim} 134239310Sdim 135239310SdimLiveRegMatrix::InterferenceKind 136239310SdimLiveRegMatrix::checkInterference(LiveInterval &VirtReg, unsigned PhysReg) { 137239310Sdim if (VirtReg.empty()) 138239310Sdim return IK_Free; 139239310Sdim 140239310Sdim // Regmask interference is the fastest check. 141239310Sdim if (checkRegMaskInterference(VirtReg, PhysReg)) 142239310Sdim return IK_RegMask; 143239310Sdim 144239310Sdim // Check for fixed interference. 145239310Sdim if (checkRegUnitInterference(VirtReg, PhysReg)) 146239310Sdim return IK_RegUnit; 147239310Sdim 148239310Sdim // Check the matrix for virtual register interference. 149239310Sdim for (MCRegUnitIterator Units(PhysReg, TRI); Units.isValid(); ++Units) 150239310Sdim if (query(VirtReg, *Units).checkInterference()) 151239310Sdim return IK_VirtReg; 152239310Sdim 153239310Sdim return IK_Free; 154239310Sdim} 155