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 
25 using namespace llvm;
26 
27 /// Given a specified llvm.global_ctors list, remove the listed elements.
28 static void removeGlobalCtors(GlobalVariable *GCL, const BitVector &CtorsToRemove) {
29   // Filter out the initializer elements to remove.
30   ConstantArray *OldCA = cast<ConstantArray>(GCL->getInitializer());
31   SmallVector<Constant *, 10> CAList;
32   for (unsigned I = 0, E = OldCA->getNumOperands(); I < E; ++I)
33     if (!CtorsToRemove.test(I))
34       CAList.push_back(OldCA->getOperand(I));
35 
36   // Create the new array initializer.
37   ArrayType *ATy =
38       ArrayType::get(OldCA->getType()->getElementType(), CAList.size());
39   Constant *CA = ConstantArray::get(ATy, 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 =
49       new GlobalVariable(CA->getType(), GCL->isConstant(), GCL->getLinkage(),
50                          CA, "", GCL->getThreadLocalMode());
51   GCL->getParent()->insertGlobalVariable(GCL->getIterator(), NGV);
52   NGV->takeName(GCL);
53 
54   // Nuke the old list, replacing any uses with the new one.
55   if (!GCL->use_empty())
56     GCL->replaceAllUsesWith(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.
63 static std::vector<std::pair<uint32_t, Function *>>
64 parseGlobalCtors(GlobalVariable *GV) {
65   ConstantArray *CA = cast<ConstantArray>(GV->getInitializer());
66   std::vector<std::pair<uint32_t, Function *>> Result;
67   Result.reserve(CA->getNumOperands());
68   for (auto &V : CA->operands()) {
69     ConstantStruct *CS = cast<ConstantStruct>(V);
70     Result.emplace_back(cast<ConstantInt>(CS->getOperand(0))->getZExtValue(),
71                         dyn_cast<Function>(CS->getOperand(1)));
72   }
73   return Result;
74 }
75 
76 /// Find the llvm.global_ctors list.
77 static GlobalVariable *findGlobalCtors(Module &M) {
78   GlobalVariable *GV = M.getGlobalVariable("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>(GV->getInitializer());
90   if (!CA)
91     return nullptr;
92 
93   for (auto &V : CA->operands()) {
94     if (isa<ConstantAggregateZero>(V))
95       continue;
96     ConstantStruct *CS = cast<ConstantStruct>(V);
97     if (isa<ConstantPointerNull>(CS->getOperand(1)))
98       continue;
99 
100     // Can only handle global constructors with no arguments.
101     Function *F = dyn_cast<Function>(CS->getOperand(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.
110 bool 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(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(CtorsByPriority.begin(), CtorsByPriority.end(), 0);
126   stable_sort(CtorsByPriority, [&](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(GlobalCtors, CtorsToRemove);
150   return true;
151 }
152