GlobalMergeFunctions.cpp Source File (original) (raw)

25#define DEBUG_TYPE "global-merge-func"

27using namespace llvm;

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

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

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

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

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

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

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

49 return false;

53 : nullptr;

54 if (Callee) {

55 if (Callee->isIntrinsic())

56 return false;

57 auto Name = Callee->getName();

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

60 return false;

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

63 return false;

64 }

69 return false;

70 } else {

75 return false;

76 }

77 return true;

78}

82 if (F->isDeclaration())

83 return false;

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

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

87 return false;

89 if (F->hasAvailableExternallyLinkage())

90 return false;

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

93 return false;

96 return false;

99 if (->hasName())

100 return false;

101

102

103

104

105

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

110 return false;

111 }

112 }

113

114 return true;

115}

116

118 switch (I->getOpcode()) {

119 case Instruction::Load:

120 case Instruction::Store:

121 case Instruction::Call:

122 case Instruction::Invoke:

123 return true;

124 default:

125 return false;

126 }

127}

128

129

130

131

132

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

135 return false;

136

138 return false;

139

141 return false;

142

145

146 return true;

147}

148

150 ++NumAnalyzedModues;

152 ++NumAnalyzedFunctions;

154 ++NumEligibleFunctions;

155

157

158

159

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

163

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

166 std::move(IndexOperandHashes));

167

168 LocalFunctionMap->insert(SF);

169 }

170 }

171}

172

173

182

183

184

185

189

190

191 auto *MergedFunc = FI.F;

192 std::string NewFunctionName =

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

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

196

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

198

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

200

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

203 ParamTypes, false);

204

205

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

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

212

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

215

216

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

218

219

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

221

222

223 auto NewArgIter = NewFunction->arg_begin();

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

225 Argument &NewArg = *NewArgIter++;

227 }

228

229

230 unsigned NumOrigArgs = MergedFunc->arg_size();

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

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

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

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

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

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

238 Inst->setOperand(OpndIndex,

239 Builder.CreateAggregateCast(NewArg, OrigC->getType()));

240 } else {

241 Inst->setOperand(OpndIndex, NewArg);

242 }

243 }

244 }

245

246 return NewFunction;

247}

248

249

250

253 auto *Thunk = FI.F;

254

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

257 Thunk->dropAllReferences();

258

261

263 unsigned ParamIdx = 0;

265

266

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

268 Args.push_back(

269 Builder.CreateAggregateCast(&AI, ToFuncTy->getParamType(ParamIdx)));

270 ++ParamIdx;

271 }

272

273

274 for (auto *Param : Params) {

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

276 Args.push_back(

277 Builder.CreateAggregateCast(Param, ToFuncTy->getParamType(ParamIdx)));

278 ++ParamIdx;

279 }

280

281 CallInst *CI = Builder.CreateCall(ToFunc, Args);

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

289 Builder.CreateRetVoid();

290 else

291 Builder.CreateRet(Builder.CreateAggregateCast(CI, Thunk->getReturnType()));

292}

293

294

295

296

297

298

299

300

301

302

303

304

305

309

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

312 auto It = CurrInstOpndIndexToConstHash.find(Index);

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

314 return false;

315

316 auto CurrHash = It->second;

317 auto J = OldHashToCurrHash.find(OldHash);

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

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

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

321 return false;

322 }

323

324 return true;

325}

326

327

328static bool

332 for (auto &ParamLocs : ParamLocsVec) {

333 std::optional<stable_hash> OldHash;

334 std::optional<Constant *> OldConst;

338 auto [InstIndex, OpndIndex] = Loc;

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

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

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

342 if (!OldHash) {

343 OldHash = CurrHash;

344 OldConst = CurrConst;

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

346 return false;

347 }

348 }

349 }

350 return true;

351}

352

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

356 auto &RSF = *SFS[0];

357 unsigned StableFunctionCount = SFS.size();

358

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

360

361

362

