SampleContextTracker.cpp Source File (original) (raw)

19#include

20#include

21#include

23using namespace llvm;

26#define DEBUG_TYPE "sample-context-tracker"

28namespace llvm {

32 if (CalleeName.empty())

36 auto It = AllChildContext.find(Hash);

37 if (It != AllChildContext.end())

38 return &It->second;

39 return nullptr;

40}

48 uint64_t MaxCalleeSamples = 0;

49 for (auto &It : AllChildContext) {

51 if (ChildNode.CallSiteLoc != CallSite)

52 continue;

54 if (!Samples)

55 continue;

57 ChildNodeRet = &ChildNode;

59 }

60 }

62 return ChildNodeRet;

63}

66SampleContextTracker::moveContextSamples(ContextTrieNode &ToNodeParent,

71 std::map<uint64_t, ContextTrieNode> &AllChildContext =

73 assert(!AllChildContext.count(Hash) && "Node to remove must exist");

75 NewNode = NodeToMove;

81 std::queue<ContextTrieNode *> NodeToUpdate;

83 NodeToUpdate.push(&NewNode);

85 while (!NodeToUpdate.empty()) {

87 NodeToUpdate.pop();

90 if (FSamples) {

91 setContextNode(FSamples, Node);

93 }

95 for (auto &It : Node->getAllChildContext()) {

98 NodeToUpdate.push(ChildNode);

99 }

100 }

101

102 return NewNode;

103}

104

108

109 AllChildContext.erase(Hash);

110}

111

113 return AllChildContext;

114}

115

117

119 return FuncSamples;

120}

121

123 FuncSamples = FSamples;

124}

125

127 return FuncSize;

128}

129

131 if (!FuncSize)

132 FuncSize = 0;

133

134 FuncSize = *FuncSize + FSize;

135}

136

138

140 return ParentContext;

141}

142

144 ParentContext = Parent;

145}

146

148 CallSiteLoc = Loc;

149}

150

152 dbgs() << "Node: " << FuncName << "\n"

153 << " Callsite: " << CallSiteLoc << "\n"

154 << " Size: " << FuncSize << "\n"

155 << " Children:\n";

156

157 for (auto &It : AllChildContext) {

158 dbgs() << " Node: " << It.second.getFuncName() << "\n";

159 }

160}

161

163 dbgs() << "Context Profile Tree:\n";

164 std::queue<ContextTrieNode *> NodeQueue;

165 NodeQueue.push(this);

166

167 while (!NodeQueue.empty()) {

169 NodeQueue.pop();

170 Node->dumpNode();

171

172 for (auto &It : Node->getAllChildContext()) {

174 NodeQueue.push(ChildNode);

175 }

176 }

177}

178

182 auto It = AllChildContext.find(Hash);

183 if (It != AllChildContext.end()) {

184 assert(It->second.getFuncName() == CalleeName &&

185 "Hash collision for child context node");

186 return &It->second;

187 }

188

189 if (!AllowCreate)

190 return nullptr;

191

193 ACC = ContextTrieNode(this, CalleeName, nullptr, CallSite);

194 return &ACC;

195}

196

197

201 : GUIDToFuncNameMap(GUIDToFuncNameMap) {

202 for (auto &FuncSample : Profiles) {

204 SampleContext Context = FuncSample.second.getContext();

205 LLVM_DEBUG(dbgs() << "Tracking Context for function: " << Context.toString()

206 << "\n");

209 "New node can't have sample profile");

211 }

213}

214

216 for (auto *Node : *this) {

218 if (FSamples) {

220 setContextNode(FSamples, Node);

221 FuncToCtxtProfiles[Node->getFuncName()].push_back(FSamples);

222 }

223 }

224}

225

229 LLVM_DEBUG(dbgs() << "Getting callee context for instr: " << Inst << "\n");

231 if (!DIL)

232 return nullptr;

233

235

237

238

239

240 ContextTrieNode *CalleeContext = getCalleeContextFor(DIL, FName);

241 if (CalleeContext) {

245 << "\n";

246 });

247 return FSamples;

248 }

249

250 return nullptr;

251}

252

253std::vector<const FunctionSamples *>

256 std::vector<const FunctionSamples *> R;

257 if (!DIL)

258 return R;

