LiveRangeEdit.cpp Source File (original) (raw)

23using namespace llvm;

25#define DEBUG_TYPE "regalloc"

27 STATISTIC(NumDCEDeleted, "Number of instructions deleted by DCE");

28 STATISTIC(NumDCEFoldedLoads, "Number of single use loads folded after DCE");

29 STATISTIC(NumFracRanges, "Number of live ranges fractured by DCE");

30 STATISTIC(NumReMaterialization, "Number of instructions rematerialized");

32void LiveRangeEdit::Delegate::anchor() { }

34LiveInterval &LiveRangeEdit::createEmptyIntervalFrom(Register OldReg,

35 bool createSubRanges) {

36 Register VReg = MRI.cloneVirtualRegister(OldReg);

37 if (VRM)

38 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));

40 LiveInterval &LI = LIS.createEmptyInterval(VReg);

41 if (Parent && !Parent->isSpillable())

43 if (createSubRanges) {

47 LiveInterval &OldLI = LIS.getInterval(OldReg);

49 for (LiveInterval::SubRange &S : OldLI.subranges())

51 }

52 return LI;

53}

56 Register VReg = MRI.cloneVirtualRegister(OldReg);

57 if (VRM) {

58 VRM->setIsSplitFromReg(VReg, VRM->getOriginal(OldReg));

59 }

66 if (Parent && !Parent->isSpillable())

67 LIS.getInterval(VReg).markNotSpillable();

68 return VReg;

69}

72 assert(RM.OrigMI && "No defining instruction for remattable value");

74 if (!TII.isReMaterializable(*RM.OrigMI))

75 return false;

79 return false;

81 return true;

82}

88 bool Late, unsigned SubIdx,

90 assert(RM.OrigMI && "Invalid remat");

91 TII.reMaterialize(MBB, MI, DestReg, SubIdx, *RM.OrigMI);

95 (*--MI).clearRegisterDeads(DestReg);

96 Rematted.insert(RM.ParentVNI);

97 ++NumReMaterialization;

99 bool EarlyClobber = MI->getOperand(0).isEarlyClobber();

100 if (ReplaceIndexMI)

101 return LIS.ReplaceMachineInstrInMaps(*ReplaceIndexMI, *MI)

102 .getRegSlot(EarlyClobber);

103 return LIS.getSlotIndexes()->insertMachineInstrInMaps(*MI, Late).getRegSlot(

104 EarlyClobber);

105}

106

108 if (TheDelegate && TheDelegate->LRE_CanEraseVirtReg(Reg))

109 LIS.removeInterval(Reg);

110}

111

112bool LiveRangeEdit::foldAsLoad(LiveInterval *LI,

115

116

119 if (MO.isDef()) {

121 return false;

122 if (->canFoldAsLoad())

123 return false;

125 } else if (!MO.isUndef()) {

127 return false;

128

129 if (MO.getSubReg())

130 return false;

132 }

133 }

135 return false;

136

137

138

140 DefMI, LIS.getInstructionIndex(*UseMI), LIS, MRI, TII))

141 return false;

142

143

144

145 bool SawStore = true;

147 return false;

148

150 << " into single use: " << *UseMI);

151

152 SmallVector<unsigned, 8> Ops;

154 return false;

155

156 MachineInstr *FoldMI = TII.foldMemoryOperand(*UseMI, Ops, *DefMI, &LIS);

157 if (!FoldMI)

158 return false;

160 LIS.ReplaceMachineInstrInMaps(*UseMI, *FoldMI);

161

167 ++NumDCEFoldedLoads;

168 return true;

169}

170

171bool LiveRangeEdit::useIsKill(const LiveInterval &LI,

172 const MachineOperand &MO) const {

173 const MachineInstr &MI = *MO.getParent();

174 SlotIndex Idx = LIS.getInstructionIndex(MI).getRegSlot();

176 return true;

177 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();

179 LaneBitmask LaneMask = TRI.getSubRegIndexLaneMask(SubReg);

180 for (const LiveInterval::SubRange &S : LI.subranges()) {

181 if ((S.LaneMask & LaneMask).any() && S.Query(Idx).isKill())

182 return true;

183 }

184 return false;

185}

