LiveRangeEdit.cpp revision 23a698e5c756c5cac7b0a7f640391443b3809dcb 
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
20using namespace llvm;
21
22LiveInterval &LiveRangeEdit::create(MachineRegisterInfo &mri,
23                                    LiveIntervals &lis,
24                                    VirtRegMap &vrm) {
25  const TargetRegisterClass *RC = mri.getRegClass(parent_.reg);
26  unsigned VReg = mri.createVirtualRegister(RC);
27  vrm.grow();
28  LiveInterval &li = lis.getOrCreateInterval(VReg);
29  newRegs_.push_back(&li);
30  return li;
31}
32
33void LiveRangeEdit::scanRemattable(LiveIntervals &lis,
34                                   const TargetInstrInfo &tii,
35                                   AliasAnalysis *aa) {
36  for (LiveInterval::vni_iterator I = parent_.vni_begin(),
37       E = parent_.vni_end(); I != E; ++I) {
38    VNInfo *VNI = *I;
39    if (VNI->isUnused())
40      continue;
41    MachineInstr *DefMI = lis.getInstructionFromIndex(VNI->def);
42    if (!DefMI)
43      continue;
44    if (tii.isTriviallyReMaterializable(DefMI, aa))
45      remattable_.insert(VNI);
46  }
47  scannedRemattable_ = true;
48}
49
50bool LiveRangeEdit::anyRematerializable(LiveIntervals &lis,
51                                        const TargetInstrInfo &tii,
52                                        AliasAnalysis *aa) {
53  if (!scannedRemattable_)
54    scanRemattable(lis, tii, aa);
55  return !remattable_.empty();
56}
57
58/// allUsesAvailableAt - Return true if all registers used by OrigMI at
59/// OrigIdx are also available with the same value at UseIdx.
60bool LiveRangeEdit::allUsesAvailableAt(const MachineInstr *OrigMI,
61                                       SlotIndex OrigIdx,
62                                       SlotIndex UseIdx,
63                                       LiveIntervals &lis) {
64  OrigIdx = OrigIdx.getUseIndex();
65  UseIdx = UseIdx.getUseIndex();
66  for (unsigned i = 0, e = OrigMI->getNumOperands(); i != e; ++i) {
67    const MachineOperand &MO = OrigMI->getOperand(i);
68    if (!MO.isReg() || !MO.getReg() || MO.getReg() == getReg())
69      continue;
70    // Reserved registers are OK.
71    if (MO.isUndef() || !lis.hasInterval(MO.getReg()))
72      continue;
73    // We don't want to move any defs.
74    if (MO.isDef())
75      return false;
76    // We cannot depend on virtual registers in uselessRegs_.
77    for (unsigned ui = 0, ue = uselessRegs_.size(); ui != ue; ++ui)
78      if (uselessRegs_[ui]->reg == MO.getReg())
79        return false;
80
81    LiveInterval &li = lis.getInterval(MO.getReg());
82    const VNInfo *OVNI = li.getVNInfoAt(OrigIdx);
83    if (!OVNI)
84      continue;
85    if (OVNI != li.getVNInfoAt(UseIdx))
86      return false;
87  }
88  return true;
89}
90
91LiveRangeEdit::Remat LiveRangeEdit::canRematerializeAt(VNInfo *ParentVNI,
92                                                       SlotIndex UseIdx,
93                                                       bool cheapAsAMove,
94                                                       LiveIntervals &lis) {
95  assert(scannedRemattable_ && "Call anyRematerializable first");
96  Remat RM = { 0, 0 };
97
98  // We could remat an undefined value as IMPLICIT_DEF, but all that should have
99  // been taken care of earlier.
100  if (!(RM.ParentVNI = parent_.getVNInfoAt(UseIdx)))
101    return RM;
102
103  // Use scanRemattable info.
104  if (!remattable_.count(RM.ParentVNI))
105    return RM;
106
107  // No defining instruction.
108  MachineInstr *OrigMI = lis.getInstructionFromIndex(RM.ParentVNI->def);
109  assert(OrigMI && "Defining instruction for remattable value disappeared");
110
111  // If only cheap remats were requested, bail out early.
112  if (cheapAsAMove && !OrigMI->getDesc().isAsCheapAsAMove())
113    return RM;
114
115  // Verify that all used registers are available with the same values.
116  if (!allUsesAvailableAt(OrigMI, RM.ParentVNI->def, UseIdx, lis))
117    return RM;
118
119  RM.OrigMI = OrigMI;
120  return RM;
121}
122
123SlotIndex LiveRangeEdit::rematerializeAt(MachineBasicBlock &MBB,
124                                         MachineBasicBlock::iterator MI,
125                                         unsigned DestReg,
126                                         const Remat &RM,
127                                         LiveIntervals &lis,
128                                         const TargetInstrInfo &tii,
129                                         const TargetRegisterInfo &tri) {
130  assert(RM.OrigMI && "Invalid remat");
131  tii.reMaterialize(MBB, MI, DestReg, 0, RM.OrigMI, tri);
132  rematted_.insert(RM.ParentVNI);
133  return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
134}
135
136