363 std::vector<stable_hash> ConstHashSeq;

364 ConstHashSeq.push_back(Hash);

365 bool Identical = true;

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

367 auto &SF = SFS[J];

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

369 if (Hash != SHash)

370 Identical = false;

371 ConstHashSeq.push_back(SHash);

372 }

373

374 if (Identical)

375 continue;

376

377

378 HashSeqToLocs[ConstHashSeq].push_back(IndexPair);

379 }

380

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

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

384

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

387 });

388

389 return ParamLocsVec;

390}

391

394

395

397 HashToFuncs;

398 for (auto &F : M) {

400 continue;

402 if (FunctionMap->contains(FI.FunctionHash))

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

404 }

405

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

407 std::optional ParamLocsVec;

409 auto &SFS = FunctionMap->at(Hash);

410 assert(!SFS.empty());

411 auto &RFS = SFS[0];

412

413

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

415

416

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

418 continue;

419

423 auto [InstIndex, OpndIndex] = Index;

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

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

426 if ( ignoreOp (Inst, OpndIndex))

427 return false;

428 }

429 return true;

430 };

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

432 continue;

433

434 for (auto &SF : SFS) {

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

437

438

440 *FI.IndexOperandHashMap))

441 continue;

442 if (!ParamLocsVec.has_value()) {

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

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

446 }

448 *ParamLocsVec))

449 continue;

450

451

452

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

454 break;

455 }

456 }

457 unsigned FuncMergeInfoSize = FuncMergeInfos.size();

458 if (FuncMergeInfoSize == 0)

459 continue;

460

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

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

463

464 for (auto &FMI : FuncMergeInfos) {

466

467

468

471 for (auto &ParamLocs : *ParamLocsVec) {

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

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

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

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

478 }

479

480

483

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

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

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

488 MergedFunc->dump();

489 });

490

491

492

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

496 FMI.F->dump();

497 });

498 ++NumMergedFunctions;

499 }

500 }

501

503}

504

506

507 LocalFunctionMap = std::make_unique();

508

509

511 return;

512

513

514

515 if (Index && !Index->hasExportedFunctions(M))

516 return;

517

522}

523

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

526 << "\n");

527

528 if (LocalFunctionMap->empty())

529 return;

532

533 std::vector PatchItems;

536 COS.patch(PatchItems);

537

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

540

541 Triple TT(M.getTargetTriple());

545}

546

549

552

554 } else {

556

557

560 LocalFunctionMap->finalize();

561 FuncMap = LocalFunctionMap.get();

562 }

563

564 return merge(M, FuncMap);

565}

566

567namespace {

568

569class GlobalMergeFuncPassWrapper : public ModulePass {

570

571public:

572 static char ID;

573

574 GlobalMergeFuncPassWrapper();

575

576 void getAnalysisUsage(AnalysisUsage &AU) const override {

580 }

581

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

583

584 bool runOnModule(Module &M) override;

585};

586

587}

588

589char GlobalMergeFuncPassWrapper::ID = 0;

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

592

594 return new GlobalMergeFuncPassWrapper();

595}

596

597GlobalMergeFuncPassWrapper::GlobalMergeFuncPassWrapper() : ModulePass(ID) {

600}

601

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

603 const ModuleSummaryIndex *Index = nullptr;

604 if (auto *IndexWrapperPass =

605 getAnalysisIfAvailable())

606 Index = IndexWrapperPass->getIndex();

607

608 return GlobalMergeFunc(Index).run(M);

609}

610

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

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

Definition GlobalMergeFunctions.cpp:306

static ParamLocsVecTy computeParamInfo(const StableFunctionMap::StableFunctionEntries &SFS)

Definition GlobalMergeFunctions.cpp:354

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)

Definition GlobalMergeFunctions.cpp:47

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

Definition GlobalMergeFunctions.cpp:186

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

Definition GlobalMergeFunctions.cpp:251

static bool isEligibleInstructionForConstantSharing(const Instruction *I)