259

265 continue;

267 R.push_back(CalleeSamples);

268 }

269

270 return R;

271}

272

275 assert(DIL && "Expect non-null location");

276

278 if (!ContextNode)

279 return nullptr;

280

281

282

283

284

285

286

288 if (Samples && ContextNode->getParentContext() != &RootContext)

290

291 return Samples;

292}

293

298 return nullptr;

299

300 return Node->getFunctionSamples();

301}

302

308

313

315 bool MergeContext) {

318}

319

321 bool MergeContext) {

322 LLVM_DEBUG(dbgs() << "Getting base profile for function: " << Name << "\n");

323

324

325

326

327

329 if (MergeContext) {

330 LLVM_DEBUG(dbgs() << " Merging context profile into base profile: " << Name

331 << "\n");

332

333

334

335

336 for (auto *CSamples : FuncToCtxtProfiles[Name]) {

338

340 continue;

341

343 if (FromNode == Node)

344 continue;

345

347 assert(( Node || Node == &ToNode) && "Expect only one base profile");

348 Node = &ToNode;

349 }

350 }

351

352

354 return nullptr;

355

356 return Node->getFunctionSamples();

357}

358

361 assert(InlinedSamples && "Expect non-null inlined samples");

362 LLVM_DEBUG(dbgs() << "Marking context profile as inlined: "

365}

366

368

371 LLVM_DEBUG(dbgs() << "Promoting and merging context tree for instr: \n"

372 << Inst << "\n");

373

374

377 if (!CallerNode)

378 return;

379

380

382

383

384 if (CalleeName.empty()) {

388 continue;

391 continue;

393 }

394 return;

395 }

396

397

400 if (!NodeToPromo)

401 return;

402

404}

405

408

409

410

411

413 assert(FromSamples && "Shouldn't promote a context without profile");

414 (void)FromSamples;

415

416 LLVM_DEBUG(dbgs() << " Found context tree root to promote: "

418

420 "Shouldn't promote inlined context profile");

422}

423

424#ifndef NDEBUG

425std::string

429

430std::string

433 if (Node == &RootContext)

434 return std::string();

436

438 Node = Node->getParentContext();

439 while (Node && Node != &RootContext) {

441 PreNode = Node;

442 Node = Node->getParentContext();

443 }

444

445 std::reverse(Res.begin(), Res.end());

446

448}

449#endif

450

452

455 return Node->getFuncName().stringRef();

456 assert(GUIDToFuncNameMap && "GUIDToFuncNameMap needs to be populated first");

457 return GUIDToFuncNameMap->lookup(Node->getFuncName().getHashCode());

458}

459

464

466SampleContextTracker::getCalleeContextFor(const DILocation *DIL,

468 assert(DIL && "Expect non-null location");

469

471 if (!CallContext)

472 return nullptr;

473

474

475

478}

479

481 assert(DIL && "Expect non-null location");

483

484

486 for (DIL = DIL->getInlinedAt(); DIL; DIL = DIL->getInlinedAt()) {

487 StringRef Name = PrevDIL->getScope()->getSubprogram()->getLinkageName();

488 if (Name.empty())

489 Name = PrevDIL->getScope()->getSubprogram()->getName();

493 PrevDIL = DIL;

494 }

495

496

497

498 StringRef RootName = PrevDIL->getScope()->getSubprogram()->getLinkageName();

499 if (RootName.empty())

500 RootName = PrevDIL->getScope()->getSubprogram()->getName();

501 S.push_back(std::make_pair(LineLocation(0, 0),

503

504 ContextTrieNode *ContextNode = &RootContext;

505 int I = S.size();

506 while (--I >= 0 && ContextNode) {

507 LineLocation &CallSite = S[I].first;

508 FunctionId CalleeName = S[I].second;

509 ContextNode = ContextNode->getChildContext(CallSite, CalleeName);

510 }

511

512 if (I < 0)

513 return ContextNode;

514

515 return nullptr;

516}

517

520 bool AllowCreate) {

523

524 for (const auto &Callsite : Context.getContextFrames()) {

525

526 if (AllowCreate) {

527 ContextNode =

529 } else {

530 ContextNode =

531 ContextNode->getChildContext(CallSiteLoc, Callsite.Func);

532 }

533 CallSiteLoc = Callsite.Location;

534 }

535

536 assert((!AllowCreate || ContextNode) &&

537 "Node must exist if creation is allowed");

538 return ContextNode;

539}