186

187

188void LiveRangeEdit::eliminateDeadDef(MachineInstr *MI, ToShrinkSet &ToShrink) {

189 assert(MI->allDefsAreDead() && "Def isn't really dead");

190 SlotIndex Idx = LIS.getInstructionIndex(*MI).getRegSlot();

191

192

193 if (MI->isBundled()) {

194

195 LLVM_DEBUG(dbgs() << "Won't delete dead bundled inst: " << Idx << '\t'

196 << *MI);

197 return;

198 }

199

200

201 if (MI->isInlineAsm()) {

202 LLVM_DEBUG(dbgs() << "Won't delete: " << Idx << '\t' << *MI);

203 return;

204 }

205

206

207 bool SawStore = false;

208 if (->isSafeToMove(SawStore)) {

209 LLVM_DEBUG(dbgs() << "Can't delete: " << Idx << '\t' << *MI);

210 return;

211 }

212

213 LLVM_DEBUG(dbgs() << "Deleting dead def " << Idx << '\t' << *MI);

214

215

217 bool ReadsPhysRegs = false;

218 bool isOrigDef = false;

220 unsigned DestSubReg;

221

222

223

224 if (VRM && MI->getOperand(0).isReg() && MI->getOperand(0).isDef() &&

225 MI->getDesc().getNumDefs() == 1) {

226 Dest = MI->getOperand(0).getReg();

227 DestSubReg = MI->getOperand(0).getSubReg();

228 Register Original = VRM->getOriginal(Dest);

229 LiveInterval &OrigLI = LIS.getInterval(Original);

230 VNInfo *OrigVNI = OrigLI.getVNInfoAt(Idx);

231

232

233

234

235 if (OrigVNI)

237 }

238

239 bool HasLiveVRegUses = false;

240

241

242 for (const MachineOperand &MO : MI->operands()) {

244 continue;

247

249 ReadsPhysRegs = true;

250 else if (MO.isDef())

251 LIS.removePhysRegDefAt(Reg.asMCReg(), Idx);

252 continue;

253 }

254 LiveInterval &LI = LIS.getInterval(Reg);

255

256

257

258

259

260 if ((MI->readsVirtualRegister(Reg) &&

261 (MO.isDef() || TII.isCopyInstr(*MI))) ||

262 (MO.readsReg() && (MRI.hasOneNonDBGUse(Reg) || useIsKill(LI, MO))))

263 ToShrink.insert(&LI);

265 HasLiveVRegUses = true;

266

267

268 if (MO.isDef()) {

269 if (TheDelegate && LI.getVNInfoAt(Idx) != nullptr)

270 TheDelegate->LRE_WillShrinkVirtReg(LI.reg());

271 LIS.removeVRegDefAt(LI, Idx);

274 }

275 }

276

277

278

279

280

281

282

283

284

285

286

287 if (isOrigDef && DeadRemats && !HasLiveVRegUses &&

288 TII.isReMaterializable(*MI)) {

289 LiveInterval &NewLI = createEmptyIntervalFrom(Dest, false);

293

294 if (DestSubReg) {

295 const TargetRegisterInfo *TRI = MRI.getTargetRegisterInfo();

296 auto *SR =

299 SR->getNextValue(Idx, Alloc)));

300 }

301

303 DeadRemats->insert(MI);

304 const TargetRegisterInfo &TRI = *MRI.getTargetRegisterInfo();

305 MI->substituteRegister(Dest, NewLI.reg(), 0, TRI);

307 }

308

309

310

311

312

313

314

315 else if (ReadsPhysRegs) {

316 MI->setDesc(TII.get(TargetOpcode::KILL));

317

318 for (unsigned i = MI->getNumOperands(); i; --i) {

319 const MachineOperand &MO = MI->getOperand(i-1);

321 continue;

322 MI->removeOperand(i-1);

323 }

324 MI->dropMemRefs(*MI->getMF());

326 } else {

327 if (TheDelegate)

328 TheDelegate->LRE_WillEraseInstruction(MI);

329 LIS.RemoveMachineInstrFromMaps(*MI);

330 MI->eraseFromParent();

331 ++NumDCEDeleted;

332 }

