RewriteStatepointsForGC.cpp

1//===- RewriteStatepointsForGC.cpp - Make GC relocations explicit ---------===//

2//

3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

4// See https://llvm.org/LICENSE.txt for license information.

5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

6//

7//===----------------------------------------------------------------------===//

8//

9// Rewrite call/invoke instructions so as to make potential relocations

10// performed by the garbage collector explicit in the IR.

11//

12//===----------------------------------------------------------------------===//

13

14#include "llvm/Transforms/Scalar/RewriteStatepointsForGC.h"

15

16#include "llvm/ADT/ArrayRef.h"

17#include "llvm/ADT/DenseMap.h"

18#include "llvm/ADT/DenseSet.h"

19#include "llvm/ADT/MapVector.h"

20#include "llvm/ADT/STLExtras.h"

21#include "llvm/ADT/Sequence.h"

22#include "llvm/ADT/SetVector.h"

23#include "llvm/ADT/SmallVector.h"

24#include "llvm/ADT/StringRef.h"

25#include "llvm/ADT/iterator_range.h"

26#include "llvm/Analysis/DomTreeUpdater.h"

27#include "llvm/Analysis/TargetLibraryInfo.h"

28#include "llvm/Analysis/TargetTransformInfo.h"

29#include "llvm/IR/Argument.h"

30#include "llvm/IR/AttributeMask.h"

31#include "llvm/IR/Attributes.h"

32#include "llvm/IR/BasicBlock.h"

33#include "llvm/IR/CallingConv.h"

34#include "llvm/IR/Constant.h"

35#include "llvm/IR/Constants.h"

36#include "llvm/IR/DataLayout.h"

37#include "llvm/IR/DerivedTypes.h"

38#include "llvm/IR/Dominators.h"

39#include "llvm/IR/Function.h"

40#include "llvm/IR/GCStrategy.h"

41#include "llvm/IR/IRBuilder.h"

42#include "llvm/IR/InstIterator.h"

43#include "llvm/IR/InstrTypes.h"

44#include "llvm/IR/Instruction.h"

45#include "llvm/IR/Instructions.h"

46#include "llvm/IR/IntrinsicInst.h"

47#include "llvm/IR/Intrinsics.h"

48#include "llvm/IR/LLVMContext.h"

49#include "llvm/IR/MDBuilder.h"

50#include "llvm/IR/Metadata.h"

51#include "llvm/IR/Module.h"

52#include "llvm/IR/Statepoint.h"

53#include "llvm/IR/Type.h"

54#include "llvm/IR/User.h"

55#include "llvm/IR/Value.h"

56#include "llvm/IR/ValueHandle.h"

57#include "llvm/Support/Casting.h"

58#include "llvm/Support/CommandLine.h"

59#include "llvm/Support/Compiler.h"

60#include "llvm/Support/Debug.h"

61#include "llvm/Support/ErrorHandling.h"

62#include "llvm/Support/raw_ostream.h"

63#include "llvm/Transforms/Utils/BasicBlockUtils.h"

64#include "llvm/Transforms/Utils/Local.h"

65#include "llvm/Transforms/Utils/PromoteMemToReg.h"

66#include <cassert>

67#include <cstddef>

68#include <cstdint>

69#include <iterator>

70#include <optional>

71#include <set>

72#include <string>

73#include <utility>

74#include <vector>

75

76 #define DEBUG_TYPE "rewrite-statepoints-for-gc"

77

78using namespace llvm;

79

80// Print the liveset found at the insert location

81 static cl::opt<bool> PrintLiveSet("spp-print-liveset", cl::Hidden,

82 cl::init(false));

83 static cl::opt<bool> PrintLiveSetSize("spp-print-liveset-size", cl::Hidden,

84 cl::init(false));

85

86// Print out the base pointers for debugging

87 static cl::opt<bool> PrintBasePointers("spp-print-base-pointers", cl::Hidden,

88 cl::init(false));

89

90// Cost threshold measuring when it is profitable to rematerialize value instead

91// of relocating it

92static cl::opt<unsigned>

93 RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden,

94 cl::init(6));

95

96#ifdef EXPENSIVE_CHECKS

97static bool ClobberNonLive = true;

98#else

99 static bool ClobberNonLive = false;

100#endif

101

102 static cl::opt<bool, true> ClobberNonLiveOverride("rs4gc-clobber-non-live",

103 cl::location(ClobberNonLive),

104 cl::Hidden);

105

106static cl::opt<bool>

107 AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info",

108 cl::Hidden, cl::init(true));

109

110 static cl::opt<bool> RematDerivedAtUses("rs4gc-remat-derived-at-uses",

111 cl::Hidden, cl::init(true));

112

113/// The IR fed into RewriteStatepointsForGC may have had attributes and

114/// metadata implying dereferenceability that are no longer valid/correct after

115/// RewriteStatepointsForGC has run. This is because semantically, after

116/// RewriteStatepointsForGC runs, all calls to gc.statepoint "free" the entire

117/// heap. stripNonValidData (conservatively) restores

118/// correctness by erasing all attributes in the module that externally imply

119/// dereferenceability. Similar reasoning also applies to the noalias

120/// attributes and metadata. gc.statepoint can touch the entire heap including

121/// noalias objects.

122/// Apart from attributes and metadata, we also remove instructions that imply

123/// constant physical memory: llvm.invariant.start.

124static void stripNonValidData(Module &M);

125

126// Find the GC strategy for a function, or null if it doesn't have one.

127static std::unique_ptr<GCStrategy> findGCStrategy(Function &F);

128

129static bool shouldRewriteStatepointsIn(Function &F);

130

131 PreservedAnalyses RewriteStatepointsForGC::run(Module &M,

132 ModuleAnalysisManager &AM) {

133 bool Changed = false;

134 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();

135 for (Function &F : M) {

136 // Nothing to do for declarations.

137 if (F.isDeclaration() || F.empty())

138 continue;

139

140 // Policy choice says not to rewrite - the most common reason is that we're

141 // compiling code without a GCStrategy.

142 if (!shouldRewriteStatepointsIn(F))

143 continue;

144

145 auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);

146 auto &TTI = FAM.getResult<TargetIRAnalysis>(F);

147 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);

148 Changed |= runOnFunction(F, DT, TTI, TLI);

149 }

150 if (!Changed)

151 return PreservedAnalyses::all();

152

153 // stripNonValidData asserts that shouldRewriteStatepointsIn

154 // returns true for at least one function in the module. Since at least

155 // one function changed, we know that the precondition is satisfied.

156 stripNonValidData(M);

157

158 PreservedAnalyses PA;

159 PA.preserve<TargetIRAnalysis>();

160 PA.preserve<TargetLibraryAnalysis>();

161 return PA;

162}

163

164namespace {

165

166struct GCPtrLivenessData {

167 /// Values defined in this block.

168 MapVector<BasicBlock *, SetVector<Value *>> KillSet;

169

170 /// Values used in this block (and thus live); does not included values

171 /// killed within this block.

172 MapVector<BasicBlock *, SetVector<Value *>> LiveSet;

173

174 /// Values live into this basic block (i.e. used by any

175 /// instruction in this basic block or ones reachable from here)

176 MapVector<BasicBlock *, SetVector<Value *>> LiveIn;

177

178 /// Values live out of this basic block (i.e. live into

179 /// any successor block)

180 MapVector<BasicBlock *, SetVector<Value *>> LiveOut;

181};

182

183// The type of the internal cache used inside the findBasePointers family

184// of functions. From the callers perspective, this is an opaque type and

185// should not be inspected.

186//

187// In the actual implementation this caches two relations:

188// - The base relation itself (i.e. this pointer is based on that one)

189// - The base defining value relation (i.e. before base_phi insertion)

190// Generally, after the execution of a full findBasePointer call, only the

191// base relation will remain. Internally, we add a mixture of the two

192// types, then update all the second type to the first type

193using DefiningValueMapTy = MapVector<Value *, Value *>;

194using IsKnownBaseMapTy = MapVector<Value *, bool>;

195using PointerToBaseTy = MapVector<Value *, Value *>;

196using StatepointLiveSetTy = SetVector<Value *>;

197using RematerializedValueMapTy =

198 MapVector<AssertingVH<Instruction>, AssertingVH<Value>>;

199

200struct PartiallyConstructedSafepointRecord {

201 /// The set of values known to be live across this safepoint

202 StatepointLiveSetTy LiveSet;

203

204 /// The *new* gc.statepoint instruction itself. This produces the token

205 /// that normal path gc.relocates and the gc.result are tied to.

206 GCStatepointInst *StatepointToken;

207

208 /// Instruction to which exceptional gc relocates are attached

209 /// Makes it easier to iterate through them during relocationViaAlloca.

210 Instruction *UnwindToken;

211

212 /// Record live values we are rematerialized instead of relocating.

213 /// They are not included into 'LiveSet' field.

214 /// Maps rematerialized copy to it's original value.

215 RematerializedValueMapTy RematerializedValues;

216};

217

218struct RematerizlizationCandidateRecord {

219 // Chain from derived pointer to base.

220 SmallVector<Instruction *, 3> ChainToBase;

221 // Original base.

222 Value *RootOfChain;

223 // Cost of chain.

224 InstructionCost Cost;

225};

226using RematCandTy = MapVector<Value *, RematerizlizationCandidateRecord>;

227

228} // end anonymous namespace

229

230 static ArrayRef<Use> GetDeoptBundleOperands(const CallBase *Call) {

231 std::optional<OperandBundleUse> DeoptBundle =

232 Call->getOperandBundle(LLVMContext::OB_deopt);

233

234 if (!DeoptBundle) {

235 assert(AllowStatepointWithNoDeoptInfo &&

236 "Found non-leaf call without deopt info!");

237 return {};

238 }

239

240 return DeoptBundle->Inputs;

241}

242

243/// Compute the live-in set for every basic block in the function

244static void computeLiveInValues(DominatorTree &DT, Function &F,

245 GCPtrLivenessData &Data, GCStrategy *GC);

246

247/// Given results from the dataflow liveness computation, find the set of live

248/// Values at a particular instruction.

249static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data,

250 StatepointLiveSetTy &out, GCStrategy *GC);

251

252 static bool isGCPointerType(Type *T, GCStrategy *GC) {

253 assert(GC && "GC Strategy for isGCPointerType cannot be null");

254

255 if (!isa<PointerType>(T))

256 return false;

257

258 // conservative - same as StatepointLowering

259 return GC->isGCManagedPointer(T).value_or(true);

260}

261

262// Return true if this type is one which a) is a gc pointer or contains a GC

263// pointer and b) is of a type this code expects to encounter as a live value.

264// (The insertion code will assert that a type which matches (a) and not (b)

265// is not encountered.)

266 static bool isHandledGCPointerType(Type *T, GCStrategy *GC) {

267 // We fully support gc pointers

268 if (isGCPointerType(T, GC))

269 return true;

270 // We partially support vectors of gc pointers. The code will assert if it

271 // can't handle something.

272 if (auto VT = dyn_cast<VectorType>(T))

273 if (isGCPointerType(VT->getElementType(), GC))

274 return true;

275 return false;

276}

277

278#ifndef NDEBUG

279/// Returns true if this type contains a gc pointer whether we know how to

280/// handle that type or not.

281 static bool containsGCPtrType(Type *Ty, GCStrategy *GC) {

282 if (isGCPointerType(Ty, GC))

283 return true;

284 if (VectorType *VT = dyn_cast<VectorType>(Ty))

285 return isGCPointerType(VT->getScalarType(), GC);

286 if (ArrayType *AT = dyn_cast<ArrayType>(Ty))

287 return containsGCPtrType(AT->getElementType(), GC);

288 if (StructType *ST = dyn_cast<StructType>(Ty))

289 return llvm::any_of(ST->elements(),

290 [GC](Type *Ty) { return containsGCPtrType(Ty, GC); });

291 return false;

292}

293

294// Returns true if this is a type which a) is a gc pointer or contains a GC

295// pointer and b) is of a type which the code doesn't expect (i.e. first class

296// aggregates). Used to trip assertions.

297 static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC) {

298 return containsGCPtrType(Ty, GC) && !isHandledGCPointerType(Ty, GC);

299}

300#endif

301

302// Return the name of the value suffixed with the provided value, or if the

303// value didn't have a name, the default value specified.

304 static std::string suffixed_name_or(Value *V, StringRef Suffix,

305 StringRef DefaultName) {

306 return V->hasName() ? (V->getName() + Suffix).str() : DefaultName.str();

307}

308

309// Conservatively identifies any definitions which might be live at the

310// given instruction. The analysis is performed immediately before the

311// given instruction. Values defined by that instruction are not considered

312// live. Values used by that instruction are considered live.

313 static void analyzeParsePointLiveness(

314 DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call,

315 PartiallyConstructedSafepointRecord &Result, GCStrategy *GC) {

316 StatepointLiveSetTy LiveSet;

317 findLiveSetAtInst(Call, OriginalLivenessData, LiveSet, GC);

318

319 if (PrintLiveSet) {

320 dbgs() << "Live Variables:\n";

321 for (Value *V : LiveSet)

322 dbgs() << " " << V->getName() << " " << *V << "\n";

323 }

324 if (PrintLiveSetSize) {

325 dbgs() << "Safepoint For: " << Call->getCalledOperand()->getName() << "\n";

326 dbgs() << "Number live values: " << LiveSet.size() << "\n";

327 }

328 Result.LiveSet = LiveSet;

329}

330

331/// Returns true if V is a known base.

332static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases);

333

334/// Caches the IsKnownBase flag for a value and asserts that it wasn't present

335/// in the cache before.

336static void setKnownBase(Value *V, bool IsKnownBase,

337 IsKnownBaseMapTy &KnownBases);

338

339static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache,

340 IsKnownBaseMapTy &KnownBases);

341

342/// Return a base defining value for the 'Index' element of the given vector

343/// instruction 'I'. If Index is null, returns a BDV for the entire vector

344/// 'I'. As an optimization, this method will try to determine when the

345/// element is known to already be a base pointer. If this can be established,

346/// the second value in the returned pair will be true. Note that either a

347/// vector or a pointer typed value can be returned. For the former, the

348/// vector returned is a BDV (and possibly a base) of the entire vector 'I'.

349/// If the later, the return pointer is a BDV (or possibly a base) for the

350/// particular element in 'I'.

351 static Value *findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache,

352 IsKnownBaseMapTy &KnownBases) {

353 // Each case parallels findBaseDefiningValue below, see that code for

354 // detailed motivation.

355

356 auto Cached = Cache.find(I);

357 if (Cached != Cache.end())

358 return Cached->second;

359

360 if (isa<Argument>(I)) {

361 // An incoming argument to the function is a base pointer

362 Cache[I] = I;

363 setKnownBase(I, /* IsKnownBase */true, KnownBases);

364 return I;

365 }

366

367 if (isa<Constant>(I)) {

368 // Base of constant vector consists only of constant null pointers.

369 // For reasoning see similar case inside 'findBaseDefiningValue' function.

370 auto *CAZ = ConstantAggregateZero::get(I->getType());

371 Cache[I] = CAZ;

372 setKnownBase(CAZ, /* IsKnownBase */true, KnownBases);

373 return CAZ;

374 }

375

376 if (isa<LoadInst>(I)) {

377 Cache[I] = I;

378 setKnownBase(I, /* IsKnownBase */true, KnownBases);

379 return I;

380 }

381

382 if (isa<InsertElementInst>(I)) {

383 // We don't know whether this vector contains entirely base pointers or

384 // not. To be conservatively correct, we treat it as a BDV and will

385 // duplicate code as needed to construct a parallel vector of bases.

386 Cache[I] = I;

387 setKnownBase(I, /* IsKnownBase */false, KnownBases);

388 return I;

389 }

390

391 if (isa<ShuffleVectorInst>(I)) {

392 // We don't know whether this vector contains entirely base pointers or

393 // not. To be conservatively correct, we treat it as a BDV and will

394 // duplicate code as needed to construct a parallel vector of bases.

395 // TODO: There a number of local optimizations which could be applied here

396 // for particular sufflevector patterns.

397 Cache[I] = I;

398 setKnownBase(I, /* IsKnownBase */false, KnownBases);

399 return I;

400 }

401

402 // The behavior of getelementptr instructions is the same for vector and

403 // non-vector data types.

404 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {

405 auto *BDV =

406 findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);

407 Cache[GEP] = BDV;

408 return BDV;

409 }

410

411 // The behavior of freeze instructions is the same for vector and

412 // non-vector data types.

413 if (auto *Freeze = dyn_cast<FreezeInst>(I)) {

414 auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);

415 Cache[Freeze] = BDV;

416 return BDV;

417 }

418

419 // If the pointer comes through a bitcast of a vector of pointers to

420 // a vector of another type of pointer, then look through the bitcast

421 if (auto *BC = dyn_cast<BitCastInst>(I)) {

422 auto *BDV = findBaseDefiningValue(BC->getOperand(0), Cache, KnownBases);

423 Cache[BC] = BDV;

424 return BDV;

425 }

426

427 // We assume that functions in the source language only return base

428 // pointers. This should probably be generalized via attributes to support

429 // both source language and internal functions.

430 if (isa<CallInst>(I) || isa<InvokeInst>(I)) {

431 Cache[I] = I;

432 setKnownBase(I, /* IsKnownBase */true, KnownBases);

433 return I;

434 }

435

436 // A PHI or Select is a base defining value. The outer findBasePointer

437 // algorithm is responsible for constructing a base value for this BDV.

438 assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&

439 "unknown vector instruction - no base found for vector element");

440 Cache[I] = I;

441 setKnownBase(I, /* IsKnownBase */false, KnownBases);

442 return I;

443}

444

445/// Helper function for findBasePointer - Will return a value which either a)

446/// defines the base pointer for the input, b) blocks the simple search

447/// (i.e. a PHI or Select of two derived pointers), or c) involves a change

448/// from pointer to vector type or back.

449 static Value *findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache,

450 IsKnownBaseMapTy &KnownBases) {

451 assert(I->getType()->isPtrOrPtrVectorTy() &&

452 "Illegal to ask for the base pointer of a non-pointer type");

453 auto Cached = Cache.find(I);

454 if (Cached != Cache.end())

455 return Cached->second;

456

457 if (I->getType()->isVectorTy())

458 return findBaseDefiningValueOfVector(I, Cache, KnownBases);

459

460 if (isa<Argument>(I)) {

461 // An incoming argument to the function is a base pointer

462 // We should have never reached here if this argument isn't an gc value

463 Cache[I] = I;

464 setKnownBase(I, /* IsKnownBase */true, KnownBases);

465 return I;

466 }

467

468 if (isa<Constant>(I)) {

469 // We assume that objects with a constant base (e.g. a global) can't move

470 // and don't need to be reported to the collector because they are always

471 // live. Besides global references, all kinds of constants (e.g. undef,

472 // constant expressions, null pointers) can be introduced by the inliner or

473 // the optimizer, especially on dynamically dead paths.

474 // Here we treat all of them as having single null base. By doing this we

475 // trying to avoid problems reporting various conflicts in a form of

476 // "phi (const1, const2)" or "phi (const, regular gc ptr)".

477 // See constant.ll file for relevant test cases.

478

479 auto *CPN = ConstantPointerNull::get(cast<PointerType>(I->getType()));

480 Cache[I] = CPN;

481 setKnownBase(CPN, /* IsKnownBase */true, KnownBases);

482 return CPN;

483 }

484

485 // inttoptrs in an integral address space are currently ill-defined. We

486 // treat them as defining base pointers here for consistency with the

487 // constant rule above and because we don't really have a better semantic

488 // to give them. Note that the optimizer is always free to insert undefined

489 // behavior on dynamically dead paths as well.

490 if (isa<IntToPtrInst>(I)) {

491 Cache[I] = I;

492 setKnownBase(I, /* IsKnownBase */true, KnownBases);

493 return I;

494 }

495

496 if (CastInst *CI = dyn_cast<CastInst>(I)) {

497 Value *Def = CI->stripPointerCasts();

498 // If stripping pointer casts changes the address space there is an

499 // addrspacecast in between.

500 assert(cast<PointerType>(Def->getType())->getAddressSpace() ==

501 cast<PointerType>(CI->getType())->getAddressSpace() &&

502 "unsupported addrspacecast");

503 // If we find a cast instruction here, it means we've found a cast which is

504 // not simply a pointer cast (i.e. an inttoptr). We don't know how to

505 // handle int->ptr conversion.

506 assert(!isa<CastInst>(Def) && "shouldn't find another cast here");

507 auto *BDV = findBaseDefiningValue(Def, Cache, KnownBases);

508 Cache[CI] = BDV;

509 return BDV;

510 }

511

512 if (isa<LoadInst>(I)) {

513 // The value loaded is an gc base itself

514 Cache[I] = I;

515 setKnownBase(I, /* IsKnownBase */true, KnownBases);

516 return I;

517 }

518

519 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {

520 // The base of this GEP is the base

521 auto *BDV =

522 findBaseDefiningValue(GEP->getPointerOperand(), Cache, KnownBases);

523 Cache[GEP] = BDV;

524 return BDV;

525 }

526

527 if (auto *Freeze = dyn_cast<FreezeInst>(I)) {

528 auto *BDV = findBaseDefiningValue(Freeze->getOperand(0), Cache, KnownBases);

529 Cache[Freeze] = BDV;

530 return BDV;

531 }

532

533 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {

534 switch (II->getIntrinsicID()) {

535 default:

536 // fall through to general call handling

537 break;

538 case Intrinsic::experimental_gc_statepoint:

539 llvm_unreachable("statepoints don't produce pointers");

540 case Intrinsic::experimental_gc_relocate:

541 // Rerunning safepoint insertion after safepoints are already

542 // inserted is not supported. It could probably be made to work,

543 // but why are you doing this? There's no good reason.

544 llvm_unreachable("repeat safepoint insertion is not supported");

545 case Intrinsic::gcroot:

546 // Currently, this mechanism hasn't been extended to work with gcroot.

547 // There's no reason it couldn't be, but I haven't thought about the

548 // implications much.

549 llvm_unreachable(

550 "interaction with the gcroot mechanism is not supported");

551 case Intrinsic::experimental_gc_get_pointer_base:

552 auto *BDV = findBaseDefiningValue(II->getOperand(0), Cache, KnownBases);

553 Cache[II] = BDV;

554 return BDV;

555 }

556 }

557 // We assume that functions in the source language only return base

558 // pointers. This should probably be generalized via attributes to support

559 // both source language and internal functions.

560 if (isa<CallInst>(I) || isa<InvokeInst>(I)) {

561 Cache[I] = I;

562 setKnownBase(I, /* IsKnownBase */true, KnownBases);

563 return I;

564 }

565

566 // TODO: I have absolutely no idea how to implement this part yet. It's not

567 // necessarily hard, I just haven't really looked at it yet.

568 assert(!isa<LandingPadInst>(I) && "Landing Pad is unimplemented");

569

570 if (isa<AtomicCmpXchgInst>(I)) {

571 // A CAS is effectively a atomic store and load combined under a

572 // predicate. From the perspective of base pointers, we just treat it

573 // like a load.

574 Cache[I] = I;

575 setKnownBase(I, /* IsKnownBase */true, KnownBases);

576 return I;

577 }

578

579 if (isa<AtomicRMWInst>(I)) {

580 assert(cast<AtomicRMWInst>(I)->getOperation() == AtomicRMWInst::Xchg &&

581 "Only Xchg is allowed for pointer values");

582 // A RMW Xchg is a combined atomic load and store, so we can treat the

583 // loaded value as a base pointer.

584 Cache[I] = I;

585 setKnownBase(I, /* IsKnownBase */ true, KnownBases);

586 return I;

587 }

588

589 // The aggregate ops. Aggregates can either be in the heap or on the

590 // stack, but in either case, this is simply a field load. As a result,

591 // this is a defining definition of the base just like a load is.

592 if (isa<ExtractValueInst>(I)) {

593 Cache[I] = I;

594 setKnownBase(I, /* IsKnownBase */true, KnownBases);

595 return I;

596 }

597

598 // We should never see an insert vector since that would require we be

599 // tracing back a struct value not a pointer value.

600 assert(!isa<InsertValueInst>(I) &&

601 "Base pointer for a struct is meaningless");

602

603 // This value might have been generated by findBasePointer() called when

604 // substituting gc.get.pointer.base() intrinsic.

605 bool IsKnownBase =

606 isa<Instruction>(I) && cast<Instruction>(I)->getMetadata("is_base_value");

607 setKnownBase(I, /* IsKnownBase */IsKnownBase, KnownBases);

608 Cache[I] = I;

609

610 // An extractelement produces a base result exactly when it's input does.

611 // We may need to insert a parallel instruction to extract the appropriate

612 // element out of the base vector corresponding to the input. Given this,

613 // it's analogous to the phi and select case even though it's not a merge.

614 if (isa<ExtractElementInst>(I))

615 // Note: There a lot of obvious peephole cases here. This are deliberately

616 // handled after the main base pointer inference algorithm to make writing

617 // test cases to exercise that code easier.

618 return I;

619

620 // The last two cases here don't return a base pointer. Instead, they

621 // return a value which dynamically selects from among several base

622 // derived pointers (each with it's own base potentially). It's the job of

623 // the caller to resolve these.

624 assert((isa<SelectInst>(I) || isa<PHINode>(I)) &&

625 "missing instruction case in findBaseDefiningValue");

626 return I;

627}

