GlobalDCE.cpp Source File (original) (raw)

31using namespace llvm;

33#define DEBUG_TYPE "globaldce"

35namespace {

36class GlobalDCELegacyPass : public ModulePass {

37public:

38 static char ID;

41 }

42 bool runOnModule(Module &M) override {

43 if (skipModule(M))

44 return false;

48 auto PA = Impl.run(M, MAM);

49 return !PA.areAllPreserved();

50 }

52private:

54};

55}

57char GlobalDCELegacyPass::ID = 0;

58 INITIALIZE_PASS(GlobalDCELegacyPass, "globaldce", "Dead Global Elimination",

59 false, false)

66 cl::desc("Enable virtual function elimination"));

68 STATISTIC(NumAliases , "Number of global aliases removed");

69 STATISTIC(NumFunctions, "Number of functions removed");

70 STATISTIC(NumIFuncs, "Number of indirect functions removed");

71 STATISTIC(NumVariables, "Number of global variables removed");

72 STATISTIC(NumVFuncs, "Number of virtual functions removed");

77 if (F->isDeclaration())

78 return false;

80 for (auto &I : Entry) {

81 if (I.isDebugOrPseudoInst())

82 continue;

84 return !RI->getReturnValue();

85 break;

86 }

87 return false;

88}

92void GlobalDCEPass::ComputeDependencies(Value *V,

95 Function *Parent = I->getParent()->getParent();

100

101 auto [Where, Inserted] = ConstantDependenciesCache.try_emplace(CE);

102 SmallPtrSetImpl<GlobalValue *> &LocalDeps = Where->second;

103 if (Inserted) {

104 for (User *CEUser : CE->users())

105 ComputeDependencies(CEUser, LocalDeps);

106 }

108 }

109}

110

111void GlobalDCEPass::UpdateGVDependencies(GlobalValue &GV) {

112 SmallPtrSet<GlobalValue *, 8> Deps;

113 for (User *User : GV.users())

114 ComputeDependencies(User, Deps);

115 Deps.erase(&GV);

116 for (GlobalValue *GVU : Deps) {

117

118

119

120

121 if (VFESafeVTables.count(GVU) && isa(&GV)) {

122 LLVM_DEBUG(dbgs() << "Ignoring dep " << GVU->getName() << " -> "

123 << GV.getName() << "\n");

124 continue;

125 }

126 GVDependencies[GVU].insert(&GV);

127 }

128}

129

130

131void GlobalDCEPass::MarkLive(GlobalValue &GV,

133 auto const Ret = AliveGlobals.insert(&GV);

134 if (!Ret.second)

135 return;

136

137 if (Updates)

140 for (auto &&CM : make_range(ComdatMembers.equal_range(C))) {

141 MarkLive(*CM.second, Updates);

142

143 }

144 }

145}

146

147void GlobalDCEPass::ScanVTables(Module &M) {

149 LLVM_DEBUG(dbgs() << "Building type info -> vtable map\n");

150

151 for (GlobalVariable &GV : M.globals()) {

153 GV.getMetadata(LLVMContext::MD_type, Types);

155 continue;

156

157

158

159

160 for (MDNode *Type : Types) {

162

166 ->getZExtValue();

167

168 TypeIdMap[TypeID].insert(std::make_pair(&GV, Offset));

169 }

170

171

172

173

177 (InLTOPostLink &&

180 VFESafeVTables.insert(&GV);

181 }

182 }

183 }

184}

185

186void GlobalDCEPass::ScanVTableLoad(Function *Caller, Metadata *TypeId,

187 uint64_t CallOffset) {

188 for (const auto &VTableInfo : TypeIdMap[TypeId]) {

189 GlobalVariable *VTable = VTableInfo.first;

190 uint64_t VTableOffset = VTableInfo.second;

191

194 *Caller->getParent(), VTable);

195 if (!Ptr) {

196 LLVM_DEBUG(dbgs() << "can't find pointer in vtable!\n");

197 VFESafeVTables.erase(VTable);

198 continue;

199 }

200

202 if (!Callee) {

203 LLVM_DEBUG(dbgs() << "vtable entry is not function pointer!\n");

204 VFESafeVTables.erase(VTable);

205 continue;

206 }

207

209 << Callee->getName() << "\n");

210 GVDependencies[Caller].insert(Callee);

211 }

212}

213

