FunctionPropertiesAnalysis.cpp Source File (original) (raw)

25#include

27using namespace llvm;

29namespace llvm {

32 cl::desc("Whether or not to compute detailed function properties."));

36 cl::desc("The minimum number of instructions a basic block should contain "

37 "before being considered big."));

41 cl::desc("The minimum number of instructions a basic block should contain "

42 "before being considered medium-sized."));

43}

47 cl::desc("The minimum number of arguments a function call must have before "

48 "it is considered having many arguments."));

50namespace {

51int64_t getNumBlocksFromCond(const BasicBlock &BB) {

52 int64_t Ret = 0;

54 if (BI->isConditional())

55 Ret += BI->getNumSuccessors();

57 Ret += (SI->getNumCases() + (nullptr != SI->getDefaultDest()));

58 }

59 return Ret;

60}

62int64_t getUses(const Function &F) {

63 return ((.hasLocalLinkage()) ? 1 : 0) + F.getNumUses();

64}

65}

67void FunctionPropertiesInfo::reIncludeBB(const BasicBlock &BB) {

68 updateForBB(BB, +1);

69}

71void FunctionPropertiesInfo::updateForBB(const BasicBlock &BB,

76 (Direction * getNumBlocksFromCond(BB));

77 for (const auto &I : BB) {

79 const auto *Callee = CS->getCalledFunction();

80 if (Callee && Callee ->isIntrinsic() && Callee ->isDeclaration())

82 }

83 if (I.getOpcode() == Instruction::Load) {

85 } else if (I.getOpcode() == Instruction::Store) {

87 }

88 }

92 unsigned SuccessorCount = succ_size(&BB);

93 if (SuccessorCount == 1)

95 else if (SuccessorCount == 2)

97 else if (SuccessorCount > 2)

100 unsigned PredecessorCount = pred_size(&BB);

101 if (PredecessorCount == 1)

103 else if (PredecessorCount == 2)

105 else if (PredecessorCount > 2)

107

112 else

114

115

116

117

118 if (SuccessorCount > 1) {

122 }

123 }

124

126

128 if (!BI->isConditional())

130 }

131

132 for (const Instruction &I : BB.instructionsWithoutDebug()) {

133 if (I.isCast())

135

136 if (I.getType()->isFloatTy())

138 else if (I.getType()->isIntegerTy())

140

143

147 else

149

163 }

164

167

168 for (const auto &Arg : Call->args()) {

169 if (Arg->getType()->isPointerTy()) {

171 break;

172 }

173 }

174 }

175

176#define COUNT_OPERAND(OPTYPE) \

177 if (isa(Operand)) { \

178 OPTYPE##OperandCount += Direction; \

179 continue; \

180 }

181

182 for (unsigned int OperandIndex = 0; OperandIndex < I.getNumOperands();

183 ++OperandIndex) {

184 Value *Operand = I.getOperand(OperandIndex);

193

194

195

197 }

198

199#undef CHECK_OPERAND

200 }

201 }

202

203 if (IR2VecVocab) {

204

205

206

208 *BB.getParent(), *IR2VecVocab);

209 if (!Embedder) {

210 BB.getContext().emitError("Error creating IR2Vec embeddings");

211 return;

212 }

213 const auto &BBEmbedding = Embedder->getBBVector(BB);

214

215

217 FunctionEmbedding -= BBEmbedding;

218 else

219 FunctionEmbedding += BBEmbedding;

220 }

221}

222

223void FunctionPropertiesInfo::updateAggregateStats(const Function &F,

225

226 Uses = getUses(F);

229 std::deque<const Loop *> Worklist;

231 while (!Worklist.empty()) {

232 const auto *L = Worklist.front();

234 std::max(MaxLoopDepth, static_cast<int64_t>(L->getLoopDepth()));

235 Worklist.pop_front();

237 }

238}

239

242

243

244

246 .getCachedResult(*F.getParent());

249}

250

254