628

629/// Returns the base defining value for this value.

630 static Value *findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache,

631 IsKnownBaseMapTy &KnownBases) {

632 if (!Cache.contains(I)) {

633 auto *BDV = findBaseDefiningValue(I, Cache, KnownBases);

634 Cache[I] = BDV;

635 LLVM_DEBUG(dbgs() << "fBDV-cached: " << I->getName() << " -> "

636 << Cache[I]->getName() << ", is known base = "

637 << KnownBases[I] << "\n");

638 }

639 assert(Cache[I] != nullptr);

640 assert(KnownBases.contains(Cache[I]) &&

641 "Cached value must be present in known bases map");

642 return Cache[I];

643}

644

645/// Return a base pointer for this value if known. Otherwise, return it's

646/// base defining value.

647 static Value *findBaseOrBDV(Value *I, DefiningValueMapTy &Cache,

648 IsKnownBaseMapTy &KnownBases) {

649 Value *Def = findBaseDefiningValueCached(I, Cache, KnownBases);

650 auto Found = Cache.find(Def);

651 if (Found != Cache.end()) {

652 // Either a base-of relation, or a self reference. Caller must check.

653 return Found->second;

654 }

655 // Only a BDV available

656 return Def;

657}

658

659#ifndef NDEBUG

660/// This value is a base pointer that is not generated by RS4GC, i.e. it already

661/// exists in the code.

662 static bool isOriginalBaseResult(Value *V) {

663 // no recursion possible

664 return !isa<PHINode>(V) && !isa<SelectInst>(V) &&

665 !isa<ExtractElementInst>(V) && !isa<InsertElementInst>(V) &&

666 !isa<ShuffleVectorInst>(V);

667}

668#endif

669

670 static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases) {

671 auto It = KnownBases.find(V);

672 assert(It != KnownBases.end() && "Value not present in the map");

673 return It->second;

674}

675

676 static void setKnownBase(Value *V, bool IsKnownBase,

677 IsKnownBaseMapTy &KnownBases) {

678#ifndef NDEBUG

679 auto It = KnownBases.find(V);

680 if (It != KnownBases.end())

681 assert(It->second == IsKnownBase && "Changing already present value");

682#endif

683 KnownBases[V] = IsKnownBase;

684}

685

686// Returns true if First and Second values are both scalar or both vector.

687 static bool areBothVectorOrScalar(Value *First, Value *Second) {

688 return isa<VectorType>(First->getType()) ==

689 isa<VectorType>(Second->getType());

690}

691

692namespace {

693

694/// Models the state of a single base defining value in the findBasePointer

695/// algorithm for determining where a new instruction is needed to propagate

696/// the base of this BDV.

697class BDVState {

698public:

699 enum StatusTy {

700 // Starting state of lattice

701 Unknown,

702 // Some specific base value -- does *not* mean that instruction

703 // propagates the base of the object

704 // ex: gep %arg, 16 -> %arg is the base value

705 Base,

706 // Need to insert a node to represent a merge.

707 Conflict

708 };

709

710 BDVState() {

711 llvm_unreachable("missing state in map");

712 }

713

714 explicit BDVState(Value *OriginalValue)

715 : OriginalValue(OriginalValue) {}

716 explicit BDVState(Value *OriginalValue, StatusTy Status, Value *BaseValue = nullptr)

717 : OriginalValue(OriginalValue), Status(Status), BaseValue(BaseValue) {

718 assert(Status != Base || BaseValue);

719 }

720

721 StatusTy getStatus() const { return Status; }

722 Value *getOriginalValue() const { return OriginalValue; }

723 Value *getBaseValue() const { return BaseValue; }

724

725 bool isBase() const { return getStatus() == Base; }

726 bool isUnknown() const { return getStatus() == Unknown; }

727 bool isConflict() const { return getStatus() == Conflict; }

728

729 // Values of type BDVState form a lattice, and this function implements the

730 // meet

731 // operation.

732 void meet(const BDVState &Other) {

733 auto markConflict = [&]() {

734 Status = BDVState::Conflict;

735 BaseValue = nullptr;

736 };

737 // Conflict is a final state.

738 if (isConflict())

739 return;

740 // if we are not known - just take other state.

741 if (isUnknown()) {

742 Status = Other.getStatus();

743 BaseValue = Other.getBaseValue();

744 return;

745 }

746 // We are base.

747 assert(isBase() && "Unknown state");

748 // If other is unknown - just keep our state.

749 if (Other.isUnknown())

750 return;

751 // If other is conflict - it is a final state.

752 if (Other.isConflict())

753 return markConflict();

754 // Other is base as well.

755 assert(Other.isBase() && "Unknown state");

756 // If bases are different - Conflict.

757 if (getBaseValue() != Other.getBaseValue())

758 return markConflict();

759 // We are identical, do nothing.

760 }

761

762 bool operator==(const BDVState &Other) const {

763 return OriginalValue == Other.OriginalValue && BaseValue == Other.BaseValue &&

764 Status == Other.Status;

765 }

766

767 bool operator!=(const BDVState &other) const { return !(*this == other); }

768

769 LLVM_DUMP_METHOD

770 void dump() const {

771 print(dbgs());

772 dbgs() << '\n';

773 }

774

775 void print(raw_ostream &OS) const {

776 switch (getStatus()) {

777 case Unknown:

778 OS << "U";

779 break;

780 case Base:

781 OS << "B";

782 break;

783 case Conflict:

784 OS << "C";

785 break;

786 }

787 OS << " (base " << getBaseValue() << " - "

788 << (getBaseValue() ? getBaseValue()->getName() : "nullptr") << ")"

789 << " for " << OriginalValue->getName() << ":";

790 }

791

792private:

793 AssertingVH<Value> OriginalValue; // instruction this state corresponds to

794 StatusTy Status = Unknown;

795 AssertingVH<Value> BaseValue = nullptr; // Non-null only if Status == Base.

796};

797

798} // end anonymous namespace

799

800#ifndef NDEBUG

801 static raw_ostream &operator<<(raw_ostream &OS, const BDVState &State) {

802 State.print(OS);

803 return OS;

804}

805#endif

806

807/// For a given value or instruction, figure out what base ptr its derived from.

808/// For gc objects, this is simply itself. On success, returns a value which is

809/// the base pointer. (This is reliable and can be used for relocation.) On

810/// failure, returns nullptr.

811 static Value *findBasePointer(Value *I, DefiningValueMapTy &Cache,

812 IsKnownBaseMapTy &KnownBases) {

813 Value *Def = findBaseOrBDV(I, Cache, KnownBases);

814

815 if (isKnownBase(Def, KnownBases) && areBothVectorOrScalar(Def, I))

816 return Def;

817

818 // Here's the rough algorithm:

819 // - For every SSA value, construct a mapping to either an actual base

820 // pointer or a PHI which obscures the base pointer.

821 // - Construct a mapping from PHI to unknown TOP state. Use an

822 // optimistic algorithm to propagate base pointer information. Lattice

823 // looks like:

824 // UNKNOWN

825 // b1 b2 b3 b4

826 // CONFLICT

827 // When algorithm terminates, all PHIs will either have a single concrete

828 // base or be in a conflict state.

829 // - For every conflict, insert a dummy PHI node without arguments. Add

830 // these to the base[Instruction] = BasePtr mapping. For every

831 // non-conflict, add the actual base.

832 // - For every conflict, add arguments for the base[a] of each input

833 // arguments.

834 //

835 // Note: A simpler form of this would be to add the conflict form of all

836 // PHIs without running the optimistic algorithm. This would be

837 // analogous to pessimistic data flow and would likely lead to an

838 // overall worse solution.

839

840#ifndef NDEBUG

841 auto isExpectedBDVType = [](Value *BDV) {

842 return isa<PHINode>(BDV) || isa<SelectInst>(BDV) ||

843 isa<ExtractElementInst>(BDV) || isa<InsertElementInst>(BDV) ||

844 isa<ShuffleVectorInst>(BDV);

845 };

846#endif

847

848 // Once populated, will contain a mapping from each potentially non-base BDV

849 // to a lattice value (described above) which corresponds to that BDV.

850 // We use the order of insertion (DFS over the def/use graph) to provide a

851 // stable deterministic ordering for visiting DenseMaps (which are unordered)

852 // below. This is important for deterministic compilation.

853 MapVector<Value *, BDVState> States;

854

855#ifndef NDEBUG

856 auto VerifyStates = [&]() {

857 for (auto &Entry : States) {

858 assert(Entry.first == Entry.second.getOriginalValue());

859 }

860 };

861#endif

862

863 auto visitBDVOperands = [](Value *BDV, std::function<void (Value*)> F) {

864 if (PHINode *PN = dyn_cast<PHINode>(BDV)) {

865 for (Value *InVal : PN->incoming_values())

866 F(InVal);

867 } else if (SelectInst *SI = dyn_cast<SelectInst>(BDV)) {

868 F(SI->getTrueValue());

869 F(SI->getFalseValue());

870 } else if (auto *EE = dyn_cast<ExtractElementInst>(BDV)) {

871 F(EE->getVectorOperand());

872 } else if (auto *IE = dyn_cast<InsertElementInst>(BDV)) {

873 F(IE->getOperand(0));

874 F(IE->getOperand(1));

875 } else if (auto *SV = dyn_cast<ShuffleVectorInst>(BDV)) {

876 // For a canonical broadcast, ignore the undef argument

877 // (without this, we insert a parallel base shuffle for every broadcast)

878 F(SV->getOperand(0));

879 if (!SV->isZeroEltSplat())

880 F(SV->getOperand(1));

881 } else {

882 llvm_unreachable("unexpected BDV type");

883 }

884 };

885

886

887 // Recursively fill in all base defining values reachable from the initial

888 // one for which we don't already know a definite base value for

889 /* scope */ {

890 SmallVector<Value*, 16> Worklist;

891 Worklist.push_back(Def);

892 States.insert({Def, BDVState(Def)});

893 while (!Worklist.empty()) {

894 Value *Current = Worklist.pop_back_val();

895 assert(!isOriginalBaseResult(Current) && "why did it get added?");

896

897 auto visitIncomingValue = [&](Value *InVal) {

898 Value *Base = findBaseOrBDV(InVal, Cache, KnownBases);

899 if (isKnownBase(Base, KnownBases) && areBothVectorOrScalar(Base, InVal))

900 // Known bases won't need new instructions introduced and can be

901 // ignored safely. However, this can only be done when InVal and Base

902 // are both scalar or both vector. Otherwise, we need to find a

903 // correct BDV for InVal, by creating an entry in the lattice

904 // (States).

905 return;

906 assert(isExpectedBDVType(Base) && "the only non-base values "

907 "we see should be base defining values");

908 if (States.insert(std::make_pair(Base, BDVState(Base))).second)

909 Worklist.push_back(Base);

910 };

911

912 visitBDVOperands(Current, visitIncomingValue);

913 }

914 }

915

916#ifndef NDEBUG

917 VerifyStates();

918 LLVM_DEBUG(dbgs() << "States after initialization:\n");

919 for (const auto &Pair : States) {

920 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");

921 }

922#endif

923

924 // Iterate forward through the value graph pruning any node from the state

925 // list where all of the inputs are base pointers. The purpose of this is to

926 // reuse existing values when the derived pointer we were asked to materialize

927 // a base pointer for happens to be a base pointer itself. (Or a sub-graph

928 // feeding it does.)

929 SmallVector<Value *> ToRemove;

930 do {

931 ToRemove.clear();

932 for (auto Pair : States) {

933 Value *BDV = Pair.first;

934 auto canPruneInput = [&](Value *V) {

935 // If the input of the BDV is the BDV itself we can prune it. This is

936 // only possible if the BDV is a PHI node.

937 if (V->stripPointerCasts() == BDV)

938 return true;

939 Value *VBDV = findBaseOrBDV(V, Cache, KnownBases);

940 if (V->stripPointerCasts() != VBDV)

941 return false;

942 // The assumption is that anything not in the state list is

943 // propagates a base pointer.

944 return States.count(VBDV) == 0;

945 };

946

947 bool CanPrune = true;

948 visitBDVOperands(BDV, [&](Value *Op) {

949 CanPrune = CanPrune && canPruneInput(Op);

950 });

951 if (CanPrune)

952 ToRemove.push_back(BDV);

953 }

954 for (Value *V : ToRemove) {

955 States.erase(V);

956 // Cache the fact V is it's own base for later usage.

957 Cache[V] = V;

958 }

959 } while (!ToRemove.empty());

960

961 // Did we manage to prove that Def itself must be a base pointer?

962 if (!States.count(Def))

963 return Def;

964

965 // Return a phi state for a base defining value. We'll generate a new

966 // base state for known bases and expect to find a cached state otherwise.

967 auto GetStateForBDV = [&](Value *BaseValue, Value *Input) {

968 auto I = States.find(BaseValue);

969 if (I != States.end())

970 return I->second;

971 assert(areBothVectorOrScalar(BaseValue, Input));

972 return BDVState(BaseValue, BDVState::Base, BaseValue);

973 };

974

975 // Even though we have identified a concrete base (or a conflict) for all live

976 // pointers at this point, there are cases where the base is of an

977 // incompatible type compared to the original instruction. We conservatively

978 // mark those as conflicts to ensure that corresponding BDVs will be generated

979 // in the next steps.

980

981 // this is a rather explicit check for all cases where we should mark the

982 // state as a conflict to force the latter stages of the algorithm to emit

983 // the BDVs.

984 // TODO: in many cases the instructions emited for the conflicting states

985 // will be identical to the I itself (if the I's operate on their BDVs

986 // themselves). We should exploit this, but can't do it here since it would

987 // break the invariant about the BDVs not being known to be a base.

988 // TODO: the code also does not handle constants at all - the algorithm relies

989 // on all constants having the same BDV and therefore constant-only insns

990 // will never be in conflict, but this check is ignored here. If the

991 // constant conflicts will be to BDVs themselves, they will be identical

992 // instructions and will get optimized away (as in the above TODO)

993 auto MarkConflict = [&](Instruction *I, Value *BaseValue) {

994 // II and EE mixes vector & scalar so is always a conflict

995 if (isa<InsertElementInst>(I) || isa<ExtractElementInst>(I))

996 return true;

997 // Shuffle vector is always a conflict as it creates new vector from

998 // existing ones.

999 if (isa<ShuffleVectorInst>(I))

1000 return true;

1001 // Any instructions where the computed base type differs from the

1002 // instruction type. An example is where an extract instruction is used by a

1003 // select. Here the select's BDV is a vector (because of extract's BDV),

1004 // while the select itself is a scalar type. Note that the IE and EE

1005 // instruction check is not fully subsumed by the vector<->scalar check at

1006 // the end, this is due to the BDV algorithm being ignorant of BDV types at

1007 // this junction.

1008 if (!areBothVectorOrScalar(BaseValue, I))

1009 return true;

1010 return false;

1011 };

1012

1013 bool Progress = true;

1014 while (Progress) {

1015#ifndef NDEBUG

1016 const size_t OldSize = States.size();

1017#endif

1018 Progress = false;

1019 // We're only changing values in this loop, thus safe to keep iterators.

1020 // Since this is computing a fixed point, the order of visit does not

1021 // effect the result. TODO: We could use a worklist here and make this run

1022 // much faster.

1023 for (auto Pair : States) {

1024 Value *BDV = Pair.first;

1025 // Only values that do not have known bases or those that have differing

1026 // type (scalar versus vector) from a possible known base should be in the

1027 // lattice.

1028 assert((!isKnownBase(BDV, KnownBases) ||

1029 !areBothVectorOrScalar(BDV, Pair.second.getBaseValue())) &&

1030 "why did it get added?");

1031

1032 BDVState NewState(BDV);

1033 visitBDVOperands(BDV, [&](Value *Op) {

1034 Value *BDV = findBaseOrBDV(Op, Cache, KnownBases);

1035 auto OpState = GetStateForBDV(BDV, Op);

1036 NewState.meet(OpState);

1037 });

1038

1039 // if the instruction has known base, but should in fact be marked as

1040 // conflict because of incompatible in/out types, we mark it as such

1041 // ensuring that it will propagate through the fixpoint iteration

1042 auto I = cast<Instruction>(BDV);

1043 auto BV = NewState.getBaseValue();

1044 if (BV && MarkConflict(I, BV))

1045 NewState = BDVState(I, BDVState::Conflict);

1046

1047 BDVState OldState = Pair.second;

1048 if (OldState != NewState) {

1049 Progress = true;

1050 States[BDV] = NewState;

1051 }

1052 }

1053

1054 assert(OldSize == States.size() &&

1055 "fixed point shouldn't be adding any new nodes to state");

1056 }

1057

1058#ifndef NDEBUG

1059 VerifyStates();

1060 LLVM_DEBUG(dbgs() << "States after meet iteration:\n");

1061 for (const auto &Pair : States) {

1062 LLVM_DEBUG(dbgs() << " " << Pair.second << " for " << *Pair.first << "\n");

1063 }

1064

1065 // since we do the conflict marking as part of the fixpoint iteration this

1066 // loop only asserts that invariants are met

1067 for (auto Pair : States) {

1068 Instruction *I = cast<Instruction>(Pair.first);

1069 BDVState State = Pair.second;

1070 auto *BaseValue = State.getBaseValue();

1071 // Only values that do not have known bases or those that have differing

1072 // type (scalar versus vector) from a possible known base should be in the

1073 // lattice.

1074 assert(

1075 (!isKnownBase(I, KnownBases) || !areBothVectorOrScalar(I, BaseValue)) &&

1076 "why did it get added?");

1077 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");

1078 }

1079#endif

1080

1081 // Insert Phis for all conflicts

1082 // TODO: adjust naming patterns to avoid this order of iteration dependency

1083 for (auto Pair : States) {

1084 Instruction *I = cast<Instruction>(Pair.first);

1085 BDVState State = Pair.second;

1086 // Only values that do not have known bases or those that have differing

1087 // type (scalar versus vector) from a possible known base should be in the

1088 // lattice.

1089 assert((!isKnownBase(I, KnownBases) ||

1090 !areBothVectorOrScalar(I, State.getBaseValue())) &&

1091 "why did it get added?");

1092 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");

1093

1094 // Since we're joining a vector and scalar base, they can never be the

1095 // same. As a result, we should always see insert element having reached

1096 // the conflict state.

1097 assert(!isa<InsertElementInst>(I) || State.isConflict());

1098

1099 if (!State.isConflict())

1100 continue;

1101

1102 auto getMangledName = [](Instruction *I) -> std::string {

1103 if (isa<PHINode>(I)) {

1104 return suffixed_name_or(I, ".base", "base_phi");

1105 } else if (isa<SelectInst>(I)) {

1106 return suffixed_name_or(I, ".base", "base_select");

1107 } else if (isa<ExtractElementInst>(I)) {

1108 return suffixed_name_or(I, ".base", "base_ee");

1109 } else if (isa<InsertElementInst>(I)) {

1110 return suffixed_name_or(I, ".base", "base_ie");

1111 } else {

1112 return suffixed_name_or(I, ".base", "base_sv");

1113 }

1114 };

1115

1116 Instruction *BaseInst = I->clone();

1117 BaseInst->insertBefore(I->getIterator());

1118 BaseInst->setName(getMangledName(I));

1119 // Add metadata marking this as a base value

1120 BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));

1121 States[I] = BDVState(I, BDVState::Conflict, BaseInst);

1122 setKnownBase(BaseInst, /* IsKnownBase */true, KnownBases);

1123 }

1124

1125#ifndef NDEBUG

1126 VerifyStates();

1127#endif

1128

1129 // Returns a instruction which produces the base pointer for a given

1130 // instruction. The instruction is assumed to be an input to one of the BDVs

1131 // seen in the inference algorithm above. As such, we must either already

1132 // know it's base defining value is a base, or have inserted a new

1133 // instruction to propagate the base of it's BDV and have entered that newly

1134 // introduced instruction into the state table. In either case, we are

1135 // assured to be able to determine an instruction which produces it's base

1136 // pointer.

1137 auto getBaseForInput = [&](Value *Input, Instruction *InsertPt) {

1138 Value *BDV = findBaseOrBDV(Input, Cache, KnownBases);

1139 Value *Base = nullptr;

1140 if (auto It = States.find(BDV); It == States.end()) {

1141 assert(areBothVectorOrScalar(BDV, Input));

1142 Base = BDV;

1143 } else {

1144 // Either conflict or base.

1145 Base = It->second.getBaseValue();

1146 }

1147 assert(Base && "Can't be null");

1148 // The cast is needed since base traversal may strip away bitcasts

1149 if (Base->getType() != Input->getType() && InsertPt)

1150 Base = new BitCastInst(Base, Input->getType(), "cast",

1151 InsertPt->getIterator());

1152 return Base;

1153 };

1154

1155 // Fixup all the inputs of the new PHIs. Visit order needs to be

1156 // deterministic and predictable because we're naming newly created

1157 // instructions.

