1//===- GlobalSplit.cpp - global variable splitter -------------------------===//
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 pass uses inrange annotations on GEP indices to split globals where
10// beneficial. Clang currently attaches these annotations to references to
11// virtual table globals under the Itanium ABI for the benefit of the
12// whole-program virtual call optimization and control flow integrity passes.
13//
14//===----------------------------------------------------------------------===//
15
16#include "llvm/Transforms/IPO/GlobalSplit.h"
17#include "llvm/ADT/SmallVector.h"
18#include "llvm/ADT/StringExtras.h"
19#include "llvm/IR/Constant.h"
20#include "llvm/IR/Constants.h"
21#include "llvm/IR/DataLayout.h"
22#include "llvm/IR/Function.h"
23#include "llvm/IR/GlobalValue.h"
24#include "llvm/IR/GlobalVariable.h"
25#include "llvm/IR/Intrinsics.h"
26#include "llvm/IR/LLVMContext.h"
27#include "llvm/IR/Metadata.h"
28#include "llvm/IR/Module.h"
29#include "llvm/IR/Operator.h"
30#include "llvm/IR/Type.h"
31#include "llvm/IR/User.h"
32#include "llvm/Support/Casting.h"
33#include "llvm/Transforms/IPO.h"
34#include <cstdint>
35#include <vector>
36
37using namespace llvm;
38
39static bool splitGlobal(GlobalVariable &GV) {
40 // If the address of the global is taken outside of the module, we cannot
41 // apply this transformation.
42 if (!GV.hasLocalLinkage())
43 return false;
44
45 // We currently only know how to split ConstantStructs.
46 auto *Init = dyn_cast_or_null<ConstantStruct>(Val: GV.getInitializer());
47 if (!Init)
48 return false;
49
50 const DataLayout &DL = GV.getDataLayout();
51 const StructLayout *SL = DL.getStructLayout(Ty: Init->getType());
52 ArrayRef<TypeSize> MemberOffsets = SL->getMemberOffsets();
53 unsigned IndexWidth = DL.getIndexTypeSizeInBits(Ty: GV.getType());
54
55 // Verify that each user of the global is an inrange getelementptr constant,
56 // and collect information on how it relates to the global.
57 struct GEPInfo {
58 GEPOperator *GEP;
59 unsigned MemberIndex;
60 APInt MemberRelativeOffset;
61
62 GEPInfo(GEPOperator *GEP, unsigned MemberIndex, APInt MemberRelativeOffset)
63 : GEP(GEP), MemberIndex(MemberIndex),
64 MemberRelativeOffset(std::move(MemberRelativeOffset)) {}
65 };
66 SmallVector<GEPInfo> Infos;
67 for (User *U : GV.users()) {
68 auto *GEP = dyn_cast<GEPOperator>(Val: U);
69 if (!GEP)
70 return false;
71
72 std::optional<ConstantRange> InRange = GEP->getInRange();
73 if (!InRange)
74 return false;
75
76 APInt Offset(IndexWidth, 0);
77 if (!GEP->accumulateConstantOffset(DL, Offset))
78 return false;
79
80 // Determine source-relative inrange.
81 ConstantRange SrcInRange = InRange->sextOrTrunc(BitWidth: IndexWidth).add(Other: Offset);
82
83 // Check that the GEP offset is in the range (treating upper bound as
84 // inclusive here).
85 if (!SrcInRange.contains(Val: Offset) && SrcInRange.getUpper() != Offset)
86 return false;
87
88 // Find which struct member the range corresponds to.
89 if (SrcInRange.getLower().uge(RHS: SL->getSizeInBytes()))
90 return false;
91
92 unsigned MemberIndex =
93 SL->getElementContainingOffset(FixedOffset: SrcInRange.getLower().getZExtValue());
94 TypeSize MemberStart = MemberOffsets[MemberIndex];
95 TypeSize MemberEnd = MemberIndex == MemberOffsets.size() - 1
96 ? SL->getSizeInBytes()
97 : MemberOffsets[MemberIndex + 1];
98
99 // Verify that the range matches that struct member.
100 if (SrcInRange.getLower() != MemberStart ||
101 SrcInRange.getUpper() != MemberEnd)
102 return false;
103
104 Infos.emplace_back(Args&: GEP, Args&: MemberIndex, Args: Offset - MemberStart);
105 }
106
107 SmallVector<MDNode *, 2> Types;
108 GV.getMetadata(KindID: LLVMContext::MD_type, MDs&: Types);
109
110 IntegerType *Int32Ty = Type::getInt32Ty(C&: GV.getContext());
111
112 std::vector<GlobalVariable *> SplitGlobals(Init->getNumOperands());
113 for (unsigned I = 0; I != Init->getNumOperands(); ++I) {
114 // Build a global representing this split piece.
115 auto *SplitGV =
116 new GlobalVariable(*GV.getParent(), Init->getOperand(i_nocapture: I)->getType(),
117 GV.isConstant(), GlobalValue::PrivateLinkage,
118 Init->getOperand(i_nocapture: I), GV.getName() + "." + utostr(X: I));
119 SplitGlobals[I] = SplitGV;
120
121 unsigned SplitBegin = SL->getElementOffset(Idx: I);
122 unsigned SplitEnd = (I == Init->getNumOperands() - 1)
123 ? SL->getSizeInBytes()
124 : SL->getElementOffset(Idx: I + 1);
125
126 // Rebuild type metadata, adjusting by the split offset.
127 // FIXME: See if we can use DW_OP_piece to preserve debug metadata here.
128 for (MDNode *Type : Types) {
129 uint64_t ByteOffset = cast<ConstantInt>(
130 Val: cast<ConstantAsMetadata>(Val: Type->getOperand(I: 0))->getValue())
131 ->getZExtValue();
132 // Type metadata may be attached one byte after the end of the vtable, for
133 // classes without virtual methods in Itanium ABI. AFAIK, it is never
134 // attached to the first byte of a vtable. Subtract one to get the right
135 // slice.
136 // This is making an assumption that vtable groups are the only kinds of
137 // global variables that !type metadata can be attached to, and that they
138 // are either Itanium ABI vtable groups or contain a single vtable (i.e.
139 // Microsoft ABI vtables).
140 uint64_t AttachedTo = (ByteOffset == 0) ? ByteOffset : ByteOffset - 1;
141 if (AttachedTo < SplitBegin || AttachedTo >= SplitEnd)
142 continue;
143 SplitGV->addMetadata(
144 KindID: LLVMContext::MD_type,
145 MD&: *MDNode::get(Context&: GV.getContext(),
146 MDs: {ConstantAsMetadata::get(
147 C: ConstantInt::get(Ty: Int32Ty, V: ByteOffset - SplitBegin)),
148 Type->getOperand(I: 1)}));
149 }
150
151 if (GV.hasMetadata(KindID: LLVMContext::MD_vcall_visibility))
152 SplitGV->setVCallVisibilityMetadata(GV.getVCallVisibility());
153 }
154
155 for (const GEPInfo &Info : Infos) {
156 assert(Info.MemberIndex < SplitGlobals.size() && "Invalid member");
157 auto *NewGEP = ConstantExpr::getGetElementPtr(
158 Ty: Type::getInt8Ty(C&: GV.getContext()), C: SplitGlobals[Info.MemberIndex],
159 Idx: ConstantInt::get(Context&: GV.getContext(), V: Info.MemberRelativeOffset),
160 NW: Info.GEP->isInBounds());
161 Info.GEP->replaceAllUsesWith(V: NewGEP);
162 }
163
164 // Finally, remove the original global. Any remaining uses refer to invalid
165 // elements of the global, so replace with poison.
166 if (!GV.use_empty())
167 GV.replaceAllUsesWith(V: PoisonValue::get(T: GV.getType()));
168 GV.eraseFromParent();
169 return true;
170}
171
172static bool splitGlobals(Module &M) {
173 // First, see if the module uses either of the llvm.type.test or
174 // llvm.type.checked.load intrinsics, which indicates that splitting globals
175 // may be beneficial.
176 Function *TypeTestFunc =
177 M.getFunction(Name: Intrinsic::getName(id: Intrinsic::type_test));
178 Function *TypeCheckedLoadFunc =
179 M.getFunction(Name: Intrinsic::getName(id: Intrinsic::type_checked_load));
180 Function *TypeCheckedLoadRelativeFunc =
181 M.getFunction(Name: Intrinsic::getName(id: Intrinsic::type_checked_load_relative));
182 if ((!TypeTestFunc || TypeTestFunc->use_empty()) &&
183 (!TypeCheckedLoadFunc || TypeCheckedLoadFunc->use_empty()) &&
184 (!TypeCheckedLoadRelativeFunc ||
185 TypeCheckedLoadRelativeFunc->use_empty()))
186 return false;
187
188 bool Changed = false;
189 for (GlobalVariable &GV : llvm::make_early_inc_range(Range: M.globals()))
190 Changed |= splitGlobal(GV);
191 return Changed;
192}
193
194PreservedAnalyses GlobalSplitPass::run(Module &M, ModuleAnalysisManager &AM) {
195 if (!splitGlobals(M))
196 return PreservedAnalyses::all();
197 return PreservedAnalyses::none();
198}
199