256 if (Vocabulary && Vocabulary->isValid()) {

257 FPI.IR2VecVocab = Vocabulary;

259 }

260 for (const auto &BB : F)

262 FPI.reIncludeBB(BB);

263 FPI.updateAggregateStats(F, LI);

264 return FPI;

265}

266

317 return false;

318 }

319

320

321 if (!FunctionEmbedding.approximatelyEquals(FPI.FunctionEmbedding))

322 return false;

323

324 return true;

325}

326

328#define PRINT_PROPERTY(PROP_NAME) OS << #PROP_NAME ": " << PROP_NAME << "\n";

329

339

376 }

377

378#undef PRINT_PROPERTY

379

380 OS << "\n";

381}

382

384

389

392 OS << "Printing analysis results of CFA for function "

393 << "'" << F.getName() << "':"

394 << "\n";

397}

398

401 : FPI(FPI), CallSiteBB(*CB.getParent()), Caller(*CallSiteBB.getParent()) {

403

404

405

407

408

409 LikelyToChangeBBs.insert(&CallSiteBB);

410

411

412 LikelyToChangeBBs.insert(&*Caller.begin());

413

414

415

416

417 for (const auto *User : CB.users())

419

420

421 CallUsers.erase(&CallSiteBB);

423

424

425

426

427 Successors.insert_range(successors(&CallSiteBB));

428

429

430

431

432

433

435 for (auto *Succ : successors(&CallSiteBB))

436 if (Inserted.insert(Succ).second)

437 DomTreeUpdates.emplace_back(DominatorTree::UpdateKind::Delete,

438 const_cast<BasicBlock *>(&CallSiteBB),

440

441

442 Inserted.clear();

443

444

445

446

447

448

449

451 const auto *UnwindDest = II->getUnwindDest();

452 Successors.insert_range(successors(UnwindDest));

453

454 for (auto *Succ : successors(UnwindDest))

455 if (Inserted.insert(Succ).second)

456 DomTreeUpdates.emplace_back(DominatorTree::UpdateKind::Delete,

457 const_cast<BasicBlock *>(UnwindDest),

459 }

460

461

462

463

464

465

466 Successors.erase(&CallSiteBB);

467

469

470

471

472

473

474 for (const auto *BB : LikelyToChangeBBs)

475 FPI.updateForBB(*BB, -1);

476}

477

478DominatorTree &FunctionPropertiesUpdater::getUpdatedDominatorTree(

480 auto &DT =

482

484

486 for (auto *Succ : successors(&CallSiteBB))

487 if (Inserted.insert(Succ).second)

488 FinalDomTreeUpdates.push_back({DominatorTree::UpdateKind::Insert,

489 const_cast<BasicBlock *>(&CallSiteBB),

491

492

493

494 for (auto &Upd : DomTreeUpdates)

496 FinalDomTreeUpdates.push_back(Upd);

497

498 DT.applyUpdates(FinalDomTreeUpdates);

499#ifdef EXPENSIVE_CHECKS

500 assert(DT.verify(DominatorTree::VerificationLevel::Full));

501#endif

502 return DT;

503}

504

506

507

508

509

510

511

512

513

514

515

516

517

518

519

520

521

522

523

524

525

526

527

528

529

532 auto &DT = getUpdatedDominatorTree(FAM);

533

534 if (&CallSiteBB != &*Caller.begin())

535 Reinclude.insert(&*Caller.begin());

536

537

539

540

541 for (const auto *Succ : Successors)

542 if (DT.isReachableFromEntry(Succ))

543 Reinclude.insert(Succ);

544 else

545 Unreachable.insert(Succ);

546

547

548

549

550

551 const auto IncludeSuccessorsMark = Reinclude.size();

552 bool CSInsertion = Reinclude.insert(&CallSiteBB);

553 (void)CSInsertion;

555 for (size_t I = 0; I < Reinclude.size(); ++I) {

556 const auto *BB = Reinclude[I];

557 FPI.reIncludeBB(*BB);

558 if (I >= IncludeSuccessorsMark)

560 }

561

562

563

564

565

566 const auto AlreadyExcludedMark = Unreachable.size();

567 for (size_t I = 0; I < Unreachable.size(); ++I) {

568 const auto *U = Unreachable[I];

569 if (I >= AlreadyExcludedMark)

570 FPI.updateForBB(*U, -1);

571 for (const auto *Succ : successors(U))

572 if (!DT.isReachableFromEntry(Succ))

573 Unreachable.insert(Succ);

574 }

575

577 FPI.updateAggregateStats(Caller, LI);

578#ifdef EXPENSIVE_CHECKS

579 assert(isUpdateValid(Caller, FPI, FAM));

580#endif

581}

582

583bool FunctionPropertiesUpdater::isUpdateValid(Function &F,

587 DominatorTree::VerificationLevel::Full))

588 return false;

592 .getCachedResult(*F.getParent());

593 auto Fresh =

595 return FPI == Fresh;

596}

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

