GlobalMergeFunctions.cpp Source File (original) (raw)

23#define DEBUG_TYPE "global-merge-func"

25using namespace llvm;

29 "disable-cgdata-for-merging", cl::Hidden,

30 cl::desc("Disable codegen data for function merging. Local "

31 "merging is still enabled within a module."),

35 "Number of functions that are actually merged using function hash");

36 STATISTIC(NumAnalyzedModues, "Number of modules that are analyzed");

37 STATISTIC(NumAnalyzedFunctions, "Number of functions that are analyzed");

38 STATISTIC(NumEligibleFunctions, "Number of functions that are eligible");

43}

47 return false;

49 ? dyn_cast_or_null(

51 : nullptr;

52 if (Callee) {

53 if (Callee->isIntrinsic())

54 return false;

55 auto Name = Callee->getName();

57 if (Name.starts_with("objc_msgSend$"))

58 return false;

60 if (Name.starts_with("__dtrace"))

61 return false;

62 }

67 return false;

68 } else {

72 OpIdx))

73 return false;

74 }

75 return true;

76}

80 if (F->isDeclaration())

81 return false;

83 if (F->hasFnAttribute(llvm::Attribute::NoMerge) ||

84 F->hasFnAttribute(llvm::Attribute::AlwaysInline))

85 return false;

87 if (F->hasAvailableExternallyLinkage())

88 return false;

90 if (F->getFunctionType()->isVarArg())

91 return false;

94 return false;

102 const auto *CB = dyn_cast(&I);

103 if (CB && CB->isMustTailCall())

104 return false;

105 }

106 }

107

108 return true;

109}

110

112 switch (I->getOpcode()) {

113 case Instruction::Load:

114 case Instruction::Store:

115 case Instruction::Call:

116 case Instruction::Invoke:

117 return true;

118 default:

119 return false;

120 }

121}

122

123

124

125

126

128 if (OpIdx >= I->getNumOperands())

129 return false;

130

132 return false;

133

134 if (!isa(I->getOperand(OpIdx)))

135 return false;

136

137 if (const auto *CI = dyn_cast(I))

139

140 return true;

141}

142

144 Type *SrcTy = V->getType();

153

155 }

156 return Result;

157 }

159 if (auto *SrcAT = dyn_cast(SrcTy)) {

160 auto *DestAT = dyn_cast(DestTy);

162 assert(SrcAT->getNumElements() == DestAT->getNumElements());

164 for (unsigned int I = 0, E = SrcAT->getNumElements(); I < E; ++I) {

167 DestAT->getElementType());

168

170 }

171 return Result;

172 }

179}

180

182 ++NumAnalyzedModues;

184 ++NumAnalyzedFunctions;

186 ++NumEligibleFunctions;

187

189

190

191

193 for (auto &Pair : *FI.IndexOperandHashMap)

195

197 M.getModuleIdentifier(), FI.IndexInstruction->size(),

198 std::move(IndexOperandHashes));

199

200 LocalFunctionMap->insert(SF);

201 }

202 }

203}

204

205

212 : SF(SF), F(F), IndexInstruction(std::move(IndexInstruction)) {}

213};

214

215

216

217

221

222

223 auto *MergedFunc = FI.F;

224 std::string NewFunctionName =

226 auto *M = MergedFunc->getParent();

227 assert(!M->getFunction(NewFunctionName));

228

229 FunctionType *OrigTy = MergedFunc->getFunctionType();

230

231 SmallVector<Type *> ParamTypes(OrigTy->param_begin(), OrigTy->param_end());

232

233 ParamTypes.append(ConstParamTypes.begin(), ConstParamTypes.end());

235 ParamTypes, false);

236

237

239 Function::Create(FuncType, MergedFunc->getLinkage(), NewFunctionName);

240 if (auto *SP = MergedFunc->getSubprogram())

244

246 NewFunction->addFnAttr(Attribute::NoInline);

247

248

