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