1158 for (auto Pair : States) {

1159 Instruction *BDV = cast<Instruction>(Pair.first);

1160 BDVState State = Pair.second;

1161

1162 // Only values that do not have known bases or those that have differing

1163 // type (scalar versus vector) from a possible known base should be in the

1164 // lattice.

1165 assert((!isKnownBase(BDV, KnownBases) ||

1166 !areBothVectorOrScalar(BDV, State.getBaseValue())) &&

1167 "why did it get added?");

1168 assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");

1169 if (!State.isConflict())

1170 continue;

1171

1172 if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {

1173 PHINode *PN = cast<PHINode>(BDV);

1174 const unsigned NumPHIValues = PN->getNumIncomingValues();

1175

1176 // The IR verifier requires phi nodes with multiple entries from the

1177 // same basic block to have the same incoming value for each of those

1178 // entries. Since we're inserting bitcasts in the loop, make sure we

1179 // do so at least once per incoming block.

1180 DenseMap<BasicBlock *, Value*> BlockToValue;

1181 for (unsigned i = 0; i < NumPHIValues; i++) {

1182 Value *InVal = PN->getIncomingValue(i);

1183 BasicBlock *InBB = PN->getIncomingBlock(i);

1184 auto [It, Inserted] = BlockToValue.try_emplace(InBB);

1185 if (Inserted)

1186 It->second = getBaseForInput(InVal, InBB->getTerminator());

1187 else {

1188#ifndef NDEBUG

1189 Value *OldBase = It->second;

1190 Value *Base = getBaseForInput(InVal, nullptr);

1191

1192 // We can't use `stripPointerCasts` instead of this function because

1193 // `stripPointerCasts` doesn't handle vectors of pointers.

1194 auto StripBitCasts = [](Value *V) -> Value * {

1195 while (auto *BC = dyn_cast<BitCastInst>(V))

1196 V = BC->getOperand(0);

1197 return V;

1198 };

1199 // In essence this assert states: the only way two values

1200 // incoming from the same basic block may be different is by

1201 // being different bitcasts of the same value. A cleanup

1202 // that remains TODO is changing findBaseOrBDV to return an

1203 // llvm::Value of the correct type (and still remain pure).

1204 // This will remove the need to add bitcasts.

1205 assert(StripBitCasts(Base) == StripBitCasts(OldBase) &&

1206 "findBaseOrBDV should be pure!");

1207#endif

1208 }

1209 Value *Base = It->second;

1210 BasePHI->setIncomingValue(i, Base);

1211 }

1212 } else if (SelectInst *BaseSI =

1213 dyn_cast<SelectInst>(State.getBaseValue())) {

1214 SelectInst *SI = cast<SelectInst>(BDV);

1215

1216 // Find the instruction which produces the base for each input.

1217 // We may need to insert a bitcast.

1218 BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));

1219 BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));

1220 } else if (auto *BaseEE =

1221 dyn_cast<ExtractElementInst>(State.getBaseValue())) {

1222 Value *InVal = cast<ExtractElementInst>(BDV)->getVectorOperand();

1223 // Find the instruction which produces the base for each input. We may

1224 // need to insert a bitcast.

1225 BaseEE->setOperand(0, getBaseForInput(InVal, BaseEE));

1226 } else if (auto *BaseIE = dyn_cast<InsertElementInst>(State.getBaseValue())){

1227 auto *BdvIE = cast<InsertElementInst>(BDV);

1228 auto UpdateOperand = [&](int OperandIdx) {

1229 Value *InVal = BdvIE->getOperand(OperandIdx);

1230 Value *Base = getBaseForInput(InVal, BaseIE);

1231 BaseIE->setOperand(OperandIdx, Base);

1232 };

1233 UpdateOperand(0); // vector operand

1234 UpdateOperand(1); // scalar operand

1235 } else {

1236 auto *BaseSV = cast<ShuffleVectorInst>(State.getBaseValue());

1237 auto *BdvSV = cast<ShuffleVectorInst>(BDV);

1238 auto UpdateOperand = [&](int OperandIdx) {

1239 Value *InVal = BdvSV->getOperand(OperandIdx);

1240 Value *Base = getBaseForInput(InVal, BaseSV);

1241 BaseSV->setOperand(OperandIdx, Base);

1242 };

1243 UpdateOperand(0); // vector operand

1244 if (!BdvSV->isZeroEltSplat())

1245 UpdateOperand(1); // vector operand

1246 else {

1247 // Never read, so just use poison

1248 Value *InVal = BdvSV->getOperand(1);

1249 BaseSV->setOperand(1, PoisonValue::get(InVal->getType()));

1250 }

1251 }

1252 }

1253

1254#ifndef NDEBUG

1255 VerifyStates();

1256#endif

1257

1258 // get the data layout to compare the sizes of base/derived pointer values

1259 [[maybe_unused]] auto &DL =

1260 cast<llvm::Instruction>(Def)->getDataLayout();

1261 // Cache all of our results so we can cheaply reuse them

1262 // NOTE: This is actually two caches: one of the base defining value

1263 // relation and one of the base pointer relation! FIXME

1264 for (auto Pair : States) {

1265 auto *BDV = Pair.first;

1266 Value *Base = Pair.second.getBaseValue();

1267 assert(BDV && Base);

1268 // Whenever we have a derived ptr(s), their base

1269 // ptr(s) must be of the same size, not necessarily the same type

1270 assert(DL.getTypeAllocSize(BDV->getType()) ==

1271 DL.getTypeAllocSize(Base->getType()) &&

1272 "Derived and base values should have same size");

1273 // Only values that do not have known bases or those that have differing

1274 // type (scalar versus vector) from a possible known base should be in the

1275 // lattice.

1276 assert(

1277 (!isKnownBase(BDV, KnownBases) || !areBothVectorOrScalar(BDV, Base)) &&

1278 "why did it get added?");

1279

1280 LLVM_DEBUG(

1281 dbgs() << "Updating base value cache"

1282 << " for: " << BDV->getName() << " from: "

1283 << (Cache.count(BDV) ? Cache[BDV]->getName().str() : "none")

1284 << " to: " << Base->getName() << "\n");

1285

1286 Cache[BDV] = Base;

1287 }

1288 assert(Cache.count(Def));

1289 return Cache[Def];

1290}

1291

1292// For a set of live pointers (base and/or derived), identify the base

1293// pointer of the object which they are derived from. This routine will

1294// mutate the IR graph as needed to make the 'base' pointer live at the

1295// definition site of 'derived'. This ensures that any use of 'derived' can

1296// also use 'base'. This may involve the insertion of a number of

1297// additional PHI nodes.

1298//

1299// preconditions: live is a set of pointer type Values

1300//

1301// side effects: may insert PHI nodes into the existing CFG, will preserve

1302// CFG, will not remove or mutate any existing nodes

1303//

1304// post condition: PointerToBase contains one (derived, base) pair for every

1305// pointer in live. Note that derived can be equal to base if the original

1306// pointer was a base pointer.

1307 static void findBasePointers(const StatepointLiveSetTy &live,

1308 PointerToBaseTy &PointerToBase, DominatorTree *DT,

1309 DefiningValueMapTy &DVCache,

1310 IsKnownBaseMapTy &KnownBases) {

1311 for (Value *ptr : live) {

1312 Value *base = findBasePointer(ptr, DVCache, KnownBases);

1313 assert(base && "failed to find base pointer");

1314 PointerToBase[ptr] = base;

1315 assert((!isa<Instruction>(base) || !isa<Instruction>(ptr) ||

1316 DT->dominates(cast<Instruction>(base)->getParent(),

1317 cast<Instruction>(ptr)->getParent())) &&

1318 "The base we found better dominate the derived pointer");

1319 }

1320}

1321

1322/// Find the required based pointers (and adjust the live set) for the given

1323/// parse point.

1324 static void findBasePointers(DominatorTree &DT, DefiningValueMapTy &DVCache,

1325 CallBase *Call,

1326 PartiallyConstructedSafepointRecord &result,

1327 PointerToBaseTy &PointerToBase,

1328 IsKnownBaseMapTy &KnownBases) {

1329 StatepointLiveSetTy PotentiallyDerivedPointers = result.LiveSet;

1330 // We assume that all pointers passed to deopt are base pointers; as an

1331 // optimization, we can use this to avoid separately materializing the base

1332 // pointer graph. This is only relevant since we're very conservative about

1333 // generating new conflict nodes during base pointer insertion. If we were

1334 // smarter there, this would be irrelevant.

1335 if (auto Opt = Call->getOperandBundle(LLVMContext::OB_deopt))

1336 for (Value *V : Opt->Inputs) {

1337 if (!PotentiallyDerivedPointers.count(V))

1338 continue;

1339 PotentiallyDerivedPointers.remove(V);

1340 PointerToBase[V] = V;

1341 }

1342 findBasePointers(PotentiallyDerivedPointers, PointerToBase, &DT, DVCache,

1343 KnownBases);

1344}

1345

1346/// Given an updated version of the dataflow liveness results, update the

1347/// liveset and base pointer maps for the call site CS.

1348static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,

1349 CallBase *Call,

1350 PartiallyConstructedSafepointRecord &result,

1351 PointerToBaseTy &PointerToBase,

1352 GCStrategy *GC);

1353

1354 static void recomputeLiveInValues(

1355 Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,

1356 MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,

1357 PointerToBaseTy &PointerToBase, GCStrategy *GC) {

1358 // TODO-PERF: reuse the original liveness, then simply run the dataflow

1359 // again. The old values are still live and will help it stabilize quickly.

1360 GCPtrLivenessData RevisedLivenessData;

1361 computeLiveInValues(DT, F, RevisedLivenessData, GC);

1362 for (size_t i = 0; i < records.size(); i++) {

1363 struct PartiallyConstructedSafepointRecord &info = records[i];

1364 recomputeLiveInValues(RevisedLivenessData, toUpdate[i], info, PointerToBase,

1365 GC);

1366 }

1367}

1368

1369// Utility function which clones all instructions from "ChainToBase"

1370// and inserts them before "InsertBefore". Returns rematerialized value

1371// which should be used after statepoint.

1372 static Instruction *rematerializeChain(ArrayRef<Instruction *> ChainToBase,

1373 BasicBlock::iterator InsertBefore,

1374 Value *RootOfChain,

1375 Value *AlternateLiveBase) {

1376 Instruction *LastClonedValue = nullptr;

1377 Instruction *LastValue = nullptr;

1378 // Walk backwards to visit top-most instructions first.

1379 for (Instruction *Instr : reverse(ChainToBase)) {

1380 // Only GEP's and casts are supported as we need to be careful to not

1381 // introduce any new uses of pointers not in the liveset.

1382 // Note that it's fine to introduce new uses of pointers which were

1383 // otherwise not used after this statepoint.

1384 assert(isa<GetElementPtrInst>(Instr) || isa<CastInst>(Instr));

1385

1386 Instruction *ClonedValue = Instr->clone();

1387 ClonedValue->insertBefore(InsertBefore);

1388 ClonedValue->setName(Instr->getName() + ".remat");

1389

1390 // If it is not first instruction in the chain then it uses previously

1391 // cloned value. We should update it to use cloned value.

1392 if (LastClonedValue) {

1393 assert(LastValue);

1394 ClonedValue->replaceUsesOfWith(LastValue, LastClonedValue);

1395#ifndef NDEBUG

1396 for (auto *OpValue : ClonedValue->operand_values()) {

1397 // Assert that cloned instruction does not use any instructions from

1398 // this chain other than LastClonedValue

1399 assert(!is_contained(ChainToBase, OpValue) &&

1400 "incorrect use in rematerialization chain");

1401 // Assert that the cloned instruction does not use the RootOfChain

1402 // or the AlternateLiveBase.

1403 assert(OpValue != RootOfChain && OpValue != AlternateLiveBase);

1404 }

1405#endif

1406 } else {

1407 // For the first instruction, replace the use of unrelocated base i.e.

1408 // RootOfChain/OrigRootPhi, with the corresponding PHI present in the

1409 // live set. They have been proved to be the same PHI nodes. Note

1410 // that the *only* use of the RootOfChain in the ChainToBase list is

1411 // the first Value in the list.

1412 if (RootOfChain != AlternateLiveBase)

1413 ClonedValue->replaceUsesOfWith(RootOfChain, AlternateLiveBase);

1414 }

1415

1416 LastClonedValue = ClonedValue;

1417 LastValue = Instr;

1418 }

1419 assert(LastClonedValue);

1420 return LastClonedValue;

1421}

1422

1423// When inserting gc.relocate and gc.result calls, we need to ensure there are

1424// no uses of the original value / return value between the gc.statepoint and

1425// the gc.relocate / gc.result call. One case which can arise is a phi node

1426// starting one of the successor blocks. We also need to be able to insert the

1427// gc.relocates only on the path which goes through the statepoint. We might

1428// need to split an edge to make this possible.

1429static BasicBlock *

1430 normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent,

1431 DominatorTree &DT) {

1432 BasicBlock *Ret = BB;

1433 if (!BB->getUniquePredecessor())

1434 Ret = SplitBlockPredecessors(BB, InvokeParent, "", &DT);

1435

1436 // Now that 'Ret' has unique predecessor we can safely remove all phi nodes

1437 // from it

1438 FoldSingleEntryPHINodes(Ret);

1439 assert(!isa<PHINode>(Ret->begin()) &&

1440 "All PHI nodes should have been removed!");

1441

1442 // At this point, we can safely insert a gc.relocate or gc.result as the first

1443 // instruction in Ret if needed.

1444 return Ret;

1445}

1446

1447// List of all function attributes which must be stripped when lowering from

1448// abstract machine model to physical machine model. Essentially, these are

1449// all the effects a safepoint might have which we ignored in the abstract

1450// machine model for purposes of optimization. We have to strip these on

1451// both function declarations and call sites.

1452 static constexpr Attribute::AttrKind FnAttrsToStrip[] =

1453 {Attribute::Memory, Attribute::NoSync, Attribute::NoFree};

1454

1455// Create new attribute set containing only attributes which can be transferred

1456// from the original call to the safepoint.

1457 static AttributeList legalizeCallAttributes(CallBase *Call, bool IsMemIntrinsic,

1458 AttributeList StatepointAL) {

1459 AttributeList OrigAL = Call->getAttributes();

1460 if (OrigAL.isEmpty())

1461 return StatepointAL;

1462

1463 // Remove the readonly, readnone, and statepoint function attributes.

1464 LLVMContext &Ctx = Call->getContext();

1465 AttrBuilder FnAttrs(Ctx, OrigAL.getFnAttrs());

1466 for (auto Attr : FnAttrsToStrip)

1467 FnAttrs.removeAttribute(Attr);

1468

1469 for (Attribute A : OrigAL.getFnAttrs()) {

1470 if (isStatepointDirectiveAttr(A))

1471 FnAttrs.removeAttribute(A);

1472 }

1473

1474 StatepointAL = StatepointAL.addFnAttributes(Ctx, FnAttrs);

1475

1476 // The memory intrinsics do not have a 1:1 correspondence of the original

1477 // call arguments to the produced statepoint. Do not transfer the argument

1478 // attributes to avoid putting them on incorrect arguments.

1479 if (IsMemIntrinsic)

1480 return StatepointAL;

1481

1482 // Attach the argument attributes from the original call at the corresponding

1483 // arguments in the statepoint. Note that any argument attributes that are

1484 // invalid after lowering are stripped in stripNonValidDataFromBody.

1485 for (unsigned I : llvm::seq(Call->arg_size()))

1486 StatepointAL = StatepointAL.addParamAttributes(

1487 Ctx, GCStatepointInst::CallArgsBeginPos + I,

1488 AttrBuilder(Ctx, OrigAL.getParamAttrs(I)));

1489

1490 // Return attributes are later attached to the gc.result intrinsic.

1491 return StatepointAL;

1492}

1493

1494/// Helper function to place all gc relocates necessary for the given

1495/// statepoint.

1496/// Inputs:

1497/// liveVariables - list of variables to be relocated.

1498/// basePtrs - base pointers.

1499/// statepointToken - statepoint instruction to which relocates should be

1500/// bound.

1501/// Builder - Llvm IR builder to be used to construct new calls.

1502 static void CreateGCRelocates(ArrayRef<Value *> LiveVariables,

1503 ArrayRef<Value *> BasePtrs,

1504 Instruction *StatepointToken,

1505 IRBuilder<> &Builder, GCStrategy *GC) {

1506 if (LiveVariables.empty())

1507 return;

1508

1509 auto FindIndex = [](ArrayRef<Value *> LiveVec, Value *Val) {

1510 auto ValIt = llvm::find(LiveVec, Val);

1511 assert(ValIt != LiveVec.end() && "Val not found in LiveVec!");

1512 size_t Index = std::distance(LiveVec.begin(), ValIt);

1513 assert(Index < LiveVec.size() && "Bug in std::find?");

1514 return Index;

1515 };

1516 Module *M = StatepointToken->getModule();

1517

1518 // All gc_relocate are generated as i8 addrspace(1)* (or a vector type whose

1519 // element type is i8 addrspace(1)*). We originally generated unique

1520 // declarations for each pointer type, but this proved problematic because

1521 // the intrinsic mangling code is incomplete and fragile. Since we're moving

1522 // towards a single unified pointer type anyways, we can just cast everything

1523 // to an i8* of the right address space. A bitcast is added later to convert

1524 // gc_relocate to the actual value's type.

1525 auto getGCRelocateDecl = [&](Type *Ty) {

1526 assert(isHandledGCPointerType(Ty, GC));

1527 auto AS = Ty->getScalarType()->getPointerAddressSpace();

1528 Type *NewTy = PointerType::get(M->getContext(), AS);

1529 if (auto *VT = dyn_cast<VectorType>(Ty))

1530 NewTy = FixedVectorType::get(NewTy,

1531 cast<FixedVectorType>(VT)->getNumElements());

1532 return Intrinsic::getOrInsertDeclaration(

1533 M, Intrinsic::experimental_gc_relocate, {NewTy});

1534 };

1535

1536 // Lazily populated map from input types to the canonicalized form mentioned

1537 // in the comment above. This should probably be cached somewhere more

1538 // broadly.

1539 DenseMap<Type *, Function *> TypeToDeclMap;

1540

1541 for (unsigned i = 0; i < LiveVariables.size(); i++) {

1542 // Generate the gc.relocate call and save the result

1543 Value *BaseIdx = Builder.getInt32(FindIndex(LiveVariables, BasePtrs[i]));

1544 Value *LiveIdx = Builder.getInt32(i);

1545

1546 Type *Ty = LiveVariables[i]->getType();

1547 auto [It, Inserted] = TypeToDeclMap.try_emplace(Ty);

1548 if (Inserted)

1549 It->second = getGCRelocateDecl(Ty);

1550 Function *GCRelocateDecl = It->second;

1551

1552 // only specify a debug name if we can give a useful one

1553 CallInst *Reloc = Builder.CreateCall(

1554 GCRelocateDecl, {StatepointToken, BaseIdx, LiveIdx},

1555 suffixed_name_or(LiveVariables[i], ".relocated", ""));

1556 // Trick CodeGen into thinking there are lots of free registers at this

1557 // fake call.

1558 Reloc->setCallingConv(CallingConv::Cold);

1559 }

1560}

1561

1562namespace {

1563

1564/// This struct is used to defer RAUWs and `eraseFromParent` s. Using this

1565/// avoids having to worry about keeping around dangling pointers to Values.

1566class DeferredReplacement {

1567 AssertingVH<Instruction> Old;

1568 AssertingVH<Instruction> New;

1569 bool IsDeoptimize = false;

1570

1571 DeferredReplacement() = default;

1572

1573public:

1574 static DeferredReplacement createRAUW(Instruction *Old, Instruction *New) {

1575 assert(Old != New && Old && New &&

1576 "Cannot RAUW equal values or to / from null!");

1577

1578 DeferredReplacement D;

1579 D.Old = Old;

1580 D.New = New;

1581 return D;

1582 }

1583

1584 static DeferredReplacement createDelete(Instruction *ToErase) {

1585 DeferredReplacement D;

1586 D.Old = ToErase;

1587 return D;

1588 }

1589

1590 static DeferredReplacement createDeoptimizeReplacement(Instruction *Old) {

1591#ifndef NDEBUG

1592 auto *F = cast<CallInst>(Old)->getCalledFunction();

1593 assert(F && F->getIntrinsicID() == Intrinsic::experimental_deoptimize &&

1594 "Only way to construct a deoptimize deferred replacement");

1595#endif

1596 DeferredReplacement D;

1597 D.Old = Old;

1598 D.IsDeoptimize = true;

1599 return D;

1600 }

1601

1602 /// Does the task represented by this instance.

1603 void doReplacement() {

1604 Instruction *OldI = Old;

1605 Instruction *NewI = New;

1606

1607 assert(OldI != NewI && "Disallowed at construction?!");

1608 assert((!IsDeoptimize || !New) &&

1609 "Deoptimize intrinsics are not replaced!");

1610

1611 Old = nullptr;

1612 New = nullptr;

1613

1614 if (NewI)

1615 OldI->replaceAllUsesWith(NewI);

1616

1617 if (IsDeoptimize) {

1618 // Note: we've inserted instructions, so the call to llvm.deoptimize may

1619 // not necessarily be followed by the matching return.

1620 auto *RI = cast<ReturnInst>(OldI->getParent()->getTerminator());

1621 new UnreachableInst(RI->getContext(), RI->getIterator());

1622 RI->eraseFromParent();

1623 }

1624

1625 OldI->eraseFromParent();

1626 }

1627};

1628

1629} // end anonymous namespace

1630

1631 static StringRef getDeoptLowering(CallBase *Call) {

1632 const char *DeoptLowering = "deopt-lowering";

1633 if (Call->hasFnAttr(DeoptLowering)) {

1634 // FIXME: Calls have a *really* confusing interface around attributes

1635 // with values.

1636 const AttributeList &CSAS = Call->getAttributes();

1637 if (CSAS.hasFnAttr(DeoptLowering))

1638 return CSAS.getFnAttr(DeoptLowering).getValueAsString();

1639 Function *F = Call->getCalledFunction();

1640 assert(F && F->hasFnAttribute(DeoptLowering));

1641 return F->getFnAttribute(DeoptLowering).getValueAsString();

1642 }

1643 return "live-through";

1644}

1645

1646static void

1647 makeStatepointExplicitImpl(CallBase *Call, /* to replace */

1648 const SmallVectorImpl<Value *> &BasePtrs,

1649 const SmallVectorImpl<Value *> &LiveVariables,

1650 PartiallyConstructedSafepointRecord &Result,

1651 std::vector<DeferredReplacement> &Replacements,

1652 const PointerToBaseTy &PointerToBase,

1653 GCStrategy *GC) {

1654 assert(BasePtrs.size() == LiveVariables.size());

1655

1656 // Then go ahead and use the builder do actually do the inserts. We insert

1657 // immediately before the previous instruction under the assumption that all

1658 // arguments will be available here. We can't insert afterwards since we may

1659 // be replacing a terminator.

1660 IRBuilder<> Builder(Call);

1661

1662 ArrayRef<Value *> GCLive(LiveVariables);

1663 uint64_t StatepointID = StatepointDirectives::DefaultStatepointID;

1664 uint32_t NumPatchBytes = 0;

1665 uint32_t Flags = uint32_t(StatepointFlags::None);

1666

1667 SmallVector<Value *, 8> CallArgs(Call->args());

1668 std::optional<ArrayRef<Use>> DeoptArgs;

1669 if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_deopt))

1670 DeoptArgs = Bundle->Inputs;

1671 std::optional<ArrayRef<Use>> TransitionArgs;

1672 if (auto Bundle = Call->getOperandBundle(LLVMContext::OB_gc_transition)) {

1673 TransitionArgs = Bundle->Inputs;

1674 // TODO: This flag no longer serves a purpose and can be removed later

1675 Flags |= uint32_t(StatepointFlags::GCTransition);

1676 }

1677

1678 // Instead of lowering calls to @llvm.experimental.deoptimize as normal calls

1679 // with a return value, we lower then as never returning calls to

1680 // __llvm_deoptimize that are followed by unreachable to get better codegen.

1681 bool IsDeoptimize = false;

1682 bool IsMemIntrinsic = false;

1683

1684 StatepointDirectives SD =

1685 parseStatepointDirectivesFromAttrs(Call->getAttributes());

1686 if (SD.NumPatchBytes)

1687 NumPatchBytes = *SD.NumPatchBytes;

1688 if (SD.StatepointID)

1689 StatepointID = *SD.StatepointID;

1690

1691 // Pass through the requested lowering if any. The default is live-through.

1692 StringRef DeoptLowering = getDeoptLowering(Call);

1693 if (DeoptLowering == "live-in")