333

334

335

337 if (LIS.hasInterval(Reg) && MRI.reg_nodbg_empty(Reg)) {

338 ToShrink.remove(&LIS.getInterval(Reg));

340 }

341 }

342}

343

346 ToShrinkSet ToShrink;

347

348 for (;;) {

349

350 while (!Dead.empty())

351 eliminateDeadDef(Dead.pop_back_val(), ToShrink);

352

353 if (ToShrink.empty())

354 break;

355

356

358 if (foldAsLoad(LI, Dead))

359 continue;

361 if (TheDelegate)

362 TheDelegate->LRE_WillShrinkVirtReg(VReg);

363 if (!LIS.shrinkToUses(LI, &Dead))

364 continue;

365

366

367

368

369

371 continue;

372

373

376 LIS.splitSeparateComponents(*LI, SplitLIs);

377 if (!SplitLIs.empty())

378 ++NumFracRanges;

379

380 Register Original = VRM ? VRM->getOriginal(VReg) : Register();

381 for (const LiveInterval *SplitLI : SplitLIs) {

382

383

384

385 if (Original != VReg && Original != 0)

386 VRM->setIsSplitFromReg(SplitLI->reg(), Original);

387 if (TheDelegate)

388 TheDelegate->LRE_DidCloneVirtReg(SplitLI->reg(), VReg);

389 }

390 }

391}

392

393

394

395void

396LiveRangeEdit::MRI_NoteNewVirtualRegister(Register VReg) {

397 if (VRM)

399

400 NewRegs.push_back(VReg);

401}

402

407 if (MRI.recomputeRegClass(LI.reg()))

411 << TRI->getRegClassName(MRI.getRegClass(LI.reg())) << '\n';

412 });

414 }

415}

unsigned const MachineRegisterInfo * MRI

MachineInstrBuilder & UseMI

MachineInstrBuilder MachineInstrBuilder & DefMI

assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")

const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]

Promote Memory to Register

This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...

#define STATISTIC(VARNAME, DESC)

ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...

LiveInterval - This class represents the liveness of a register, or stack slot.

void markNotSpillable()

markNotSpillable - Mark interval as not spillable

iterator_range< subrange_iterator > subranges()

SubRange * createSubRange(BumpPtrAllocator &Allocator, LaneBitmask LaneMask)

Creates a new empty subregister live range.

bool isKill() const

Return true if the live-in value is killed by this instruction.

void eraseVirtReg(Register Reg)

eraseVirtReg - Notify the delegate that Reg is no longer in use, and try to erase it from LIS.

Definition LiveRangeEdit.cpp:107

createFrom - Create a new virtual register based on OldReg.

Definition LiveRangeEdit.cpp:55

void calculateRegClassAndHint(MachineFunction &, VirtRegAuxInfo &)

calculateRegClassAndHint - Recompute register class and hint for each new register.

Definition LiveRangeEdit.cpp:403

bool canRematerializeAt(Remat &RM, SlotIndex UseIdx)

canRematerializeAt - Determine if RM.Orig can be rematerialized at UseIdx.

Definition LiveRangeEdit.cpp:71

SlotIndex rematerializeAt(MachineBasicBlock &MBB, MachineBasicBlock::iterator MI, Register DestReg, const Remat &RM, const TargetRegisterInfo &, bool Late=false, unsigned SubIdx=0, MachineInstr *ReplaceIndexMI=nullptr)

rematerializeAt - Rematerialize RM.ParentVNI into DestReg by inserting an instruction into MBB before...

Definition LiveRangeEdit.cpp:84

void eliminateDeadDefs(SmallVectorImpl< MachineInstr * > &Dead, ArrayRef< Register > RegsBeingSpilled={})

