lib/CodeGen/LiveRangeEdit.cpp

   1 //===--- LiveRangeEdit.cpp - Basic tools for editing a register live range --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // The LiveRangeEdit class represents changes done to a virtual register when it
  11 // is spilled or split.
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "LiveRangeEdit.h"
  15 #include "VirtRegMap.h"
  16 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  17 #include "llvm/CodeGen/MachineRegisterInfo.h"
  18 #include "llvm/Target/TargetInstrInfo.h"
  19
  20 using namespace llvm;
  21
  22 int LiveRangeEdit::assignStackSlot(VirtRegMap &vrm) {
  23   int ss = vrm.getStackSlot(getReg());
  24   if (ss != VirtRegMap::NO_STACK_SLOT)
  25     return ss;
  26   return vrm.assignVirt2StackSlot(getReg());
  27 }
  28
  29 LiveInterval &LiveRangeEdit::create(MachineRegisterInfo &mri,
  30                                     LiveIntervals &lis,
  31                                     VirtRegMap &vrm) {
  32   const TargetRegisterClass *RC = mri.getRegClass(parent_.reg);
  33   unsigned VReg = mri.createVirtualRegister(RC);
  34   vrm.grow();
  35   // Immediately assign to the same stack slot as parent.
  36   vrm.assignVirt2StackSlot(VReg, assignStackSlot(vrm));
  37   LiveInterval &li = lis.getOrCreateInterval(VReg);
  38   newRegs_.push_back(&li);
  39   return li;
  40 }
  41
  42 void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
  43                                    const TargetInstrInfo &tii,
  44                                    AliasAnalysis *aa) {
  45   for (LiveInterval::vni_iterator I = parent_.vni_begin(),
  46        E = parent_.vni_end(); I != E; ++I) {
  47     VNInfo *VNI = *I;
  48     if (VNI->isUnused())
  49       continue;
  50     MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def);
  51     if (!DefMI)
  52       continue;
  53     if (tii.isTriviallyReMaterializable(DefMI, aa))
  54       remattable_.insert(VNI);
  55   }
  56   scannedRemattable_ = true;
  57 }
  58
  59 bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
  60                                         const TargetInstrInfo &tii,
  61                                         AliasAnalysis *aa) {
  62   if (!scannedRemattable_)
  63     scanRemattable(lis, tii, aa);
  64   return !remattable_.empty();
  65 }
  66
  67 /// allUsesAvailableAt - Return true if all registers used by OrigMI at
  68 /// OrigIdx are also available with the same value at UseIdx.
  69 bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
  70                                        SlotIndex OrigIdx,
  71                                        SlotIndex UseIdx,
  72                                        LiveIntervals &lis) {
  73   OrigIdx = OrigIdx.getUseIndex();
  74   UseIdx = UseIdx.getUseIndex();
  75   for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
  76     const MachineOperand &MO = OrigMI->getOperand(i);
  77     if (!MO.isReg() || !MO.getReg() || MO.getReg() == getReg())
  78       continue;
  79     // Reserved registers are OK.
  80     if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
  81       continue;
  82     // We don't want to move any defs.
  83     if (MO.isDef())
  84       return false;
  85     // We cannot depend on virtual registers in uselessRegs_.
  86     for (unsigned ui = 0, ue = uselessRegs_.size(); ui != ue; ++ui)
  87       if (uselessRegs_[ui]->reg == MO.getReg())
  88         return false;
  89
  90     LiveInterval &li = lis.getInterval(MO.getReg());
  91     const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
  92     if (!OVNI)
  93       continue;
  94     if (OVNI != li.getVNInfoAt(UseIdx))
  95       return false;
  96   }
  97   return true;
  98 }
  99
 100 LiveRangeEdit::Remat LiveRangeEdit::canRematerializeAt(VNInfo *ParentVNI,
 101                                                        SlotIndex UseIdx,
 102                                                        bool cheapAsAMove,
 103                                                        LiveIntervals &lis) {
 104   assert(scannedRemattable_ && "Call anyRematerializable first");
 105   Remat RM = { 0, 0 };
 106
 107   // We could remat an undefined value as IMPLICIT_DEF, but all that should have
 108   // been taken care of earlier.
 109   if (!(RM.ParentVNI = parent_.getVNInfoAt(UseIdx)))
 110     return RM;
 111
 112   // Use scanRemattable info.
 113   if (!remattable_.count(RM.ParentVNI))
 114     return RM;
 115
 116   // No defining instruction.
 117   MachineInstr *OrigMI = lis.getInstructionFromIndex(RM.ParentVNI->def);
 118   assert(OrigMI && "Defining instruction for remattable value disappeared");
 119
 120   // If only cheap remats were requested, bail out early.
 121   if (cheapAsAMove && !OrigMI->getDesc().isAsCheapAsAMove())
 122     return RM;
 123
 124   // Verify that all used registers are available with the same values.
 125   if (!allUsesAvailableAt(OrigMI, RM.ParentVNI->def, UseIdx, lis))
 126     return RM;
 127
 128   RM.OrigMI = OrigMI;
 129   return RM;
 130 }
 131
 132 SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
 133                                          MachineBasicBlock::iterator MI,
 134                                          unsigned DestReg,
 135                                          const Remat &RM,
 136                                          LiveIntervals &lis,
 137                                          const TargetInstrInfo &tii,
 138                                          const TargetRegisterInfo &tri) {
 139   assert(RM.OrigMI && "Invalid remat");
 140   tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
 141   rematted_.insert(RM.ParentVNI);
 142   return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
 143 }
 144