1694 Flags |= uint32_t(StatepointFlags::DeoptLiveIn);

1695 else {

1696 assert(DeoptLowering == "live-through" && "Unsupported value!");

1697 }

1698

1699 FunctionCallee CallTarget(Call->getFunctionType(), Call->getCalledOperand());

1700 if (Function *F = dyn_cast<Function>(CallTarget.getCallee())) {

1701 auto IID = F->getIntrinsicID();

1702 if (IID == Intrinsic::experimental_deoptimize) {

1703 // Calls to llvm.experimental.deoptimize are lowered to calls to the

1704 // __llvm_deoptimize symbol. We want to resolve this now, since the

1705 // verifier does not allow taking the address of an intrinsic function.

1706

1707 SmallVector<Type *, 8> DomainTy;

1708 for (Value *Arg : CallArgs)

1709 DomainTy.push_back(Arg->getType());

1710 auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,

1711 /* isVarArg = */ false);

1712

1713 // Note: CallTarget can be a bitcast instruction of a symbol if there are

1714 // calls to @llvm.experimental.deoptimize with different argument types in

1715 // the same module. This is fine -- we assume the frontend knew what it

1716 // was doing when generating this kind of IR.

1717 CallTarget = F->getParent()

1718 ->getOrInsertFunction("__llvm_deoptimize", FTy);

1719

1720 IsDeoptimize = true;

1721 } else if (IID == Intrinsic::memcpy_element_unordered_atomic ||

1722 IID == Intrinsic::memmove_element_unordered_atomic) {

1723 IsMemIntrinsic = true;

1724

1725 // Unordered atomic memcpy and memmove intrinsics which are not explicitly

1726 // marked as "gc-leaf-function" should be lowered in a GC parseable way.

1727 // Specifically, these calls should be lowered to the

1728 // __llvm_{memcpy|memmove}_element_unordered_atomic_safepoint symbols.

1729 // Similarly to __llvm_deoptimize we want to resolve this now, since the

1730 // verifier does not allow taking the address of an intrinsic function.

1731 //

1732 // Moreover we need to shuffle the arguments for the call in order to

1733 // accommodate GC. The underlying source and destination objects might be

1734 // relocated during copy operation should the GC occur. To relocate the

1735 // derived source and destination pointers the implementation of the

1736 // intrinsic should know the corresponding base pointers.

1737 //

1738 // To make the base pointers available pass them explicitly as arguments:

1739 // memcpy(dest_derived, source_derived, ...) =>

1740 // memcpy(dest_base, dest_offset, source_base, source_offset, ...)

1741 auto &Context = Call->getContext();

1742 auto &DL = Call->getDataLayout();

1743 auto GetBaseAndOffset = [&](Value *Derived) {

1744 Value *Base = nullptr;

1745 // Optimizations in unreachable code might substitute the real pointer

1746 // with undef, poison or null-derived constant. Return null base for

1747 // them to be consistent with the handling in the main algorithm in

1748 // findBaseDefiningValue.

1749 if (isa<Constant>(Derived))

1750 Base =

1751 ConstantPointerNull::get(cast<PointerType>(Derived->getType()));

1752 else {

1753 assert(PointerToBase.count(Derived));

1754 Base = PointerToBase.find(Derived)->second;

1755 }

1756 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();

1757 unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);

1758 Value *Base_int = Builder.CreatePtrToInt(

1759 Base, Type::getIntNTy(Context, IntPtrSize));

1760 Value *Derived_int = Builder.CreatePtrToInt(

1761 Derived, Type::getIntNTy(Context, IntPtrSize));

1762 return std::make_pair(Base, Builder.CreateSub(Derived_int, Base_int));

1763 };

1764

1765 auto *Dest = CallArgs[0];

1766 Value *DestBase, *DestOffset;

1767 std::tie(DestBase, DestOffset) = GetBaseAndOffset(Dest);

1768

1769 auto *Source = CallArgs[1];

1770 Value *SourceBase, *SourceOffset;

1771 std::tie(SourceBase, SourceOffset) = GetBaseAndOffset(Source);

1772

1773 auto *LengthInBytes = CallArgs[2];

1774 auto *ElementSizeCI = cast<ConstantInt>(CallArgs[3]);

1775

1776 CallArgs.clear();

1777 CallArgs.push_back(DestBase);

1778 CallArgs.push_back(DestOffset);

1779 CallArgs.push_back(SourceBase);

1780 CallArgs.push_back(SourceOffset);

1781 CallArgs.push_back(LengthInBytes);

1782

1783 SmallVector<Type *, 8> DomainTy;

1784 for (Value *Arg : CallArgs)

1785 DomainTy.push_back(Arg->getType());

1786 auto *FTy = FunctionType::get(Type::getVoidTy(F->getContext()), DomainTy,

1787 /* isVarArg = */ false);

1788

1789 auto GetFunctionName = [](Intrinsic::ID IID, ConstantInt *ElementSizeCI) {

1790 uint64_t ElementSize = ElementSizeCI->getZExtValue();

1791 if (IID == Intrinsic::memcpy_element_unordered_atomic) {

1792 switch (ElementSize) {

1793 case 1:

1794 return "__llvm_memcpy_element_unordered_atomic_safepoint_1";

1795 case 2:

1796 return "__llvm_memcpy_element_unordered_atomic_safepoint_2";

1797 case 4:

1798 return "__llvm_memcpy_element_unordered_atomic_safepoint_4";

1799 case 8:

1800 return "__llvm_memcpy_element_unordered_atomic_safepoint_8";

1801 case 16:

1802 return "__llvm_memcpy_element_unordered_atomic_safepoint_16";

1803 default:

1804 llvm_unreachable("unexpected element size!");

1805 }

1806 }

1807 assert(IID == Intrinsic::memmove_element_unordered_atomic);

1808 switch (ElementSize) {

1809 case 1:

1810 return "__llvm_memmove_element_unordered_atomic_safepoint_1";

1811 case 2:

1812 return "__llvm_memmove_element_unordered_atomic_safepoint_2";

1813 case 4:

1814 return "__llvm_memmove_element_unordered_atomic_safepoint_4";

1815 case 8:

1816 return "__llvm_memmove_element_unordered_atomic_safepoint_8";

1817 case 16:

1818 return "__llvm_memmove_element_unordered_atomic_safepoint_16";

1819 default:

1820 llvm_unreachable("unexpected element size!");

1821 }

1822 };

1823

1824 CallTarget =

1825 F->getParent()

1826 ->getOrInsertFunction(GetFunctionName(IID, ElementSizeCI), FTy);

1827 }

1828 }

1829

1830 // Create the statepoint given all the arguments

1831 GCStatepointInst *Token = nullptr;

1832 if (auto *CI = dyn_cast<CallInst>(Call)) {

1833 CallInst *SPCall = Builder.CreateGCStatepointCall(

1834 StatepointID, NumPatchBytes, CallTarget, Flags, CallArgs,

1835 TransitionArgs, DeoptArgs, GCLive, "safepoint_token");

1836

1837 SPCall->setTailCallKind(CI->getTailCallKind());

1838 SPCall->setCallingConv(CI->getCallingConv());

1839

1840 // Set up function attrs directly on statepoint and return attrs later for

1841 // gc_result intrinsic.

1842 SPCall->setAttributes(

1843 legalizeCallAttributes(CI, IsMemIntrinsic, SPCall->getAttributes()));

1844

1845 Token = cast<GCStatepointInst>(SPCall);

1846

1847 // Put the following gc_result and gc_relocate calls immediately after the

1848 // the old call (which we're about to delete)

1849 assert(CI->getNextNode() && "Not a terminator, must have next!");

1850 Builder.SetInsertPoint(CI->getNextNode());

1851 Builder.SetCurrentDebugLocation(CI->getNextNode()->getDebugLoc());

1852 } else {

1853 auto *II = cast<InvokeInst>(Call);

1854

1855 // Insert the new invoke into the old block. We'll remove the old one in a

1856 // moment at which point this will become the new terminator for the

1857 // original block.

1858 InvokeInst *SPInvoke = Builder.CreateGCStatepointInvoke(

1859 StatepointID, NumPatchBytes, CallTarget, II->getNormalDest(),

1860 II->getUnwindDest(), Flags, CallArgs, TransitionArgs, DeoptArgs,

1861 GCLive, "statepoint_token");

1862

1863 SPInvoke->setCallingConv(II->getCallingConv());

1864

1865 // Set up function attrs directly on statepoint and return attrs later for

1866 // gc_result intrinsic.

1867 SPInvoke->setAttributes(

1868 legalizeCallAttributes(II, IsMemIntrinsic, SPInvoke->getAttributes()));

1869

1870 Token = cast<GCStatepointInst>(SPInvoke);

1871

1872 // Generate gc relocates in exceptional path

1873 BasicBlock *UnwindBlock = II->getUnwindDest();

1874 assert(!isa<PHINode>(UnwindBlock->begin()) &&

1875 UnwindBlock->getUniquePredecessor() &&

1876 "can't safely insert in this block!");

1877

1878 Builder.SetInsertPoint(UnwindBlock, UnwindBlock->getFirstInsertionPt());

1879 Builder.SetCurrentDebugLocation(II->getDebugLoc());

1880

1881 // Attach exceptional gc relocates to the landingpad.

1882 Instruction *ExceptionalToken = UnwindBlock->getLandingPadInst();

1883 Result.UnwindToken = ExceptionalToken;

1884

1885 CreateGCRelocates(LiveVariables, BasePtrs, ExceptionalToken, Builder, GC);

1886

1887 // Generate gc relocates and returns for normal block

1888 BasicBlock *NormalDest = II->getNormalDest();

1889 assert(!isa<PHINode>(NormalDest->begin()) &&

1890 NormalDest->getUniquePredecessor() &&

1891 "can't safely insert in this block!");

1892

1893 Builder.SetInsertPoint(NormalDest, NormalDest->getFirstInsertionPt());

1894

1895 // gc relocates will be generated later as if it were regular call

1896 // statepoint

1897 }

1898 assert(Token && "Should be set in one of the above branches!");

1899

1900 if (IsDeoptimize) {

1901 // If we're wrapping an @llvm.experimental.deoptimize in a statepoint, we

1902 // transform the tail-call like structure to a call to a void function

1903 // followed by unreachable to get better codegen.

1904 Replacements.push_back(

1905 DeferredReplacement::createDeoptimizeReplacement(Call));

1906 } else {

1907 Token->setName("statepoint_token");

1908 if (!Call->getType()->isVoidTy() && !Call->use_empty()) {

1909 StringRef Name = Call->hasName() ? Call->getName() : "";

1910 CallInst *GCResult = Builder.CreateGCResult(Token, Call->getType(), Name);

1911 GCResult->setAttributes(

1912 AttributeList::get(GCResult->getContext(), AttributeList::ReturnIndex,

1913 Call->getAttributes().getRetAttrs()));

1914

1915 // We cannot RAUW or delete CS.getInstruction() because it could be in the

1916 // live set of some other safepoint, in which case that safepoint's

1917 // PartiallyConstructedSafepointRecord will hold a raw pointer to this

1918 // llvm::Instruction. Instead, we defer the replacement and deletion to

1919 // after the live sets have been made explicit in the IR, and we no longer

1920 // have raw pointers to worry about.

1921 Replacements.emplace_back(

1922 DeferredReplacement::createRAUW(Call, GCResult));

1923 } else {

1924 Replacements.emplace_back(DeferredReplacement::createDelete(Call));

1925 }

1926 }

1927

1928 Result.StatepointToken = Token;

1929

1930 // Second, create a gc.relocate for every live variable

1931 CreateGCRelocates(LiveVariables, BasePtrs, Token, Builder, GC);

1932}

1933

1934// Replace an existing gc.statepoint with a new one and a set of gc.relocates

1935// which make the relocations happening at this safepoint explicit.

1936//

1937// WARNING: Does not do any fixup to adjust users of the original live

1938// values. That's the callers responsibility.

1939static void

1940 makeStatepointExplicit(DominatorTree &DT, CallBase *Call,

1941 PartiallyConstructedSafepointRecord &Result,

1942 std::vector<DeferredReplacement> &Replacements,

1943 const PointerToBaseTy &PointerToBase, GCStrategy *GC) {

1944 const auto &LiveSet = Result.LiveSet;

1945

1946 // Convert to vector for efficient cross referencing.

1947 SmallVector<Value *, 64> BaseVec, LiveVec;

1948 LiveVec.reserve(LiveSet.size());

1949 BaseVec.reserve(LiveSet.size());

1950 for (Value *L : LiveSet) {

1951 LiveVec.push_back(L);

1952 assert(PointerToBase.count(L));

1953 Value *Base = PointerToBase.find(L)->second;

1954 BaseVec.push_back(Base);

1955 }

1956 assert(LiveVec.size() == BaseVec.size());

1957

1958 // Do the actual rewriting and delete the old statepoint

1959 makeStatepointExplicitImpl(Call, BaseVec, LiveVec, Result, Replacements,

1960 PointerToBase, GC);

1961}

1962

1963// Helper function for the relocationViaAlloca.

1964//

1965// It receives iterator to the statepoint gc relocates and emits a store to the

1966// assigned location (via allocaMap) for the each one of them. It adds the

1967// visited values into the visitedLiveValues set, which we will later use them

1968// for validation checking.

1969static void

1970 insertRelocationStores(iterator_range<Value::user_iterator> GCRelocs,

1971 DenseMap<Value *, AllocaInst *> &AllocaMap,

1972 DenseSet<Value *> &VisitedLiveValues) {

1973 for (User *U : GCRelocs) {

1974 GCRelocateInst *Relocate = dyn_cast<GCRelocateInst>(U);

1975 if (!Relocate)

1976 continue;

1977

1978 Value *OriginalValue = Relocate->getDerivedPtr();

1979 assert(AllocaMap.count(OriginalValue));

1980 Value *Alloca = AllocaMap[OriginalValue];

1981

1982 // Emit store into the related alloca.

1983 assert(Relocate->getNextNode() &&

1984 "Should always have one since it's not a terminator");

1985 new StoreInst(Relocate, Alloca, std::next(Relocate->getIterator()));

1986

1987#ifndef NDEBUG

1988 VisitedLiveValues.insert(OriginalValue);

1989#endif

1990 }

1991}

1992

1993// Helper function for the "relocationViaAlloca". Similar to the

1994// "insertRelocationStores" but works for rematerialized values.

1995 static void insertRematerializationStores(

1996 const RematerializedValueMapTy &RematerializedValues,

1997 DenseMap<Value *, AllocaInst *> &AllocaMap,

1998 DenseSet<Value *> &VisitedLiveValues) {

1999 for (auto RematerializedValuePair: RematerializedValues) {

2000 Instruction *RematerializedValue = RematerializedValuePair.first;

2001 Value *OriginalValue = RematerializedValuePair.second;

2002

2003 assert(AllocaMap.count(OriginalValue) &&

2004 "Can not find alloca for rematerialized value");

2005 Value *Alloca = AllocaMap[OriginalValue];

2006

2007 new StoreInst(RematerializedValue, Alloca,

2008 std::next(RematerializedValue->getIterator()));

2009

2010#ifndef NDEBUG

2011 VisitedLiveValues.insert(OriginalValue);

2012#endif

2013 }

2014}

2015

2016/// Do all the relocation update via allocas and mem2reg

2017 static void relocationViaAlloca(

2018 Function &F, DominatorTree &DT, ArrayRef<Value *> Live,

2019 ArrayRef<PartiallyConstructedSafepointRecord> Records) {

2020#ifndef NDEBUG

2021 // record initial number of (static) allocas; we'll check we have the same

2022 // number when we get done.

2023 int InitialAllocaNum = 0;

2024 for (Instruction &I : F.getEntryBlock())

2025 if (isa<AllocaInst>(I))

2026 InitialAllocaNum++;

2027#endif

2028

2029 // TODO-PERF: change data structures, reserve

2030 DenseMap<Value *, AllocaInst *> AllocaMap;

2031 SmallVector<AllocaInst *, 200> PromotableAllocas;

2032 // Used later to chack that we have enough allocas to store all values

2033 std::size_t NumRematerializedValues = 0;

2034 PromotableAllocas.reserve(Live.size());

2035

2036 // Emit alloca for "LiveValue" and record it in "allocaMap" and

2037 // "PromotableAllocas"

2038 const DataLayout &DL = F.getDataLayout();

2039 auto emitAllocaFor = [&](Value *LiveValue) {

2040 AllocaInst *Alloca =

2041 new AllocaInst(LiveValue->getType(), DL.getAllocaAddrSpace(), "",

2042 F.getEntryBlock().getFirstNonPHIIt());

2043 AllocaMap[LiveValue] = Alloca;

2044 PromotableAllocas.push_back(Alloca);

2045 };

2046

2047 // Emit alloca for each live gc pointer

2048 for (Value *V : Live)

2049 emitAllocaFor(V);

2050

2051 // Emit allocas for rematerialized values

2052 for (const auto &Info : Records)

2053 for (auto RematerializedValuePair : Info.RematerializedValues) {

2054 Value *OriginalValue = RematerializedValuePair.second;

2055 if (AllocaMap.contains(OriginalValue))

2056 continue;

2057

2058 emitAllocaFor(OriginalValue);

2059 ++NumRematerializedValues;

2060 }

2061

2062 // The next two loops are part of the same conceptual operation. We need to

2063 // insert a store to the alloca after the original def and at each

2064 // redefinition. We need to insert a load before each use. These are split

2065 // into distinct loops for performance reasons.

2066

2067 // Update gc pointer after each statepoint: either store a relocated value or

2068 // null (if no relocated value was found for this gc pointer and it is not a

2069 // gc_result). This must happen before we update the statepoint with load of

2070 // alloca otherwise we lose the link between statepoint and old def.

2071 for (const auto &Info : Records) {

2072 Value *Statepoint = Info.StatepointToken;

2073

2074 // This will be used for consistency check

2075 DenseSet<Value *> VisitedLiveValues;

2076

2077 // Insert stores for normal statepoint gc relocates

2078 insertRelocationStores(Statepoint->users(), AllocaMap, VisitedLiveValues);

2079

2080 // In case if it was invoke statepoint

2081 // we will insert stores for exceptional path gc relocates.

2082 if (isa<InvokeInst>(Statepoint)) {

2083 insertRelocationStores(Info.UnwindToken->users(), AllocaMap,

2084 VisitedLiveValues);

2085 }

2086

2087 // Do similar thing with rematerialized values

2088 insertRematerializationStores(Info.RematerializedValues, AllocaMap,

2089 VisitedLiveValues);

2090

2091 if (ClobberNonLive) {

2092 // As a debugging aid, pretend that an unrelocated pointer becomes null at

2093 // the gc.statepoint. This will turn some subtle GC problems into

2094 // slightly easier to debug SEGVs. Note that on large IR files with

2095 // lots of gc.statepoints this is extremely costly both memory and time

2096 // wise.

2097 SmallVector<AllocaInst *, 64> ToClobber;

2098 for (auto Pair : AllocaMap) {

2099 Value *Def = Pair.first;

2100 AllocaInst *Alloca = Pair.second;

2101

2102 // This value was relocated

2103 if (VisitedLiveValues.count(Def)) {

2104 continue;

2105 }

2106 ToClobber.push_back(Alloca);

2107 }

2108

2109 auto InsertClobbersAt = [&](BasicBlock::iterator IP) {

2110 for (auto *AI : ToClobber) {

2111 auto AT = AI->getAllocatedType();

2112 Constant *CPN;

2113 if (AT->isVectorTy())

2114 CPN = ConstantAggregateZero::get(AT);

2115 else

2116 CPN = ConstantPointerNull::get(cast<PointerType>(AT));

2117 new StoreInst(CPN, AI, IP);

2118 }

2119 };

2120

2121 // Insert the clobbering stores. These may get intermixed with the

2122 // gc.results and gc.relocates, but that's fine.

2123 if (auto II = dyn_cast<InvokeInst>(Statepoint)) {

2124 InsertClobbersAt(II->getNormalDest()->getFirstInsertionPt());

2125 InsertClobbersAt(II->getUnwindDest()->getFirstInsertionPt());

2126 } else {

2127 InsertClobbersAt(

2128 std::next(cast<Instruction>(Statepoint)->getIterator()));

2129 }

2130 }

2131 }

2132

2133 // Update use with load allocas and add store for gc_relocated.

2134 for (auto Pair : AllocaMap) {

2135 Value *Def = Pair.first;

2136 AllocaInst *Alloca = Pair.second;

2137

2138 // We pre-record the uses of allocas so that we dont have to worry about

2139 // later update that changes the user information..

2140

2141 SmallVector<Instruction *, 20> Uses;

2142 // PERF: trade a linear scan for repeated reallocation

2143 Uses.reserve(Def->getNumUses());

2144 for (User *U : Def->users()) {

2145 if (!isa<ConstantExpr>(U)) {

2146 // If the def has a ConstantExpr use, then the def is either a

2147 // ConstantExpr use itself or null. In either case

2148 // (recursively in the first, directly in the second), the oop

2149 // it is ultimately dependent on is null and this particular

2150 // use does not need to be fixed up.

2151 Uses.push_back(cast<Instruction>(U));

2152 }

2153 }

2154

2155 llvm::sort(Uses);

2156 auto Last = llvm::unique(Uses);

2157 Uses.erase(Last, Uses.end());

2158

2159 for (Instruction *Use : Uses) {

2160 if (isa<PHINode>(Use)) {

2161 PHINode *Phi = cast<PHINode>(Use);

2162 for (unsigned i = 0; i < Phi->getNumIncomingValues(); i++) {

2163 if (Def == Phi->getIncomingValue(i)) {

2164 LoadInst *Load = new LoadInst(

2165 Alloca->getAllocatedType(), Alloca, "",

2166 Phi->getIncomingBlock(i)->getTerminator()->getIterator());

2167 Phi->setIncomingValue(i, Load);

2168 }

2169 }

2170 } else {

2171 LoadInst *Load = new LoadInst(Alloca->getAllocatedType(), Alloca, "",

2172 Use->getIterator());

2173 Use->replaceUsesOfWith(Def, Load);

2174 }

2175 }

2176

2177 // Emit store for the initial gc value. Store must be inserted after load,

2178 // otherwise store will be in alloca's use list and an extra load will be

2179 // inserted before it.

2180 StoreInst *Store = new StoreInst(Def, Alloca, /*volatile*/ false,

2181 DL.getABITypeAlign(Def->getType()));

2182 if (Instruction *Inst = dyn_cast<Instruction>(Def)) {

2183 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Inst)) {

2184 // InvokeInst is a terminator so the store need to be inserted into its

2185 // normal destination block.

2186 BasicBlock *NormalDest = Invoke->getNormalDest();

2187 Store->insertBefore(NormalDest->getFirstNonPHIIt());

2188 } else {

2189 assert(!Inst->isTerminator() &&

2190 "The only terminator that can produce a value is "

2191 "InvokeInst which is handled above.");

2192 Store->insertAfter(Inst->getIterator());

2193 }

2194 } else {

2195 assert(isa<Argument>(Def));

2196 Store->insertAfter(cast<Instruction>(Alloca)->getIterator());

2197 }

2198 }

2199

2200 assert(PromotableAllocas.size() == Live.size() + NumRematerializedValues &&

2201 "we must have the same allocas with lives");

2202 (void) NumRematerializedValues;

2203 if (!PromotableAllocas.empty()) {

2204 // Apply mem2reg to promote alloca to SSA

2205 PromoteMemToReg(PromotableAllocas, DT);

2206 }

2207

2208#ifndef NDEBUG

2209 for (auto &I : F.getEntryBlock())

2210 if (isa<AllocaInst>(I))

2211 InitialAllocaNum--;