249 M->getFunctionList().insert(MergedFunc->getIterator(), NewFunction);

250

251

252 NewFunction->splice(NewFunction->begin(), MergedFunc);

253

254

255 auto NewArgIter = NewFunction->arg_begin();

256 for (Argument &OrigArg : MergedFunc->args()) {

257 Argument &NewArg = *NewArgIter++;

259 }

260

261

262 unsigned NumOrigArgs = MergedFunc->arg_size();

263 for (unsigned ParamIdx = 0; ParamIdx < ParamLocsVec.size(); ++ParamIdx) {

264 Argument *NewArg = NewFunction->getArg(NumOrigArgs + ParamIdx);

265 for (auto [InstIndex, OpndIndex] : ParamLocsVec[ParamIdx]) {

267 auto *OrigC = Inst->getOperand(OpndIndex);

268 if (OrigC->getType() != NewArg->getType()) {

269 IRBuilder<> Builder(Inst->getParent(), Inst->getIterator());

270 Inst->setOperand(OpndIndex,

272 } else {

273 Inst->setOperand(OpndIndex, NewArg);

274 }

275 }

276 }

277

278 return NewFunction;

279}

280

281

282

285 auto *Thunk = FI.F;

286

287 assert(Thunk->arg_size() + Params.size() ==

289 Thunk->dropAllReferences();

290

293

295 unsigned ParamIdx = 0;

297

298

299 for (Argument &AI : Thunk->args()) {

300 Args.push_back(createCast(Builder, &AI, ToFuncTy->getParamType(ParamIdx)));

301 ++ParamIdx;

302 }

303

304

305 for (auto *Param : Params) {

306 assert(ParamIdx < ToFuncTy->getNumParams());

307 Args.push_back(

308 createCast(Builder, Param, ToFuncTy->getParamType(ParamIdx)));

309 ++ParamIdx;

310 }

311

319 if (Thunk->getReturnType()->isVoidTy())

321 else

323}

324

325

326

327

328

329

330

331

332

333

334

335

336

340

342 for (const auto &[Index, OldHash] : OldInstOpndIndexToConstHash) {

343 auto It = CurrInstOpndIndexToConstHash.find(Index);

344 if (It == CurrInstOpndIndexToConstHash.end())

345 return false;

346

347 auto CurrHash = It->second;

348 auto J = OldHashToCurrHash.find(OldHash);

349 if (J == OldHashToCurrHash.end())

350 OldHashToCurrHash.insert({OldHash, CurrHash});

351 else if (J->second != CurrHash)

352 return false;

353 }

354

355 return true;

356}

357

358

359static bool

363 for (auto &ParamLocs : ParamLocsVec) {

364 std::optional<stable_hash> OldHash;

365 std::optional<Constant *> OldConst;

369 auto [InstIndex, OpndIndex] = Loc;

370 assert(InstIndex < IndexInstruction.size());

371 const auto *Inst = IndexInstruction.lookup(InstIndex);

372 auto *CurrConst = cast(Inst->getOperand(OpndIndex));

373 if (!OldHash) {

374 OldHash = CurrHash;

375 OldConst = CurrConst;

376 } else if (CurrConst != *OldConst || CurrHash != *OldHash) {

377 return false;

378 }

379 }

380 }

381 return true;

382}

383

385 const SmallVector<std::unique_ptrStableFunctionMap::StableFunctionEntry>

386 &SFS) {

387 std::map<std::vector<stable_hash>, ParamLocs> HashSeqToLocs;

388 auto &RSF = *SFS[0];

389 unsigned StableFunctionCount = SFS.size();

390

391 for (auto &[IndexPair, Hash] : *RSF.IndexOperandHashMap) {

392

393

394

395 std::vector<stable_hash> ConstHashSeq;

396 ConstHashSeq.push_back(Hash);

397 bool Identical = true;

398 for (unsigned J = 1; J < StableFunctionCount; ++J) {

399 auto &SF = SFS[J];

400 auto SHash = SF->IndexOperandHashMap->at(IndexPair);

401 if (Hash != SHash)

402 Identical = false;

403 ConstHashSeq.push_back(SHash);

404 }

405

406 if (Identical)

407 continue;

408

409

410 HashSeqToLocs[ConstHashSeq].push_back(IndexPair);

411 }

412

414 for (auto &[HashSeq, Locs] : HashSeqToLocs)

415 ParamLocsVec.push_back(std::move(Locs));

416

418 return L[0] < R[0];

419 });

