LiveRangeEdit.cpp revision 7792e980c43536814ea42448db9799b4da32fef6 
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/ADT/SetVector.h"
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/Target/TargetInstrInfo.h"
20#include "llvm/Support/Debug.h"
21#include "llvm/Support/raw_ostream.h"
22
23using namespace llvm;
24
25LiveInterval &LiveRangeEdit::create(MachineRegisterInfo &mri,
26                                    LiveIntervals &lis,
27                                    VirtRegMap &vrm) {
28  const TargetRegisterClass *RC = mri.getRegClass(getReg());
29  unsigned VReg = mri.createVirtualRegister(RC);
30  vrm.grow();
31  vrm.setIsSplitFromReg(VReg, vrm.getOriginal(getReg()));
32  LiveInterval &li = lis.getOrCreateInterval(VReg);
33  newRegs_.push_back(&li);
34  return li;
35}
36
37void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
38                                   const TargetInstrInfo &tii,
39                                   AliasAnalysis *aa) {
40  for (LiveInterval::vni_iterator I = parent_.vni_begin(),
41       E = parent_.vni_end(); I != E; ++I) {
42    VNInfo *VNI = *I;
43    if (VNI->isUnused())
44      continue;
45    MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def);
46    if (!DefMI)
47      continue;
48    if (tii.isTriviallyReMaterializable(DefMI, aa))
49      remattable_.insert(VNI);
50  }
51  scannedRemattable_ = true;
52}
53
54bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
55                                        const TargetInstrInfo &tii,
56                                        AliasAnalysis *aa) {
57  if (!scannedRemattable_)
58    scanRemattable(lis, tii, aa);
59  return !remattable_.empty();
60}
61
62/// allUsesAvailableAt - Return true if all registers used by OrigMI at
63/// OrigIdx are also available with the same value at UseIdx.
64bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
65                                       SlotIndex OrigIdx,
66                                       SlotIndex UseIdx,
67                                       LiveIntervals &lis) {
68  OrigIdx = OrigIdx.getUseIndex();
69  UseIdx = UseIdx.getUseIndex();
70  for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
71    const MachineOperand &MO = OrigMI->getOperand(i);
72    if (!MO.isReg() || !MO.getReg() || MO.getReg() == getReg())
73      continue;
74    // Reserved registers are OK.
75    if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
76      continue;
77    // We don't want to move any defs.
78    if (MO.isDef())
79      return false;
80    // We cannot depend on virtual registers in uselessRegs_.
81    if (uselessRegs_)
82      for (unsigned ui = 0, ue = uselessRegs_->size(); ui != ue; ++ui)
83        if ((*uselessRegs_)[ui]->reg == MO.getReg())
84          return false;
85
86    LiveInterval &li = lis.getInterval(MO.getReg());
87    const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
88    if (!OVNI)
89      continue;
90    if (OVNI != li.getVNInfoAt(UseIdx))
91      return false;
92  }
93  return true;
94}
95
96bool LiveRangeEdit::canRematerializeAt(Remat &RM,
97                                       SlotIndex UseIdx,
98                                       bool cheapAsAMove,
99                                       LiveIntervals &lis) {
100  assert(scannedRemattable_ && "Call anyRematerializable first");
101
102  // Use scanRemattable info.
103  if (!remattable_.count(RM.ParentVNI))
104    return false;
105
106  // No defining instruction.
107  RM.OrigMI = lis.getInstructionFromIndex(RM.ParentVNI->def);
108  assert(RM.OrigMI && "Defining instruction for remattable value disappeared");
109
110  // If only cheap remats were requested, bail out early.
111  if (cheapAsAMove && !RM.OrigMI->getDesc().isAsCheapAsAMove())
112    return false;
113
114  // Verify that all used registers are available with the same values.
115  if (!allUsesAvailableAt(RM.OrigMI, RM.ParentVNI->def, UseIdx, lis))
116    return false;
117
118  return true;
119}
120
121SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
122                                         MachineBasicBlock::iterator MI,
123                                         unsigned DestReg,
124                                         const Remat &RM,
125                                         LiveIntervals &lis,
126                                         const TargetInstrInfo &tii,
127                                         const TargetRegisterInfo &tri) {
128  assert(RM.OrigMI && "Invalid remat");
129  tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
130  rematted_.insert(RM.ParentVNI);
131  return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
132}
133
134void LiveRangeEdit::eraseVirtReg(unsigned Reg, LiveIntervals &LIS) {
135  if (delegate_ && delegate_->LRE_CanEraseVirtReg(Reg))
136    LIS.removeInterval(Reg);
137}
138
139void LiveRangeEdit::eliminateDeadDefs(SmallVectorImpl<MachineInstr*> &Dead,
140                                      LiveIntervals &LIS,
141                                      const TargetInstrInfo &TII) {
142  SetVector<LiveInterval*,
143            SmallVector<LiveInterval*, 8>,
144            SmallPtrSet<LiveInterval*, 8> > ToShrink;
145
146  for (;;) {
147    // Erase all dead defs.
148    while (!Dead.empty()) {
149      MachineInstr *MI = Dead.pop_back_val();
150      assert(MI->allDefsAreDead() && "Def isn't really dead");
151
152      // Never delete inline asm.
153      if (MI->isInlineAsm())
154        continue;
155
156      // Use the same criteria as DeadMachineInstructionElim.
157      bool SawStore = false;
158      if (!MI->isSafeToMove(&TII, 0, SawStore))
159        continue;
160
161      SlotIndex Idx = LIS.getInstructionIndex(MI).getDefIndex();
162      DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);
163
164      // Check for live intervals that may shrink
165      for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
166             MOE = MI->operands_end(); MOI != MOE; ++MOI) {
167        if (!MOI->isReg())
168          continue;
169        unsigned Reg = MOI->getReg();
170        if (!TargetRegisterInfo::isVirtualRegister(Reg))
171          continue;
172        LiveInterval &LI = LIS.getInterval(Reg);
173        // Remove defined value.
174        if (MOI->isDef())
175          if (VNInfo *VNI = LI.getVNInfoAt(Idx))
176            LI.removeValNo(VNI);
177        // Shrink read registers.
178        if (MI->readsVirtualRegister(Reg))
179          ToShrink.insert(&LI);
180      }
181
182      if (delegate_)
183        delegate_->LRE_WillEraseInstruction(MI);
184      LIS.RemoveMachineInstrFromMaps(MI);
185      MI->eraseFromParent();
186    }
187
188    if (ToShrink.empty())
189      break;
190
191    // Shrink just one live interval. Then delete new dead defs.
192    LIS.shrinkToUses(ToShrink.back(), &Dead);
193    ToShrink.pop_back();
194  }
195}
196
197