2212 assert(InitialAllocaNum == 0 && "We must not introduce any extra allocas");

2213#endif

2214}

2215

2216/// Insert holders so that each Value is obviously live through the entire

2217/// lifetime of the call.

2218 static void insertUseHolderAfter(CallBase *Call, const ArrayRef<Value *> Values,

2219 SmallVectorImpl<CallInst *> &Holders) {

2220 if (Values.empty())

2221 // No values to hold live, might as well not insert the empty holder

2222 return;

2223

2224 Module *M = Call->getModule();

2225 // Use a dummy vararg function to actually hold the values live

2226 FunctionCallee Func = M->getOrInsertFunction(

2227 "__tmp_use", FunctionType::get(Type::getVoidTy(M->getContext()), true));

2228 if (isa<CallInst>(Call)) {

2229 // For call safepoints insert dummy calls right after safepoint

2230 Holders.push_back(

2231 CallInst::Create(Func, Values, "", std::next(Call->getIterator())));

2232 return;

2233 }

2234 // For invoke safepooints insert dummy calls both in normal and

2235 // exceptional destination blocks

2236 auto *II = cast<InvokeInst>(Call);

2237 Holders.push_back(CallInst::Create(

2238 Func, Values, "", II->getNormalDest()->getFirstInsertionPt()));

2239 Holders.push_back(CallInst::Create(

2240 Func, Values, "", II->getUnwindDest()->getFirstInsertionPt()));

2241}

2242

2243 static void findLiveReferences(

2244 Function &F, DominatorTree &DT, ArrayRef<CallBase *> toUpdate,

2245 MutableArrayRef<struct PartiallyConstructedSafepointRecord> records,

2246 GCStrategy *GC) {

2247 GCPtrLivenessData OriginalLivenessData;

2248 computeLiveInValues(DT, F, OriginalLivenessData, GC);

2249 for (size_t i = 0; i < records.size(); i++) {

2250 struct PartiallyConstructedSafepointRecord &info = records[i];

2251 analyzeParsePointLiveness(DT, OriginalLivenessData, toUpdate[i], info, GC);

2252 }

2253}

2254

2255// Helper function for the "rematerializeLiveValues". It walks use chain

2256// starting from the "CurrentValue" until it reaches the root of the chain, i.e.

2257// the base or a value it cannot process. Only "simple" values are processed

2258// (currently it is GEP's and casts). The returned root is examined by the

2259// callers of findRematerializableChainToBasePointer. Fills "ChainToBase" array

2260// with all visited values.

2261 static Value* findRematerializableChainToBasePointer(

2262 SmallVectorImpl<Instruction*> &ChainToBase,

2263 Value *CurrentValue) {

2264 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurrentValue)) {

2265 ChainToBase.push_back(GEP);

2266 return findRematerializableChainToBasePointer(ChainToBase,

2267 GEP->getPointerOperand());

2268 }

2269

2270 if (CastInst *CI = dyn_cast<CastInst>(CurrentValue)) {

2271 if (!CI->isNoopCast(CI->getDataLayout()))

2272 return CI;

2273

2274 ChainToBase.push_back(CI);

2275 return findRematerializableChainToBasePointer(ChainToBase,

2276 CI->getOperand(0));

2277 }

2278

2279 // We have reached the root of the chain, which is either equal to the base or

2280 // is the first unsupported value along the use chain.

2281 return CurrentValue;

2282}

2283

2284// Helper function for the "rematerializeLiveValues". Compute cost of the use

2285// chain we are going to rematerialize.

2286static InstructionCost

2287 chainToBasePointerCost(SmallVectorImpl<Instruction *> &Chain,

2288 TargetTransformInfo &TTI) {

2289 InstructionCost Cost = 0;

2290

2291 for (Instruction *Instr : Chain) {

2292 if (CastInst *CI = dyn_cast<CastInst>(Instr)) {

2293 assert(CI->isNoopCast(CI->getDataLayout()) &&

2294 "non noop cast is found during rematerialization");

2295

2296 Type *SrcTy = CI->getOperand(0)->getType();

2297 Cost += TTI.getCastInstrCost(CI->getOpcode(), CI->getType(), SrcTy,

2298 TTI::getCastContextHint(CI),

2299 TargetTransformInfo::TCK_SizeAndLatency, CI);

2300

2301 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Instr)) {

2302 // Cost of the address calculation

2303 Cost += TTI.getAddressComputationCost(

2304 GEP->getType(), nullptr, nullptr,

2305 TargetTransformInfo::TCK_SizeAndLatency);

2306

2307 // And cost of the GEP itself

2308 // TODO: Use TTI->getGEPCost here (it exists, but appears to be not

2309 // allowed for the external usage)

2310 if (!GEP->hasAllConstantIndices())

2311 Cost += 2;

2312

2313 } else {

2314 llvm_unreachable("unsupported instruction type during rematerialization");

2315 }

2316 }

2317

2318 return Cost;

2319}

2320

2321 static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi) {

2322 unsigned PhiNum = OrigRootPhi.getNumIncomingValues();

2323 if (PhiNum != AlternateRootPhi.getNumIncomingValues() ||

2324 OrigRootPhi.getParent() != AlternateRootPhi.getParent())

2325 return false;

2326 // Map of incoming values and their corresponding basic blocks of

2327 // OrigRootPhi.

2328 SmallDenseMap<Value *, BasicBlock *, 8> CurrentIncomingValues;

2329 for (unsigned i = 0; i < PhiNum; i++)

2330 CurrentIncomingValues[OrigRootPhi.getIncomingValue(i)] =

2331 OrigRootPhi.getIncomingBlock(i);

2332

2333 // Both current and base PHIs should have same incoming values and

2334 // the same basic blocks corresponding to the incoming values.

2335 for (unsigned i = 0; i < PhiNum; i++) {

2336 auto CIVI =

2337 CurrentIncomingValues.find(AlternateRootPhi.getIncomingValue(i));

2338 if (CIVI == CurrentIncomingValues.end())

2339 return false;

2340 BasicBlock *CurrentIncomingBB = CIVI->second;

2341 if (CurrentIncomingBB != AlternateRootPhi.getIncomingBlock(i))

2342 return false;

2343 }

2344 return true;

2345}

2346

2347// Find derived pointers that can be recomputed cheap enough and fill

2348// RematerizationCandidates with such candidates.

2349static void

2350 findRematerializationCandidates(PointerToBaseTy PointerToBase,

2351 RematCandTy &RematerizationCandidates,

2352 TargetTransformInfo &TTI) {

2353 const unsigned int ChainLengthThreshold = 10;

2354

2355 for (auto P2B : PointerToBase) {

2356 auto *Derived = P2B.first;

2357 auto *Base = P2B.second;

2358 // Consider only derived pointers.

2359 if (Derived == Base)

2360 continue;

2361

2362 // For each live pointer find its defining chain.

2363 SmallVector<Instruction *, 3> ChainToBase;

2364 Value *RootOfChain =

2365 findRematerializableChainToBasePointer(ChainToBase, Derived);

2366

2367 // Nothing to do, or chain is too long

2368 if ( ChainToBase.size() == 0 ||

2369 ChainToBase.size() > ChainLengthThreshold)

2370 continue;

2371

2372 // Handle the scenario where the RootOfChain is not equal to the

2373 // Base Value, but they are essentially the same phi values.

2374 if (Value *BaseVal = PointerToBase[Derived]; RootOfChain != BaseVal) {

2375 PHINode *OrigRootPhi = dyn_cast<PHINode>(RootOfChain);

2376 PHINode *AlternateRootPhi = dyn_cast<PHINode>(BaseVal);

2377 if (!OrigRootPhi || !AlternateRootPhi)

2378 continue;

2379 // PHI nodes that have the same incoming values, and belonging to the same

2380 // basic blocks are essentially the same SSA value. When the original phi

2381 // has incoming values with different base pointers, the original phi is

2382 // marked as conflict, and an additional `AlternateRootPhi` with the same

2383 // incoming values get generated by the findBasePointer function. We need

2384 // to identify the newly generated AlternateRootPhi (.base version of phi)

2385 // and RootOfChain (the original phi node itself) are the same, so that we

2386 // can rematerialize the gep and casts. This is a workaround for the

2387 // deficiency in the findBasePointer algorithm.

2388 if (!AreEquivalentPhiNodes(*OrigRootPhi, *AlternateRootPhi))

2389 continue;

2390 }

2391 // Compute cost of this chain.

2392 InstructionCost Cost = chainToBasePointerCost(ChainToBase, TTI);

2393 // TODO: We can also account for cases when we will be able to remove some

2394 // of the rematerialized values by later optimization passes. I.e if

2395 // we rematerialized several intersecting chains. Or if original values

2396 // don't have any uses besides this statepoint.

2397

2398 // Ok, there is a candidate.

2399 RematerizlizationCandidateRecord Record;

2400 Record.ChainToBase = ChainToBase;

2401 Record.RootOfChain = RootOfChain;

2402 Record.Cost = Cost;

2403 RematerizationCandidates.insert({ Derived, Record });

2404 }

2405}

2406

2407// Try to rematerialize derived pointers immediately before their uses

2408// (instead of rematerializing after every statepoint it is live through).

2409// This can be beneficial when derived pointer is live across many

2410// statepoints, but uses are rare.

2411 static void rematerializeLiveValuesAtUses(

2412 RematCandTy &RematerizationCandidates,

2413 MutableArrayRef<PartiallyConstructedSafepointRecord> Records,

2414 PointerToBaseTy &PointerToBase) {

2415 if (!RematDerivedAtUses)

2416 return;

2417

2418 SmallVector<Instruction *, 32> LiveValuesToBeDeleted;

2419

2420 LLVM_DEBUG(dbgs() << "Rematerialize derived pointers at uses, "

2421 << "Num statepoints: " << Records.size() << '\n');

2422

2423 for (auto &It : RematerizationCandidates) {

2424 Instruction *Cand = cast<Instruction>(It.first);

2425 auto &Record = It.second;

2426

2427 if (Record.Cost >= RematerializationThreshold)

2428 continue;

2429

2430 if (Cand->user_empty())

2431 continue;

2432

2433 if (Cand->hasOneUse())

2434 if (auto *U = dyn_cast<Instruction>(Cand->getUniqueUndroppableUser()))

2435 if (U->getParent() == Cand->getParent())

2436 continue;

2437

2438 // Rematerialization before PHI nodes is not implemented.

2439 if (llvm::any_of(Cand->users(),

2440 [](const auto *U) { return isa<PHINode>(U); }))

2441 continue;

2442

2443 LLVM_DEBUG(dbgs() << "Trying cand " << *Cand << " ... ");

2444

2445 // Count of rematerialization instructions we introduce is equal to number

2446 // of candidate uses.

2447 // Count of rematerialization instructions we eliminate is equal to number

2448 // of statepoints it is live through.

2449 // Consider transformation profitable if latter is greater than former

2450 // (in other words, we create less than eliminate).

2451 unsigned NumLiveStatepoints = llvm::count_if(

2452 Records, [Cand](const auto &R) { return R.LiveSet.contains(Cand); });

2453 unsigned NumUses = Cand->getNumUses();

2454

2455 LLVM_DEBUG(dbgs() << "Num uses: " << NumUses << " Num live statepoints: "

2456 << NumLiveStatepoints << " ");

2457

2458 if (NumLiveStatepoints < NumUses) {

2459 LLVM_DEBUG(dbgs() << "not profitable\n");

2460 continue;

2461 }

2462

2463 // If rematerialization is 'free', then favor rematerialization at

2464 // uses as it generally shortens live ranges.

2465 // TODO: Short (size ==1) chains only?

2466 if (NumLiveStatepoints == NumUses && Record.Cost > 0) {

2467 LLVM_DEBUG(dbgs() << "not profitable\n");

2468 continue;

2469 }

2470

2471 LLVM_DEBUG(dbgs() << "looks profitable\n");

2472

2473 // ChainToBase may contain another remat candidate (as a sub chain) which

2474 // has been rewritten by now. Need to recollect chain to have up to date

2475 // value.

2476 // TODO: sort records in findRematerializationCandidates() in

2477 // decreasing chain size order?

2478 if (Record.ChainToBase.size() > 1) {

2479 Record.ChainToBase.clear();

2480 findRematerializableChainToBasePointer(Record.ChainToBase, Cand);

2481 }

2482

2483 // Current rematerialization algorithm is very simple: we rematerialize

2484 // immediately before EVERY use, even if there are several uses in same

2485 // block or if use is local to Cand Def. The reason is that this allows

2486 // us to avoid recomputing liveness without complicated analysis:

2487 // - If we did not eliminate all uses of original Candidate, we do not

2488 // know exaclty in what BBs it is still live.

2489 // - If we rematerialize once per BB, we need to find proper insertion

2490 // place (first use in block, but after Def) and analyze if there is

2491 // statepoint between uses in the block.

2492 while (!Cand->user_empty()) {

2493 Instruction *UserI = cast<Instruction>(*Cand->user_begin());

2494 Instruction *RematChain =

2495 rematerializeChain(Record.ChainToBase, UserI->getIterator(),

2496 Record.RootOfChain, PointerToBase[Cand]);

2497 UserI->replaceUsesOfWith(Cand, RematChain);

2498 PointerToBase[RematChain] = PointerToBase[Cand];

2499 }

2500 LiveValuesToBeDeleted.push_back(Cand);

2501 }

2502

2503 LLVM_DEBUG(dbgs() << "Rematerialized " << LiveValuesToBeDeleted.size()

2504 << " derived pointers\n");

2505 for (auto *Cand : LiveValuesToBeDeleted) {

2506 assert(Cand->use_empty() && "Unexpected user remain");

2507 RematerizationCandidates.erase(Cand);

2508 for (auto &R : Records) {

2509 assert(!R.LiveSet.contains(Cand) ||

2510 R.LiveSet.contains(PointerToBase[Cand]));

2511 R.LiveSet.remove(Cand);

2512 }

2513 }

2514

2515 // Recollect not rematerialized chains - we might have rewritten

2516 // their sub-chains.

2517 if (!LiveValuesToBeDeleted.empty()) {

2518 for (auto &P : RematerizationCandidates) {

2519 auto &R = P.second;

2520 if (R.ChainToBase.size() > 1) {

2521 R.ChainToBase.clear();

2522 findRematerializableChainToBasePointer(R.ChainToBase, P.first);

2523 }

2524 }

2525 }

2526}

2527

2528// From the statepoint live set pick values that are cheaper to recompute then

2529// to relocate. Remove this values from the live set, rematerialize them after

2530// statepoint and record them in "Info" structure. Note that similar to

2531// relocated values we don't do any user adjustments here.

2532 static void rematerializeLiveValues(CallBase *Call,

2533 PartiallyConstructedSafepointRecord &Info,

2534 PointerToBaseTy &PointerToBase,

2535 RematCandTy &RematerizationCandidates,

2536 TargetTransformInfo &TTI) {

2537 // Record values we are going to delete from this statepoint live set.

2538 // We can not di this in following loop due to iterator invalidation.

2539 SmallVector<Value *, 32> LiveValuesToBeDeleted;

2540

2541 for (Value *LiveValue : Info.LiveSet) {

2542 auto It = RematerizationCandidates.find(LiveValue);

2543 if (It == RematerizationCandidates.end())

2544 continue;

2545

2546 RematerizlizationCandidateRecord &Record = It->second;

2547

2548 InstructionCost Cost = Record.Cost;

2549 // For invokes we need to rematerialize each chain twice - for normal and

2550 // for unwind basic blocks. Model this by multiplying cost by two.

2551 if (isa<InvokeInst>(Call))

2552 Cost *= 2;

2553

2554 // If it's too expensive - skip it.

2555 if (Cost >= RematerializationThreshold)

2556 continue;

2557

2558 // Remove value from the live set

2559 LiveValuesToBeDeleted.push_back(LiveValue);

2560

2561 // Clone instructions and record them inside "Info" structure.

2562

2563 // Different cases for calls and invokes. For invokes we need to clone

2564 // instructions both on normal and unwind path.

2565 if (isa<CallInst>(Call)) {

2566 Instruction *InsertBefore = Call->getNextNode();

2567 assert(InsertBefore);

2568 Instruction *RematerializedValue =

2569 rematerializeChain(Record.ChainToBase, InsertBefore->getIterator(),

2570 Record.RootOfChain, PointerToBase[LiveValue]);

2571 Info.RematerializedValues[RematerializedValue] = LiveValue;

2572 } else {

2573 auto *Invoke = cast<InvokeInst>(Call);

2574

2575 BasicBlock::iterator NormalInsertBefore =

2576 Invoke->getNormalDest()->getFirstInsertionPt();

2577 BasicBlock::iterator UnwindInsertBefore =

2578 Invoke->getUnwindDest()->getFirstInsertionPt();

2579

2580 Instruction *NormalRematerializedValue =

2581 rematerializeChain(Record.ChainToBase, NormalInsertBefore,

2582 Record.RootOfChain, PointerToBase[LiveValue]);

2583 Instruction *UnwindRematerializedValue =

2584 rematerializeChain(Record.ChainToBase, UnwindInsertBefore,

2585 Record.RootOfChain, PointerToBase[LiveValue]);

2586

2587 Info.RematerializedValues[NormalRematerializedValue] = LiveValue;

2588 Info.RematerializedValues[UnwindRematerializedValue] = LiveValue;

2589 }

2590 }

2591

2592 // Remove rematerialized values from the live set.

2593 for (auto *LiveValue: LiveValuesToBeDeleted) {

2594 Info.LiveSet.remove(LiveValue);

2595 }

2596}

2597

2598 static bool inlineGetBaseAndOffset(Function &F,

2599 SmallVectorImpl<CallInst *> &Intrinsics,

2600 DefiningValueMapTy &DVCache,

2601 IsKnownBaseMapTy &KnownBases) {

2602 auto &Context = F.getContext();

2603 auto &DL = F.getDataLayout();

2604 bool Changed = false;

2605

2606 for (auto *Callsite : Intrinsics)

2607 switch (Callsite->getIntrinsicID()) {

2608 case Intrinsic::experimental_gc_get_pointer_base: {

2609 Changed = true;

2610 Value *Base =

2611 findBasePointer(Callsite->getOperand(0), DVCache, KnownBases);

2612 assert(!DVCache.count(Callsite));

2613 Callsite->replaceAllUsesWith(Base);

2614 if (!Base->hasName())

2615 Base->takeName(Callsite);

2616 Callsite->eraseFromParent();

2617 break;

2618 }

2619 case Intrinsic::experimental_gc_get_pointer_offset: {

2620 Changed = true;

2621 Value *Derived = Callsite->getOperand(0);

2622 Value *Base = findBasePointer(Derived, DVCache, KnownBases);

2623 assert(!DVCache.count(Callsite));

2624 unsigned AddressSpace = Derived->getType()->getPointerAddressSpace();

2625 unsigned IntPtrSize = DL.getPointerSizeInBits(AddressSpace);

2626 IRBuilder<> Builder(Callsite);

2627 Value *BaseInt =

2628 Builder.CreatePtrToInt(Base, Type::getIntNTy(Context, IntPtrSize),

2629 suffixed_name_or(Base, ".int", ""));

2630 Value *DerivedInt =

2631 Builder.CreatePtrToInt(Derived, Type::getIntNTy(Context, IntPtrSize),

2632 suffixed_name_or(Derived, ".int", ""));

2633 Value *Offset = Builder.CreateSub(DerivedInt, BaseInt);

2634 Callsite->replaceAllUsesWith(Offset);

2635 Offset->takeName(Callsite);

2636 Callsite->eraseFromParent();

2637 break;

2638 }

2639 default:

2640 llvm_unreachable("Unknown intrinsic");

2641 }

2642

2643 return Changed;

2644}

2645

