GlobalMerge.cpp Source File (original) (raw)

97#include

98#include

99#include

100#include

101#include

102#include

103

104using namespace llvm;

105

106#define DEBUG_TYPE "global-merge"

107

108

111 cl::desc("Enable the global merge pass"),

113

116 cl::desc("Set maximum offset for global merge pass"),

118

120 "global-merge-group-by-use", cl::Hidden,

121 cl::desc("Improve global merge pass to look at uses"), cl::init(true));

122

124 "global-merge-all-const", cl::Hidden,

125 cl::desc("Merge all const globals without looking at uses"),

127

129 "global-merge-ignore-single-use", cl::Hidden,

130 cl::desc("Improve global merge pass to ignore globals only used alone"),

132

135 cl::desc("Enable global merge pass on constants"),

137

138

139

142 cl::desc("Enable global merge pass on external linkage"));

143

146 cl::desc("The minimum size in bytes of each global "

147 "that should considered in merging."),

149

150 STATISTIC(NumMerged, "Number of globals merged");

151

152namespace {

153

154class GlobalMergeImpl {

157 bool IsMachO = false;

158

159private:

161 bool isConst, unsigned AddrSpace) const;

162

163

164

167 unsigned AddrSpace) const;

168

169

170

171

172 bool isMustKeepGlobalVariable(const GlobalVariable *GV) const {

173 return MustKeepGlobalVariables.count(GV);

174 }

175

176

177

178 void setMustKeepGlobalVariables(Module &M);

179

180

182

183

184 SmallSetVector<const GlobalVariable *, 16> MustKeepGlobalVariables;

185

186public:

187 GlobalMergeImpl(const TargetMachine *TM, GlobalMergeOptions Opt)

188 : TM(TM), Opt(Opt) {}

190};

191

193 const TargetMachine *TM = nullptr;

194 GlobalMergeOptions Opt;

195

196public:

197 static char ID;

198

199 explicit GlobalMerge() : FunctionPass(ID) {

204 }

205

206 explicit GlobalMerge(const TargetMachine *TM, unsigned MaximalOffset,

207 bool OnlyOptimizeForSize, bool MergeExternalGlobals,

208 bool MergeConstantGlobals, bool MergeConstAggressive)

209 : FunctionPass(ID), TM(TM) {

210 Opt.MaxOffset = MaximalOffset;

211 Opt.SizeOnly = OnlyOptimizeForSize;

212 Opt.MergeExternal = MergeExternalGlobals;

213 Opt.MergeConstantGlobals = MergeConstantGlobals;

214 Opt.MergeConstAggressive = MergeConstAggressive;

216 }

217

218 bool doInitialization(Module &M) override {

219 auto GetSmallDataLimit = [](Module &M) -> std::optional<uint64_t> {

220 Metadata *SDL = M.getModuleFlag("SmallDataLimit");

221 if (!SDL)

222 return std::nullopt;

224 };

227 else if (auto SDL = GetSmallDataLimit(M); SDL && *SDL > 0)

228 Opt.MinSize = *SDL + 1;

229 else

230 Opt.MinSize = 0;

231

232 GlobalMergeImpl P(TM, Opt);

233 return P.run(M);

234 }

235 bool runOnFunction(Function &F) override { return false; }

236

237 StringRef getPassName() const override { return "Merge internal globals"; }

238

239 void getAnalysisUsage(AnalysisUsage &AU) const override {

241 FunctionPass::getAnalysisUsage(AU);

242 }

243};

244

245}

246

248 GlobalMergeImpl P(TM, Options);

252

255 return PA;

256}

257

258char GlobalMerge::ID = 0;

259

261

263 Module &M, bool isConst,

264 unsigned AddrSpace) const {

265 auto &DL = M.getDataLayout();

266

269

270 return DL.getTypeAllocSize(GV1->getValueType()).getFixedValue() <

271 DL.getTypeAllocSize(GV2->getValueType()).getFixedValue();

272 });

273

274

276 BitVector AllGlobals(Globals.size(), true);

277 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);

278 }

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299 struct UsedGlobalSet {

300 BitVector Globals;

301 unsigned UsageCount = 1;

302

303 UsedGlobalSet(size_t Size) : Globals(Size) {}

304 };

305

306

307 std::vector UsedGlobalSets;

308

309

310 auto CreateGlobalSet = [&]() -> UsedGlobalSet & {

311 UsedGlobalSets.emplace_back(Globals.size());

312 return UsedGlobalSets.back();

313 };