540

542SampleContextTracker::getTopLevelContextNode(FunctionId FName) {

543 assert(!FName.empty() && "Top level node query must provide valid name");

545}

546

548SampleContextTracker::addTopLevelContextNode(FunctionId FName) {

549 assert(!getTopLevelContextNode(FName) && "Node to add must not exist");

551}

552

553void SampleContextTracker::mergeContextNode(ContextTrieNode &FromNode,

557 if (FromSamples && ToSamples) {

558

559 ToSamples->merge(*FromSamples);

564 } else if (FromSamples) {

565

567 setContextNode(FromSamples, &ToNode);

569 }

570}

571

574

575

576 LineLocation NewCallSiteLoc = LineLocation(0, 0);

577 LineLocation OldCallSiteLoc = FromNode.getCallSiteLoc();

578 ContextTrieNode &FromNodeParent = *FromNode.getParentContext();

579 ContextTrieNode *ToNode = nullptr;

580 bool MoveToRoot = (&ToNodeParent == &RootContext);

581 if (!MoveToRoot) {

582 NewCallSiteLoc = OldCallSiteLoc;

583 }

584

585

587 if (!ToNode) {

588

589

590 ToNode =

591 &moveContextSamples(ToNodeParent, NewCallSiteLoc, std::move(FromNode));

594 << "\n";

595 });

596 } else {

597

598 mergeContextNode(FromNode, *ToNode);

601 dbgs() << " Context promoted and merged to: "

603 });

604

605

607 ContextTrieNode &FromChildNode = It.second;

609 }

610

611

613 }

614

615

616 if (MoveToRoot)

618

619 return *ToNode;

620}

621

624 for (auto *Node : *this) {

626

627 if (FProfile)

628 ContextLessProfiles.create(Node->getFuncName()).merge(*FProfile);

629 }

630}

631}

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

This file provides the interface for context-sensitive profile tracker used by CSSPGO.

Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...

LLVM_ABI ContextTrieNode * getOrCreateChildContext(const LineLocation &CallSite, FunctionId ChildName, bool AllowCreate=true)

Definition SampleContextTracker.cpp:179

LLVM_ABI std::map< uint64_t, ContextTrieNode > & getAllChildContext()

Definition SampleContextTracker.cpp:112

LLVM_ABI void setCallSiteLoc(const LineLocation &Loc)

Definition SampleContextTracker.cpp:147

LLVM_ABI LineLocation getCallSiteLoc() const

Definition SampleContextTracker.cpp:137

LLVM_ABI FunctionSamples * getFunctionSamples() const

Definition SampleContextTracker.cpp:118

LLVM_ABI std::optional< uint32_t > getFunctionSize() const

Definition SampleContextTracker.cpp:126

LLVM_ABI ContextTrieNode * getHottestChildContext(const LineLocation &CallSite)

Definition SampleContextTracker.cpp:43

LLVM_ABI void setParentContext(ContextTrieNode *Parent)

Definition SampleContextTracker.cpp:143

LLVM_ABI void dumpNode()

Definition SampleContextTracker.cpp:151

LLVM_ABI void removeChildContext(const LineLocation &CallSite, FunctionId ChildName)

Definition SampleContextTracker.cpp:105

LLVM_ABI void dumpTree()

Definition SampleContextTracker.cpp:162

LLVM_ABI void addFunctionSize(uint32_t FSize)

Definition SampleContextTracker.cpp:130

LLVM_ABI FunctionId getFuncName() const

Definition SampleContextTracker.cpp:116

LLVM_ABI ContextTrieNode * getChildContext(const LineLocation &CallSite, FunctionId ChildName)

Definition SampleContextTracker.cpp:30

LLVM_ABI ContextTrieNode * getParentContext() const

Definition SampleContextTracker.cpp:139

LLVM_ABI void setFunctionSamples(FunctionSamples *FSamples)

Definition SampleContextTracker.cpp:122

ContextTrieNode(ContextTrieNode *Parent=nullptr, FunctionId FName=FunctionId(), FunctionSamples *FSamples=nullptr, LineLocation CallLoc={0, 0})