2646 static bool insertParsePoints(Function &F, DominatorTree &DT,

2647 TargetTransformInfo &TTI,

2648 SmallVectorImpl<CallBase *> &ToUpdate,

2649 DefiningValueMapTy &DVCache,

2650 IsKnownBaseMapTy &KnownBases) {

2651 std::unique_ptr<GCStrategy> GC = findGCStrategy(F);

2652

2653#ifndef NDEBUG

2654 // Validate the input

2655 std::set<CallBase *> Uniqued;

2656 Uniqued.insert(ToUpdate.begin(), ToUpdate.end());

2657 assert(Uniqued.size() == ToUpdate.size() && "no duplicates please!");

2658

2659 for (CallBase *Call : ToUpdate)

2660 assert(Call->getFunction() == &F);

2661#endif

2662

2663 // When inserting gc.relocates for invokes, we need to be able to insert at

2664 // the top of the successor blocks. See the comment on

2665 // normalForInvokeSafepoint on exactly what is needed. Note that this step

2666 // may restructure the CFG.

2667 for (CallBase *Call : ToUpdate) {

2668 auto *II = dyn_cast<InvokeInst>(Call);

2669 if (!II)

2670 continue;

2671 normalizeForInvokeSafepoint(II->getNormalDest(), II->getParent(), DT);

2672 normalizeForInvokeSafepoint(II->getUnwindDest(), II->getParent(), DT);

2673 }

2674

2675 // A list of dummy calls added to the IR to keep various values obviously

2676 // live in the IR. We'll remove all of these when done.

2677 SmallVector<CallInst *, 64> Holders;

2678

2679 // Insert a dummy call with all of the deopt operands we'll need for the

2680 // actual safepoint insertion as arguments. This ensures reference operands

2681 // in the deopt argument list are considered live through the safepoint (and

2682 // thus makes sure they get relocated.)

2683 for (CallBase *Call : ToUpdate) {

2684 SmallVector<Value *, 64> DeoptValues;

2685

2686 for (Value *Arg : GetDeoptBundleOperands(Call)) {

2687 assert(!isUnhandledGCPointerType(Arg->getType(), GC.get()) &&

2688 "support for FCA unimplemented");

2689 if (isHandledGCPointerType(Arg->getType(), GC.get()))

2690 DeoptValues.push_back(Arg);

2691 }

2692

2693 insertUseHolderAfter(Call, DeoptValues, Holders);

2694 }

2695

2696 SmallVector<PartiallyConstructedSafepointRecord, 64> Records(ToUpdate.size());

2697

2698 // A) Identify all gc pointers which are statically live at the given call

2699 // site.

2700 findLiveReferences(F, DT, ToUpdate, Records, GC.get());

2701

2702 /// Global mapping from live pointers to a base-defining-value.

2703 PointerToBaseTy PointerToBase;

2704

2705 // B) Find the base pointers for each live pointer

2706 for (size_t i = 0; i < Records.size(); i++) {

2707 PartiallyConstructedSafepointRecord &info = Records[i];

2708 findBasePointers(DT, DVCache, ToUpdate[i], info, PointerToBase, KnownBases);

2709 }

2710 if (PrintBasePointers) {

2711 errs() << "Base Pairs (w/o Relocation):\n";

2712 for (auto &Pair : PointerToBase) {

2713 errs() << " derived ";

2714 Pair.first->printAsOperand(errs(), false);

2715 errs() << " base ";

2716 Pair.second->printAsOperand(errs(), false);

2717 errs() << "\n";

2718 ;

2719 }

2720 }

2721

2722 // The base phi insertion logic (for any safepoint) may have inserted new

2723 // instructions which are now live at some safepoint. The simplest such

2724 // example is:

2725 // loop:

2726 // phi a <-- will be a new base_phi here

2727 // safepoint 1 <-- that needs to be live here

2728 // gep a + 1

2729 // safepoint 2

2730 // br loop

2731 // We insert some dummy calls after each safepoint to definitely hold live

2732 // the base pointers which were identified for that safepoint. We'll then

2733 // ask liveness for _every_ base inserted to see what is now live. Then we

2734 // remove the dummy calls.

2735 Holders.reserve(Holders.size() + Records.size());

2736 for (size_t i = 0; i < Records.size(); i++) {

2737 PartiallyConstructedSafepointRecord &Info = Records[i];

2738

2739 SmallVector<Value *, 128> Bases;

2740 for (auto *Derived : Info.LiveSet) {

2741 assert(PointerToBase.count(Derived) && "Missed base for derived pointer");

2742 Bases.push_back(PointerToBase[Derived]);

2743 }

2744

2745 insertUseHolderAfter(ToUpdate[i], Bases, Holders);

2746 }

2747

2748 // By selecting base pointers, we've effectively inserted new uses. Thus, we

2749 // need to rerun liveness. We may *also* have inserted new defs, but that's

2750 // not the key issue.

2751 recomputeLiveInValues(F, DT, ToUpdate, Records, PointerToBase, GC.get());

2752

2753 if (PrintBasePointers) {

2754 errs() << "Base Pairs: (w/Relocation)\n";

2755 for (auto Pair : PointerToBase) {

2756 errs() << " derived ";

2757 Pair.first->printAsOperand(errs(), false);

2758 errs() << " base ";

2759 Pair.second->printAsOperand(errs(), false);

2760 errs() << "\n";

2761 }

2762 }

2763

2764 // It is possible that non-constant live variables have a constant base. For

2765 // example, a GEP with a variable offset from a global. In this case we can

2766 // remove it from the liveset. We already don't add constants to the liveset

2767 // because we assume they won't move at runtime and the GC doesn't need to be

2768 // informed about them. The same reasoning applies if the base is constant.

2769 // Note that the relocation placement code relies on this filtering for

2770 // correctness as it expects the base to be in the liveset, which isn't true

2771 // if the base is constant.

2772 for (auto &Info : Records) {

2773 Info.LiveSet.remove_if([&](Value *LiveV) {

2774 assert(PointerToBase.count(LiveV) && "Missed base for derived pointer");

2775 return isa<Constant>(PointerToBase[LiveV]);

2776 });

2777 }

2778

2779 for (CallInst *CI : Holders)

2780 CI->eraseFromParent();

2781

2782 Holders.clear();

2783

2784 // Compute the cost of possible re-materialization of derived pointers.

2785 RematCandTy RematerizationCandidates;

2786 findRematerializationCandidates(PointerToBase, RematerizationCandidates, TTI);

2787

2788 // In order to reduce live set of statepoint we might choose to rematerialize

2789 // some values instead of relocating them. This is purely an optimization and

2790 // does not influence correctness.

2791 // First try rematerialization at uses, then after statepoints.

2792 rematerializeLiveValuesAtUses(RematerizationCandidates, Records,

2793 PointerToBase);

2794 for (size_t i = 0; i < Records.size(); i++)

2795 rematerializeLiveValues(ToUpdate[i], Records[i], PointerToBase,

2796 RematerizationCandidates, TTI);

2797

2798 // We need this to safely RAUW and delete call or invoke return values that

2799 // may themselves be live over a statepoint. For details, please see usage in

2800 // makeStatepointExplicitImpl.

2801 std::vector<DeferredReplacement> Replacements;

2802

2803 // Now run through and replace the existing statepoints with new ones with

2804 // the live variables listed. We do not yet update uses of the values being

2805 // relocated. We have references to live variables that need to

2806 // survive to the last iteration of this loop. (By construction, the

2807 // previous statepoint can not be a live variable, thus we can and remove

2808 // the old statepoint calls as we go.)

2809 for (size_t i = 0; i < Records.size(); i++)

2810 makeStatepointExplicit(DT, ToUpdate[i], Records[i], Replacements,

2811 PointerToBase, GC.get());

2812

2813 ToUpdate.clear(); // prevent accident use of invalid calls.

2814

2815 for (auto &PR : Replacements)

2816 PR.doReplacement();

2817

2818 Replacements.clear();

2819

2820 for (auto &Info : Records) {

2821 // These live sets may contain state Value pointers, since we replaced calls

2822 // with operand bundles with calls wrapped in gc.statepoint, and some of

2823 // those calls may have been def'ing live gc pointers. Clear these out to

2824 // avoid accidentally using them.

2825 //

2826 // TODO: We should create a separate data structure that does not contain

2827 // these live sets, and migrate to using that data structure from this point

2828 // onward.

2829 Info.LiveSet.clear();

2830 }

2831 PointerToBase.clear();

2832

2833 // Do all the fixups of the original live variables to their relocated selves.

2834 // A SmallSetVector is used to collect live variables while retaining the

2835 // order in which we add them, which is important for reproducible tests.

2836 SmallSetVector<Value *, 16> Live;

2837 for (const PartiallyConstructedSafepointRecord &Info : Records) {

2838 // We can't simply save the live set from the original insertion. One of

2839 // the live values might be the result of a call which needs a safepoint.

2840 // That Value* no longer exists and we need to use the new gc_result.

2841 // Thankfully, the live set is embedded in the statepoint (and updated), so

2842 // we just grab that.

2843 Live.insert_range(Info.StatepointToken->gc_live());

2844#ifndef NDEBUG

2845 // Do some basic validation checking on our liveness results before

2846 // performing relocation. Relocation can and will turn mistakes in liveness

2847 // results into non-sensical code which is must harder to debug.

2848 // TODO: It would be nice to test consistency as well

2849 assert(DT.isReachableFromEntry(Info.StatepointToken->getParent()) &&

2850 "statepoint must be reachable or liveness is meaningless");

2851 for (Value *V : Info.StatepointToken->gc_live()) {

2852 if (!isa<Instruction>(V))

2853 // Non-instruction values trivial dominate all possible uses

2854 continue;

2855 auto *LiveInst = cast<Instruction>(V);

2856 assert(DT.isReachableFromEntry(LiveInst->getParent()) &&

2857 "unreachable values should never be live");

2858 assert(DT.dominates(LiveInst, Info.StatepointToken) &&

2859 "basic SSA liveness expectation violated by liveness analysis");

2860 }

2861#endif

2862 }

2863

2864#ifndef NDEBUG

2865 // Validation check

2866 for (auto *Ptr : Live)

2867 assert(isHandledGCPointerType(Ptr->getType(), GC.get()) &&

2868 "must be a gc pointer type");

2869#endif

2870

2871 relocationViaAlloca(F, DT, Live.getArrayRef(), Records);

2872 return !Records.empty();

2873}

2874

2875// List of all parameter and return attributes which must be stripped when

2876// lowering from the abstract machine model. Note that we list attributes

2877// here which aren't valid as return attributes, that is okay.

2878 static AttributeMask getParamAndReturnAttributesToRemove() {

2879 AttributeMask R;

2880 R.addAttribute(Attribute::Dereferenceable);

2881 R.addAttribute(Attribute::DereferenceableOrNull);

2882 R.addAttribute(Attribute::ReadNone);

2883 R.addAttribute(Attribute::ReadOnly);

2884 R.addAttribute(Attribute::WriteOnly);

2885 R.addAttribute(Attribute::NoAlias);

2886 R.addAttribute(Attribute::NoFree);

2887 return R;

2888}

2889

2890 static void stripNonValidAttributesFromPrototype(Function &F) {

2891 LLVMContext &Ctx = F.getContext();

2892

2893 // Intrinsics are very delicate. Lowering sometimes depends the presence

2894 // of certain attributes for correctness, but we may have also inferred

2895 // additional ones in the abstract machine model which need stripped. This

2896 // assumes that the attributes defined in Intrinsic.td are conservatively

2897 // correct for both physical and abstract model.

2898 if (Intrinsic::ID id = F.getIntrinsicID()) {

2899 F.setAttributes(Intrinsic::getAttributes(Ctx, id, F.getFunctionType()));

2900 return;

2901 }

2902

2903 AttributeMask R = getParamAndReturnAttributesToRemove();

2904 for (Argument &A : F.args())

2905 if (isa<PointerType>(A.getType()))

2906 F.removeParamAttrs(A.getArgNo(), R);

2907

2908 if (isa<PointerType>(F.getReturnType()))

2909 F.removeRetAttrs(R);

2910

2911 for (auto Attr : FnAttrsToStrip)

2912 F.removeFnAttr(Attr);

2913}

2914

2915/// Certain metadata on instructions are invalid after running RS4GC.

2916/// Optimizations that run after RS4GC can incorrectly use this metadata to

2917/// optimize functions. We drop such metadata on the instruction.

2918 static void stripInvalidMetadataFromInstruction(Instruction &I) {

2919 if (!isa<LoadInst>(I) && !isa<StoreInst>(I))

2920 return;

2921 // These are the attributes that are still valid on loads and stores after

2922 // RS4GC.

2923 // The metadata implying dereferenceability and noalias are (conservatively)

2924 // dropped. This is because semantically, after RewriteStatepointsForGC runs,

2925 // all calls to gc.statepoint "free" the entire heap. Also, gc.statepoint can

2926 // touch the entire heap including noalias objects. Note: The reasoning is

2927 // same as stripping the dereferenceability and noalias attributes that are

2928 // analogous to the metadata counterparts.

2929 // We also drop the invariant.load metadata on the load because that metadata

2930 // implies the address operand to the load points to memory that is never

2931 // changed once it became dereferenceable. This is no longer true after RS4GC.

2932 // Similar reasoning applies to invariant.group metadata, which applies to

2933 // loads within a group.

2934 unsigned ValidMetadataAfterRS4GC[] = {LLVMContext::MD_tbaa,

2935 LLVMContext::MD_range,

2936 LLVMContext::MD_alias_scope,

2937 LLVMContext::MD_nontemporal,

2938 LLVMContext::MD_nonnull,

2939 LLVMContext::MD_align,

2940 LLVMContext::MD_type};

2941

2942 // Drops all metadata on the instruction other than ValidMetadataAfterRS4GC.

2943 I.dropUnknownNonDebugMetadata(ValidMetadataAfterRS4GC);

2944}

2945

2946 static void stripNonValidDataFromBody(Function &F) {

2947 if (F.empty())

2948 return;

2949

2950 LLVMContext &Ctx = F.getContext();

2951 MDBuilder Builder(Ctx);

2952

2953 // Set of invariantstart instructions that we need to remove.

2954 // Use this to avoid invalidating the instruction iterator.

2955 SmallVector<IntrinsicInst*, 12> InvariantStartInstructions;

2956

2957 for (Instruction &I : instructions(F)) {

2958 // invariant.start on memory location implies that the referenced memory

2959 // location is constant and unchanging. This is no longer true after

2960 // RewriteStatepointsForGC runs because there can be calls to gc.statepoint

2961 // which frees the entire heap and the presence of invariant.start allows

2962 // the optimizer to sink the load of a memory location past a statepoint,

2963 // which is incorrect.

2964 if (auto *II = dyn_cast<IntrinsicInst>(&I))

2965 if (II->getIntrinsicID() == Intrinsic::invariant_start) {

2966 InvariantStartInstructions.push_back(II);

2967 continue;

2968 }

2969

2970 if (MDNode *Tag = I.getMetadata(LLVMContext::MD_tbaa)) {

2971 MDNode *MutableTBAA = Builder.createMutableTBAAAccessTag(Tag);

2972 I.setMetadata(LLVMContext::MD_tbaa, MutableTBAA);

2973 }

2974

2975 stripInvalidMetadataFromInstruction(I);

2976

2977 AttributeMask R = getParamAndReturnAttributesToRemove();

2978 if (auto *Call = dyn_cast<CallBase>(&I)) {

2979 for (int i = 0, e = Call->arg_size(); i != e; i++)

2980 if (isa<PointerType>(Call->getArgOperand(i)->getType()))

2981 Call->removeParamAttrs(i, R);

2982 if (isa<PointerType>(Call->getType()))

2983 Call->removeRetAttrs(R);

2984 }

2985 }

2986

2987 // Delete the invariant.start instructions and RAUW poison.

2988 for (auto *II : InvariantStartInstructions) {

2989 II->replaceAllUsesWith(PoisonValue::get(II->getType()));

2990 II->eraseFromParent();

2991 }

2992}

2993

2994/// Looks up the GC strategy for a given function, returning null if the

2995/// function doesn't have a GC tag. The strategy is stored in the cache.

2996 static std::unique_ptr<GCStrategy> findGCStrategy(Function &F) {

2997 if (!F.hasGC())

2998 return nullptr;

2999

3000 return getGCStrategy(F.getGC());

3001}

3002

3003/// Returns true if this function should be rewritten by this pass. The main

3004/// point of this function is as an extension point for custom logic.

3005 static bool shouldRewriteStatepointsIn(Function &F) {

3006 if (!F.hasGC())

3007 return false;

3008

3009 std::unique_ptr<GCStrategy> Strategy = findGCStrategy(F);

3010

3011 assert(Strategy && "GC strategy is required by function, but was not found");

3012

3013 return Strategy->useRS4GC();

3014}

3015

3016 static void stripNonValidData(Module &M) {

3017#ifndef NDEBUG

3018 assert(llvm::any_of(M, shouldRewriteStatepointsIn) && "precondition!");

3019#endif

3020

3021 for (Function &F : M)

3022 stripNonValidAttributesFromPrototype(F);

3023

3024 for (Function &F : M)

3025 stripNonValidDataFromBody(F);

3026}

3027

3028 bool RewriteStatepointsForGC::runOnFunction(Function &F, DominatorTree &DT,

3029 TargetTransformInfo &TTI,

3030 const TargetLibraryInfo &TLI) {

3031 assert(!F.isDeclaration() && !F.empty() &&

3032 "need function body to rewrite statepoints in");

3033 assert(shouldRewriteStatepointsIn(F) && "mismatch in rewrite decision");

3034

3035 auto NeedsRewrite = [&TLI](Instruction &I) {

3036 if (const auto *Call = dyn_cast<CallBase>(&I)) {

3037 if (isa<GCStatepointInst>(Call))

3038 return false;

3039 if (callsGCLeafFunction(Call, TLI))

3040 return false;

3041

3042 // Normally it's up to the frontend to make sure that non-leaf calls also

3043 // have proper deopt state if it is required. We make an exception for

3044 // element atomic memcpy/memmove intrinsics here. Unlike other intrinsics

3045 // these are non-leaf by default. They might be generated by the optimizer

3046 // which doesn't know how to produce a proper deopt state. So if we see a

3047 // non-leaf memcpy/memmove without deopt state just treat it as a leaf

3048 // copy and don't produce a statepoint.

3049 if (!AllowStatepointWithNoDeoptInfo && !Call->hasDeoptState()) {

3050 assert(isa<AnyMemTransferInst>(Call) &&

3051 cast<AnyMemTransferInst>(Call)->isAtomic() &&

3052 "Don't expect any other calls here!");

3053 return false;

3054 }

3055 return true;

3056 }

3057 return false;

3058 };

3059

3060 // Delete any unreachable statepoints so that we don't have unrewritten

3061 // statepoints surviving this pass. This makes testing easier and the

3062 // resulting IR less confusing to human readers.

3063 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);

3064 bool MadeChange = removeUnreachableBlocks(F, &DTU);

3065 // Flush the Dominator Tree.

3066 DTU.getDomTree();

3067

3068 // Gather all the statepoints which need rewritten. Be careful to only

3069 // consider those in reachable code since we need to ask dominance queries

3070 // when rewriting. We'll delete the unreachable ones in a moment.

3071 SmallVector<CallBase *, 64> ParsePointNeeded;

3072 SmallVector<CallInst *, 64> Intrinsics;

3073 for (Instruction &I : instructions(F)) {

3074 // TODO: only the ones with the flag set!

3075 if (NeedsRewrite(I)) {

3076 // NOTE removeUnreachableBlocks() is stronger than

3077 // DominatorTree::isReachableFromEntry(). In other words

3078 // removeUnreachableBlocks can remove some blocks for which

3079 // isReachableFromEntry() returns true.

3080 assert(DT.isReachableFromEntry(I.getParent()) &&

3081 "no unreachable blocks expected");

3082 ParsePointNeeded.push_back(cast<CallBase>(&I));

3083 }

3084 if (auto *CI = dyn_cast<CallInst>(&I))

3085 if (CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_base ||

3086 CI->getIntrinsicID() == Intrinsic::experimental_gc_get_pointer_offset)

3087 Intrinsics.emplace_back(CI);

3088 }

3089

3090 // Return early if no work to do.

3091 if (ParsePointNeeded.empty() && Intrinsics.empty())

3092 return MadeChange;

3093

3094 // As a prepass, go ahead and aggressively destroy single entry phi nodes.

3095 // These are created by LCSSA. They have the effect of increasing the size

3096 // of liveness sets for no good reason. It may be harder to do this post

3097 // insertion since relocations and base phis can confuse things.

3098 for (BasicBlock &BB : F)

3099 if (BB.getUniquePredecessor())

3100 MadeChange |= FoldSingleEntryPHINodes(&BB);

3101

3102 // Before we start introducing relocations, we want to tweak the IR a bit to

3103 // avoid unfortunate code generation effects. The main example is that we

3104 // want to try to make sure the comparison feeding a branch is after any

3105 // safepoints. Otherwise, we end up with a comparison of pre-relocation

3106 // values feeding a branch after relocation. This is semantically correct,

3107 // but results in extra register pressure since both the pre-relocation and

3108 // post-relocation copies must be available in registers. For code without

3109 // relocations this is handled elsewhere, but teaching the scheduler to

3110 // reverse the transform we're about to do would be slightly complex.

3111 // Note: This may extend the live range of the inputs to the icmp and thus

3112 // increase the liveset of any statepoint we move over. This is profitable

3113 // as long as all statepoints are in rare blocks. If we had in-register

3114 // lowering for live values this would be a much safer transform.

3115 auto getConditionInst = [](Instruction *TI) -> Instruction * {

3116 if (auto *BI = dyn_cast<BranchInst>(TI))

3117 if (BI->isConditional())

3118 return dyn_cast<Instruction>(BI->getCondition());

3119 // TODO: Extend this to handle switches

3120 return nullptr;

3121 };

3122 for (BasicBlock &BB : F) {

3123 Instruction *TI = BB.getTerminator();

3124 if (auto *Cond = getConditionInst(TI))

3125 // TODO: Handle more than just ICmps here. We should be able to move

3126 // most instructions without side effects or memory access.

3127 if (isa<ICmpInst>(Cond) && Cond->hasOneUse()) {

3128 MadeChange = true;

3129 Cond->moveBefore(TI->getIterator());

3130 }

3131 }

3132

3133 // Nasty workaround - The base computation code in the main algorithm doesn't

3134 // consider the fact that a GEP can be used to convert a scalar to a vector.

3135 // The right fix for this is to integrate GEPs into the base rewriting

3136 // algorithm properly, this is just a short term workaround to prevent

3137 // crashes by canonicalizing such GEPs into fully vector GEPs.

3138 for (Instruction &I : instructions(F)) {

3139 if (!isa<GetElementPtrInst>(I))

3140 continue;

3141

3142 unsigned VF = 0;

3143 for (unsigned i = 0; i < I.getNumOperands(); i++)

3144 if (auto *OpndVTy = dyn_cast<VectorType>(I.getOperand(i)->getType())) {

3145 assert(VF == 0 ||

3146 VF == cast<FixedVectorType>(OpndVTy)->getNumElements());

3147 VF = cast<FixedVectorType>(OpndVTy)->getNumElements();

3148 }

3149

3150 // It's the vector to scalar traversal through the pointer operand which

3151 // confuses base pointer rewriting, so limit ourselves to that case.

3152 if (!I.getOperand(0)->getType()->isVectorTy() && VF != 0) {

3153 IRBuilder<> B(&I);

3154 auto *Splat = B.CreateVectorSplat(VF, I.getOperand(0));

3155 I.setOperand(0, Splat);

3156 MadeChange = true;

3157 }

3158 }

3159

3160 // Cache the 'defining value' relation used in the computation and

3161 // insertion of base phis and selects. This ensures that we don't insert

3162 // large numbers of duplicate base_phis. Use one cache for both

3163 // inlineGetBaseAndOffset() and insertParsePoints().

3164 DefiningValueMapTy DVCache;

3165

3166 // Mapping between a base values and a flag indicating whether it's a known

3167 // base or not.

3168 IsKnownBaseMapTy KnownBases;

3169

3170 if (!Intrinsics.empty())

3171 // Inline @gc.get.pointer.base() and @gc.get.pointer.offset() before finding

3172 // live references.

3173 MadeChange |= inlineGetBaseAndOffset(F, Intrinsics, DVCache, KnownBases);

3174

3175 if (!ParsePointNeeded.empty())

3176 MadeChange |=

3177 insertParsePoints(F, DT, TTI, ParsePointNeeded, DVCache, KnownBases);

3178

3179 return MadeChange;

3180}

3181

3182// liveness computation via standard dataflow

3183// -------------------------------------------------------------------

3184

3185// TODO: Consider using bitvectors for liveness, the set of potentially

3186// interesting values should be small and easy to pre-compute.

3187

3188/// Compute the live-in set for the location rbegin starting from

3189/// the live-out set of the basic block

3190 static void computeLiveInValues(BasicBlock::reverse_iterator Begin,

3191 BasicBlock::reverse_iterator End,

3192 SetVector<Value *> &LiveTmp, GCStrategy *GC) {

3193 for (auto &I : make_range(Begin, End)) {

3194 // KILL/Def - Remove this definition from LiveIn

3195 LiveTmp.remove(&I);

3196

3197 // Don't consider *uses* in PHI nodes, we handle their contribution to

3198 // predecessor blocks when we seed the LiveOut sets

3199 if (isa<PHINode>(I))

3200 continue;

3201

3202 // USE - Add to the LiveIn set for this instruction

3203 for (Value *V : I.operands()) {

3204 assert(!isUnhandledGCPointerType(V->getType(), GC) &&

3205 "support for FCA unimplemented");

3206 if (isHandledGCPointerType(V->getType(), GC) && !isa<Constant>(V)) {

3207 // The choice to exclude all things constant here is slightly subtle.

3208 // There are two independent reasons:

3209 // - We assume that things which are constant (from LLVM's definition)

3210 // do not move at runtime. For example, the address of a global

3211 // variable is fixed, even though it's contents may not be.

3212 // - Second, we can't disallow arbitrary inttoptr constants even

3213 // if the language frontend does. Optimization passes are free to

3214 // locally exploit facts without respect to global reachability. This

3215 // can create sections of code which are dynamically unreachable and

3216 // contain just about anything. (see constants.ll in tests)

3217 LiveTmp.insert(V);

3218 }

3219 }

3220 }

3221}

3222

3223 static void computeLiveOutSeed(BasicBlock *BB, SetVector<Value *> &LiveTmp,

3224 GCStrategy *GC) {

3225 for (BasicBlock *Succ : successors(BB)) {

3226 for (auto &I : *Succ) {

3227 PHINode *PN = dyn_cast<PHINode>(&I);

3228 if (!PN)

3229 break;

3230

3231 Value *V = PN->getIncomingValueForBlock(BB);

3232 assert(!isUnhandledGCPointerType(V->getType(), GC) &&

3233 "support for FCA unimplemented");

3234 if (isHandledGCPointerType(V->getType(), GC) && !isa<Constant>(V))

3235 LiveTmp.insert(V);

3236 }

3237 }

3238}

3239

3240 static SetVector<Value *> computeKillSet(BasicBlock *BB, GCStrategy *GC) {

3241 SetVector<Value *> KillSet;

3242 for (Instruction &I : *BB)

3243 if (isHandledGCPointerType(I.getType(), GC))

3244 KillSet.insert(&I);

3245 return KillSet;

3246}

3247

3248#ifndef NDEBUG

3249/// Check that the items in 'Live' dominate 'TI'. This is used as a basic