314

315

316 CreateGlobalSet().UsageCount = 0;

317

318

319

320

321

322

323

324

325

326

327

328 DenseMap<Function *, size_t > GlobalUsesByFunction;

329

330

331

332

333

334

335

336

337 std::vector<size_t> EncounteredUGS;

338

339 for (size_t GI = 0, GE = Globals.size(); GI != GE; ++GI) {

341

342

343

344 EncounteredUGS.assign(UsedGlobalSets.size(), 0);

345

346

347

348 size_t CurGVOnlySetIdx = 0;

349

350

351 for (auto &U : GV->uses()) {

352

353

354 Use *UI, *UE;

356 if (CE->use_empty())

357 continue;

358 UI = &*CE->use_begin();

359 UE = nullptr;

361 UI = &U;

362 UE = UI->getNext();

363 } else {

364 continue;

365 }

366

367

368

369 for (; UI != UE; UI = UI->getNext()) {

371 if ()

372 continue;

373

375

376

378 continue;

379

380 size_t UGSIdx = GlobalUsesByFunction[ParentFn];

381

382

383

384 if (!UGSIdx) {

385

386 if (!CurGVOnlySetIdx) {

387 CurGVOnlySetIdx = UsedGlobalSets.size();

388 CreateGlobalSet().Globals.set(GI);

389 } else {

390 ++UsedGlobalSets[CurGVOnlySetIdx].UsageCount;

391 }

392

393 GlobalUsesByFunction[ParentFn] = CurGVOnlySetIdx;

394 continue;

395 }

396

397

398

399 if (UsedGlobalSets[UGSIdx].Globals.test(GI)) {

400 ++UsedGlobalSets[UGSIdx].UsageCount;

401 continue;

402 }

403

404

405 --UsedGlobalSets[UGSIdx].UsageCount;

406

407

408

409 if (size_t ExpandedIdx = EncounteredUGS[UGSIdx]) {

410 ++UsedGlobalSets[ExpandedIdx].UsageCount;

411 GlobalUsesByFunction[ParentFn] = ExpandedIdx;

412 continue;

413 }

414

415

416

417 GlobalUsesByFunction[ParentFn] = EncounteredUGS[UGSIdx] =

418 UsedGlobalSets.size();

419

420 UsedGlobalSet &NewUGS = CreateGlobalSet();

421 NewUGS.Globals.set(GI);

422 NewUGS.Globals |= UsedGlobalSets[UGSIdx].Globals;

423 }

424 }

425 }

426

427

428

429

431 BitVector AllGlobals(Globals.size());

432 for (const UsedGlobalSet &UGS : UsedGlobalSets) {

433 if (UGS.UsageCount == 0)

434 continue;

435 if (UGS.Globals.count() > 1)

436 AllGlobals |= UGS.Globals;

437 }

438 return doMerge(Globals, AllGlobals, M, isConst, AddrSpace);

439 }

440

441

442

443

444

445

446

448 [](const UsedGlobalSet &UGS1, const UsedGlobalSet &UGS2) {

449 return UGS1.Globals.count() * UGS1.UsageCount <

450 UGS2.Globals.count() * UGS2.UsageCount;

451 });

452

453

454

455

456

457

458

459 BitVector PickedGlobals(Globals.size());

461

462 for (const UsedGlobalSet &UGS : llvm::reverse(UsedGlobalSets)) {

463 if (UGS.UsageCount == 0)

464 continue;

465 if (PickedGlobals.anyCommon(UGS.Globals))

466 continue;

467 PickedGlobals |= UGS.Globals;

468

469

470

471 if (UGS.Globals.count() < 2)

472 continue;

473 Changed |= doMerge(Globals, UGS.Globals, M, isConst, AddrSpace);

474 }

475

477}

478