static const Function * getParent(const Value *V)

This file contains the declarations for the subclasses of Constant, which represent the different fla...

#define PRINT_PROPERTY(PROP_NAME)

static cl::opt< unsigned > CallWithManyArgumentsThreshold("call-with-many-arguments-threshold", cl::Hidden, cl::init(4), cl::desc("The minimum number of arguments a function call must have before " "it is considered having many arguments."))

#define COUNT_OPERAND(OPTYPE)

This file provides various utilities for inspecting and working with the control flow graph in LLVM I...

Loop::LoopBounds::Direction Direction

uint64_t IntrinsicInst * II

FunctionAnalysisManager FAM

This file implements a set that has insertion order iteration characteristics.

PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)

Get the result of an analysis pass for a given IR unit.

LLVM Basic Block Representation.

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...

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

LLVM_ABI bool isIndirectCall() const

Return true if the callsite is an indirect call.

iterator_range< User::op_iterator > args()

Iteration adapter for range-for loops.

unsigned arg_size() const

Implements a dense probed hash-table based set.

Analysis pass which computes a DominatorTree.

Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.

LLVM_ABI bool isReachableFromEntry(const Use &U) const

Provide an overload for a Use.

static LLVM_ABI AnalysisKey Key

LLVM_ABI FunctionPropertiesInfo run(Function &F, FunctionAnalysisManager &FAM)

Definition FunctionPropertiesAnalysis.cpp:386

int64_t BasicBlocksWithMoreThanTwoSuccessors

int64_t BasicBlocksWithSinglePredecessor

int64_t CallReturnsVectorPointerCount

int64_t CallReturnsPointerCount

int64_t CallWithManyArgumentsCount

int64_t CallReturnsVectorIntCount

int64_t CallReturnsVectorFloatCount

int64_t CastInstructionCount

int64_t BasicBlockCount

Number of basic blocks.

int64_t CriticalEdgeCount

int64_t Uses

Number of uses of this function, plus 1 if the function is callable outside the module.

int64_t InlineAsmOperandCount

int64_t ConstantFPOperandCount

int64_t BasicBlocksWithTwoSuccessors

int64_t InstructionOperandCount

int64_t CallWithPointerArgumentCount

int64_t FloatingPointInstructionCount

int64_t TopLevelLoopCount

int64_t CallReturnsIntegerCount

int64_t BlocksReachedFromConditionalInstruction

Number of blocks reached from a conditional instruction, or that are 'cases' of a SwitchInstr.

int64_t GlobalValueOperandCount

int64_t UnconditionalBranchCount

int64_t ArgumentOperandCount

int64_t BasicBlocksWithSingleSuccessor

LLVM_ABI bool operator==(const FunctionPropertiesInfo &FPI) const

Definition FunctionPropertiesAnalysis.cpp:267

int64_t BasicBlockOperandCount

int64_t ControlFlowEdgeCount

int64_t BasicBlocksWithTwoPredecessors

int64_t MediumBasicBlocks

int64_t IntegerInstructionCount

