1//===- CtorUtils.cpp - Helpers for working with global_ctors ----*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file defines functions that are used to process llvm.global_ctors.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Transforms/Utils/CtorUtils.h"
14#include "llvm/ADT/BitVector.h"
15#include "llvm/IR/Constants.h"
16#include "llvm/IR/Function.h"
17#include "llvm/IR/GlobalVariable.h"
18#include "llvm/IR/Module.h"
19#include "llvm/Support/Debug.h"
20#include "llvm/Support/raw_ostream.h"
21#include <numeric>
22
23#define DEBUG_TYPE "ctor_utils"
24
25using namespace llvm;
26
27/// Given a specified llvm.global_ctors list, remove the listed elements.
28static void removeGlobalCtors(GlobalVariable *GCL, const BitVector &CtorsToRemove) {
29 // Filter out the initializer elements to remove.
30 ConstantArray *OldCA = cast<ConstantArray>(Val: GCL->getInitializer());
31 SmallVector<Constant *, 10> CAList;
32 for (unsigned I = 0, E = OldCA->getNumOperands(); I < E; ++I)
33 if (!CtorsToRemove.test(Idx: I))
34 CAList.push_back(Elt: OldCA->getOperand(i_nocapture: I));
35
36 // Create the new array initializer.
37 ArrayType *ATy =
38 ArrayType::get(ElementType: OldCA->getType()->getElementType(), NumElements: CAList.size());
39 Constant *CA = ConstantArray::get(T: ATy, V: CAList);
40
41 // If we didn't change the number of elements, don't create a new GV.
42 if (CA->getType() == OldCA->getType()) {
43 GCL->setInitializer(CA);
44 return;
45 }
46
47 // Create the new global and insert it next to the existing list.
48 GlobalVariable *NGV = new GlobalVariable(
49 CA->getType(), GCL->isConstant(), GCL->getLinkage(), CA, "",
50 GCL->getThreadLocalMode(), GCL->getAddressSpace());
51 GCL->getParent()->insertGlobalVariable(Where: GCL->getIterator(), GV: NGV);
52 NGV->takeName(V: GCL);
53
54 // Nuke the old list, replacing any uses with the new one.
55 if (!GCL->use_empty())
56 GCL->replaceAllUsesWith(V: NGV);
57
58 GCL->eraseFromParent();
59}
60
61/// Given a llvm.global_ctors list that we can understand,
62/// return a list of the functions and null terminator as a vector.
63static std::vector<std::pair<uint32_t, Function *>>
64parseGlobalCtors(GlobalVariable *GV) {
65 ConstantArray *CA = cast<ConstantArray>(Val: GV->getInitializer());
66 std::vector<std::pair<uint32_t, Function *>> Result;
67 Result.reserve(n: CA->getNumOperands());
68 for (auto &V : CA->operands()) {
69 ConstantStruct *CS = cast<ConstantStruct>(Val&: V);
70 Result.emplace_back(args: cast<ConstantInt>(Val: CS->getOperand(i_nocapture: 0))->getZExtValue(),
71 args: dyn_cast<Function>(Val: CS->getOperand(i_nocapture: 1)));
72 }
73 return Result;
74}
75
76/// Find the llvm.global_ctors list.
77static GlobalVariable *findGlobalCtors(Module &M) {
78 GlobalVariable *GV = M.getGlobalVariable(Name: "llvm.global_ctors");
79 if (!GV)
80 return nullptr;
81
82 // Verify that the initializer is simple enough for us to handle. We are
83 // only allowed to optimize the initializer if it is unique.
84 if (!GV->hasUniqueInitializer())
85 return nullptr;
86
87 // If there are no ctors, then the initializer might be null/undef/poison.
88 // Ignore anything but an array.
89 ConstantArray *CA = dyn_cast<ConstantArray>(Val: GV->getInitializer());
90 if (!CA)
91 return nullptr;
92
93 for (auto &V : CA->operands()) {
94 if (isa<ConstantAggregateZero>(Val: V))
95 continue;
96 ConstantStruct *CS = cast<ConstantStruct>(Val&: V);
97 if (isa<ConstantPointerNull>(Val: CS->getOperand(i_nocapture: 1)))
98 continue;
99
100 // Can only handle global constructors with no arguments.
101 Function *F = dyn_cast<Function>(Val: CS->getOperand(i_nocapture: 1));
102 if (!F || F->arg_size() != 0)
103 return nullptr;
104 }
105 return GV;
106}
107
108/// Call "ShouldRemove" for every entry in M's global_ctor list and remove the
109/// entries for which it returns true. Return true if anything changed.
110bool llvm::optimizeGlobalCtorsList(
111 Module &M, function_ref<bool(uint32_t, Function *)> ShouldRemove) {
112 GlobalVariable *GlobalCtors = findGlobalCtors(M);
113 if (!GlobalCtors)
114 return false;
115
116 std::vector<std::pair<uint32_t, Function *>> Ctors =
117 parseGlobalCtors(GV: GlobalCtors);
118 if (Ctors.empty())
119 return false;
120
121 bool MadeChange = false;
122 // Loop over global ctors, optimizing them when we can.
123 BitVector CtorsToRemove(Ctors.size());
124 std::vector<size_t> CtorsByPriority(Ctors.size());
125 std::iota(first: CtorsByPriority.begin(), last: CtorsByPriority.end(), value: 0);
126 stable_sort(Range&: CtorsByPriority, C: [&](size_t LHS, size_t RHS) {
127 return Ctors[LHS].first < Ctors[RHS].first;
128 });
129 for (unsigned CtorIndex : CtorsByPriority) {
130 const uint32_t Priority = Ctors[CtorIndex].first;
131 Function *F = Ctors[CtorIndex].second;
132 if (!F)
133 continue;
134
135 LLVM_DEBUG(dbgs() << "Optimizing Global Constructor: " << *F << "\n");
136
137 // If we can evaluate the ctor at compile time, do.
138 if (ShouldRemove(Priority, F)) {
139 Ctors[CtorIndex].second = nullptr;
140 CtorsToRemove.set(CtorIndex);
141 MadeChange = true;
142 continue;
143 }
144 }
145
146 if (!MadeChange)
147 return false;
148
149 removeGlobalCtors(GCL: GlobalCtors, CtorsToRemove);
150 return true;
151}
152