481 bool isConst, unsigned AddrSpace) const {

483

486 auto &DL = M.getDataLayout();

487

488 LLVM_DEBUG(dbgs() << " Trying to merge set, starts with #"

489 << GlobalSet.find_first() << ", total of " << Globals.size()

490 << "\n");

491

494 while (i != -1) {

495 ssize_t j = 0;

496 uint64_t MergedSize = 0;

497 std::vector<Type*> Tys;

498 std::vector<Constant*> Inits;

499 std::vector StructIdxs;

500

501 bool HasExternal = false;

504 unsigned CurIdx = 0;

505 for (j = i; j != -1; j = GlobalSet.find_next(j)) {

506 Type *Ty = Globals[j]->getValueType();

507

508

509 Align Alignment = DL.getPreferredAlign(Globals[j]);

510 unsigned Padding = alignTo(MergedSize, Alignment) - MergedSize;

512 MergedSize += DL.getTypeAllocSize(Ty);

513 if (MergedSize > Opt.MaxOffset) {

514 break;

515 }

516 if (Padding) {

519 ++CurIdx;

520 }

521 Tys.push_back(Ty);

522 Inits.push_back(Globals[j]->getInitializer());

523 StructIdxs.push_back(CurIdx++);

524

525 MaxAlign = std::max(MaxAlign, Alignment);

526

527 if (Globals[j]->hasExternalLinkage() && !HasExternal) {

528 HasExternal = true;

529 FirstExternalName = Globals[j]->getName();

530 }

531 }

532

533

534 if (Tys.size() < 2) {

535 i = j;

536 continue;

537 }

538

539

540

544

547

548

549

550

551

552

553

554 Twine MergedName =

555 (IsMachO && HasExternal)

556 ? "_MergedGlobals_" + FirstExternalName

557 : "_MergedGlobals";

560 M, MergedTy, isConst, MergedLinkage, MergedInit, MergedName, nullptr,

562

563 MergedGV->setAlignment(MaxAlign);

564 MergedGV->setSection(Globals[i]->getSection());

565

566 LLVM_DEBUG(dbgs() << "MergedGV: " << *MergedGV << "\n");

567

568 const StructLayout *MergedLayout = DL.getStructLayout(MergedTy);

569 for (ssize_t k = i, idx = 0; k != j; k = GlobalSet.find_next(k), ++idx) {

574 Globals[k]->getDLLStorageClass();

575

576

577

578 MergedGV->copyMetadata(Globals[k],

580

582 ConstantInt::get(Int32Ty, 0),

583 ConstantInt::get(Int32Ty, StructIdxs[idx]),

584 };

587 Globals[k]->replaceAllUsesWith(GEP);

588 Globals[k]->eraseFromParent();

589

590

591

592

593

594

595

596

597

598

599

600

606 }

607

608 NumMerged++;

609 }

611 i = j;

612 }

613

615}

616

617void GlobalMergeImpl::collectUsedGlobalVariables(Module &M, StringRef Name) {

618

621

622

624

625 for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i)

628 MustKeepGlobalVariables.insert(G);

629}

630

631void GlobalMergeImpl::setMustKeepGlobalVariables(Module &M) {

634

639 if (!Pad->isEHPad() &&

640 !(II && II->getIntrinsicID() == Intrinsic::eh_typeid_for))

641 continue;

642

643

644

645 for (const Use &U : Pad->operands()) {

648 MustKeepGlobalVariables.insert(GV);

650 for (const Use &Elt : CA->operands()) {

653 MustKeepGlobalVariables.insert(GV);

654 }

655 }

656 }

657 }

658 }

659}

660

661

662

663

664

666

667

668 return Section.starts_with("__DATA,__cfstring") ||

669 Section.starts_with("__DATA,__objc_classrefs") ||

670 Section.starts_with("__DATA,__objc_selrefs");

671}

672

673bool GlobalMergeImpl::run(Module &M) {

675 return false;

676

677 IsMachO = M.getTargetTriple().isOSBinFormatMachO();

678

679 auto &DL = M.getDataLayout();

681 Globals, ConstGlobals, BSSGlobals;

683 setMustKeepGlobalVariables(M);

684

686 dbgs() << "Number of GV that must be kept: " <<

687 MustKeepGlobalVariables.size() << "\n";

688 for (const GlobalVariable *KeptGV : MustKeepGlobalVariables)

689 dbgs() << "Kept: " << *KeptGV << "\n";

690 });

691

692 for (auto &GV : M.globals()) {

693

695 continue;

696

697

699 continue;

700

703 continue;

704

706 assert(PT && "Global variable is not a pointer!");

707

708 unsigned AddressSpace = PT->getAddressSpace();

710

711

713 continue;

714

715

718 continue;

719

720

721 if (isMustKeepGlobalVariable(&GV))

722 continue;

723

724

725

726

727

728

730 continue;

731

733 TypeSize AllocSize = DL.getTypeAllocSize(Ty);

736 if (TM &&

741 else

743 }

745 << "\n");