Definition GlobalMergeFunctions.cpp:117

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

Definition GlobalMergeFunctions.cpp:133

bool isEligibleFunction(Function *F)

Returns true if function F is eligible for merging.

Definition GlobalMergeFunctions.cpp:81

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

Definition GlobalMergeFunctions.cpp:329

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

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

Definition GlobalMergeFunctions.cpp:43

Machine Check Debug Module

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

MachineInstr unsigned OpIdx

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

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.

A wrapper class to abstract writer stream with support of bytes back patching.

LLVM_ABI void patch(ArrayRef< CGDataPatchItem > P)

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

Definition GlobalMergeFunctions.cpp:149

void initializeMergerMode(const Module &M)

Definition GlobalMergeFunctions.cpp:505

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

Merge functions in the module using the given function map.

Definition GlobalMergeFunctions.cpp:392

void emitFunctionMap(Module &M)

Emit LocalFunctionMap into __llvm_merge section.

Definition GlobalMergeFunctions.cpp:524

bool run(Module &M)

Definition GlobalMergeFunctions.cpp:547

static constexpr 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).

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

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

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

static LLVM_ABI PassRegistry * getPassRegistry()

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

virtual void getAnalysisUsage(AnalysisUsage &) const

getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...

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)

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.

std::string str() const

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

Triple - Helper class for working with autoconf configuration names.

const Use & getOperandUse(unsigned i) const

Value * getOperand(unsigned i) const

Type * getType() const

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

LLVM_ABI void replaceAllUsesWith(Value *V)

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

LLVM_ABI const Value * stripPointerCasts() const

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

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

LLVM_ABI void dump() const

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

A raw_ostream that writes to an SmallVector or SmallString.

StringRef str() const

Return a StringRef for the vector contents.

unsigned ID

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

@ SwiftTail

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

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.

decltype(auto) dyn_cast(const From &Val)

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

LLVM_ABI FunctionHashInfo StructuralHashWithDifferences(const Function &F, IgnoreOperandFunc IgnoreOp)

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

MapVector< unsigned, Instruction * > IndexInstrMap

A map from an instruction index to an instruction pointer.

LLVM_ABI ModulePass * createGlobalMergeFuncPass()

This pass performs merging similar functions globally.

SmallVector< IndexPairHash > IndexOperandHashVecType

auto dyn_cast_or_null(const Y &Val)

void sort(IteratorTy Start, IteratorTy End)

LLVM_ABI raw_ostream & dbgs()

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

StringRef get_stable_name(StringRef Name)

bool isa(const From &Val)

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

SmallVector< IndexPair, 4 > ParamLocs

LLVM_ABI void initializeGlobalMergeFuncPassWrapperPass(PassRegistry &)

std::pair< unsigned, unsigned > IndexPair

The pair of an instruction index and a operand index.

SmallVector< ParamLocs, 8 > ParamLocsVecTy

OutputIt move(R &&Range, OutputIt Out)

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

decltype(auto) cast(const From &Val)

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

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

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

Definition GlobalMergeFunctions.cpp:174

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

Definition GlobalMergeFunctions.cpp:178

StableFunctionMap::StableFunctionEntry * SF

Definition GlobalMergeFunctions.cpp:175

Function * F

Definition GlobalMergeFunctions.cpp:176

IndexInstrMap * IndexInstruction

Definition GlobalMergeFunctions.cpp:177

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

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

Definition GlobalMergeFunctions.cpp:611

const ModuleSummaryIndex * ImportSummary

static LLVM_ABI void serialize(raw_ostream &OS, const StableFunctionMap *FunctionMap, std::vector< CGDataPatchItem > &PatchItems)

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.

SmallVector< std::unique_ptr< StableFunctionEntry > > StableFunctionEntries

const StableFunctionEntries & at(HashFuncsMapType::key_type FunctionHash) const

bool contains(HashFuncsMapType::key_type FunctionHash) const

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