3250/// validation check for the liveness computation.

3251 static void checkBasicSSA(DominatorTree &DT, SetVector<Value *> &Live,

3252 Instruction *TI, bool TermOkay = false) {

3253 for (Value *V : Live) {

3254 if (auto *I = dyn_cast<Instruction>(V)) {

3255 // The terminator can be a member of the LiveOut set. LLVM's definition

3256 // of instruction dominance states that V does not dominate itself. As

3257 // such, we need to special case this to allow it.

3258 if (TermOkay && TI == I)

3259 continue;

3260 assert(DT.dominates(I, TI) &&

3261 "basic SSA liveness expectation violated by liveness analysis");

3262 }

3263 }

3264}

3265

3266/// Check that all the liveness sets used during the computation of liveness

3267/// obey basic SSA properties. This is useful for finding cases where we miss

3268/// a def.

3269 static void checkBasicSSA(DominatorTree &DT, GCPtrLivenessData &Data,

3270 BasicBlock &BB) {

3271 checkBasicSSA(DT, Data.LiveSet[&BB], BB.getTerminator());

3272 checkBasicSSA(DT, Data.LiveOut[&BB], BB.getTerminator(), true);

3273 checkBasicSSA(DT, Data.LiveIn[&BB], BB.getTerminator());

3274}

3275#endif

3276

3277 static void computeLiveInValues(DominatorTree &DT, Function &F,

3278 GCPtrLivenessData &Data, GCStrategy *GC) {

3279 SmallSetVector<BasicBlock *, 32> Worklist;

3280

3281 // Seed the liveness for each individual block

3282 for (BasicBlock &BB : F) {

3283 Data.KillSet[&BB] = computeKillSet(&BB, GC);

3284 auto &LiveSet = Data.LiveSet[&BB];

3285 LiveSet.clear();

3286 computeLiveInValues(BB.rbegin(), BB.rend(), LiveSet, GC);

3287

3288#ifndef NDEBUG

3289 for (Value *Kill : Data.KillSet[&BB])

3290 assert(!Data.LiveSet[&BB].count(Kill) && "live set contains kill");

3291#endif

3292

3293 auto &Out = Data.LiveOut[&BB] = SetVector<Value *>();

3294 computeLiveOutSeed(&BB, Out, GC);

3295 auto &In = Data.LiveIn[&BB] = Data.LiveSet[&BB];

3296 In.set_union(Out);

3297 In.set_subtract(Data.KillSet[&BB]);

3298 if (!In.empty())

3299 Worklist.insert_range(predecessors(&BB));

3300 }

3301

3302 // Propagate that liveness until stable

3303 while (!Worklist.empty()) {

3304 BasicBlock *BB = Worklist.pop_back_val();

3305

3306 // Compute our new liveout set, then exit early if it hasn't changed despite

3307 // the contribution of our successor.

3308 SetVector<Value *> &LiveOut = Data.LiveOut[BB];

3309 const auto OldLiveOutSize = LiveOut.size();

3310 for (BasicBlock *Succ : successors(BB)) {

3311 assert(Data.LiveIn.count(Succ));

3312 LiveOut.set_union(Data.LiveIn[Succ]);

3313 }

3314 // assert OutLiveOut is a subset of LiveOut

3315 if (OldLiveOutSize == LiveOut.size()) {

3316 // If the sets are the same size, then we didn't actually add anything

3317 // when unioning our successors LiveIn. Thus, the LiveIn of this block

3318 // hasn't changed.

3319 continue;

3320 }

3321

3322 // Apply the effects of this basic block

3323 SetVector<Value *> LiveTmp = LiveOut;

3324 LiveTmp.set_union(Data.LiveSet[BB]);

3325 LiveTmp.set_subtract(Data.KillSet[BB]);

3326

3327 assert(Data.LiveIn.count(BB));

3328 SetVector<Value *> &LiveIn = Data.LiveIn[BB];

3329 // assert: LiveIn is a subset of LiveTmp

3330 if (LiveIn.size() != LiveTmp.size()) {

3331 LiveIn = std::move(LiveTmp);

3332 Worklist.insert_range(predecessors(BB));

3333 }

3334 } // while (!Worklist.empty())

3335

3336#ifndef NDEBUG

3337 // Verify our output against SSA properties. This helps catch any

3338 // missing kills during the above iteration.

3339 for (BasicBlock &BB : F)

3340 checkBasicSSA(DT, Data, BB);

3341#endif

3342}

3343

3344 static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,

3345 StatepointLiveSetTy &Out, GCStrategy *GC) {

3346 BasicBlock *BB = Inst->getParent();

3347

3348 // Note: The copy is intentional and required

3349 assert(Data.LiveOut.count(BB));

3350 SetVector<Value *> LiveOut = Data.LiveOut[BB];

3351

3352 // We want to handle the statepoint itself oddly. It's

3353 // call result is not live (normal), nor are it's arguments

3354 // (unless they're used again later). This adjustment is

3355 // specifically what we need to relocate

3356 computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(), LiveOut,

3357 GC);

3358 LiveOut.remove(Inst);

3359 Out.insert_range(LiveOut);

3360}

3361

3362 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,

3363 CallBase *Call,

3364 PartiallyConstructedSafepointRecord &Info,

3365 PointerToBaseTy &PointerToBase,

3366 GCStrategy *GC) {

3367 StatepointLiveSetTy Updated;

3368 findLiveSetAtInst(Call, RevisedLivenessData, Updated, GC);

3369

3370 // We may have base pointers which are now live that weren't before. We need

3371 // to update the PointerToBase structure to reflect this.

3372 for (auto *V : Updated)

3373 PointerToBase.insert({ V, V });

3374

3375 Info.LiveSet = Updated;

3376}

assert

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

ToRemove

ReachingDefInfo InstSet & ToRemove

Definition ARMLowOverheadLoops.cpp:527

DL

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

Definition ARMSLSHardening.cpp:73

print

static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)

Definition ArchiveWriter.cpp:205

ArrayRef.h

instructions

Expand Atomic instructions

Definition AtomicExpandPass.cpp:184

AttributeMask.h

Attributes.h

This file contains the simple types necessary to represent the attributes associated with functions a...

BasicBlockUtils.h

A

static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")

D

static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")

B

static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")

Info

Analysis containing CSE Info

Definition CSEInfo.cpp:27

#define LLVM_DUMP_METHOD

Mark debug helper function definitions like dump() that should not be stripped from debug builds.

Definition Compiler.h:638

Constants.h

This file contains the declarations for the subclasses of Constant, which represent the different fla...

IntrinsicCostStrategy::InstructionCost

@ InstructionCost

Definition CostModel.cpp:52

DataLayout.h

DenseMap.h

This file defines the DenseMap class.

DenseSet.h

This file defines the DenseSet and SmallDenseSet classes.

GEP

Hexagon Common GEP

Definition HexagonCommonGEP.cpp:164

Module.h This file contains the declarations for the Module class.

lazy value info

Definition LazyValueInfo.cpp:59

F

#define F(x, y, z)

Definition MD5.cpp:55

I

#define I(x, y, z)

Definition MD5.cpp:58

MDBuilder.h

MapVector.h

This file implements a map that provides insertion order iteration.

Metadata.h

This file contains the declarations for metadata subclasses.

T

#define T

Definition Mips16ISelLowering.cpp:353

Unknown

@ Unknown

Definition NVPTXISelLowering.cpp:5798

II

uint64_t IntrinsicInst * II

Definition NVVMIntrRange.cpp:46

P

#define P(N)

FAM

FunctionAnalysisManager FAM

Definition PassBuilderBindings.cpp:61

PromoteMemToReg.h

Cond

const SmallVectorImpl< MachineOperand > & Cond

Definition RISCVRedundantCopyElimination.cpp:71

Uses

Remove Loads Into Fake Uses

Definition RemoveLoadsIntoFakeUses.cpp:81

makeStatepointExplicitImpl

static void makeStatepointExplicitImpl(CallBase *Call, const SmallVectorImpl< Value * > &BasePtrs, const SmallVectorImpl< Value * > &LiveVariables, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:1647

rematerializeLiveValues

static void rematerializeLiveValues(CallBase *Call, PartiallyConstructedSafepointRecord &Info, PointerToBaseTy &PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)

Definition RewriteStatepointsForGC.cpp:2532

findRematerializationCandidates

static void findRematerializationCandidates(PointerToBaseTy PointerToBase, RematCandTy &RematerizationCandidates, TargetTransformInfo &TTI)

Definition RewriteStatepointsForGC.cpp:2350

findGCStrategy

static std::unique_ptr< GCStrategy > findGCStrategy(Function &F)

Looks up the GC strategy for a given function, returning null if the function doesn't have a GC tag.

Definition RewriteStatepointsForGC.cpp:2996

stripNonValidDataFromBody

static void stripNonValidDataFromBody(Function &F)

Definition RewriteStatepointsForGC.cpp:2946

isKnownBase

static bool isKnownBase(Value *V, const IsKnownBaseMapTy &KnownBases)

Returns true if V is a known base.

Definition RewriteStatepointsForGC.cpp:670

findBasePointer

static Value * findBasePointer(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)

For a given value or instruction, figure out what base ptr its derived from.

Definition RewriteStatepointsForGC.cpp:811

ClobberNonLiveOverride

static cl::opt< bool, true > ClobberNonLiveOverride("rs4gc-clobber-non-live", cl::location(ClobberNonLive), cl::Hidden)

insertRelocationStores

static void insertRelocationStores(iterator_range< Value::user_iterator > GCRelocs, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)

Definition RewriteStatepointsForGC.cpp:1970

normalizeForInvokeSafepoint

static BasicBlock * normalizeForInvokeSafepoint(BasicBlock *BB, BasicBlock *InvokeParent, DominatorTree &DT)

Definition RewriteStatepointsForGC.cpp:1430

analyzeParsePointLiveness

static void analyzeParsePointLiveness(DominatorTree &DT, GCPtrLivenessData &OriginalLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &Result, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:313

computeLiveOutSeed

static void computeLiveOutSeed(BasicBlock *BB, SetVector< Value * > &LiveTmp, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:3223

relocationViaAlloca

static void relocationViaAlloca(Function &F, DominatorTree &DT, ArrayRef< Value * > Live, ArrayRef< PartiallyConstructedSafepointRecord > Records)

Do all the relocation update via allocas and mem2reg.

Definition RewriteStatepointsForGC.cpp:2017

AreEquivalentPhiNodes

static bool AreEquivalentPhiNodes(PHINode &OrigRootPhi, PHINode &AlternateRootPhi)

Definition RewriteStatepointsForGC.cpp:2321

RematerializationThreshold

static cl::opt< unsigned > RematerializationThreshold("spp-rematerialization-threshold", cl::Hidden, cl::init(6))

findBaseOrBDV

static Value * findBaseOrBDV(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)

Return a base pointer for this value if known.

Definition RewriteStatepointsForGC.cpp:647

findBaseDefiningValueCached

static Value * findBaseDefiningValueCached(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)

Returns the base defining value for this value.

Definition RewriteStatepointsForGC.cpp:630

insertUseHolderAfter

static void insertUseHolderAfter(CallBase *Call, const ArrayRef< Value * > Values, SmallVectorImpl< CallInst * > &Holders)

Insert holders so that each Value is obviously live through the entire lifetime of the call.

Definition RewriteStatepointsForGC.cpp:2218

legalizeCallAttributes

static AttributeList legalizeCallAttributes(CallBase *Call, bool IsMemIntrinsic, AttributeList StatepointAL)

Definition RewriteStatepointsForGC.cpp:1457

insertRematerializationStores

static void insertRematerializationStores(const RematerializedValueMapTy &RematerializedValues, DenseMap< Value *, AllocaInst * > &AllocaMap, DenseSet< Value * > &VisitedLiveValues)

Definition RewriteStatepointsForGC.cpp:1995

insertParsePoints

static bool insertParsePoints(Function &F, DominatorTree &DT, TargetTransformInfo &TTI, SmallVectorImpl< CallBase * > &ToUpdate, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)

Definition RewriteStatepointsForGC.cpp:2646

findBasePointers

static void findBasePointers(const StatepointLiveSetTy &live, PointerToBaseTy &PointerToBase, DominatorTree *DT, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)

Definition RewriteStatepointsForGC.cpp:1307

shouldRewriteStatepointsIn

static bool shouldRewriteStatepointsIn(Function &F)

Returns true if this function should be rewritten by this pass.

Definition RewriteStatepointsForGC.cpp:3005

RematDerivedAtUses

static cl::opt< bool > RematDerivedAtUses("rs4gc-remat-derived-at-uses", cl::Hidden, cl::init(true))

GetDeoptBundleOperands

static ArrayRef< Use > GetDeoptBundleOperands(const CallBase *Call)

Definition RewriteStatepointsForGC.cpp:230

rematerializeChain

static Instruction * rematerializeChain(ArrayRef< Instruction * > ChainToBase, BasicBlock::iterator InsertBefore, Value *RootOfChain, Value *AlternateLiveBase)

Definition RewriteStatepointsForGC.cpp:1372

stripNonValidAttributesFromPrototype

static void stripNonValidAttributesFromPrototype(Function &F)

Definition RewriteStatepointsForGC.cpp:2890

findLiveSetAtInst

static void findLiveSetAtInst(Instruction *inst, GCPtrLivenessData &Data, StatepointLiveSetTy &out, GCStrategy *GC)

Given results from the dataflow liveness computation, find the set of live Values at a particular ins...

Definition RewriteStatepointsForGC.cpp:3344

computeLiveInValues

static void computeLiveInValues(DominatorTree &DT, Function &F, GCPtrLivenessData &Data, GCStrategy *GC)

Compute the live-in set for every basic block in the function.

Definition RewriteStatepointsForGC.cpp:3277

stripInvalidMetadataFromInstruction

static void stripInvalidMetadataFromInstruction(Instruction &I)

Certain metadata on instructions are invalid after running RS4GC.

Definition RewriteStatepointsForGC.cpp:2918

FnAttrsToStrip

static constexpr Attribute::AttrKind FnAttrsToStrip[]

Definition RewriteStatepointsForGC.cpp:1452

areBothVectorOrScalar

static bool areBothVectorOrScalar(Value *First, Value *Second)

Definition RewriteStatepointsForGC.cpp:687

rematerializeLiveValuesAtUses

static void rematerializeLiveValuesAtUses(RematCandTy &RematerizationCandidates, MutableArrayRef< PartiallyConstructedSafepointRecord > Records, PointerToBaseTy &PointerToBase)

Definition RewriteStatepointsForGC.cpp:2411

isHandledGCPointerType

static bool isHandledGCPointerType(Type *T, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:266

findRematerializableChainToBasePointer

static Value * findRematerializableChainToBasePointer(SmallVectorImpl< Instruction * > &ChainToBase, Value *CurrentValue)

Definition RewriteStatepointsForGC.cpp:2261

PrintLiveSetSize

static cl::opt< bool > PrintLiveSetSize("spp-print-liveset-size", cl::Hidden, cl::init(false))

findBaseDefiningValueOfVector

static Value * findBaseDefiningValueOfVector(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)

Return a base defining value for the 'Index' element of the given vector instruction 'I'.

Definition RewriteStatepointsForGC.cpp:351

stripNonValidData

static void stripNonValidData(Module &M)

The IR fed into RewriteStatepointsForGC may have had attributes and metadata implying dereferenceabil...

Definition RewriteStatepointsForGC.cpp:3016

chainToBasePointerCost

static InstructionCost chainToBasePointerCost(SmallVectorImpl< Instruction * > &Chain, TargetTransformInfo &TTI)

Definition RewriteStatepointsForGC.cpp:2287

isUnhandledGCPointerType

static bool isUnhandledGCPointerType(Type *Ty, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:297

computeKillSet

static SetVector< Value * > computeKillSet(BasicBlock *BB, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:3240

ClobberNonLive

static bool ClobberNonLive

Definition RewriteStatepointsForGC.cpp:99

PrintBasePointers

static cl::opt< bool > PrintBasePointers("spp-print-base-pointers", cl::Hidden, cl::init(false))

isOriginalBaseResult

static bool isOriginalBaseResult(Value *V)

This value is a base pointer that is not generated by RS4GC, i.e.

Definition RewriteStatepointsForGC.cpp:662

PrintLiveSet

static cl::opt< bool > PrintLiveSet("spp-print-liveset", cl::Hidden, cl::init(false))

setKnownBase

static void setKnownBase(Value *V, bool IsKnownBase, IsKnownBaseMapTy &KnownBases)

Caches the IsKnownBase flag for a value and asserts that it wasn't present in the cache before.

Definition RewriteStatepointsForGC.cpp:676

AllowStatepointWithNoDeoptInfo

static cl::opt< bool > AllowStatepointWithNoDeoptInfo("rs4gc-allow-statepoint-with-no-deopt-info", cl::Hidden, cl::init(true))

makeStatepointExplicit

static void makeStatepointExplicit(DominatorTree &DT, CallBase *Call, PartiallyConstructedSafepointRecord &Result, std::vector< DeferredReplacement > &Replacements, const PointerToBaseTy &PointerToBase, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:1940

suffixed_name_or

static std::string suffixed_name_or(Value *V, StringRef Suffix, StringRef DefaultName)

Definition RewriteStatepointsForGC.cpp:304

CreateGCRelocates

static void CreateGCRelocates(ArrayRef< Value * > LiveVariables, ArrayRef< Value * > BasePtrs, Instruction *StatepointToken, IRBuilder<> &Builder, GCStrategy *GC)

Helper function to place all gc relocates necessary for the given statepoint.

Definition RewriteStatepointsForGC.cpp:1502

checkBasicSSA

static void checkBasicSSA(DominatorTree &DT, SetVector< Value * > &Live, Instruction *TI, bool TermOkay=false)

Check that the items in 'Live' dominate 'TI'.

Definition RewriteStatepointsForGC.cpp:3251

getDeoptLowering

static StringRef getDeoptLowering(CallBase *Call)

Definition RewriteStatepointsForGC.cpp:1631

findLiveReferences

static void findLiveReferences(Function &F, DominatorTree &DT, ArrayRef< CallBase * > toUpdate, MutableArrayRef< struct PartiallyConstructedSafepointRecord > records, GCStrategy *GC)

Definition RewriteStatepointsForGC.cpp:2243

getParamAndReturnAttributesToRemove

static AttributeMask getParamAndReturnAttributesToRemove()

Definition RewriteStatepointsForGC.cpp:2878

inlineGetBaseAndOffset

static bool inlineGetBaseAndOffset(Function &F, SmallVectorImpl< CallInst * > &Intrinsics, DefiningValueMapTy &DVCache, IsKnownBaseMapTy &KnownBases)

Definition RewriteStatepointsForGC.cpp:2598

findBaseDefiningValue

static Value * findBaseDefiningValue(Value *I, DefiningValueMapTy &Cache, IsKnownBaseMapTy &KnownBases)

Helper function for findBasePointer - Will return a value which either a) defines the base pointer fo...

Definition RewriteStatepointsForGC.cpp:449

recomputeLiveInValues

static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData, CallBase *Call, PartiallyConstructedSafepointRecord &result, PointerToBaseTy &PointerToBase, GCStrategy *GC)

Given an updated version of the dataflow liveness results, update the liveset and base pointer maps f...

Definition RewriteStatepointsForGC.cpp:3362

RewriteStatepointsForGC.h

getNumElements

static unsigned getNumElements(Type *Ty)

Definition SLPVectorizer.cpp:275

STLExtras.h

This file contains some templates that are useful if you are working with the STL at all.

isGCPointerType

verify safepoint Safepoint IR static false bool isGCPointerType(Type *T)

Definition SafepointIRVerifier.cpp:250

containsGCPtrType

static bool containsGCPtrType(Type *Ty)

Definition SafepointIRVerifier.cpp:259

Sequence.h

Provides some synthesis utilities to produce sequences of values.

SetVector.h

This file implements a set that has insertion order iteration characteristics.

SmallVector.h

This file defines the SmallVector class.

#define LLVM_DEBUG(...)

Definition Debug.h:114

Ptr

@ Ptr

Definition TargetLibraryInfo.cpp:77

TargetLibraryInfo.h

TargetTransformInfo.h

This pass exposes codegen information to IR-level passes.

Local.h

ValueHandle.h

ArrayType

Definition ItaniumDemangle.h:797

Input

The Input class is used to parse a yaml document into in-memory structs and vectors.

Definition YAMLTraits.h:1313

VectorType

Definition ItaniumDemangle.h:1189

llvm::AllocaInst

an instruction to allocate memory on the stack

Definition Instructions.h:65

llvm::AllocaInst::getAllocatedType

Type * getAllocatedType() const

Return the type that is being allocated by the instruction.

Definition Instructions.h:122

llvm::AnalysisManager::getResult

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

Definition PassManager.h:412

llvm::Argument

This class represents an incoming formal argument to a Function.

Definition Argument.h:32

llvm::ArrayRef

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

Definition ArrayRef.h:41

llvm::ArrayRef::end

iterator end() const

Definition ArrayRef.h:132

llvm::ArrayRef::size

size_t size() const

size - Get the array size.

Definition ArrayRef.h:143

llvm::ArrayRef::begin

iterator begin() const

Definition ArrayRef.h:131

llvm::ArrayRef::empty

bool empty() const

empty - Check if the array is empty.

Definition ArrayRef.h:138

llvm::AssertingVH

Value handle that asserts if the Value is deleted.

Definition ValueHandle.h:265

llvm::AtomicRMWInst::Xchg

@ Xchg

*p = v

Definition Instructions.h:724

llvm::AttributeMask

This class stores enough information to efficiently remove some attributes from an existing AttrBuild...

Definition AttributeMask.h:29

llvm::Attribute

Functions, function parameters, and return types can have attributes to indicate how they should be t...

Definition Attributes.h:69

llvm::Attribute::AttrKind

AttrKind

This enumeration lists the attributes that can be associated with parameters, function results,...

Definition Attributes.h:88

llvm::BasicBlock

LLVM Basic Block Representation.

Definition BasicBlock.h:62

llvm::BasicBlock::begin

iterator begin()

Instruction iterator methods.

Definition BasicBlock.h:459

llvm::BasicBlock::getLandingPadInst

LLVM_ABI const LandingPadInst * getLandingPadInst() const

Return the landingpad instruction associated with the landing pad.

Definition BasicBlock.cpp:665

llvm::BasicBlock::getFirstInsertionPt

LLVM_ABI const_iterator getFirstInsertionPt() const

Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...

Definition BasicBlock.cpp:393

llvm::BasicBlock::rbegin

reverse_iterator rbegin()

Definition BasicBlock.h:475

llvm::BasicBlock::getFirstNonPHIIt

LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const

Returns an iterator to the first instruction in this block that is not a PHINode instruction.

Definition BasicBlock.cpp:337

llvm::BasicBlock::reverse_iterator

InstListType::reverse_iterator reverse_iterator

Definition BasicBlock.h:172

llvm::BasicBlock::getUniquePredecessor

LLVM_ABI const BasicBlock * getUniquePredecessor() const

Return the predecessor of this block if it has a unique predecessor block.

Definition BasicBlock.cpp:445

llvm::BasicBlock::iterator

InstListType::iterator iterator

Instruction iterators...

Definition BasicBlock.h:170

llvm::BasicBlock::getTerminator

const Instruction * getTerminator() const LLVM_READONLY

Returns the terminator instruction if the block is well formed or null if the block is not well forme...

Definition BasicBlock.h:233

llvm::BitCastInst

This class represents a no-op cast from one type to another.

Definition Instructions.h:5001

llvm::CallBase

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

Definition InstrTypes.h:1114

llvm::CallBase::setCallingConv

void setCallingConv(CallingConv::ID CC)

Definition InstrTypes.h:1408

llvm::CallBase::setAttributes

void setAttributes(AttributeList A)

Set the attributes for this call.

Definition InstrTypes.h:1425

llvm::CallBase::getAttributes

AttributeList getAttributes() const

Return the attributes for this call.

Definition InstrTypes.h:1422

llvm::CallInst

This class represents a function call, abstracting a target machine's calling convention.

Definition Instructions.h:1511

llvm::CallInst::setTailCallKind

void setTailCallKind(TailCallKind TCK)

Definition Instructions.h:1631

llvm::CallInst::Create

static CallInst * Create(FunctionType *Ty, Value *F, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)

Definition Instructions.h:1546

llvm::CastInst

This is the base class for all instructions that perform data casts.

Definition InstrTypes.h:448

llvm::ConstantAggregateZero::get

static LLVM_ABI ConstantAggregateZero * get(Type *Ty)

Definition Constants.cpp:1680

llvm::ConstantInt

This is the shared class of boolean and integer constants.

Definition Constants.h:87

llvm::ConstantPointerNull::get

static LLVM_ABI ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

Definition Constants.cpp:1836

llvm::Constant

This is an important base class in LLVM.

Definition Constant.h:43

llvm::DataLayout

A parsed version of the target data layout string in and methods for querying it.

Definition DataLayout.h:63

llvm::DenseMapBase::find

iterator find(const_arg_type_t< KeyT > Val)

Definition DenseMap.h:178

llvm::DenseMapBase::try_emplace

std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)

Definition DenseMap.h:248

llvm::DenseMapBase::count

size_type count(const_arg_type_t< KeyT > Val) const

Return 1 if the specified key is in the map, 0 otherwise.

Definition DenseMap.h:174

llvm::DenseMapBase::end

iterator end()

Definition DenseMap.h:81

llvm::DenseMapBase::contains

bool contains(const_arg_type_t< KeyT > Val) const

Return true if the specified key is in the map, false otherwise.

Definition DenseMap.h:169

llvm::DenseMap

Definition DenseMap.h:713

llvm::DenseSet

Implements a dense probed hash-table based set.

Definition DenseSet.h:279

llvm::DomTreeUpdater

Definition DomTreeUpdater.h:34

llvm::DominatorTreeAnalysis

Analysis pass which computes a DominatorTree.

Definition Dominators.h:284

llvm::DominatorTree

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

Definition Dominators.h:165

llvm::DominatorTree::isReachableFromEntry

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

Definition Dominators.cpp:334

llvm::DominatorTree::dominates

LLVM_ABI bool dominates(const BasicBlock *BB, const Use &U) const

Return true if the (end of the) basic block BB dominates the use U.

Definition Dominators.cpp:135

llvm::FixedVectorType::get

static LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)

Definition Type.cpp:803

llvm::FunctionCallee

A handy container for a FunctionType+Callee-pointer pair, which can be passed around as a single enti...

Definition DerivedTypes.h:170

llvm::FunctionCallee::getCallee

Value * getCallee()

Definition DerivedTypes.h:189

llvm::FunctionType::get

static LLVM_ABI FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

llvm::Function

Definition Function.h:64

llvm::GCRelocateInst

Represents calls to the gc.relocate intrinsic.

Definition IntrinsicInst.h:1711

llvm::GCRelocateInst::getDerivedPtr

LLVM_ABI Value * getDerivedPtr() const

Definition IntrinsicInst.cpp:883

llvm::GCStatepointInst

Represents a gc.statepoint intrinsic call.

Definition Statepoint.h:61

llvm::GCStatepointInst::CallArgsBeginPos

@ CallArgsBeginPos

Definition Statepoint.h:83

llvm::GCStrategy

GCStrategy describes a garbage collector algorithm's code generation requirements,...

Definition GCStrategy.h:64

llvm::GenericDomTreeUpdater::getDomTree

DomTreeT & getDomTree()

Flush DomTree updates and return DomTree.

Definition GenericDomTreeUpdaterImpl.h:153

llvm::GetElementPtrInst

an instruction for type-safe pointer arithmetic to access elements of arrays and structs

Definition Instructions.h:950

llvm::IRBuilder

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Definition IRBuilder.h:2788

llvm::InstructionCost

Definition InstructionCost.h:30

llvm::Instruction

Definition Instruction.h:69

llvm::Instruction::getModule

LLVM_ABI const Module * getModule() const

Return the module owning the function this instruction belongs to or nullptr it the function does not...

Definition Instruction.cpp:82

llvm::Instruction::insertBefore

LLVM_ABI void insertBefore(InstListType::iterator InsertPos)

Insert an unlinked instruction into a basic block immediately before the specified position.

Definition Instruction.cpp:119

llvm::Instruction::eraseFromParent

LLVM_ABI InstListType::iterator eraseFromParent()

This method unlinks 'this' from the containing basic block and deletes it.

Definition Instruction.cpp:108

llvm::Instruction::setMetadata

LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)

Set the metadata of the specified kind to the specified node.

Definition Metadata.cpp:1746

llvm::IntrinsicInst

A wrapper class for inspecting calls to intrinsic functions.

Definition IntrinsicInst.h:49

llvm::InvokeInst

Invoke instruction.

Definition Instructions.h:3716

llvm::LLVMContext

This is an important class for using LLVM in a threaded context.

Definition LLVMContext.h:68

llvm::LLVMContext::OB_gc_transition

@ OB_gc_transition

Definition LLVMContext.h:92

llvm::LLVMContext::OB_deopt

@ OB_deopt

Definition LLVMContext.h:90

llvm::LiveVariables

Definition LiveVariables.h:49

llvm::LoadInst

An instruction for reading from memory.

Definition Instructions.h:181

llvm::MDBuilder

Definition MDBuilder.h:37

llvm::MDNode

Metadata node.

Definition Metadata.h:1078

llvm::MDNode::get

static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)

Definition Metadata.h:1569

llvm::MapVector

This class implements a map that also provides access to all stored values in a deterministic order.

Definition MapVector.h:36

llvm::MapVector::count

size_type count(const KeyT &Key) const

Definition MapVector.h:145

llvm::MapVector::end

iterator end()

Definition MapVector.h:67

llvm::MapVector::find

iterator find(const KeyT &Key)

Definition MapVector.h:149

llvm::MapVector::insert

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

Definition MapVector.h:119

llvm::MapVector::size

size_type size() const

Definition MapVector.h:56

llvm::Module

A Module instance is used to store all the information related to an LLVM module.

Definition Module.h:67

llvm::MutableArrayRef

MutableArrayRef - Represent a mutable reference to an array (0 or more elements consecutively in memo...

Definition ArrayRef.h:299

llvm::PHINode

Definition Instructions.h:2639

llvm::PHINode::getIncomingValueForBlock

Value * getIncomingValueForBlock(const BasicBlock *BB) const

Definition Instructions.h:2815

llvm::PHINode::getIncomingBlock

BasicBlock * getIncomingBlock(unsigned i) const

Return incoming basic block number i.

Definition Instructions.h:2734

llvm::PHINode::getIncomingValue

Value * getIncomingValue(unsigned i) const

Return incoming value number x.

Definition Instructions.h:2714

llvm::PHINode::getNumIncomingValues

unsigned getNumIncomingValues() const

Return the number of incoming edges.

Definition Instructions.h:2710

llvm::PointerType::get

static LLVM_ABI PointerType * get(Type *ElementType, unsigned AddressSpace)

This constructs a pointer to an object of the specified type in a numbered address space.

llvm::PoisonValue::get

static LLVM_ABI PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

Definition Constants.cpp:1888

llvm::PreservedAnalyses

A set of analyses that are preserved following a run of a transformation pass.

Definition Analysis.h:112

llvm::PreservedAnalyses::all

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

Definition Analysis.h:118

llvm::PreservedAnalyses::preserve

PreservedAnalyses & preserve()

Mark an analysis as preserved.

Definition Analysis.h:132

llvm::Record

Definition Record.h:1629

llvm::SelectInst

This class represents the LLVM 'select' instruction.

Definition Instructions.h:1690

llvm::SetVector

A vector that has set insertion semantics.

Definition SetVector.h:59

llvm::SetVector::getArrayRef

ArrayRef< value_type > getArrayRef() const

Definition SetVector.h:90

llvm::SetVector::remove

bool remove(const value_type &X)

Remove an item from the set vector.

Definition SetVector.h:180

llvm::SetVector::size

size_type size() const

Determine the number of elements in the SetVector.

Definition SetVector.h:102

llvm::SetVector::insert_range

void insert_range(Range &&R)

Definition SetVector.h:175

llvm::SetVector::set_union

bool set_union(const STy &S)

Compute This := This u S, return whether 'This' changed.

Definition SetVector.h:296

llvm::SetVector::empty

bool empty() const

Determine if the SetVector is empty or not.

Definition SetVector.h:99

llvm::SetVector::set_subtract

void set_subtract(const STy &S)

Compute This := This - B TODO: We should be able to use set_subtract from SetOperations....

Definition SetVector.h:310

llvm::SetVector::insert

bool insert(const value_type &X)

Insert a new element into the SetVector.

Definition SetVector.h:150

llvm::SetVector::pop_back_val

value_type pop_back_val()

Definition SetVector.h:278

llvm::SmallDenseMap

Definition DenseMap.h:860

llvm::SmallSetVector

A SetVector that performs no allocations if smaller than a certain size.

Definition SetVector.h:338

llvm::SmallVectorImpl

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

Definition SmallVector.h:574

llvm::SmallVectorImpl::pop_back_val

T pop_back_val()

Definition SmallVector.h:674

llvm::SmallVectorImpl::emplace_back

reference emplace_back(ArgTypes &&... Args)

Definition SmallVector.h:944

llvm::SmallVectorImpl::reserve

void reserve(size_type N)

Definition SmallVector.h:664

llvm::SmallVectorImpl::clear

void clear()

Definition SmallVector.h:611

llvm::SmallVectorTemplateBase::push_back

void push_back(const T &Elt)

Definition SmallVector.h:417

llvm::SmallVectorTemplateCommon::end

iterator end()

Definition SmallVector.h:273

llvm::SmallVectorTemplateCommon::size

size_t size() const

Definition SmallVector.h:80

llvm::SmallVectorTemplateCommon::begin

iterator begin()

Definition SmallVector.h:271

llvm::SmallVectorTemplateCommon::empty

bool empty() const

Definition SmallVector.h:83

llvm::SmallVector

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

Definition SmallVector.h:1203

llvm::StoreInst

An instruction for storing to memory.

Definition Instructions.h:297

llvm::StringRef

StringRef - Represent a constant reference to a string, i.e.

Definition StringRef.h:55

llvm::StringRef::str

std::string str() const

str - Get the contents as an std::string.

Definition StringRef.h:225

llvm::StructType

Class to represent struct types.

Definition DerivedTypes.h:218

llvm::TargetIRAnalysis

Analysis pass providing the TargetTransformInfo.

Definition TargetTransformInfo.h:1992

llvm::TargetLibraryAnalysis

Analysis pass providing the TargetLibraryInfo.

Definition TargetLibraryInfo.h:625

llvm::TargetLibraryInfo

Provides information about what library functions are available for the current target.

Definition TargetLibraryInfo.h:285

llvm::TargetTransformInfo

This pass provides access to the codegen interfaces that are needed for IR-level transformations.

Definition TargetTransformInfo.h:223

llvm::TargetTransformInfo::getCastContextHint

static LLVM_ABI CastContextHint getCastContextHint(const Instruction *I)

Calculates a CastContextHint from I.

Definition TargetTransformInfo.cpp:1024

llvm::TargetTransformInfo::TCK_SizeAndLatency

@ TCK_SizeAndLatency

The weighted sum of size and latency.

Definition TargetTransformInfo.h:282

llvm::Type

The instances of the Type class are immutable: once they are created, they are never changed.

Definition Type.h:45

llvm::Type::getPointerAddressSpace

LLVM_ABI unsigned getPointerAddressSpace() const

Get the address space of this pointer or pointer vector type.

Definition DerivedTypes.h:773

llvm::Type::getVoidTy

static LLVM_ABI Type * getVoidTy(LLVMContext &C)

Definition Type.cpp:281

llvm::Type::getIntNTy

static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)

Definition Type.cpp:301

llvm::Use

A Use represents the edge between a Value definition and its users.

Definition Use.h:35

llvm::User

Definition User.h:44

llvm::User::replaceUsesOfWith

LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)