746 }

747

748 for (auto &P : Globals)

749 if (P.second.size() > 1)

750 Changed |= doMerge(P.second, M, false, P.first.first);

751

752 for (auto &P : BSSGlobals)

753 if (P.second.size() > 1)

754 Changed |= doMerge(P.second, M, false, P.first.first);

755

757 for (auto &P : ConstGlobals)

758 if (P.second.size() > 1)

759 Changed |= doMerge(P.second, M, true, P.first.first);

760

762}

763

765 bool OnlyOptimizeForSize,

766 bool MergeExternalByDefault,

767 bool MergeConstantByDefault,

768 bool MergeConstAggressiveByDefault) {

774 : MergeConstAggressiveByDefault;

778 return new GlobalMerge(TM, PreferOffset, OnlyOptimizeForSize, MergeExternal,

779 MergeConstant, MergeConstAggressive);

780}

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

MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL

This file implements the BitVector class.

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

This file defines the DenseMap class.

static bool runOnFunction(Function &F, bool PostInlining)

static cl::opt< bool > GlobalMergeIgnoreSingleUse("global-merge-ignore-single-use", cl::Hidden, cl::desc("Improve global merge pass to ignore globals only used alone"), cl::init(true))

static cl::opt< bool > GlobalMergeGroupByUse("global-merge-group-by-use", cl::Hidden, cl::desc("Improve global merge pass to look at uses"), cl::init(true))

static bool isSpecialMachOSection(StringRef Section)

Definition GlobalMerge.cpp:665

static cl::opt< bool > GlobalMergeAllConst("global-merge-all-const", cl::Hidden, cl::desc("Merge all const globals without looking at uses"), cl::init(false))

static cl::opt< bool > EnableGlobalMergeOnConst("global-merge-on-const", cl::Hidden, cl::desc("Enable global merge pass on constants"), cl::init(false))

static cl::opt< unsigned > GlobalMergeMinDataSize("global-merge-min-data-size", cl::desc("The minimum size in bytes of each global " "that should considered in merging."), cl::init(0), cl::Hidden)

static cl::opt< unsigned > GlobalMergeMaxOffset("global-merge-max-offset", cl::Hidden, cl::desc("Set maximum offset for global merge pass"), cl::init(0))

static cl::opt< bool > EnableGlobalMerge("enable-global-merge", cl::Hidden, cl::desc("Enable the global merge pass"), cl::init(true))

static cl::opt< cl::boolOrDefault > EnableGlobalMergeOnExternal("global-merge-on-external", cl::Hidden, cl::desc("Enable global merge pass on external linkage"))

Module.h This file contains the declarations for the Module class.

This defines the Use class.

Machine Check Debug Module

This file implements a map that provides insertion order iteration.

uint64_t IntrinsicInst * II

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

static StringRef getName(Value *V)

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

This file defines the SmallVector class.

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

#define STATISTIC(VARNAME, DESC)

LLVM_ABI void setPreservesCFG()

This function should be called by the pass, iff they do not:

static LLVM_ABI ArrayType * get(Type *ElementType, uint64_t NumElements)

This static method is the primary way to construct an ArrayType.

LLVM Basic Block Representation.

InstListType::iterator iterator

Instruction iterators...

int find_first() const

find_first - Returns the index of the first set bit, -1 if none of the bits are set.

int find_next(unsigned Prev) const

find_next - Returns the index of the next set bit following the "Prev" bit.

Represents analyses that only rely on functions' control flow.

static LLVM_ABI ConstantAggregateZero * get(Type *Ty)

ConstantArray - Constant Array Declarations.

A constant value that is initialized with an expression using other constant values.

static Constant * getInBoundsGetElementPtr(Type *Ty, Constant *C, ArrayRef< Constant * > IdxList)

Create an "inbounds" getelementptr.

static LLVM_ABI Constant * get(StructType *T, ArrayRef< Constant * > V)

This is an important base class in LLVM.

FunctionPass class - This class is used to implement most global optimizations.

bool hasMinSize() const

Optimize this function for minimum size (-Oz).

static LLVM_ABI GlobalAlias * create(Type *Ty, unsigned AddressSpace, LinkageTypes Linkage, const Twine &Name, Constant *Aliasee, Module *Parent)

If a parent module is specified, the alias is automatically inserted into the end of the specified mo...

PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM)

Definition GlobalMerge.cpp:247

StringRef getSection() const

Get the custom section of this global if it has one.

bool hasExternalLinkage() const

bool isThreadLocal() const

If the value is "Thread Local", its value isn't shared by the threads.

LLVM_ABI bool isDeclaration() const

Return true if the primary definition of this global value is outside of the current translation unit...

bool hasLocalLinkage() const

void setDLLStorageClass(DLLStorageClassTypes C)

DLLStorageClassTypes

Storage classes of global values for PE targets.

Module * getParent()

Get the module that this global value is contained inside of...

PointerType * getType() const

Global values are always pointers.

VisibilityTypes

An enumeration for the kinds of visibility of global values.

void setVisibility(VisibilityTypes V)

LinkageTypes

An enumeration for the kinds of linkage for global values.

@ PrivateLinkage

Like Internal, but omit from symbol table.

@ InternalLinkage

Rename collisions when linking (static functions).

@ ExternalLinkage

Externally visible function.

Type * getValueType() const

const Constant * getInitializer() const

getInitializer - Return the initializer for this global variable.

bool hasInitializer() const

Definitions have initializers, declarations don't.

bool hasImplicitSection() const

Check if section name is present.

bool isConstant() const

If the value is a global constant, its value is immutable throughout the runtime execution of the pro...

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

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

Pass interface - Implemented by all 'passes'.

Class to represent pointers.

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.

PreservedAnalyses & preserveSet()

Mark an analysis set as preserved.

This class consists of common code factored out of the SmallVector class to reduce code duplication b...

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.

bool starts_with(StringRef Prefix) const

Check if this string starts with the given Prefix.

Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...

TypeSize getElementOffset(unsigned Idx) const

Class to represent struct types.

static LLVM_ABI StructType * get(LLVMContext &Context, ArrayRef< Type * > Elements, bool isPacked=false)

This static method is the primary way to create a literal StructType.

static SectionKind getKindForGlobal(const GlobalObject *GO, const TargetMachine &TM)

Classify the specified global variable into a set of target independent categories embodied in Sectio...

Primary interface to the complete machine description for the target machine.

bool shouldAssumeDSOLocal(const GlobalValue *GV) const

Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...

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

static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)

static LLVM_ABI IntegerType * getInt8Ty(LLVMContext &C)

A Use represents the edge between a Value definition and its users.

Value * getOperand(unsigned i) const

unsigned getNumOperands() const

LLVM_ABI const Value * stripPointerCasts() const

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

iterator_range< use_iterator > uses()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

@ CE

Windows NT (Windows on ARM)

initializer< Ty > init(const Ty &Val)

PointerTypeMap run(const Module &M)

Compute the PointerTypeMap for the module M.

std::enable_if_t< detail::IsValidPointer< X, Y >::value, X * > extract(Y &&MD)

Extract a Value from Metadata.

Expected< const typename ELFT::Shdr * > getSection(typename ELFT::ShdrRange Sections, uint32_t Index)

This is an optimization pass for GlobalISel generic memory operations.

void stable_sort(R &&Range)

decltype(auto) dyn_cast(const From &Val)

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

FunctionAddr VTableAddr uintptr_t uintptr_t Int32Ty

LLVM_ABI Pass * createGlobalMergePass(const TargetMachine *TM, unsigned MaximalOffset, bool OnlyOptimizeForSize=false, bool MergeExternalByDefault=false, bool MergeConstantByDefault=false, bool MergeConstAggressiveByDefault=false)

GlobalMerge - This pass merges internal (by default) globals into structs to enable reuse of a base p...

Definition GlobalMerge.cpp:764

LLVM_ABI void initializeGlobalMergePass(PassRegistry &)

auto reverse(ContainerTy &&C)

LLVM_ABI raw_ostream & dbgs()

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

bool isa(const From &Val)

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

uint64_t alignTo(uint64_t Size, Align A)

Returns a multiple of A needed to store Size bytes.

decltype(auto) cast(const From &Val)

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

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

LLVM_ABI GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallVectorImpl< GlobalValue * > &Vec, bool CompilerUsed)

Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...

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

bool MergeConstAggressive

Whether we should merge constant global variables aggressively without looking at use.

bool SizeOnly

Whether we should try to optimize for size only.

bool MergeExternal

Whether we should merge global variables that have external linkage.

bool MergeConstantGlobals

Whether we should merge constant global variables.