420

421 return ParamLocsVec;

422}

423

425 bool Changed = false;

426

427

429 HashToFuncs;

431 for (auto &F : M) {

433 continue;

435 if (Maps.contains(FI.FunctionHash))

436 HashToFuncs[FI.FunctionHash].emplace_back(&F, std::move(FI));

437 }

438

439 for (auto &[Hash, Funcs] : HashToFuncs) {

440 std::optional ParamLocsVec;

442 auto &SFS = Maps.at(Hash);

443 assert(!SFS.empty());

444 auto &RFS = SFS[0];

445

446

447 for (auto &[F, FI] : Funcs) {

448

449

450 if (RFS->InstCount != FI.IndexInstruction->size())

451 continue;

452

456 auto [InstIndex, OpndIndex] = Index;

457 assert(InstIndex < FHI.IndexInstruction->size());

458 auto *Inst = FHI.IndexInstruction->lookup(InstIndex);

459 if ( ignoreOp (Inst, OpndIndex))

460 return false;

461 }

462 return true;

463 };

464 if (!hasValidSharedConst(RFS.get(), FI))

465 continue;

466

467 for (auto &SF : SFS) {

469 assert(hasValidSharedConst(SF.get(), FI));

470

471

473 *FI.IndexOperandHashMap))

474 continue;

475 if (!ParamLocsVec.has_value()) {

477 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging hash: " << Hash

478 << " with Params " << ParamLocsVec->size() << "\n");

479 }

481 *ParamLocsVec))

482 continue;

483

484

485

486 FuncMergeInfos.emplace_back(SF.get(), F, FI.IndexInstruction.get());

487 break;

488 }

489 }

490 unsigned FuncMergeInfoSize = FuncMergeInfos.size();

491 if (FuncMergeInfoSize == 0)

492 continue;

493

494 LLVM_DEBUG(dbgs() << "[GlobalMergeFunc] Merging function count "

495 << FuncMergeInfoSize << " for hash: " << Hash << "\n");

496

497 for (auto &FMI : FuncMergeInfos) {

498 Changed = true;

499

500

501

504 for (auto &ParamLocs : *ParamLocsVec) {

506 auto &[InstIndex, OpndIndex] = ParamLocs[0];

507 auto *Inst = FMI.IndexInstruction->lookup(InstIndex);

508 auto *Opnd = cast(Inst->getOperand(OpndIndex));

510 ParamTypes.push_back(Opnd->getType());

511 }

512

513

516

518 dbgs() << "[GlobalMergeFunc] Merged function (hash:" << FMI.SF->Hash

519 << ") " << MergedFunc->getName() << " generated from "

520 << FMI.F->getName() << ":\n";

521 MergedFunc->dump();

522 });

523

524

525

528 dbgs() << "[GlobalMergeFunc] Thunk generated: \n";

529 FMI.F->dump();

530 });

531 ++NumMergedFunctions;

532 }

533 }

534

535 return Changed;

536}

537

539

540 LocalFunctionMap = std::make_unique();

541

542

544 return;

545

546

547

549 return;

550

552 MergerMode = HashFunctionMode::BuildingHashFuncion;

554 MergerMode = HashFunctionMode::UsingHashFunction;

555}

556

558 LLVM_DEBUG(dbgs() << "Emit function map. Size: " << LocalFunctionMap->size()

559 << "\n");

560

561 if (LocalFunctionMap->empty())