Replace uses of one Value with another.

Definition User.cpp:21

llvm::User::operand_values

iterator_range< value_op_iterator > operand_values()

Definition User.h:316

llvm::Value

LLVM Value Representation.

Definition Value.h:75

llvm::Value::getType

Type * getType() const

All values are typed, get the type of this value.

Definition Value.h:256

llvm::Value::user_begin

user_iterator user_begin()

Definition Value.h:402

llvm::Value::setName

LLVM_ABI void setName(const Twine &Name)

Change the name of the value.

Definition Value.cpp:390

llvm::Value::hasOneUse

bool hasOneUse() const

Return true if there is exactly one use of this value.

Definition Value.h:439

llvm::Value::replaceAllUsesWith

LLVM_ABI void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

Definition Value.cpp:546

llvm::Value::users

iterator_range< user_iterator > users()

Definition Value.h:426

llvm::Value::getUniqueUndroppableUser

LLVM_ABI User * getUniqueUndroppableUser()

Return true if there is exactly one unique user of this value that cannot be dropped (that user can h...

Definition Value.cpp:188

llvm::Value::getContext

LLVM_ABI LLVMContext & getContext() const

All values hold a context through their type.

Definition Value.cpp:1099

llvm::Value::getNumUses

LLVM_ABI unsigned getNumUses() const

This method computes the number of uses of this Value.

Definition Value.cpp:265

llvm::Value::getName

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

Definition Value.cpp:322

llvm::Value::user_empty

bool user_empty() const

Definition Value.h:389

llvm::cl::opt

Definition CommandLine.h:1455

llvm::detail::DenseSetImpl::insert

std::pair< iterator, bool > insert(const ValueT &V)

Definition DenseSet.h:202

llvm::detail::DenseSetImpl::count

size_type count(const_arg_type_t< ValueT > V) const

Return 1 if the specified key is in the set, 0 otherwise.

Definition DenseSet.h:180

llvm::ilist_detail::node_parent_access::getParent

const ParentTy * getParent() const

Definition ilist_node.h:34

llvm::ilist_node_impl::getIterator

self_iterator getIterator()

Definition ilist_node.h:123

llvm::ilist_node_with_parent::getNextNode

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

Definition ilist_node.h:348

llvm::iterator_range

A range adaptor for a pair of iterators.

Definition iterator_range.h:32

llvm::raw_ostream

This class implements an extremely fast bulk output stream that can only output to a stream.

Definition raw_ostream.h:53

uint32_t

uint64_t

Call

CallInst * Call

Definition ObjCARCOpts.cpp:2359

Changed

Definition ObjCARCOpts.cpp:2369

iterator_range.h

This provides a very simple, boring adaptor for a begin and end iterator into a range type.

ErrorHandling.h

llvm_unreachable

#define llvm_unreachable(msg)

Marks that the current location is not supposed to be reachable.

Definition ErrorHandling.h:164

llvm::CallingConv::Cold

@ Cold

Attempts to make code in the caller as efficient as possible under the assumption that the call is no...

Definition CallingConv.h:47

llvm::Intrinsic::getOrInsertDeclaration

LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > Tys={})

Look up the Function declaration of the intrinsic id in the Module M.

Definition Intrinsics.cpp:723

llvm::Intrinsic::ID

unsigned ID

Definition GenericSSAContext.h:28

llvm::Intrinsic::getAttributes

LLVM_ABI AttributeList getAttributes(LLVMContext &C, ID id, FunctionType *FT)

Return the attributes for an intrinsic.

llvm::NVPTXAS::AddressSpace

AddressSpace

Definition NVPTXAddrSpace.h:21

llvm::Reloc

Definition CodeGen.h:23

llvm::SI

Definition SIInstrInfo.h:1805

llvm::cl::Hidden

@ Hidden

Definition CommandLine.h:139

llvm::cl::init

initializer< Ty > init(const Ty &Val)

Definition CommandLine.h:445

llvm::cl::location

LocationClass< Ty > location(Ty &L)

Definition CommandLine.h:465

llvm::ms_demangle::IntrinsicFunctionKind::New

@ New

Definition MicrosoftDemangleNodes.h:121

llvm::sampleprof::Base

@ Base

Definition Discriminator.h:58

llvm::sandboxir::Instruction

friend class Instruction

Iterator for Instructions in a `BasicBlock.

Definition BasicBlock.h:73

llvm

This is an optimization pass for GlobalISel generic memory operations.

Definition AddressRanges.h:18

llvm::dump

void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)

Definition SparseBitVector.h:874

llvm::Offset

@ Offset

Definition DWP.cpp:477

llvm::Value

FunctionAddr VTableAddr Value

Definition InstrProf.h:137

llvm::find

auto find(R &&Range, const T &Val)

Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.

Definition STLExtras.h:1751

llvm::Cost

InstructionCost Cost

Definition FunctionSpecialization.h:103

llvm::PromoteMemToReg

LLVM_ABI void PromoteMemToReg(ArrayRef< AllocaInst * > Allocas, DominatorTree &DT, AssumptionCache *AC=nullptr)

Promote the specified list of alloca instructions into scalar registers, inserting PHI nodes as appro...

Definition PromoteMemoryToRegister.cpp:1206

llvm::dyn_cast

decltype(auto) dyn_cast(const From &Val)

dyn_cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:643

llvm::successors

auto successors(const MachineBasicBlock *BB)

Definition MachineBasicBlock.h:1437

llvm::operator!=

bool operator!=(uint64_t V1, const APInt &V2)

Definition APInt.h:2114

llvm::make_range

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

Definition iterator_range.h:70

llvm::FunctionAnalysisManagerModuleProxy

InnerAnalysisManagerProxy< FunctionAnalysisManager, Module > FunctionAnalysisManagerModuleProxy

Provide the FunctionAnalysisManager to Module proxy.

Definition PassManager.h:671

llvm::unique

auto unique(Range &&R, Predicate P)

Definition STLExtras.h:2076

llvm::operator==

bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)

Definition AddressRanges.h:151

llvm::any_of

bool any_of(R &&range, UnaryPredicate P)

Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.

Definition STLExtras.h:1732

llvm::reverse

auto reverse(ContainerTy &&C)

Definition STLExtras.h:406

llvm::sort

void sort(IteratorTy Start, IteratorTy End)

Definition STLExtras.h:1622

llvm::ComplexDeinterleavingOperation::Splat

@ Splat

Definition ComplexDeinterleavingPass.h:42

llvm::dbgs

LLVM_ABI raw_ostream & dbgs()

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

Definition Debug.cpp:207

llvm::parseStatepointDirectivesFromAttrs

StatepointDirectives parseStatepointDirectivesFromAttrs(AttributeList AS)

Parse out statepoint directives from the function attributes present in AS.

Definition Statepoint.cpp:24

llvm::SmallVector

class LLVM_GSL_OWNER SmallVector

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

Definition SmallVector.h:1129

llvm::isa

bool isa(const From &Val)

isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...

Definition Casting.h:547

llvm::errs

LLVM_ABI raw_fd_ostream & errs()

This returns a reference to a raw_ostream for standard error.

Definition raw_ostream.cpp:897

llvm::SplitBlockPredecessors

LLVM_ABI BasicBlock * SplitBlockPredecessors(BasicBlock *BB, ArrayRef< BasicBlock * > Preds, const char *Suffix, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, bool PreserveLCSSA=false)

This method introduces at least one new basic block into the function and moves some of the predecess...

Definition BasicBlockUtils.cpp:1369

llvm::IRMemLocation::Other

@ Other

Any other memory.

Definition ModRef.h:68

llvm::IRMemLocation::First

@ First

Helpers to iterate all locations in the MemoryEffectsBase class.

Definition ModRef.h:71

llvm::TTI

TargetTransformInfo TTI

Definition TargetTransformInfo.h:218

llvm::Data

FunctionAddr VTableAddr uintptr_t uintptr_t Data

Definition InstrProf.h:189

llvm::Op

DWARFExpression::Operation Op

Definition DWARFExpressionPrinter.cpp:22

llvm::FoldSingleEntryPHINodes

LLVM_ABI bool FoldSingleEntryPHINodes(BasicBlock *BB, MemoryDependenceResults *MemDep=nullptr)

We know that BB has one predecessor.

Definition BasicBlockUtils.cpp:185

llvm::operator<<

raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)

Definition APFixedPoint.h:312

llvm::StatepointFlags::None

@ None

Definition Statepoint.h:40

llvm::StatepointFlags::DeoptLiveIn

@ DeoptLiveIn

Mark the deopt arguments associated with the statepoint as only being "live-in".

Definition Statepoint.h:49

llvm::StatepointFlags::GCTransition

@ GCTransition

Indicates that this statepoint is a transition from GC-aware code to code that is not GC-aware.

Definition Statepoint.h:41

llvm::PseudoProbeReservedId::Last

@ Last

Definition PseudoProbe.h:28

llvm::count_if

auto count_if(R &&Range, UnaryPredicate P)

Wrapper function around std::count_if to count the number of times an element satisfying a given pred...

Definition STLExtras.h:1961

llvm::cast

decltype(auto) cast(const From &Val)

cast<X> - Return the argument parameter cast to the specified type.

Definition Casting.h:559

llvm::getGCStrategy

LLVM_ABI std::unique_ptr< GCStrategy > getGCStrategy(const StringRef Name)

Lookup the GCStrategy object associated with the given gc name.

Definition GCStrategy.cpp:24

llvm::predecessors

auto predecessors(const MachineBasicBlock *BB)

Definition MachineBasicBlock.h:1438

llvm::is_contained

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

Returns true if Element is found in Range.

Definition STLExtras.h:1897

llvm::seq

auto seq(T Begin, T End)

Iterate over an integral type from Begin up to - but not including - End.

Definition Sequence.h:305

llvm::isStatepointDirectiveAttr

bool isStatepointDirectiveAttr(Attribute Attr)

Return true if the Attr is an attribute that is a statepoint directive.

Definition Statepoint.cpp:18

llvm::removeUnreachableBlocks

LLVM_ABI bool removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)

Remove all blocks that can not be reached from the function's entry.

Definition Local.cpp:2883

llvm::callsGCLeafFunction

LLVM_ABI bool callsGCLeafFunction(const CallBase *Call, const TargetLibraryInfo &TLI)

Return true if this call calls a gc leaf function.

Definition Local.cpp:3283

llvm::ModuleAnalysisManager

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

Definition MIRParser.h:39

raw_ostream.h

llvm::RewriteStatepointsForGC::runOnFunction

bool runOnFunction(Function &F, DominatorTree &, TargetTransformInfo &, const TargetLibraryInfo &)

Definition RewriteStatepointsForGC.cpp:3028

llvm::RewriteStatepointsForGC::run

PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)

Definition RewriteStatepointsForGC.cpp:131

llvm::StatepointDirectives

Call sites that get wrapped by a gc.statepoint (currently only in RewriteStatepointsForGC and potenti...

Definition Statepoint.h:235

llvm::StatepointDirectives::NumPatchBytes

std::optional< uint32_t > NumPatchBytes

Definition Statepoint.h:236

llvm::StatepointDirectives::StatepointID

std::optional< uint64_t > StatepointID

Definition Statepoint.h:237

llvm::StatepointDirectives::DefaultStatepointID

static const uint64_t DefaultStatepointID

Definition Statepoint.h:239

Generated on for LLVM by doxygen 1.14.0

LLVM: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp Source File