LiveRangeEdit.cpp revision d96c9853192af2baea0d164228582f1dac8efbf2 
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
22int 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
29LiveInterval &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
42void 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
59bool 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.
69bool 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
100LiveRangeEdit::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
132SlotIndex 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  return lis.InsertMachineInstrInMaps(--MI).getDefIndex();
142}
143
144