562 return;

565

567

569 OS.str(), "in-memory stable function map", false);

570

571 Triple TT(M.getTargetTriple());

575}

576

579

581 if (MergerMode == HashFunctionMode::UsingHashFunction) {

582

584 } else {

586

587

588 if (MergerMode == HashFunctionMode::BuildingHashFuncion)

590 LocalFunctionMap->finalize();

591 FuncMap = LocalFunctionMap.get();

592 }

593

594 return merge(M, FuncMap);

595}

596

597namespace {

598

599class GlobalMergeFuncPassWrapper : public ModulePass {

600

601public:

602 static char ID;

603

604 GlobalMergeFuncPassWrapper();

605

606 void getAnalysisUsage(AnalysisUsage &AU) const override {

609 ModulePass::getAnalysisUsage(AU);

610 }

611

612 StringRef getPassName() const override { return "Global Merge Functions"; }

613

614 bool runOnModule(Module &M) override;

615};

616

617}

618

619char GlobalMergeFuncPassWrapper::ID = 0;

621 "Global merge function pass", false, false)

624

625namespace llvm {

627 return new GlobalMergeFuncPassWrapper();

628}

629}

630

631GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() : ModulePass(ID) {

634}

635

636bool GlobalMergeFuncPassWrapper::runOnModule(Module &M) {

638 if (auto *IndexWrapperPass =

639 getAnalysisIfAvailable())

640 Index = IndexWrapperPass->getIndex();

641

643}

644

649}

Performs the initial survey of the specified function

static ParamLocsVecTy computeParamInfo(const SmallVector< std::unique_ptr< StableFunctionMap::StableFunctionEntry > > &SFS)

static bool checkConstHashCompatible(const DenseMap< IndexPair, stable_hash > &OldInstOpndIndexToConstHash, const DenseMap< IndexPair, stable_hash > &CurrInstOpndIndexToConstHash)

static cl::opt< bool > DisableCGDataForMerging("disable-cgdata-for-merging", cl::Hidden, cl::desc("Disable codegen data for function merging. Local " "merging is still enabled within a module."), cl::init(false))

static bool canParameterizeCallOperand(const CallBase *CI, unsigned OpIdx)

static Function * createMergedFunction(FuncMergeInfo &FI, ArrayRef< Type * > ConstParamTypes, const ParamLocsVecTy &ParamLocsVec)

static void createThunk(FuncMergeInfo &FI, ArrayRef< Constant * > Params, Function *ToFunc)

global merge Global merge function pass

static Value * createCast(IRBuilder<> &Builder, Value *V, Type *DestTy)

static bool isEligibleInstructionForConstantSharing(const Instruction *I)

static bool ignoreOp(const Instruction *I, unsigned OpIdx)

bool isEligibleFunction(Function *F)

Returns true if function F is eligible for merging.

static bool checkConstLocationCompatible(const StableFunctionMap::StableFunctionEntry &SF, const IndexInstrMap &IndexInstruction, const ParamLocsVecTy &ParamLocsVec)

static bool isCalleeOperand(const CallBase *CI, unsigned OpIdx)

Returns true if the \OpIdx operand of CI is the callee operand.

static LoopDeletionResult merge(LoopDeletionResult A, LoopDeletionResult B)

This is the interface to build a ModuleSummaryIndex for a module.

#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)

#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)

assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())

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

#define STATISTIC(VARNAME, DESC)

A container for analyses that lazily runs them and caches their results.

Represent the analysis usage information of a pass.

AnalysisUsage & addUsedIfAvailable()

Add the specified Pass class to the set of analyses used by this pass.

void setPreservesAll()

Set by analyses that do not transform their input at all.

This class represents an incoming formal argument to a Function.

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

size_t size() const

size - Get the array size.

LLVM Basic Block Representation.

static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)

Creates a new BasicBlock.

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

bool isInlineAsm() const

Check if this call is an inline asm statement.