214void GlobalDCEPass::ScanTypeCheckedLoadIntrinsics(Module &M) {

215 LLVM_DEBUG(dbgs() << "Scanning type.checked.load intrinsics\n");

216 Function *TypeCheckedLoadFunc =

219 &M, Intrinsic::type_checked_load_relative);

220

221 auto scan = [&](Function *CheckedLoadFunc) {

222 if (!CheckedLoadFunc)

223 return;

224

225 for (auto *U : CheckedLoadFunc->users()) {

227 if (!CI)

228 continue;

229

231 Value *TypeIdValue = CI->getArgOperand(2);

233

235 ScanVTableLoad(CI->getFunction(), TypeId, Offset->getZExtValue());

236 } else {

237

238

239 for (const auto &VTableInfo : TypeIdMap[TypeId]) {

240 VFESafeVTables.erase(VTableInfo.first);

241 }

242 }

243 }

244 };

245

246 scan(TypeCheckedLoadFunc);

247 scan(TypeCheckedLoadRelativeFunc);

248}

249

250void GlobalDCEPass::AddVirtualFunctionDependencies(Module &M) {

252 return;

253

254

255

256

257

259 M.getModuleFlag("Virtual Function Elim"));

260 if (!Val || Val->isZero())

261 return;

262

263 ScanVTables(M);

264

265 if (VFESafeVTables.empty())

266 return;

267

268 ScanTypeCheckedLoadIntrinsics(M);

269

271 dbgs() << "VFE safe vtables:\n";

272 for (auto *VTable : VFESafeVTables)

273 dbgs() << " " << VTable->getName() << "\n";

274 );

275}

276

279

280

281

282

283

284

285

286

287

288

291

292

294 if (Comdat *C = F.getComdat())

295 ComdatMembers.insert(std::make_pair(C, &F));

298 ComdatMembers.insert(std::make_pair(C, &GV));

300 if (Comdat *C = GA.getComdat())

301 ComdatMembers.insert(std::make_pair(C, &GA));

302

303

304

305 AddVirtualFunctionDependencies(M);

306

307

308 for (GlobalObject &GO : M.global_objects()) {

309 GO.removeDeadConstantUsers();

310

311

312

313 if (!GO.isDeclaration())

314 if (!GO.isDiscardableIfUnused())

315 MarkLive(GO);

316

317 UpdateGVDependencies(GO);

318 }

319

320

322 GA.removeDeadConstantUsers();

323

324 if (!GA.isDiscardableIfUnused())

325 MarkLive(GA);

326

327 UpdateGVDependencies(GA);

328 }

329

330

332 GIF.removeDeadConstantUsers();

333

334 if (!GIF.isDiscardableIfUnused())

335 MarkLive(GIF);

336

337 UpdateGVDependencies(GIF);

338 }

339

340

341

343 AliveGlobals.end()};

344 while (!NewLiveGVs.empty()) {

346 for (auto *GVD : GVDependencies[LGV])

347 MarkLive(*GVD, &NewLiveGVs);

348 }

349

350

351

352

353

354

355 std::vector<GlobalVariable *> DeadGlobalVars;

357 if (!AliveGlobals.count(&GV)) {

358 DeadGlobalVars.push_back(&GV);

359 if (GV.hasInitializer()) {

361 GV.setInitializer(nullptr);

363 Init->destroyConstant();

364 }

365 }

366

367

368 std::vector<Function *> DeadFunctions;

370 if (!AliveGlobals.count(&F)) {

371 DeadFunctions.push_back(&F);

372 if (.isDeclaration())

373 F.deleteBody();

374 }

375

376

377 std::vector<GlobalAlias*> DeadAliases;

379 if (!AliveGlobals.count(&GA)) {

380 DeadAliases.push_back(&GA);

381 GA.setAliasee(nullptr);

382 }

383

384

385 std::vector<GlobalIFunc*> DeadIFuncs;

387 if (!AliveGlobals.count(&GIF)) {

388 DeadIFuncs.push_back(&GIF);

389 GIF.setResolver(nullptr);

390 }

391

392

393

394 auto EraseUnusedGlobalValue = [&](GlobalValue *GV) {

398 };

399

400 NumFunctions += DeadFunctions.size();

401 for (Function *F : DeadFunctions) {

402 if (->use_empty()) {

403

404

405

406

407 ++NumVFuncs;

408

409

410

411

412

413

414

415

417

419 }

420 EraseUnusedGlobalValue(F);

421 }