const DebugLoc & getDebugLoc() const

Return the debug location for this node as a DebugLoc.

LLVM_ABI void promoteMergeContextSamplesTree(const Instruction &Inst, FunctionId CalleeName)

Definition SampleContextTracker.cpp:369

LLVM_ABI FunctionSamples * getBaseSamplesFor(const Function &Func, bool MergeContext=true)

Definition SampleContextTracker.cpp:314

LLVM_ABI ContextTrieNode * getOrCreateContextPath(const SampleContext &Context, bool AllowCreate)

Definition SampleContextTracker.cpp:519

LLVM_ABI StringRef getFuncNameFor(ContextTrieNode *Node) const

Definition SampleContextTracker.cpp:453

LLVM_ABI void populateFuncToCtxtMap()

Definition SampleContextTracker.cpp:215

LLVM_ABI ContextTrieNode & getRootContext()

Definition SampleContextTracker.cpp:367

LLVM_ABI std::string getContextString(const FunctionSamples &FSamples) const

Definition SampleContextTracker.cpp:426

ContextTrieNode * getContextNodeForProfile(const FunctionSamples *FSamples) const

LLVM_ABI FunctionSamples * getContextSamplesFor(const DILocation *DIL)

Definition SampleContextTracker.cpp:274

std::vector< FunctionSamples * > ContextSamplesTy

LLVM_ABI void dump()

Definition SampleContextTracker.cpp:451

LLVM_ABI ContextSamplesTy & getAllContextSamplesFor(const Function &Func)

Definition SampleContextTracker.cpp:304

LLVM_ABI void markContextSamplesInlined(const FunctionSamples *InlinedSamples)

Definition SampleContextTracker.cpp:359

LLVM_ABI void createContextLessProfileMap(SampleProfileMap &ContextLessProfiles)

Definition SampleContextTracker.cpp:622

LLVM_ABI std::vector< const FunctionSamples * > getIndirectCalleeContextSamplesFor(const DILocation *DIL)

Definition SampleContextTracker.cpp:254

SampleContextTracker()=default

LLVM_ABI FunctionSamples * getCalleeContextSamplesFor(const CallBase &Inst, StringRef CalleeName)

Definition SampleContextTracker.cpp:227

LLVM_ABI ContextTrieNode * getContextFor(const SampleContext &Context)

Definition SampleContextTracker.cpp:461

reference emplace_back(ArgTypes &&... Args)

void push_back(const T &Elt)

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

StringRef - Represent a constant reference to a string, i.e.

constexpr bool empty() const

empty - Check if the string is empty.

This class represents a function that is read from a sample profile.

Representation of the samples collected for a function.

static uint64_t getCallSiteHash(FunctionId Callee, const LineLocation &Callsite)

Returns a unique hash code for a combination of a callsite location and the callee function name.

static StringRef getCanonicalFnName(const Function &F)

Return the canonical name for a function, taking into account suffix elision policy attributes.

SampleContext & getContext() const

uint64_t getTotalSamples() const

Return the total number of samples collected inside the function.

sampleprof_error merge(const FunctionSamples &Other, uint64_t Weight=1)

Merge the samples in Other into this one.

static LLVM_ABI LineLocation getCallSiteIdentifier(const DILocation *DIL, bool ProfileIsFS=false)

Returns a unique call site identifier for a given debug location of a call instruction.

static LLVM_ABI bool UseMD5

Whether the profile uses MD5 to represent string.

bool hasState(ContextStateMask S)

static std::string getContextString(SampleContextFrames Context, bool IncludeLeafLineLocation=false)

void setState(ContextStateMask S)

void setAttribute(ContextAttributeMask A)

bool hasAttribute(ContextAttributeMask A)

This class provides operator overloads to the map container using MD5 as the key type,...

mapped_type & create(const SampleContext &Ctx)

static FunctionId getRepInFormat(StringRef Name)

Get the proper representation of a string according to whether the current Format uses MD5 to represe...

SmallVector< SampleContextFrame, 1 > SampleContextFrameVector

This is an optimization pass for GlobalISel generic memory operations.

LLVM_ABI raw_ostream & dbgs()

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

Represents the relative location of an instruction.