void setCallingConv(CallingConv::ID CC)

bool isOperandBundleOfType(uint32_t ID, unsigned Idx) const

Return true if the operand at index Idx is a bundle operand that has tag ID ID.

std::optional< OperandBundleUse > getOperandBundle(StringRef Name) const

Return an operand bundle by name, if present.

Value * getCalledOperand() const

const Use & getCalledOperandUse() const

void setAttributes(AttributeList A)

Set the attributes for this call.

This class represents a function call, abstracting a target machine's calling convention.

void setTailCallKind(TailCallKind TCK)

iterator find(const_arg_type_t< KeyT > Val)

std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)

unsigned getNumParams() const

Return the number of fixed parameters this function type requires.

static FunctionType * get(Type *Result, ArrayRef< Type * > Params, bool isVarArg)

This static method is the primary way of constructing a FunctionType.

void addFnAttr(Attribute::AttrKind Kind)

Add function attributes to this function.

void setSubprogram(DISubprogram *SP)

Set the attached subprogram.

static Function * Create(FunctionType *Ty, LinkageTypes Linkage, unsigned AddrSpace, const Twine &N="", Module *M=nullptr)

void splice(Function::iterator ToIt, Function *FromF)

Transfer all blocks from FromF to this function at ToIt.

FunctionType * getFunctionType() const

Returns the FunctionType for me.

CallingConv::ID getCallingConv() const

getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...

AttributeList getAttributes() const

Return the attribute list for this Function.

Argument * getArg(unsigned i) const

void copyAttributesFrom(const Function *Src)

copyAttributesFrom - copy all additional attributes (those not needed to create a Function) from the ...

GlobalMergeFunc is a ModulePass that implements a function merging mechanism using stable function ha...

void analyze(Module &M)

Analyze module to create stable function into LocalFunctionMap.

void initializeMergerMode(const Module &M)

bool merge(Module &M, const StableFunctionMap *FunctionMap)

Merge functions in the module using the given function map.

void emitFunctionMap(Module &M)

Emit LocalFunctionMap into __llvm_merge section.

static constexpr const char MergingInstanceSuffix[]

The suffix used to identify the merged function that parameterizes the constant values.

void setDLLStorageClass(DLLStorageClassTypes C)

void setLinkage(LinkageTypes LT)

@ InternalLinkage

Rename collisions when linking (static functions).

Value * CreateInsertValue(Value *Agg, Value *Val, ArrayRef< unsigned > Idxs, const Twine &Name="")

Value * CreateExtractValue(Value *Agg, ArrayRef< unsigned > Idxs, const Twine &Name="")

Value * CreateIntToPtr(Value *V, Type *DestTy, const Twine &Name="")

ReturnInst * CreateRet(Value *V)

Create a 'ret ' instruction.

Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")

ReturnInst * CreateRetVoid()

Create a 'ret void' instruction.

Value * CreatePtrToInt(Value *V, Type *DestTy, const Twine &Name="")

CallInst * CreateCall(FunctionType *FTy, Value *Callee, ArrayRef< Value * > Args={}, const Twine &Name="", MDNode *FPMathTag=nullptr)

This provides a uniform API for creating instructions and inserting them into a basic block: either a...

Legacy wrapper pass to provide the ModuleSummaryIndex object.

@ OB_clang_arc_attachedcall

This class implements a map that also provides access to all stored values in a deterministic order.

ValueT lookup(const KeyT &Key) const

static std::unique_ptr< MemoryBuffer > getMemBuffer(StringRef InputData, StringRef BufferName="", bool RequiresNullTerminator=true)

Open the specified memory range as a MemoryBuffer.

ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...

Class to hold module path string table and global value map, and encapsulate methods for operating on...

bool hasExportedFunctions(const Module &M) const

Check if the given Module has any functions available for exporting in the index.

A Module instance is used to store all the information related to an LLVM module.

static PassRegistry * getPassRegistry()

getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...