422

423 NumVariables += DeadGlobalVars.size();

425 EraseUnusedGlobalValue(GV);

426

427 NumAliases += DeadAliases.size();

429 EraseUnusedGlobalValue(GA);

430

431 NumIFuncs += DeadIFuncs.size();

433 EraseUnusedGlobalValue(GIF);

434

435

436 AliveGlobals.clear();

437 ConstantDependenciesCache.clear();

438 GVDependencies.clear();

439 ComdatMembers.clear();

440 TypeIdMap.clear();

441 VFESafeVTables.clear();

442

446}

447

451 OS, MapClassName2PassName);

452 if (InLTOPostLink)

453 OS << "";

454}

static bool isEmptyFunction(Function *F)

Returns true if F is effectively empty.

Definition GlobalDCE.cpp:75

static cl::opt< bool > ClEnableVFE("enable-vfe", cl::Hidden, cl::init(true), cl::desc("Enable virtual function elimination"))

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

ModuleAnalysisManager MAM

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

This file defines the SmallPtrSet class.

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

#define STATISTIC(VARNAME, DESC)

LLVM Basic Block Representation.

static LLVM_ABI ConstantPointerNull * get(PointerType *T)

Static factory methods - Return objects of the specified value.

This is an important base class in LLVM.

const Constant * stripPointerCasts() const

LLVM_ABI void removeDeadConstantUsers() const

If there are any dead constant users dangling off of this constant, remove them.

Pass to remove unused function declarations.

LLVM_ABI void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)

Definition GlobalDCE.cpp:448

LLVM_ABI PreservedAnalyses run(Module &M, ModuleAnalysisManager &)

Definition GlobalDCE.cpp:277

@ VCallVisibilityLinkageUnit

@ VCallVisibilityTranslationUnit

LLVM_ABI bool isDeclaration() const

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

LLVM_ABI const Comdat * getComdat() const

LLVM_ABI void eraseFromParent()

This method unlinks 'this' from the containing module and deletes it.

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

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.

A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...

bool erase(PtrType Ptr)

Remove pointer from the set.

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.

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

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.

LLVM Value Representation.

iterator_range< user_iterator > users()

LLVM_ABI StringRef getName() const

Return a constant reference to the value's name.

MDNode * getMetadata(unsigned KindID) const

Get the current metadata attachments for the given kind, if any.

An efficient, type-erasing, non-owning reference to a callable.

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

unsigned ID

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

@ C

The default llvm calling convention, compatible with C.

LLVM_ABI Function * getDeclarationIfExists(const Module *M, ID id)

Look up the Function declaration of the intrinsic id in the Module M and return it if it exists.

@ CE

Windows NT (Windows on ARM)

initializer< Ty > init(const Ty &Val)

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

Extract a Value from Metadata, if any, allowing null.

This is an optimization pass for GlobalISel generic memory operations.

FunctionAddr VTableAddr Value

decltype(auto) dyn_cast(const From &Val)

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

iterator_range< T > make_range(T x, T y)

Convenience function for iterating over sub-ranges.

LLVM_ABI ModulePass * createGlobalDCEPass()

bool isSafeToDestroyConstant(const Constant *C)

It is safe to destroy a constant iff it is only used by constants itself.

LLVM_ABI void initializeGlobalDCELegacyPassPass(PassRegistry &)

bool optimizeGlobalCtorsList(Module &M, function_ref< bool(uint32_t, Function *)> ShouldRemove)

Call "ShouldRemove" for every entry in M's global_ctor list and remove the entries for which it retur...

LLVM_ABI raw_ostream & dbgs()

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

class LLVM_GSL_OWNER SmallVector

Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...

bool isa(const From &Val)

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

decltype(auto) cast(const From &Val)

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

void replaceRelativePointerUsersWithZero(Constant *C)

Finds the same "relative pointer" pattern as described above, where the target is C,...

AnalysisManager< Module > ModuleAnalysisManager

Convenience typedef for the Module analysis manager.

Constant * getPointerAtOffset(Constant *I, uint64_t Offset, Module &M, Constant *TopLevelGlobal=nullptr)

Processes a Constant recursively looking into elements of arrays, structs and expressions to find a t...

A CRTP mix-in to automatically provide informational APIs needed for passes.