llvm/lib/CodeGen/LiveIntervalCalc.cpp

   1 //===- LiveIntervalCalc.cpp - Calculate live interval --------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // Implementation of the LiveIntervalCalc class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/CodeGen/LiveIntervalCalc.h"
  14 #include "llvm/ADT/SmallVector.h"
  15 #include "llvm/CodeGen/LiveInterval.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineOperand.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/SlotIndexes.h"
  20 #include "llvm/CodeGen/TargetRegisterInfo.h"
  21 #include "llvm/MC/LaneBitmask.h"
  22 #include "llvm/Support/ErrorHandling.h"
  23 #include <cassert>
  24
  25 using namespace llvm;
  26
  27 #define DEBUG_TYPE "regalloc"
  28
  29 // Reserve an address that indicates a value that is known to be "undef".
  30 static VNInfo UndefVNI(0xbad, SlotIndex());
  31
  32 static void createDeadDef(SlotIndexes &Indexes, VNInfo::Allocator &Alloc,
  33                           LiveRange &LR, const MachineOperand &MO) {
  34   const MachineInstr &MI = *MO.getParent();
  35   SlotIndex DefIdx =
  36       Indexes.getInstructionIndex(MI).getRegSlot(MO.isEarlyClobber());
  37
  38   // Create the def in LR. This may find an existing def.
  39   LR.createDeadDef(DefIdx, Alloc);
  40 }
  41
  42 void LiveIntervalCalc::calculate(LiveInterval &LI, bool TrackSubRegs) {
  43   const MachineRegisterInfo *MRI = getRegInfo();
  44   SlotIndexes *Indexes = getIndexes();
  45   VNInfo::Allocator *Alloc = getVNAlloc();
  46
  47   assert(MRI && Indexes && "call reset() first");
  48
  49   // Step 1: Create minimal live segments for every definition of Reg.
  50   // Visit all def operands. If the same instruction has multiple defs of Reg,
  51   // createDeadDef() will deduplicate.
  52   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
  53   Register Reg = LI.reg();
  54   for (const MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
  55     if (!MO.isDef() && !MO.readsReg())
  56       continue;
  57
  58     unsigned SubReg = MO.getSubReg();
  59     if (LI.hasSubRanges() || (SubReg != 0 && TrackSubRegs)) {
  60       LaneBitmask SubMask = SubReg != 0 ? TRI.getSubRegIndexLaneMask(SubReg)
  61                                         : MRI->getMaxLaneMaskForVReg(Reg);
  62       // If this is the first time we see a subregister def, initialize
  63       // subranges by creating a copy of the main range.
  64       if (!LI.hasSubRanges() && !LI.empty()) {
  65         LaneBitmask ClassMask = MRI->getMaxLaneMaskForVReg(Reg);
  66         LI.createSubRangeFrom(*Alloc, ClassMask, LI);
  67       }
  68
  69       LI.refineSubRanges(
  70           *Alloc, SubMask,
  71           [&MO, Indexes, Alloc](LiveInterval::SubRange &SR) {
  72             if (MO.isDef())
  73               createDeadDef(*Indexes, *Alloc, SR, MO);
  74           },
  75           *Indexes, TRI);
  76     }
  77
  78     // Create the def in the main liverange. We do not have to do this if
  79     // subranges are tracked as we recreate the main range later in this case.
  80     if (MO.isDef() && !LI.hasSubRanges())
  81       createDeadDef(*Indexes, *Alloc, LI, MO);
  82   }
  83
  84   // We may have created empty live ranges for partially undefined uses, we
  85   // can't keep them because we won't find defs in them later.
  86   LI.removeEmptySubRanges();
  87
  88   const MachineFunction *MF = getMachineFunction();
  89   MachineDominatorTree *DomTree = getDomTree();
  90   // Step 2: Extend live segments to all uses, constructing SSA form as
  91   // necessary.
  92   if (LI.hasSubRanges()) {
  93     for (LiveInterval::SubRange &S : LI.subranges()) {
  94       LiveIntervalCalc SubLIC;
  95       SubLIC.reset(MF, Indexes, DomTree, Alloc);
  96       SubLIC.extendToUses(S, Reg, S.LaneMask, &LI);
  97     }
  98     LI.clear();
  99     constructMainRangeFromSubranges(LI);
 100   } else {
 101     resetLiveOutMap();
 102     extendToUses(LI, Reg, LaneBitmask::getAll());
 103   }
 104 }
 105
 106 void LiveIntervalCalc::constructMainRangeFromSubranges(LiveInterval &LI) {
 107   // First create dead defs at all defs found in subranges.
 108   LiveRange &MainRange = LI;
 109   assert(MainRange.segments.empty() && MainRange.valnos.empty() &&
 110          "Expect empty main liverange");
 111
 112   VNInfo::Allocator *Alloc = getVNAlloc();
 113   for (const LiveInterval::SubRange &SR : LI.subranges()) {
 114     for (const VNInfo *VNI : SR.valnos) {
 115       if (!VNI->isUnused() && !VNI->isPHIDef())
 116         MainRange.createDeadDef(VNI->def, *Alloc);
 117     }
 118   }
 119   resetLiveOutMap();
 120   extendToUses(MainRange, LI.reg(), LaneBitmask::getAll(), &LI);
 121 }
 122
 123 void LiveIntervalCalc::createDeadDefs(LiveRange &LR, Register Reg) {
 124   const MachineRegisterInfo *MRI = getRegInfo();
 125   SlotIndexes *Indexes = getIndexes();
 126   VNInfo::Allocator *Alloc = getVNAlloc();
 127   assert(MRI && Indexes && "call reset() first");
 128
 129   // Visit all def operands. If the same instruction has multiple defs of Reg,
 130   // LR.createDeadDef() will deduplicate.
 131   for (MachineOperand &MO : MRI->def_operands(Reg))
 132     createDeadDef(*Indexes, *Alloc, LR, MO);
 133 }
 134
 135 void LiveIntervalCalc::extendToUses(LiveRange &LR, Register Reg,
 136                                     LaneBitmask Mask, LiveInterval *LI) {
 137   const MachineRegisterInfo *MRI = getRegInfo();
 138   SlotIndexes *Indexes = getIndexes();
 139   SmallVector<SlotIndex, 4> Undefs;
 140   if (LI != nullptr)
 141     LI->computeSubRangeUndefs(Undefs, Mask, *MRI, *Indexes);
 142
 143   // Visit all operands that read Reg. This may include partial defs.
 144   bool IsSubRange = !Mask.all();
 145   const TargetRegisterInfo &TRI = *MRI->getTargetRegisterInfo();
 146   for (MachineOperand &MO : MRI->reg_nodbg_operands(Reg)) {
 147     // Clear all kill flags. They will be reinserted after register allocation
 148     // by LiveIntervals::addKillFlags().
 149     if (MO.isUse())
 150       MO.setIsKill(false);
 151     // MO::readsReg returns "true" for subregister defs. This is for keeping
 152     // liveness of the entire register (i.e. for the main range of the live
 153     // interval). For subranges, definitions of non-overlapping subregisters
 154     // do not count as uses.
 155     if (!MO.readsReg() || (IsSubRange && MO.isDef()))
 156       continue;
 157
 158     unsigned SubReg = MO.getSubReg();
 159     if (SubReg != 0) {
 160       LaneBitmask SLM = TRI.getSubRegIndexLaneMask(SubReg);
 161       if (MO.isDef())
 162         SLM = ~SLM;
 163       // Ignore uses not reading the current (sub)range.
 164       if ((SLM & Mask).none())
 165         continue;
 166     }
 167
 168     // Determine the actual place of the use.
 169     const MachineInstr *MI = MO.getParent();
 170     unsigned OpNo = (&MO - &MI->getOperand(0));
 171     SlotIndex UseIdx;
 172     if (MI->isPHI()) {
 173       assert(!MO.isDef() && "Cannot handle PHI def of partial register.");
 174       // The actual place where a phi operand is used is the end of the pred
 175       // MBB. PHI operands are paired: (Reg, PredMBB).
 176       UseIdx = Indexes->getMBBEndIdx(MI->getOperand(OpNo + 1).getMBB());
 177     } else {
 178       // Check for early-clobber redefs.
 179       bool isEarlyClobber = false;
 180       unsigned DefIdx;
 181       if (MO.isDef())
 182         isEarlyClobber = MO.isEarlyClobber();
 183       else if (MI->isRegTiedToDefOperand(OpNo, &DefIdx)) {
 184         // FIXME: This would be a lot easier if tied early-clobber uses also
 185         // had an early-clobber flag.
 186         isEarlyClobber = MI->getOperand(DefIdx).isEarlyClobber();
 187       }
 188       UseIdx = Indexes->getInstructionIndex(*MI).getRegSlot(isEarlyClobber);
 189     }
 190
 191     // MI is reading Reg. We may have visited MI before if it happens to be
 192     // reading Reg multiple times. That is OK, extend() is idempotent.
 193     extend(LR, UseIdx, Reg, Undefs);
 194   }
 195 }