static LLVM_ABI FunctionPropertiesInfo getFunctionPropertiesInfo(const Function &F, const DominatorTree &DT, const LoopInfo &LI, const ir2vec::Vocabulary *Vocabulary)

Definition FunctionPropertiesAnalysis.cpp:251

int64_t CallReturnsFloatCount

LLVM_ABI void print(raw_ostream &OS) const

Definition FunctionPropertiesAnalysis.cpp:327

int64_t TotalInstructionCount

int64_t BasicBlocksWithMoreThanTwoPredecessors

int64_t ConstantOperandCount

int64_t ConstantIntOperandCount

int64_t UnknownOperandCount

int64_t DirectCallsToDefinedFunctions

Number of direct calls made from this function to other functions defined in this module.

int64_t IndirectCallCount

LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)

Definition FunctionPropertiesAnalysis.cpp:391

LLVM_ABI FunctionPropertiesUpdater(FunctionPropertiesInfo &FPI, CallBase &CB)

Definition FunctionPropertiesAnalysis.cpp:399

LLVM_ABI void finish(FunctionAnalysisManager &FAM) const

Definition FunctionPropertiesAnalysis.cpp:505

Analysis pass that exposes the LoopInfo for a function.

A set of analyses that are preserved following a run of a transformation pass.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

A vector that has set insertion semantics.

size_type size() const

Determine the number of elements in the SetVector.

void insert_range(Range &&R)

bool insert(const value_type &X)

Insert a new element into the SetVector.

void insert_range(Range &&R)

std::pair< iterator, bool > insert(PtrType Ptr)

Inserts Ptr if and only if there is no element in the container equal to Ptr.

SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.

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

bool isVectorTy() const

True if this is an instance of VectorType.

bool isPointerTy() const

True if this is an instance of PointerType.

Type * getScalarType() const

If this is a vector type, return the element type, otherwise return 'this'.

bool isFloatingPointTy() const

Return true if this is one of the floating-point types.

bool isIntegerTy() const

True if this is an instance of IntegerType.

Type * getType() const

All values are typed, get the type of this value.

iterator_range< user_iterator > users()

static LLVM_ABI std::unique_ptr< Embedder > create(IR2VecKind Mode, const Function &F, const Vocabulary &Vocab)

Factory method to create an Embedder object.

Class for storing and accessing the IR2Vec vocabulary.

LLVM_ABI unsigned getDimension() const

LLVM_ABI bool isValid() const

This class implements an extremely fast bulk output stream that can only output to a stream.

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)

auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)

Get the size of a range.

decltype(auto) dyn_cast(const From &Val)

dyn_cast - Return the argument parameter cast to the specified type.

auto successors(const MachineBasicBlock *BB)

OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy

Provide the ModuleAnalysisManager to Function proxy.

LLVM_ABI cl::opt< bool > EnableDetailedFunctionProperties("enable-detailed-function-properties", cl::Hidden, cl::init(false), cl::desc("Whether or not to compute detailed function properties."))

void append_range(Container &C, Range &&R)

Wrapper function to append range R to container C.

auto pred_size(const MachineBasicBlock *BB)

auto succ_size(const MachineBasicBlock *BB)

bool isa(const From &Val)

isa - Return true if the parameter to the template is an instance of one of the template type argu...

static cl::opt< unsigned > BigBasicBlockInstructionThreshold("big-basic-block-instruction-threshold", cl::Hidden, cl::init(500), cl::desc("The minimum number of instructions a basic block should contain " "before being considered big."))

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

Returns true if Element is found in Range.

static cl::opt< unsigned > MediumBasicBlockInstructionThreshold("medium-basic-block-instruction-threshold", cl::Hidden, cl::init(15), cl::desc("The minimum number of instructions a basic block should contain " "before being considered medium-sized."))

AnalysisManager< Function > FunctionAnalysisManager

Convenience typedef for the Function analysis manager.

A special type used by analysis passes to provide an address that identifies that particular analysis...

Embedding is a datatype that wraps std::vector.