static PoisonValue * get(Type *T)

Static factory methods - Return an 'poison' object of the specified type.

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

static PreservedAnalyses none()

Convenience factory function for the empty preserved set.

static PreservedAnalyses all()

Construct a special preserved set that preserves all passes.

reference emplace_back(ArgTypes &&... Args)

void append(ItTy in_start, ItTy in_end)

Add the specified range to the end of the SmallVector.

void push_back(const T &Elt)

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

std::string str() const

str - Get the contents as an std::string.

Triple - Helper class for working with autoconf configuration names.

The instances of the Type class are immutable: once they are created, they are never changed.

Type * getStructElementType(unsigned N) const

bool isArrayTy() const

True if this is an instance of ArrayType.

bool isPointerTy() const

True if this is an instance of PointerType.

unsigned getStructNumElements() const

bool isStructTy() const

True if this is an instance of StructType.

bool isIntegerTy() const

True if this is an instance of IntegerType.

const Use & getOperandUse(unsigned i) const

LLVM Value Representation.

Type * getType() const

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

void replaceAllUsesWith(Value *V)

Change all uses of this to point to a new Value.

const Value * stripPointerCasts() const

Strip off pointer casts, all-zero GEPs and address space casts.

StringRef getName() const

Return a constant reference to the value's name.

void dump() const

Support for debugging, callable in GDB: V->dump()

A raw_ostream that writes to an SmallVector or SmallString.

@ SwiftTail

This follows the Swift calling convention in how arguments are passed but guarantees tail calls will ...

unsigned ID

LLVM IR allows to use arbitrary numbers as calling convention identifiers.

bool hasStableFunctionMap()

const StableFunctionMap * getStableFunctionMap()

initializer< Ty > init(const Ty &Val)

This is an optimization pass for GlobalISel generic memory operations.

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.

ModulePass * createGlobalMergeFuncPass()

This pass performs merging similar functions globally.

FunctionHashInfo StructuralHashWithDifferences(const Function &F, IgnoreOperandFunc IgnoreOp)

Computes a structural hash of a given function, considering the structure and content of the function...

std::pair< unsigned, unsigned > IndexPair

The pair of an instruction index and a operand index.

void sort(IteratorTy Start, IteratorTy End)

raw_ostream & dbgs()

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

StringRef get_stable_name(StringRef Name)

@ Global

Append to llvm.global_dtors.

void initializeGlobalMergeFuncPassWrapperPass(PassRegistry &)

OutputIt move(R &&Range, OutputIt Out)

Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.

void embedBufferInModule(Module &M, MemoryBufferRef Buf, StringRef SectionName, Align Alignment=Align(1))

Embed the memory buffer Buf into the module M as a global using the specified section name.

std::string getCodeGenDataSectionName(CGDataSectKind CGSK, Triple::ObjectFormatType OF, bool AddSegmentInfo=true)

Implement std::hash so that hash_code can be used in STL containers.

Tuple to hold function info to process merging.

FuncMergeInfo(StableFunctionMap::StableFunctionEntry *SF, Function *F, IndexInstrMap *IndexInstruction)

StableFunctionMap::StableFunctionEntry * SF

IndexInstrMap * IndexInstruction

This struct is a compact representation of a valid (non-zero power of two) alignment.

PreservedAnalyses run(Module &M, AnalysisManager< Module > &)

const ModuleSummaryIndex * ImportSummary

static void serialize(raw_ostream &OS, const StableFunctionMap *FunctionMap)

A static helper function to serialize the stable function map without owning the stable function map.

An efficient form of StableFunction for fast look-up.

std::unique_ptr< IndexOperandHashMapType > IndexOperandHashMap

A map from an IndexPair to a stable_hash which was skipped.

unsigned InstCount

The number of instructions.

const HashFuncsMapType & getFunctionMap() const

Get the HashToFuncs map for serialization.

A stable function is a function with a stable hash while tracking the locations of ignored operands a...