eliminateDeadDefs - Try to delete machine instructions that are now dead (allDefsAreDead returns true...

Definition LiveRangeEdit.cpp:344

void pop_back()

pop_back - It allows LiveRangeEdit users to drop new registers.

LLVM_ABI iterator addSegment(Segment S)

Add the specified Segment to this range, merging segments as appropriate.

LLVM_ABI void RenumberValues()

RenumberValues - Renumber all values in order of appearance and remove unused values.

LiveQueryResult Query(SlotIndex Idx) const

Query Liveness at Idx.

VNInfo * getNextValue(SlotIndex Def, VNInfo::Allocator &VNInfoAllocator)

getNextValue - Create a new value number and return it.

VNInfo * getVNInfoAt(SlotIndex Idx) const

getVNInfoAt - Return the VNInfo that is live at Idx, or NULL.

MachineInstrBundleIterator< MachineInstr > iterator

void moveAdditionalCallInfo(const MachineInstr *Old, const MachineInstr *New)

Move the call site info from Old to \New call site info.

const TargetSubtargetInfo & getSubtarget() const

getSubtarget - Return the subtarget for which this machine code is being compiled.

Representation of each machine instruction.

LLVM_ABI std::pair< bool, bool > readsWritesVirtualRegister(Register Reg, SmallVectorImpl< unsigned > *Ops=nullptr) const

Return a pair of bools (reads, writes) indicating if this instruction reads or writes Reg.

LLVM_ABI bool isSafeToMove(bool &SawStore) const

Return true if it is safe to move this instruction.

LLVM_ABI const MachineFunction * getMF() const

Return the function that contains the basic block that this instruction belongs to.

LLVM_ABI void eraseFromParent()

Unlink 'this' from the containing basic block and delete it.

LLVM_ABI bool shouldUpdateAdditionalCallInfo() const

Return true if copying, moving, or erasing this instruction requires updating additional call info (s...

LLVM_ABI bool addRegisterDead(Register Reg, const TargetRegisterInfo *RegInfo, bool AddIfNotFound=false)

We have determined MI defined a register without a use.

MachineOperand class - Representation of each machine instruction operand.

unsigned getSubReg() const

bool readsReg() const

readsReg - Returns true if this operand reads the previous value of its register.

bool isReg() const

isReg - Tests if this is a MO_Register operand.

MachineInstr * getParent()

getParent - Return the instruction that this operand belongs to.

getReg - Returns the register number.

Wrapper class representing virtual and physical registers.

MCRegister asMCReg() const

Utility to check-convert this value to a MCRegister.

constexpr bool isVirtual() const

Return true if the specified register number is in the virtual register namespace.

constexpr bool isPhysical() const

Return true if the specified register number is in the physical register namespace.

bool empty() const

Determine if the SetVector is empty or not.

value_type pop_back_val()

SlotIndex - An opaque wrapper around machine indexes.

static bool isSameInstr(SlotIndex A, SlotIndex B)

isSameInstr - Return true if A and B refer to the same instruction.

SlotIndex getDeadSlot() const

Returns the dead def kill slot for the current instruction.

SlotIndex getRegSlot(bool EC=false) const

Returns the register use/def slot in the current instruction for a normal or early-clobber def.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

void push_back(const T &Elt)

This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.

TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...

virtual const TargetRegisterInfo * getRegisterInfo() const =0

Return the target's register information.

BumpPtrAllocator Allocator

SlotIndex def

The index of the defining instruction.

Calculate auxiliary information for a virtual register such as its spill weight and allocation hint.

static bool allUsesAvailableAt(const MachineInstr *MI, SlotIndex UseIdx, const LiveIntervals &LIS, const MachineRegisterInfo &MRI, const TargetInstrInfo &TII)

void calculateSpillWeightAndHint(LiveInterval &LI)

(re)compute li's spill weight and allocation hint.

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI raw_ostream & dbgs()

dbgs() - This returns a reference to a raw_ostream for debugging messages.

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool is_contained(R &&Range, const E &Element)

Returns true if Element is found in Range.

LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)

Prints virtual and physical registers with or without a TRI instance.

Remat - Information needed to rematerialize at a specific location.