1 | //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// |
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 transforms simple global variables that never have their address |
10 | // taken. If obviously true, it marks read/write globals as constant, deletes |
11 | // variables only stored to, etc. |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "llvm/Transforms/IPO/GlobalOpt.h" |
16 | #include "llvm/ADT/DenseMap.h" |
17 | #include "llvm/ADT/STLExtras.h" |
18 | #include "llvm/ADT/SmallPtrSet.h" |
19 | #include "llvm/ADT/SmallVector.h" |
20 | #include "llvm/ADT/Statistic.h" |
21 | #include "llvm/ADT/Twine.h" |
22 | #include "llvm/ADT/iterator_range.h" |
23 | #include "llvm/Analysis/BlockFrequencyInfo.h" |
24 | #include "llvm/Analysis/ConstantFolding.h" |
25 | #include "llvm/Analysis/MemoryBuiltins.h" |
26 | #include "llvm/Analysis/TargetLibraryInfo.h" |
27 | #include "llvm/Analysis/TargetTransformInfo.h" |
28 | #include "llvm/Analysis/ValueTracking.h" |
29 | #include "llvm/BinaryFormat/Dwarf.h" |
30 | #include "llvm/IR/Attributes.h" |
31 | #include "llvm/IR/BasicBlock.h" |
32 | #include "llvm/IR/CallingConv.h" |
33 | #include "llvm/IR/Constant.h" |
34 | #include "llvm/IR/Constants.h" |
35 | #include "llvm/IR/DataLayout.h" |
36 | #include "llvm/IR/DebugInfoMetadata.h" |
37 | #include "llvm/IR/DerivedTypes.h" |
38 | #include "llvm/IR/Dominators.h" |
39 | #include "llvm/IR/Function.h" |
40 | #include "llvm/IR/GlobalAlias.h" |
41 | #include "llvm/IR/GlobalValue.h" |
42 | #include "llvm/IR/GlobalVariable.h" |
43 | #include "llvm/IR/IRBuilder.h" |
44 | #include "llvm/IR/InstrTypes.h" |
45 | #include "llvm/IR/Instruction.h" |
46 | #include "llvm/IR/Instructions.h" |
47 | #include "llvm/IR/IntrinsicInst.h" |
48 | #include "llvm/IR/Module.h" |
49 | #include "llvm/IR/Operator.h" |
50 | #include "llvm/IR/Type.h" |
51 | #include "llvm/IR/Use.h" |
52 | #include "llvm/IR/User.h" |
53 | #include "llvm/IR/Value.h" |
54 | #include "llvm/IR/ValueHandle.h" |
55 | #include "llvm/Support/AtomicOrdering.h" |
56 | #include "llvm/Support/Casting.h" |
57 | #include "llvm/Support/CommandLine.h" |
58 | #include "llvm/Support/Debug.h" |
59 | #include "llvm/Support/ErrorHandling.h" |
60 | #include "llvm/Support/raw_ostream.h" |
61 | #include "llvm/Transforms/IPO.h" |
62 | #include "llvm/Transforms/Utils/CtorUtils.h" |
63 | #include "llvm/Transforms/Utils/Evaluator.h" |
64 | #include "llvm/Transforms/Utils/GlobalStatus.h" |
65 | #include "llvm/Transforms/Utils/Local.h" |
66 | #include <cassert> |
67 | #include <cstdint> |
68 | #include <optional> |
69 | #include <utility> |
70 | #include <vector> |
71 | |
72 | using namespace llvm; |
73 | |
74 | #define DEBUG_TYPE "globalopt" |
75 | |
76 | STATISTIC(NumMarked , "Number of globals marked constant" ); |
77 | STATISTIC(NumUnnamed , "Number of globals marked unnamed_addr" ); |
78 | STATISTIC(NumSRA , "Number of aggregate globals broken into scalars" ); |
79 | STATISTIC(NumSubstitute,"Number of globals with initializers stored into them" ); |
80 | STATISTIC(NumDeleted , "Number of globals deleted" ); |
81 | STATISTIC(NumGlobUses , "Number of global uses devirtualized" ); |
82 | STATISTIC(NumLocalized , "Number of globals localized" ); |
83 | STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans" ); |
84 | STATISTIC(NumFastCallFns , "Number of functions converted to fastcc" ); |
85 | STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated" ); |
86 | STATISTIC(NumNestRemoved , "Number of nest attributes removed" ); |
87 | STATISTIC(NumAliasesResolved, "Number of global aliases resolved" ); |
88 | STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated" ); |
89 | STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed" ); |
90 | STATISTIC(NumInternalFunc, "Number of internal functions" ); |
91 | STATISTIC(NumColdCC, "Number of functions marked coldcc" ); |
92 | STATISTIC(NumIFuncsResolved, "Number of statically resolved IFuncs" ); |
93 | STATISTIC(NumIFuncsDeleted, "Number of IFuncs removed" ); |
94 | |
95 | static cl::opt<bool> |
96 | EnableColdCCStressTest("enable-coldcc-stress-test" , |
97 | cl::desc("Enable stress test of coldcc by adding " |
98 | "calling conv to all internal functions." ), |
99 | cl::init(Val: false), cl::Hidden); |
100 | |
101 | static cl::opt<int> ColdCCRelFreq( |
102 | "coldcc-rel-freq" , cl::Hidden, cl::init(Val: 2), |
103 | cl::desc( |
104 | "Maximum block frequency, expressed as a percentage of caller's " |
105 | "entry frequency, for a call site to be considered cold for enabling" |
106 | "coldcc" )); |
107 | |
108 | /// Is this global variable possibly used by a leak checker as a root? If so, |
109 | /// we might not really want to eliminate the stores to it. |
110 | static bool isLeakCheckerRoot(GlobalVariable *GV) { |
111 | // A global variable is a root if it is a pointer, or could plausibly contain |
112 | // a pointer. There are two challenges; one is that we could have a struct |
113 | // the has an inner member which is a pointer. We recurse through the type to |
114 | // detect these (up to a point). The other is that we may actually be a union |
115 | // of a pointer and another type, and so our LLVM type is an integer which |
116 | // gets converted into a pointer, or our type is an [i8 x #] with a pointer |
117 | // potentially contained here. |
118 | |
119 | if (GV->hasPrivateLinkage()) |
120 | return false; |
121 | |
122 | SmallVector<Type *, 4> Types; |
123 | Types.push_back(Elt: GV->getValueType()); |
124 | |
125 | unsigned Limit = 20; |
126 | do { |
127 | Type *Ty = Types.pop_back_val(); |
128 | switch (Ty->getTypeID()) { |
129 | default: break; |
130 | case Type::PointerTyID: |
131 | return true; |
132 | case Type::FixedVectorTyID: |
133 | case Type::ScalableVectorTyID: |
134 | if (cast<VectorType>(Val: Ty)->getElementType()->isPointerTy()) |
135 | return true; |
136 | break; |
137 | case Type::ArrayTyID: |
138 | Types.push_back(Elt: cast<ArrayType>(Val: Ty)->getElementType()); |
139 | break; |
140 | case Type::StructTyID: { |
141 | StructType *STy = cast<StructType>(Val: Ty); |
142 | if (STy->isOpaque()) return true; |
143 | for (Type *InnerTy : STy->elements()) { |
144 | if (isa<PointerType>(Val: InnerTy)) return true; |
145 | if (isa<StructType>(Val: InnerTy) || isa<ArrayType>(Val: InnerTy) || |
146 | isa<VectorType>(Val: InnerTy)) |
147 | Types.push_back(Elt: InnerTy); |
148 | } |
149 | break; |
150 | } |
151 | } |
152 | if (--Limit == 0) return true; |
153 | } while (!Types.empty()); |
154 | return false; |
155 | } |
156 | |
157 | /// Given a value that is stored to a global but never read, determine whether |
158 | /// it's safe to remove the store and the chain of computation that feeds the |
159 | /// store. |
160 | static bool IsSafeComputationToRemove( |
161 | Value *V, function_ref<TargetLibraryInfo &(Function &)> GetTLI) { |
162 | do { |
163 | if (isa<Constant>(Val: V)) |
164 | return true; |
165 | if (!V->hasOneUse()) |
166 | return false; |
167 | if (isa<LoadInst>(Val: V) || isa<InvokeInst>(Val: V) || isa<Argument>(Val: V) || |
168 | isa<GlobalValue>(Val: V)) |
169 | return false; |
170 | if (isAllocationFn(V, GetTLI)) |
171 | return true; |
172 | |
173 | Instruction *I = cast<Instruction>(Val: V); |
174 | if (I->mayHaveSideEffects()) |
175 | return false; |
176 | if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: I)) { |
177 | if (!GEP->hasAllConstantIndices()) |
178 | return false; |
179 | } else if (I->getNumOperands() != 1) { |
180 | return false; |
181 | } |
182 | |
183 | V = I->getOperand(i: 0); |
184 | } while (true); |
185 | } |
186 | |
187 | /// This GV is a pointer root. Loop over all users of the global and clean up |
188 | /// any that obviously don't assign the global a value that isn't dynamically |
189 | /// allocated. |
190 | static bool |
191 | CleanupPointerRootUsers(GlobalVariable *GV, |
192 | function_ref<TargetLibraryInfo &(Function &)> GetTLI) { |
193 | // A brief explanation of leak checkers. The goal is to find bugs where |
194 | // pointers are forgotten, causing an accumulating growth in memory |
195 | // usage over time. The common strategy for leak checkers is to explicitly |
196 | // allow the memory pointed to by globals at exit. This is popular because it |
197 | // also solves another problem where the main thread of a C++ program may shut |
198 | // down before other threads that are still expecting to use those globals. To |
199 | // handle that case, we expect the program may create a singleton and never |
200 | // destroy it. |
201 | |
202 | bool Changed = false; |
203 | |
204 | // If Dead[n].first is the only use of a malloc result, we can delete its |
205 | // chain of computation and the store to the global in Dead[n].second. |
206 | SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead; |
207 | |
208 | SmallVector<User *> Worklist(GV->users()); |
209 | // Constants can't be pointers to dynamically allocated memory. |
210 | while (!Worklist.empty()) { |
211 | User *U = Worklist.pop_back_val(); |
212 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
213 | Value *V = SI->getValueOperand(); |
214 | if (isa<Constant>(Val: V)) { |
215 | Changed = true; |
216 | SI->eraseFromParent(); |
217 | } else if (Instruction *I = dyn_cast<Instruction>(Val: V)) { |
218 | if (I->hasOneUse()) |
219 | Dead.push_back(Elt: std::make_pair(x&: I, y&: SI)); |
220 | } |
221 | } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(Val: U)) { |
222 | if (isa<Constant>(Val: MSI->getValue())) { |
223 | Changed = true; |
224 | MSI->eraseFromParent(); |
225 | } else if (Instruction *I = dyn_cast<Instruction>(Val: MSI->getValue())) { |
226 | if (I->hasOneUse()) |
227 | Dead.push_back(Elt: std::make_pair(x&: I, y&: MSI)); |
228 | } |
229 | } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(Val: U)) { |
230 | GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(Val: MTI->getSource()); |
231 | if (MemSrc && MemSrc->isConstant()) { |
232 | Changed = true; |
233 | MTI->eraseFromParent(); |
234 | } else if (Instruction *I = dyn_cast<Instruction>(Val: MTI->getSource())) { |
235 | if (I->hasOneUse()) |
236 | Dead.push_back(Elt: std::make_pair(x&: I, y&: MTI)); |
237 | } |
238 | } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Val: U)) { |
239 | if (isa<GEPOperator>(Val: CE)) |
240 | append_range(C&: Worklist, R: CE->users()); |
241 | } |
242 | } |
243 | |
244 | for (int i = 0, e = Dead.size(); i != e; ++i) { |
245 | if (IsSafeComputationToRemove(V: Dead[i].first, GetTLI)) { |
246 | Dead[i].second->eraseFromParent(); |
247 | Instruction *I = Dead[i].first; |
248 | do { |
249 | if (isAllocationFn(V: I, GetTLI)) |
250 | break; |
251 | Instruction *J = dyn_cast<Instruction>(Val: I->getOperand(i: 0)); |
252 | if (!J) |
253 | break; |
254 | I->eraseFromParent(); |
255 | I = J; |
256 | } while (true); |
257 | I->eraseFromParent(); |
258 | Changed = true; |
259 | } |
260 | } |
261 | |
262 | GV->removeDeadConstantUsers(); |
263 | return Changed; |
264 | } |
265 | |
266 | /// We just marked GV constant. Loop over all users of the global, cleaning up |
267 | /// the obvious ones. This is largely just a quick scan over the use list to |
268 | /// clean up the easy and obvious cruft. This returns true if it made a change. |
269 | static bool CleanupConstantGlobalUsers(GlobalVariable *GV, |
270 | const DataLayout &DL) { |
271 | Constant *Init = GV->getInitializer(); |
272 | SmallVector<User *, 8> WorkList(GV->users()); |
273 | SmallPtrSet<User *, 8> Visited; |
274 | bool Changed = false; |
275 | |
276 | SmallVector<WeakTrackingVH> MaybeDeadInsts; |
277 | auto EraseFromParent = [&](Instruction *I) { |
278 | for (Value *Op : I->operands()) |
279 | if (auto *OpI = dyn_cast<Instruction>(Val: Op)) |
280 | MaybeDeadInsts.push_back(Elt: OpI); |
281 | I->eraseFromParent(); |
282 | Changed = true; |
283 | }; |
284 | while (!WorkList.empty()) { |
285 | User *U = WorkList.pop_back_val(); |
286 | if (!Visited.insert(Ptr: U).second) |
287 | continue; |
288 | |
289 | if (auto *BO = dyn_cast<BitCastOperator>(Val: U)) |
290 | append_range(C&: WorkList, R: BO->users()); |
291 | if (auto *ASC = dyn_cast<AddrSpaceCastOperator>(Val: U)) |
292 | append_range(C&: WorkList, R: ASC->users()); |
293 | else if (auto *GEP = dyn_cast<GEPOperator>(Val: U)) |
294 | append_range(C&: WorkList, R: GEP->users()); |
295 | else if (auto *LI = dyn_cast<LoadInst>(Val: U)) { |
296 | // A load from a uniform value is always the same, regardless of any |
297 | // applied offset. |
298 | Type *Ty = LI->getType(); |
299 | if (Constant *Res = ConstantFoldLoadFromUniformValue(C: Init, Ty, DL)) { |
300 | LI->replaceAllUsesWith(V: Res); |
301 | EraseFromParent(LI); |
302 | continue; |
303 | } |
304 | |
305 | Value *PtrOp = LI->getPointerOperand(); |
306 | APInt Offset(DL.getIndexTypeSizeInBits(Ty: PtrOp->getType()), 0); |
307 | PtrOp = PtrOp->stripAndAccumulateConstantOffsets( |
308 | DL, Offset, /* AllowNonInbounds */ true); |
309 | if (PtrOp == GV) { |
310 | if (auto *Value = ConstantFoldLoadFromConst(C: Init, Ty, Offset, DL)) { |
311 | LI->replaceAllUsesWith(V: Value); |
312 | EraseFromParent(LI); |
313 | } |
314 | } |
315 | } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
316 | // Store must be unreachable or storing Init into the global. |
317 | EraseFromParent(SI); |
318 | } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(Val: U)) { // memset/cpy/mv |
319 | if (getUnderlyingObject(V: MI->getRawDest()) == GV) |
320 | EraseFromParent(MI); |
321 | } |
322 | } |
323 | |
324 | Changed |= |
325 | RecursivelyDeleteTriviallyDeadInstructionsPermissive(DeadInsts&: MaybeDeadInsts); |
326 | GV->removeDeadConstantUsers(); |
327 | return Changed; |
328 | } |
329 | |
330 | /// Part of the global at a specific offset, which is only accessed through |
331 | /// loads and stores with the given type. |
332 | struct GlobalPart { |
333 | Type *Ty; |
334 | Constant *Initializer = nullptr; |
335 | bool IsLoaded = false; |
336 | bool IsStored = false; |
337 | }; |
338 | |
339 | /// Look at all uses of the global and determine which (offset, type) pairs it |
340 | /// can be split into. |
341 | static bool collectSRATypes(DenseMap<uint64_t, GlobalPart> &Parts, |
342 | GlobalVariable *GV, const DataLayout &DL) { |
343 | SmallVector<Use *, 16> Worklist; |
344 | SmallPtrSet<Use *, 16> Visited; |
345 | auto AppendUses = [&](Value *V) { |
346 | for (Use &U : V->uses()) |
347 | if (Visited.insert(Ptr: &U).second) |
348 | Worklist.push_back(Elt: &U); |
349 | }; |
350 | AppendUses(GV); |
351 | while (!Worklist.empty()) { |
352 | Use *U = Worklist.pop_back_val(); |
353 | User *V = U->getUser(); |
354 | |
355 | auto *GEP = dyn_cast<GEPOperator>(Val: V); |
356 | if (isa<BitCastOperator>(Val: V) || isa<AddrSpaceCastOperator>(Val: V) || |
357 | (GEP && GEP->hasAllConstantIndices())) { |
358 | AppendUses(V); |
359 | continue; |
360 | } |
361 | |
362 | if (Value *Ptr = getLoadStorePointerOperand(V)) { |
363 | // This is storing the global address into somewhere, not storing into |
364 | // the global. |
365 | if (isa<StoreInst>(Val: V) && U->getOperandNo() == 0) |
366 | return false; |
367 | |
368 | APInt Offset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0); |
369 | Ptr = Ptr->stripAndAccumulateConstantOffsets(DL, Offset, |
370 | /* AllowNonInbounds */ true); |
371 | if (Ptr != GV || Offset.getActiveBits() >= 64) |
372 | return false; |
373 | |
374 | // TODO: We currently require that all accesses at a given offset must |
375 | // use the same type. This could be relaxed. |
376 | Type *Ty = getLoadStoreType(I: V); |
377 | const auto &[It, Inserted] = |
378 | Parts.try_emplace(Key: Offset.getZExtValue(), Args: GlobalPart{.Ty: Ty}); |
379 | if (Ty != It->second.Ty) |
380 | return false; |
381 | |
382 | if (Inserted) { |
383 | It->second.Initializer = |
384 | ConstantFoldLoadFromConst(C: GV->getInitializer(), Ty, Offset, DL); |
385 | if (!It->second.Initializer) { |
386 | LLVM_DEBUG(dbgs() << "Global SRA: Failed to evaluate initializer of " |
387 | << *GV << " with type " << *Ty << " at offset " |
388 | << Offset.getZExtValue()); |
389 | return false; |
390 | } |
391 | } |
392 | |
393 | // Scalable types not currently supported. |
394 | if (Ty->isScalableTy()) |
395 | return false; |
396 | |
397 | auto IsStored = [](Value *V, Constant *Initializer) { |
398 | auto *SI = dyn_cast<StoreInst>(Val: V); |
399 | if (!SI) |
400 | return false; |
401 | |
402 | Constant *StoredConst = dyn_cast<Constant>(Val: SI->getOperand(i_nocapture: 0)); |
403 | if (!StoredConst) |
404 | return true; |
405 | |
406 | // Don't consider stores that only write the initializer value. |
407 | return Initializer != StoredConst; |
408 | }; |
409 | |
410 | It->second.IsLoaded |= isa<LoadInst>(Val: V); |
411 | It->second.IsStored |= IsStored(V, It->second.Initializer); |
412 | continue; |
413 | } |
414 | |
415 | // Ignore dead constant users. |
416 | if (auto *C = dyn_cast<Constant>(Val: V)) { |
417 | if (!isSafeToDestroyConstant(C)) |
418 | return false; |
419 | continue; |
420 | } |
421 | |
422 | // Unknown user. |
423 | return false; |
424 | } |
425 | |
426 | return true; |
427 | } |
428 | |
429 | /// Copy over the debug info for a variable to its SRA replacements. |
430 | static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV, |
431 | uint64_t FragmentOffsetInBits, |
432 | uint64_t FragmentSizeInBits, |
433 | uint64_t VarSize) { |
434 | SmallVector<DIGlobalVariableExpression *, 1> GVs; |
435 | GV->getDebugInfo(GVs); |
436 | for (auto *GVE : GVs) { |
437 | DIVariable *Var = GVE->getVariable(); |
438 | DIExpression *Expr = GVE->getExpression(); |
439 | int64_t CurVarOffsetInBytes = 0; |
440 | uint64_t CurVarOffsetInBits = 0; |
441 | uint64_t FragmentEndInBits = FragmentOffsetInBits + FragmentSizeInBits; |
442 | |
443 | // Calculate the offset (Bytes), Continue if unknown. |
444 | if (!Expr->extractIfOffset(Offset&: CurVarOffsetInBytes)) |
445 | continue; |
446 | |
447 | // Ignore negative offset. |
448 | if (CurVarOffsetInBytes < 0) |
449 | continue; |
450 | |
451 | // Convert offset to bits. |
452 | CurVarOffsetInBits = CHAR_BIT * (uint64_t)CurVarOffsetInBytes; |
453 | |
454 | // Current var starts after the fragment, ignore. |
455 | if (CurVarOffsetInBits >= FragmentEndInBits) |
456 | continue; |
457 | |
458 | uint64_t CurVarSize = Var->getType()->getSizeInBits(); |
459 | uint64_t CurVarEndInBits = CurVarOffsetInBits + CurVarSize; |
460 | // Current variable ends before start of fragment, ignore. |
461 | if (CurVarSize != 0 && /* CurVarSize is known */ |
462 | CurVarEndInBits <= FragmentOffsetInBits) |
463 | continue; |
464 | |
465 | // Current variable fits in (not greater than) the fragment, |
466 | // does not need fragment expression. |
467 | if (CurVarSize != 0 && /* CurVarSize is known */ |
468 | CurVarOffsetInBits >= FragmentOffsetInBits && |
469 | CurVarEndInBits <= FragmentEndInBits) { |
470 | uint64_t CurVarOffsetInFragment = |
471 | (CurVarOffsetInBits - FragmentOffsetInBits) / 8; |
472 | if (CurVarOffsetInFragment != 0) |
473 | Expr = DIExpression::get(Context&: Expr->getContext(), Elements: {dwarf::DW_OP_plus_uconst, |
474 | CurVarOffsetInFragment}); |
475 | else |
476 | Expr = DIExpression::get(Context&: Expr->getContext(), Elements: {}); |
477 | auto *NGVE = |
478 | DIGlobalVariableExpression::get(Context&: GVE->getContext(), Variable: Var, Expression: Expr); |
479 | NGV->addDebugInfo(GV: NGVE); |
480 | continue; |
481 | } |
482 | // Current variable does not fit in single fragment, |
483 | // emit a fragment expression. |
484 | if (FragmentSizeInBits < VarSize) { |
485 | if (CurVarOffsetInBits > FragmentOffsetInBits) |
486 | continue; |
487 | uint64_t CurVarFragmentOffsetInBits = |
488 | FragmentOffsetInBits - CurVarOffsetInBits; |
489 | uint64_t CurVarFragmentSizeInBits = FragmentSizeInBits; |
490 | if (CurVarSize != 0 && CurVarEndInBits < FragmentEndInBits) |
491 | CurVarFragmentSizeInBits -= (FragmentEndInBits - CurVarEndInBits); |
492 | if (CurVarOffsetInBits) |
493 | Expr = DIExpression::get(Context&: Expr->getContext(), Elements: {}); |
494 | if (auto E = DIExpression::createFragmentExpression( |
495 | Expr, OffsetInBits: CurVarFragmentOffsetInBits, SizeInBits: CurVarFragmentSizeInBits)) |
496 | Expr = *E; |
497 | else |
498 | continue; |
499 | } |
500 | auto *NGVE = DIGlobalVariableExpression::get(Context&: GVE->getContext(), Variable: Var, Expression: Expr); |
501 | NGV->addDebugInfo(GV: NGVE); |
502 | } |
503 | } |
504 | |
505 | /// Perform scalar replacement of aggregates on the specified global variable. |
506 | /// This opens the door for other optimizations by exposing the behavior of the |
507 | /// program in a more fine-grained way. We have determined that this |
508 | /// transformation is safe already. We return the first global variable we |
509 | /// insert so that the caller can reprocess it. |
510 | static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) { |
511 | assert(GV->hasLocalLinkage()); |
512 | |
513 | // Collect types to split into. |
514 | DenseMap<uint64_t, GlobalPart> Parts; |
515 | if (!collectSRATypes(Parts, GV, DL) || Parts.empty()) |
516 | return nullptr; |
517 | |
518 | // Make sure we don't SRA back to the same type. |
519 | if (Parts.size() == 1 && Parts.begin()->second.Ty == GV->getValueType()) |
520 | return nullptr; |
521 | |
522 | // Don't perform SRA if we would have to split into many globals. Ignore |
523 | // parts that are either only loaded or only stored, because we expect them |
524 | // to be optimized away. |
525 | unsigned NumParts = count_if(Range&: Parts, P: [](const auto &Pair) { |
526 | return Pair.second.IsLoaded && Pair.second.IsStored; |
527 | }); |
528 | if (NumParts > 16) |
529 | return nullptr; |
530 | |
531 | // Sort by offset. |
532 | SmallVector<std::tuple<uint64_t, Type *, Constant *>, 16> TypesVector; |
533 | for (const auto &Pair : Parts) { |
534 | TypesVector.push_back( |
535 | Elt: {Pair.first, Pair.second.Ty, Pair.second.Initializer}); |
536 | } |
537 | sort(C&: TypesVector, Comp: llvm::less_first()); |
538 | |
539 | // Check that the types are non-overlapping. |
540 | uint64_t Offset = 0; |
541 | for (const auto &[OffsetForTy, Ty, _] : TypesVector) { |
542 | // Overlaps with previous type. |
543 | if (OffsetForTy < Offset) |
544 | return nullptr; |
545 | |
546 | Offset = OffsetForTy + DL.getTypeAllocSize(Ty); |
547 | } |
548 | |
549 | // Some accesses go beyond the end of the global, don't bother. |
550 | if (Offset > DL.getTypeAllocSize(Ty: GV->getValueType())) |
551 | return nullptr; |
552 | |
553 | LLVM_DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n" ); |
554 | |
555 | // Get the alignment of the global, either explicit or target-specific. |
556 | Align StartAlignment = |
557 | DL.getValueOrABITypeAlignment(Alignment: GV->getAlign(), Ty: GV->getValueType()); |
558 | uint64_t VarSize = DL.getTypeSizeInBits(Ty: GV->getValueType()); |
559 | |
560 | // Create replacement globals. |
561 | DenseMap<uint64_t, GlobalVariable *> NewGlobals; |
562 | unsigned NameSuffix = 0; |
563 | for (auto &[OffsetForTy, Ty, Initializer] : TypesVector) { |
564 | GlobalVariable *NGV = new GlobalVariable( |
565 | *GV->getParent(), Ty, false, GlobalVariable::InternalLinkage, |
566 | Initializer, GV->getName() + "." + Twine(NameSuffix++), GV, |
567 | GV->getThreadLocalMode(), GV->getAddressSpace()); |
568 | NGV->copyAttributesFrom(Src: GV); |
569 | NewGlobals.insert(KV: {OffsetForTy, NGV}); |
570 | |
571 | // Calculate the known alignment of the field. If the original aggregate |
572 | // had 256 byte alignment for example, something might depend on that: |
573 | // propagate info to each field. |
574 | Align NewAlign = commonAlignment(A: StartAlignment, Offset: OffsetForTy); |
575 | if (NewAlign > DL.getABITypeAlign(Ty)) |
576 | NGV->setAlignment(NewAlign); |
577 | |
578 | // Copy over the debug info for the variable. |
579 | transferSRADebugInfo(GV, NGV, FragmentOffsetInBits: OffsetForTy * 8, |
580 | FragmentSizeInBits: DL.getTypeAllocSizeInBits(Ty), VarSize); |
581 | } |
582 | |
583 | // Replace uses of the original global with uses of the new global. |
584 | SmallVector<Value *, 16> Worklist; |
585 | SmallPtrSet<Value *, 16> Visited; |
586 | SmallVector<WeakTrackingVH, 16> DeadInsts; |
587 | auto AppendUsers = [&](Value *V) { |
588 | for (User *U : V->users()) |
589 | if (Visited.insert(Ptr: U).second) |
590 | Worklist.push_back(Elt: U); |
591 | }; |
592 | AppendUsers(GV); |
593 | while (!Worklist.empty()) { |
594 | Value *V = Worklist.pop_back_val(); |
595 | if (isa<BitCastOperator>(Val: V) || isa<AddrSpaceCastOperator>(Val: V) || |
596 | isa<GEPOperator>(Val: V)) { |
597 | AppendUsers(V); |
598 | if (isa<Instruction>(Val: V)) |
599 | DeadInsts.push_back(Elt: V); |
600 | continue; |
601 | } |
602 | |
603 | if (Value *Ptr = getLoadStorePointerOperand(V)) { |
604 | APInt Offset(DL.getIndexTypeSizeInBits(Ty: Ptr->getType()), 0); |
605 | Ptr = Ptr->stripAndAccumulateConstantOffsets(DL, Offset, |
606 | /* AllowNonInbounds */ true); |
607 | assert(Ptr == GV && "Load/store must be from/to global" ); |
608 | GlobalVariable *NGV = NewGlobals[Offset.getZExtValue()]; |
609 | assert(NGV && "Must have replacement global for this offset" ); |
610 | |
611 | // Update the pointer operand and recalculate alignment. |
612 | Align PrefAlign = DL.getPrefTypeAlign(Ty: getLoadStoreType(I: V)); |
613 | Align NewAlign = |
614 | getOrEnforceKnownAlignment(V: NGV, PrefAlign, DL, CxtI: cast<Instruction>(Val: V)); |
615 | |
616 | if (auto *LI = dyn_cast<LoadInst>(Val: V)) { |
617 | LI->setOperand(i_nocapture: 0, Val_nocapture: NGV); |
618 | LI->setAlignment(NewAlign); |
619 | } else { |
620 | auto *SI = cast<StoreInst>(Val: V); |
621 | SI->setOperand(i_nocapture: 1, Val_nocapture: NGV); |
622 | SI->setAlignment(NewAlign); |
623 | } |
624 | continue; |
625 | } |
626 | |
627 | assert(isa<Constant>(V) && isSafeToDestroyConstant(cast<Constant>(V)) && |
628 | "Other users can only be dead constants" ); |
629 | } |
630 | |
631 | // Delete old instructions and global. |
632 | RecursivelyDeleteTriviallyDeadInstructions(DeadInsts); |
633 | GV->removeDeadConstantUsers(); |
634 | GV->eraseFromParent(); |
635 | ++NumSRA; |
636 | |
637 | assert(NewGlobals.size() > 0); |
638 | return NewGlobals.begin()->second; |
639 | } |
640 | |
641 | /// Return true if all users of the specified value will trap if the value is |
642 | /// dynamically null. PHIs keeps track of any phi nodes we've seen to avoid |
643 | /// reprocessing them. |
644 | static bool AllUsesOfValueWillTrapIfNull(const Value *V, |
645 | SmallPtrSetImpl<const PHINode*> &PHIs) { |
646 | for (const User *U : V->users()) { |
647 | if (const Instruction *I = dyn_cast<Instruction>(Val: U)) { |
648 | // If null pointer is considered valid, then all uses are non-trapping. |
649 | // Non address-space 0 globals have already been pruned by the caller. |
650 | if (NullPointerIsDefined(F: I->getFunction())) |
651 | return false; |
652 | } |
653 | if (isa<LoadInst>(Val: U)) { |
654 | // Will trap. |
655 | } else if (const StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
656 | if (SI->getOperand(i_nocapture: 0) == V) { |
657 | return false; // Storing the value. |
658 | } |
659 | } else if (const CallInst *CI = dyn_cast<CallInst>(Val: U)) { |
660 | if (CI->getCalledOperand() != V) { |
661 | return false; // Not calling the ptr |
662 | } |
663 | } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Val: U)) { |
664 | if (II->getCalledOperand() != V) { |
665 | return false; // Not calling the ptr |
666 | } |
667 | } else if (const AddrSpaceCastInst *CI = dyn_cast<AddrSpaceCastInst>(Val: U)) { |
668 | if (!AllUsesOfValueWillTrapIfNull(V: CI, PHIs)) |
669 | return false; |
670 | } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) { |
671 | if (!AllUsesOfValueWillTrapIfNull(V: GEPI, PHIs)) return false; |
672 | } else if (const PHINode *PN = dyn_cast<PHINode>(Val: U)) { |
673 | // If we've already seen this phi node, ignore it, it has already been |
674 | // checked. |
675 | if (PHIs.insert(Ptr: PN).second && !AllUsesOfValueWillTrapIfNull(V: PN, PHIs)) |
676 | return false; |
677 | } else if (isa<ICmpInst>(Val: U) && |
678 | !ICmpInst::isSigned(predicate: cast<ICmpInst>(Val: U)->getPredicate()) && |
679 | isa<LoadInst>(Val: U->getOperand(i: 0)) && |
680 | isa<ConstantPointerNull>(Val: U->getOperand(i: 1))) { |
681 | assert(isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) |
682 | ->getPointerOperand() |
683 | ->stripPointerCasts()) && |
684 | "Should be GlobalVariable" ); |
685 | // This and only this kind of non-signed ICmpInst is to be replaced with |
686 | // the comparing of the value of the created global init bool later in |
687 | // optimizeGlobalAddressOfAllocation for the global variable. |
688 | } else { |
689 | return false; |
690 | } |
691 | } |
692 | return true; |
693 | } |
694 | |
695 | /// Return true if all uses of any loads from GV will trap if the loaded value |
696 | /// is null. Note that this also permits comparisons of the loaded value |
697 | /// against null, as a special case. |
698 | static bool allUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) { |
699 | SmallVector<const Value *, 4> Worklist; |
700 | Worklist.push_back(Elt: GV); |
701 | while (!Worklist.empty()) { |
702 | const Value *P = Worklist.pop_back_val(); |
703 | for (const auto *U : P->users()) { |
704 | if (auto *LI = dyn_cast<LoadInst>(Val: U)) { |
705 | SmallPtrSet<const PHINode *, 8> PHIs; |
706 | if (!AllUsesOfValueWillTrapIfNull(V: LI, PHIs)) |
707 | return false; |
708 | } else if (auto *SI = dyn_cast<StoreInst>(Val: U)) { |
709 | // Ignore stores to the global. |
710 | if (SI->getPointerOperand() != P) |
711 | return false; |
712 | } else if (auto *CE = dyn_cast<ConstantExpr>(Val: U)) { |
713 | if (CE->stripPointerCasts() != GV) |
714 | return false; |
715 | // Check further the ConstantExpr. |
716 | Worklist.push_back(Elt: CE); |
717 | } else { |
718 | // We don't know or understand this user, bail out. |
719 | return false; |
720 | } |
721 | } |
722 | } |
723 | |
724 | return true; |
725 | } |
726 | |
727 | /// Get all the loads/store uses for global variable \p GV. |
728 | static void allUsesOfLoadAndStores(GlobalVariable *GV, |
729 | SmallVector<Value *, 4> &Uses) { |
730 | SmallVector<Value *, 4> Worklist; |
731 | Worklist.push_back(Elt: GV); |
732 | while (!Worklist.empty()) { |
733 | auto *P = Worklist.pop_back_val(); |
734 | for (auto *U : P->users()) { |
735 | if (auto *CE = dyn_cast<ConstantExpr>(Val: U)) { |
736 | Worklist.push_back(Elt: CE); |
737 | continue; |
738 | } |
739 | |
740 | assert((isa<LoadInst>(U) || isa<StoreInst>(U)) && |
741 | "Expect only load or store instructions" ); |
742 | Uses.push_back(Elt: U); |
743 | } |
744 | } |
745 | } |
746 | |
747 | static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { |
748 | bool Changed = false; |
749 | for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { |
750 | Instruction *I = cast<Instruction>(Val: *UI++); |
751 | // Uses are non-trapping if null pointer is considered valid. |
752 | // Non address-space 0 globals are already pruned by the caller. |
753 | if (NullPointerIsDefined(F: I->getFunction())) |
754 | return false; |
755 | if (LoadInst *LI = dyn_cast<LoadInst>(Val: I)) { |
756 | LI->setOperand(i_nocapture: 0, Val_nocapture: NewV); |
757 | Changed = true; |
758 | } else if (StoreInst *SI = dyn_cast<StoreInst>(Val: I)) { |
759 | if (SI->getOperand(i_nocapture: 1) == V) { |
760 | SI->setOperand(i_nocapture: 1, Val_nocapture: NewV); |
761 | Changed = true; |
762 | } |
763 | } else if (isa<CallInst>(Val: I) || isa<InvokeInst>(Val: I)) { |
764 | CallBase *CB = cast<CallBase>(Val: I); |
765 | if (CB->getCalledOperand() == V) { |
766 | // Calling through the pointer! Turn into a direct call, but be careful |
767 | // that the pointer is not also being passed as an argument. |
768 | CB->setCalledOperand(NewV); |
769 | Changed = true; |
770 | bool PassedAsArg = false; |
771 | for (unsigned i = 0, e = CB->arg_size(); i != e; ++i) |
772 | if (CB->getArgOperand(i) == V) { |
773 | PassedAsArg = true; |
774 | CB->setArgOperand(i, v: NewV); |
775 | } |
776 | |
777 | if (PassedAsArg) { |
778 | // Being passed as an argument also. Be careful to not invalidate UI! |
779 | UI = V->user_begin(); |
780 | } |
781 | } |
782 | } else if (AddrSpaceCastInst *CI = dyn_cast<AddrSpaceCastInst>(Val: I)) { |
783 | Changed |= OptimizeAwayTrappingUsesOfValue( |
784 | V: CI, NewV: ConstantExpr::getAddrSpaceCast(C: NewV, Ty: CI->getType())); |
785 | if (CI->use_empty()) { |
786 | Changed = true; |
787 | CI->eraseFromParent(); |
788 | } |
789 | } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Val: I)) { |
790 | // Should handle GEP here. |
791 | SmallVector<Constant*, 8> Idxs; |
792 | Idxs.reserve(N: GEPI->getNumOperands()-1); |
793 | for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end(); |
794 | i != e; ++i) |
795 | if (Constant *C = dyn_cast<Constant>(Val&: *i)) |
796 | Idxs.push_back(Elt: C); |
797 | else |
798 | break; |
799 | if (Idxs.size() == GEPI->getNumOperands()-1) |
800 | Changed |= OptimizeAwayTrappingUsesOfValue( |
801 | V: GEPI, NewV: ConstantExpr::getGetElementPtr(Ty: GEPI->getSourceElementType(), |
802 | C: NewV, IdxList: Idxs)); |
803 | if (GEPI->use_empty()) { |
804 | Changed = true; |
805 | GEPI->eraseFromParent(); |
806 | } |
807 | } |
808 | } |
809 | |
810 | return Changed; |
811 | } |
812 | |
813 | /// The specified global has only one non-null value stored into it. If there |
814 | /// are uses of the loaded value that would trap if the loaded value is |
815 | /// dynamically null, then we know that they cannot be reachable with a null |
816 | /// optimize away the load. |
817 | static bool OptimizeAwayTrappingUsesOfLoads( |
818 | GlobalVariable *GV, Constant *LV, const DataLayout &DL, |
819 | function_ref<TargetLibraryInfo &(Function &)> GetTLI) { |
820 | bool Changed = false; |
821 | |
822 | // Keep track of whether we are able to remove all the uses of the global |
823 | // other than the store that defines it. |
824 | bool AllNonStoreUsesGone = true; |
825 | |
826 | // Replace all uses of loads with uses of uses of the stored value. |
827 | for (User *GlobalUser : llvm::make_early_inc_range(Range: GV->users())) { |
828 | if (LoadInst *LI = dyn_cast<LoadInst>(Val: GlobalUser)) { |
829 | Changed |= OptimizeAwayTrappingUsesOfValue(V: LI, NewV: LV); |
830 | // If we were able to delete all uses of the loads |
831 | if (LI->use_empty()) { |
832 | LI->eraseFromParent(); |
833 | Changed = true; |
834 | } else { |
835 | AllNonStoreUsesGone = false; |
836 | } |
837 | } else if (isa<StoreInst>(Val: GlobalUser)) { |
838 | // Ignore the store that stores "LV" to the global. |
839 | assert(GlobalUser->getOperand(1) == GV && |
840 | "Must be storing *to* the global" ); |
841 | } else { |
842 | AllNonStoreUsesGone = false; |
843 | |
844 | // If we get here we could have other crazy uses that are transitively |
845 | // loaded. |
846 | assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || |
847 | isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || |
848 | isa<BitCastInst>(GlobalUser) || |
849 | isa<GetElementPtrInst>(GlobalUser) || |
850 | isa<AddrSpaceCastInst>(GlobalUser)) && |
851 | "Only expect load and stores!" ); |
852 | } |
853 | } |
854 | |
855 | if (Changed) { |
856 | LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV |
857 | << "\n" ); |
858 | ++NumGlobUses; |
859 | } |
860 | |
861 | // If we nuked all of the loads, then none of the stores are needed either, |
862 | // nor is the global. |
863 | if (AllNonStoreUsesGone) { |
864 | if (isLeakCheckerRoot(GV)) { |
865 | Changed |= CleanupPointerRootUsers(GV, GetTLI); |
866 | } else { |
867 | Changed = true; |
868 | CleanupConstantGlobalUsers(GV, DL); |
869 | } |
870 | if (GV->use_empty()) { |
871 | LLVM_DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n" ); |
872 | Changed = true; |
873 | GV->eraseFromParent(); |
874 | ++NumDeleted; |
875 | } |
876 | } |
877 | return Changed; |
878 | } |
879 | |
880 | /// Walk the use list of V, constant folding all of the instructions that are |
881 | /// foldable. |
882 | static void ConstantPropUsersOf(Value *V, const DataLayout &DL, |
883 | TargetLibraryInfo *TLI) { |
884 | for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; ) |
885 | if (Instruction *I = dyn_cast<Instruction>(Val: *UI++)) |
886 | if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) { |
887 | I->replaceAllUsesWith(V: NewC); |
888 | |
889 | // Advance UI to the next non-I use to avoid invalidating it! |
890 | // Instructions could multiply use V. |
891 | while (UI != E && *UI == I) |
892 | ++UI; |
893 | if (isInstructionTriviallyDead(I, TLI)) |
894 | I->eraseFromParent(); |
895 | } |
896 | } |
897 | |
898 | /// This function takes the specified global variable, and transforms the |
899 | /// program as if it always contained the result of the specified malloc. |
900 | /// Because it is always the result of the specified malloc, there is no reason |
901 | /// to actually DO the malloc. Instead, turn the malloc into a global, and any |
902 | /// loads of GV as uses of the new global. |
903 | static GlobalVariable * |
904 | OptimizeGlobalAddressOfAllocation(GlobalVariable *GV, CallInst *CI, |
905 | uint64_t AllocSize, Constant *InitVal, |
906 | const DataLayout &DL, |
907 | TargetLibraryInfo *TLI) { |
908 | LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI |
909 | << '\n'); |
910 | |
911 | // Create global of type [AllocSize x i8]. |
912 | Type *GlobalType = ArrayType::get(ElementType: Type::getInt8Ty(C&: GV->getContext()), |
913 | NumElements: AllocSize); |
914 | |
915 | // Create the new global variable. The contents of the allocated memory is |
916 | // undefined initially, so initialize with an undef value. |
917 | GlobalVariable *NewGV = new GlobalVariable( |
918 | *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage, |
919 | UndefValue::get(T: GlobalType), GV->getName() + ".body" , nullptr, |
920 | GV->getThreadLocalMode()); |
921 | |
922 | // Initialize the global at the point of the original call. Note that this |
923 | // is a different point from the initialization referred to below for the |
924 | // nullability handling. Sublety: We have not proven the original global was |
925 | // only initialized once. As such, we can not fold this into the initializer |
926 | // of the new global as may need to re-init the storage multiple times. |
927 | if (!isa<UndefValue>(Val: InitVal)) { |
928 | IRBuilder<> Builder(CI->getNextNode()); |
929 | // TODO: Use alignment above if align!=1 |
930 | Builder.CreateMemSet(Ptr: NewGV, Val: InitVal, Size: AllocSize, Align: std::nullopt); |
931 | } |
932 | |
933 | // Update users of the allocation to use the new global instead. |
934 | CI->replaceAllUsesWith(V: NewGV); |
935 | |
936 | // If there is a comparison against null, we will insert a global bool to |
937 | // keep track of whether the global was initialized yet or not. |
938 | GlobalVariable *InitBool = |
939 | new GlobalVariable(Type::getInt1Ty(C&: GV->getContext()), false, |
940 | GlobalValue::InternalLinkage, |
941 | ConstantInt::getFalse(Context&: GV->getContext()), |
942 | GV->getName()+".init" , GV->getThreadLocalMode()); |
943 | bool InitBoolUsed = false; |
944 | |
945 | // Loop over all instruction uses of GV, processing them in turn. |
946 | SmallVector<Value *, 4> Guses; |
947 | allUsesOfLoadAndStores(GV, Uses&: Guses); |
948 | for (auto *U : Guses) { |
949 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: U)) { |
950 | // The global is initialized when the store to it occurs. If the stored |
951 | // value is null value, the global bool is set to false, otherwise true. |
952 | new StoreInst(ConstantInt::getBool( |
953 | Context&: GV->getContext(), |
954 | V: !isa<ConstantPointerNull>(Val: SI->getValueOperand())), |
955 | InitBool, false, Align(1), SI->getOrdering(), |
956 | SI->getSyncScopeID(), SI->getIterator()); |
957 | SI->eraseFromParent(); |
958 | continue; |
959 | } |
960 | |
961 | LoadInst *LI = cast<LoadInst>(Val: U); |
962 | while (!LI->use_empty()) { |
963 | Use &LoadUse = *LI->use_begin(); |
964 | ICmpInst *ICI = dyn_cast<ICmpInst>(Val: LoadUse.getUser()); |
965 | if (!ICI) { |
966 | LoadUse.set(NewGV); |
967 | continue; |
968 | } |
969 | |
970 | // Replace the cmp X, 0 with a use of the bool value. |
971 | Value *LV = new LoadInst(InitBool->getValueType(), InitBool, |
972 | InitBool->getName() + ".val" , false, Align(1), |
973 | LI->getOrdering(), LI->getSyncScopeID(), |
974 | LI->getIterator()); |
975 | InitBoolUsed = true; |
976 | switch (ICI->getPredicate()) { |
977 | default: llvm_unreachable("Unknown ICmp Predicate!" ); |
978 | case ICmpInst::ICMP_ULT: // X < null -> always false |
979 | LV = ConstantInt::getFalse(Context&: GV->getContext()); |
980 | break; |
981 | case ICmpInst::ICMP_UGE: // X >= null -> always true |
982 | LV = ConstantInt::getTrue(Context&: GV->getContext()); |
983 | break; |
984 | case ICmpInst::ICMP_ULE: |
985 | case ICmpInst::ICMP_EQ: |
986 | LV = BinaryOperator::CreateNot(Op: LV, Name: "notinit" , InsertBefore: ICI->getIterator()); |
987 | break; |
988 | case ICmpInst::ICMP_NE: |
989 | case ICmpInst::ICMP_UGT: |
990 | break; // no change. |
991 | } |
992 | ICI->replaceAllUsesWith(V: LV); |
993 | ICI->eraseFromParent(); |
994 | } |
995 | LI->eraseFromParent(); |
996 | } |
997 | |
998 | // If the initialization boolean was used, insert it, otherwise delete it. |
999 | if (!InitBoolUsed) { |
1000 | while (!InitBool->use_empty()) // Delete initializations |
1001 | cast<StoreInst>(Val: InitBool->user_back())->eraseFromParent(); |
1002 | delete InitBool; |
1003 | } else |
1004 | GV->getParent()->insertGlobalVariable(Where: GV->getIterator(), GV: InitBool); |
1005 | |
1006 | // Now the GV is dead, nuke it and the allocation.. |
1007 | GV->eraseFromParent(); |
1008 | CI->eraseFromParent(); |
1009 | |
1010 | // To further other optimizations, loop over all users of NewGV and try to |
1011 | // constant prop them. This will promote GEP instructions with constant |
1012 | // indices into GEP constant-exprs, which will allow global-opt to hack on it. |
1013 | ConstantPropUsersOf(V: NewGV, DL, TLI); |
1014 | |
1015 | return NewGV; |
1016 | } |
1017 | |
1018 | /// Scan the use-list of GV checking to make sure that there are no complex uses |
1019 | /// of GV. We permit simple things like dereferencing the pointer, but not |
1020 | /// storing through the address, unless it is to the specified global. |
1021 | static bool |
1022 | valueIsOnlyUsedLocallyOrStoredToOneGlobal(const CallInst *CI, |
1023 | const GlobalVariable *GV) { |
1024 | SmallPtrSet<const Value *, 4> Visited; |
1025 | SmallVector<const Value *, 4> Worklist; |
1026 | Worklist.push_back(Elt: CI); |
1027 | |
1028 | while (!Worklist.empty()) { |
1029 | const Value *V = Worklist.pop_back_val(); |
1030 | if (!Visited.insert(Ptr: V).second) |
1031 | continue; |
1032 | |
1033 | for (const Use &VUse : V->uses()) { |
1034 | const User *U = VUse.getUser(); |
1035 | if (isa<LoadInst>(Val: U) || isa<CmpInst>(Val: U)) |
1036 | continue; // Fine, ignore. |
1037 | |
1038 | if (auto *SI = dyn_cast<StoreInst>(Val: U)) { |
1039 | if (SI->getValueOperand() == V && |
1040 | SI->getPointerOperand()->stripPointerCasts() != GV) |
1041 | return false; // Storing the pointer not into GV... bad. |
1042 | continue; // Otherwise, storing through it, or storing into GV... fine. |
1043 | } |
1044 | |
1045 | if (auto *BCI = dyn_cast<BitCastInst>(Val: U)) { |
1046 | Worklist.push_back(Elt: BCI); |
1047 | continue; |
1048 | } |
1049 | |
1050 | if (auto *GEPI = dyn_cast<GetElementPtrInst>(Val: U)) { |
1051 | Worklist.push_back(Elt: GEPI); |
1052 | continue; |
1053 | } |
1054 | |
1055 | return false; |
1056 | } |
1057 | } |
1058 | |
1059 | return true; |
1060 | } |
1061 | |
1062 | /// If we have a global that is only initialized with a fixed size allocation |
1063 | /// try to transform the program to use global memory instead of heap |
1064 | /// allocated memory. This eliminates dynamic allocation, avoids an indirection |
1065 | /// accessing the data, and exposes the resultant global to further GlobalOpt. |
1066 | static bool tryToOptimizeStoreOfAllocationToGlobal(GlobalVariable *GV, |
1067 | CallInst *CI, |
1068 | const DataLayout &DL, |
1069 | TargetLibraryInfo *TLI) { |
1070 | if (!isRemovableAlloc(V: CI, TLI)) |
1071 | // Must be able to remove the call when we get done.. |
1072 | return false; |
1073 | |
1074 | Type *Int8Ty = Type::getInt8Ty(C&: CI->getFunction()->getContext()); |
1075 | Constant *InitVal = getInitialValueOfAllocation(V: CI, TLI, Ty: Int8Ty); |
1076 | if (!InitVal) |
1077 | // Must be able to emit a memset for initialization |
1078 | return false; |
1079 | |
1080 | uint64_t AllocSize; |
1081 | if (!getObjectSize(Ptr: CI, Size&: AllocSize, DL, TLI, Opts: ObjectSizeOpts())) |
1082 | return false; |
1083 | |
1084 | // Restrict this transformation to only working on small allocations |
1085 | // (2048 bytes currently), as we don't want to introduce a 16M global or |
1086 | // something. |
1087 | if (AllocSize >= 2048) |
1088 | return false; |
1089 | |
1090 | // We can't optimize this global unless all uses of it are *known* to be |
1091 | // of the malloc value, not of the null initializer value (consider a use |
1092 | // that compares the global's value against zero to see if the malloc has |
1093 | // been reached). To do this, we check to see if all uses of the global |
1094 | // would trap if the global were null: this proves that they must all |
1095 | // happen after the malloc. |
1096 | if (!allUsesOfLoadedValueWillTrapIfNull(GV)) |
1097 | return false; |
1098 | |
1099 | // We can't optimize this if the malloc itself is used in a complex way, |
1100 | // for example, being stored into multiple globals. This allows the |
1101 | // malloc to be stored into the specified global, loaded, gep, icmp'd. |
1102 | // These are all things we could transform to using the global for. |
1103 | if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV)) |
1104 | return false; |
1105 | |
1106 | OptimizeGlobalAddressOfAllocation(GV, CI, AllocSize, InitVal, DL, TLI); |
1107 | return true; |
1108 | } |
1109 | |
1110 | // Try to optimize globals based on the knowledge that only one value (besides |
1111 | // its initializer) is ever stored to the global. |
1112 | static bool |
1113 | optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, |
1114 | const DataLayout &DL, |
1115 | function_ref<TargetLibraryInfo &(Function &)> GetTLI) { |
1116 | // Ignore no-op GEPs and bitcasts. |
1117 | StoredOnceVal = StoredOnceVal->stripPointerCasts(); |
1118 | |
1119 | // If we are dealing with a pointer global that is initialized to null and |
1120 | // only has one (non-null) value stored into it, then we can optimize any |
1121 | // users of the loaded value (often calls and loads) that would trap if the |
1122 | // value was null. |
1123 | if (GV->getInitializer()->getType()->isPointerTy() && |
1124 | GV->getInitializer()->isNullValue() && |
1125 | StoredOnceVal->getType()->isPointerTy() && |
1126 | !NullPointerIsDefined( |
1127 | F: nullptr /* F */, |
1128 | AS: GV->getInitializer()->getType()->getPointerAddressSpace())) { |
1129 | if (Constant *SOVC = dyn_cast<Constant>(Val: StoredOnceVal)) { |
1130 | // Optimize away any trapping uses of the loaded value. |
1131 | if (OptimizeAwayTrappingUsesOfLoads(GV, LV: SOVC, DL, GetTLI)) |
1132 | return true; |
1133 | } else if (isAllocationFn(V: StoredOnceVal, GetTLI)) { |
1134 | if (auto *CI = dyn_cast<CallInst>(Val: StoredOnceVal)) { |
1135 | auto *TLI = &GetTLI(*CI->getFunction()); |
1136 | if (tryToOptimizeStoreOfAllocationToGlobal(GV, CI, DL, TLI)) |
1137 | return true; |
1138 | } |
1139 | } |
1140 | } |
1141 | |
1142 | return false; |
1143 | } |
1144 | |
1145 | /// At this point, we have learned that the only two values ever stored into GV |
1146 | /// are its initializer and OtherVal. See if we can shrink the global into a |
1147 | /// boolean and select between the two values whenever it is used. This exposes |
1148 | /// the values to other scalar optimizations. |
1149 | static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) { |
1150 | Type *GVElType = GV->getValueType(); |
1151 | |
1152 | // If GVElType is already i1, it is already shrunk. If the type of the GV is |
1153 | // an FP value, pointer or vector, don't do this optimization because a select |
1154 | // between them is very expensive and unlikely to lead to later |
1155 | // simplification. In these cases, we typically end up with "cond ? v1 : v2" |
1156 | // where v1 and v2 both require constant pool loads, a big loss. |
1157 | if (GVElType == Type::getInt1Ty(C&: GV->getContext()) || |
1158 | GVElType->isFloatingPointTy() || |
1159 | GVElType->isPointerTy() || GVElType->isVectorTy()) |
1160 | return false; |
1161 | |
1162 | // Walk the use list of the global seeing if all the uses are load or store. |
1163 | // If there is anything else, bail out. |
1164 | for (User *U : GV->users()) { |
1165 | if (!isa<LoadInst>(Val: U) && !isa<StoreInst>(Val: U)) |
1166 | return false; |
1167 | if (getLoadStoreType(I: U) != GVElType) |
1168 | return false; |
1169 | } |
1170 | |
1171 | LLVM_DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV << "\n" ); |
1172 | |
1173 | // Create the new global, initializing it to false. |
1174 | GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(C&: GV->getContext()), |
1175 | false, |
1176 | GlobalValue::InternalLinkage, |
1177 | ConstantInt::getFalse(Context&: GV->getContext()), |
1178 | GV->getName()+".b" , |
1179 | GV->getThreadLocalMode(), |
1180 | GV->getType()->getAddressSpace()); |
1181 | NewGV->copyAttributesFrom(Src: GV); |
1182 | GV->getParent()->insertGlobalVariable(Where: GV->getIterator(), GV: NewGV); |
1183 | |
1184 | Constant *InitVal = GV->getInitializer(); |
1185 | assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) && |
1186 | "No reason to shrink to bool!" ); |
1187 | |
1188 | SmallVector<DIGlobalVariableExpression *, 1> GVs; |
1189 | GV->getDebugInfo(GVs); |
1190 | |
1191 | // If initialized to zero and storing one into the global, we can use a cast |
1192 | // instead of a select to synthesize the desired value. |
1193 | bool IsOneZero = false; |
1194 | bool EmitOneOrZero = true; |
1195 | auto *CI = dyn_cast<ConstantInt>(Val: OtherVal); |
1196 | if (CI && CI->getValue().getActiveBits() <= 64) { |
1197 | IsOneZero = InitVal->isNullValue() && CI->isOne(); |
1198 | |
1199 | auto *CIInit = dyn_cast<ConstantInt>(Val: GV->getInitializer()); |
1200 | if (CIInit && CIInit->getValue().getActiveBits() <= 64) { |
1201 | uint64_t ValInit = CIInit->getZExtValue(); |
1202 | uint64_t ValOther = CI->getZExtValue(); |
1203 | uint64_t ValMinus = ValOther - ValInit; |
1204 | |
1205 | for(auto *GVe : GVs){ |
1206 | DIGlobalVariable *DGV = GVe->getVariable(); |
1207 | DIExpression *E = GVe->getExpression(); |
1208 | const DataLayout &DL = GV->getParent()->getDataLayout(); |
1209 | unsigned SizeInOctets = |
1210 | DL.getTypeAllocSizeInBits(Ty: NewGV->getValueType()) / 8; |
1211 | |
1212 | // It is expected that the address of global optimized variable is on |
1213 | // top of the stack. After optimization, value of that variable will |
1214 | // be ether 0 for initial value or 1 for other value. The following |
1215 | // expression should return constant integer value depending on the |
1216 | // value at global object address: |
1217 | // val * (ValOther - ValInit) + ValInit: |
1218 | // DW_OP_deref DW_OP_constu <ValMinus> |
1219 | // DW_OP_mul DW_OP_constu <ValInit> DW_OP_plus DW_OP_stack_value |
1220 | SmallVector<uint64_t, 12> Ops = { |
1221 | dwarf::DW_OP_deref_size, SizeInOctets, |
1222 | dwarf::DW_OP_constu, ValMinus, |
1223 | dwarf::DW_OP_mul, dwarf::DW_OP_constu, ValInit, |
1224 | dwarf::DW_OP_plus}; |
1225 | bool WithStackValue = true; |
1226 | E = DIExpression::prependOpcodes(Expr: E, Ops, StackValue: WithStackValue); |
1227 | DIGlobalVariableExpression *DGVE = |
1228 | DIGlobalVariableExpression::get(Context&: NewGV->getContext(), Variable: DGV, Expression: E); |
1229 | NewGV->addDebugInfo(GV: DGVE); |
1230 | } |
1231 | EmitOneOrZero = false; |
1232 | } |
1233 | } |
1234 | |
1235 | if (EmitOneOrZero) { |
1236 | // FIXME: This will only emit address for debugger on which will |
1237 | // be written only 0 or 1. |
1238 | for(auto *GV : GVs) |
1239 | NewGV->addDebugInfo(GV); |
1240 | } |
1241 | |
1242 | while (!GV->use_empty()) { |
1243 | Instruction *UI = cast<Instruction>(Val: GV->user_back()); |
1244 | if (StoreInst *SI = dyn_cast<StoreInst>(Val: UI)) { |
1245 | // Change the store into a boolean store. |
1246 | bool StoringOther = SI->getOperand(i_nocapture: 0) == OtherVal; |
1247 | // Only do this if we weren't storing a loaded value. |
1248 | Value *StoreVal; |
1249 | if (StoringOther || SI->getOperand(i_nocapture: 0) == InitVal) { |
1250 | StoreVal = ConstantInt::get(Ty: Type::getInt1Ty(C&: GV->getContext()), |
1251 | V: StoringOther); |
1252 | } else { |
1253 | // Otherwise, we are storing a previously loaded copy. To do this, |
1254 | // change the copy from copying the original value to just copying the |
1255 | // bool. |
1256 | Instruction *StoredVal = cast<Instruction>(Val: SI->getOperand(i_nocapture: 0)); |
1257 | |
1258 | // If we've already replaced the input, StoredVal will be a cast or |
1259 | // select instruction. If not, it will be a load of the original |
1260 | // global. |
1261 | if (LoadInst *LI = dyn_cast<LoadInst>(Val: StoredVal)) { |
1262 | assert(LI->getOperand(0) == GV && "Not a copy!" ); |
1263 | // Insert a new load, to preserve the saved value. |
1264 | StoreVal = |
1265 | new LoadInst(NewGV->getValueType(), NewGV, LI->getName() + ".b" , |
1266 | false, Align(1), LI->getOrdering(), |
1267 | LI->getSyncScopeID(), LI->getIterator()); |
1268 | } else { |
1269 | assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && |
1270 | "This is not a form that we understand!" ); |
1271 | StoreVal = StoredVal->getOperand(i: 0); |
1272 | assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!" ); |
1273 | } |
1274 | } |
1275 | StoreInst *NSI = |
1276 | new StoreInst(StoreVal, NewGV, false, Align(1), SI->getOrdering(), |
1277 | SI->getSyncScopeID(), SI->getIterator()); |
1278 | NSI->setDebugLoc(SI->getDebugLoc()); |
1279 | } else { |
1280 | // Change the load into a load of bool then a select. |
1281 | LoadInst *LI = cast<LoadInst>(Val: UI); |
1282 | LoadInst *NLI = new LoadInst( |
1283 | NewGV->getValueType(), NewGV, LI->getName() + ".b" , false, Align(1), |
1284 | LI->getOrdering(), LI->getSyncScopeID(), LI->getIterator()); |
1285 | Instruction *NSI; |
1286 | if (IsOneZero) |
1287 | NSI = new ZExtInst(NLI, LI->getType(), "" , LI->getIterator()); |
1288 | else |
1289 | NSI = SelectInst::Create(C: NLI, S1: OtherVal, S2: InitVal, NameStr: "" , InsertBefore: LI->getIterator()); |
1290 | NSI->takeName(V: LI); |
1291 | // Since LI is split into two instructions, NLI and NSI both inherit the |
1292 | // same DebugLoc |
1293 | NLI->setDebugLoc(LI->getDebugLoc()); |
1294 | NSI->setDebugLoc(LI->getDebugLoc()); |
1295 | LI->replaceAllUsesWith(V: NSI); |
1296 | } |
1297 | UI->eraseFromParent(); |
1298 | } |
1299 | |
1300 | // Retain the name of the old global variable. People who are debugging their |
1301 | // programs may expect these variables to be named the same. |
1302 | NewGV->takeName(V: GV); |
1303 | GV->eraseFromParent(); |
1304 | return true; |
1305 | } |
1306 | |
1307 | static bool |
1308 | deleteIfDead(GlobalValue &GV, |
1309 | SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats, |
1310 | function_ref<void(Function &)> DeleteFnCallback = nullptr) { |
1311 | GV.removeDeadConstantUsers(); |
1312 | |
1313 | if (!GV.isDiscardableIfUnused() && !GV.isDeclaration()) |
1314 | return false; |
1315 | |
1316 | if (const Comdat *C = GV.getComdat()) |
1317 | if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(Ptr: C)) |
1318 | return false; |
1319 | |
1320 | bool Dead; |
1321 | if (auto *F = dyn_cast<Function>(Val: &GV)) |
1322 | Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead(); |
1323 | else |
1324 | Dead = GV.use_empty(); |
1325 | if (!Dead) |
1326 | return false; |
1327 | |
1328 | LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n" ); |
1329 | if (auto *F = dyn_cast<Function>(Val: &GV)) { |
1330 | if (DeleteFnCallback) |
1331 | DeleteFnCallback(*F); |
1332 | } |
1333 | GV.eraseFromParent(); |
1334 | ++NumDeleted; |
1335 | return true; |
1336 | } |
1337 | |
1338 | static bool isPointerValueDeadOnEntryToFunction( |
1339 | const Function *F, GlobalValue *GV, |
1340 | function_ref<DominatorTree &(Function &)> LookupDomTree) { |
1341 | // Find all uses of GV. We expect them all to be in F, and if we can't |
1342 | // identify any of the uses we bail out. |
1343 | // |
1344 | // On each of these uses, identify if the memory that GV points to is |
1345 | // used/required/live at the start of the function. If it is not, for example |
1346 | // if the first thing the function does is store to the GV, the GV can |
1347 | // possibly be demoted. |
1348 | // |
1349 | // We don't do an exhaustive search for memory operations - simply look |
1350 | // through bitcasts as they're quite common and benign. |
1351 | const DataLayout &DL = GV->getParent()->getDataLayout(); |
1352 | SmallVector<LoadInst *, 4> Loads; |
1353 | SmallVector<StoreInst *, 4> Stores; |
1354 | for (auto *U : GV->users()) { |
1355 | Instruction *I = dyn_cast<Instruction>(Val: U); |
1356 | if (!I) |
1357 | return false; |
1358 | assert(I->getParent()->getParent() == F); |
1359 | |
1360 | if (auto *LI = dyn_cast<LoadInst>(Val: I)) |
1361 | Loads.push_back(Elt: LI); |
1362 | else if (auto *SI = dyn_cast<StoreInst>(Val: I)) |
1363 | Stores.push_back(Elt: SI); |
1364 | else |
1365 | return false; |
1366 | } |
1367 | |
1368 | // We have identified all uses of GV into loads and stores. Now check if all |
1369 | // of them are known not to depend on the value of the global at the function |
1370 | // entry point. We do this by ensuring that every load is dominated by at |
1371 | // least one store. |
1372 | auto &DT = LookupDomTree(*const_cast<Function *>(F)); |
1373 | |
1374 | // The below check is quadratic. Check we're not going to do too many tests. |
1375 | // FIXME: Even though this will always have worst-case quadratic time, we |
1376 | // could put effort into minimizing the average time by putting stores that |
1377 | // have been shown to dominate at least one load at the beginning of the |
1378 | // Stores array, making subsequent dominance checks more likely to succeed |
1379 | // early. |
1380 | // |
1381 | // The threshold here is fairly large because global->local demotion is a |
1382 | // very powerful optimization should it fire. |
1383 | const unsigned Threshold = 100; |
1384 | if (Loads.size() * Stores.size() > Threshold) |
1385 | return false; |
1386 | |
1387 | for (auto *L : Loads) { |
1388 | auto *LTy = L->getType(); |
1389 | if (none_of(Range&: Stores, P: [&](const StoreInst *S) { |
1390 | auto *STy = S->getValueOperand()->getType(); |
1391 | // The load is only dominated by the store if DomTree says so |
1392 | // and the number of bits loaded in L is less than or equal to |
1393 | // the number of bits stored in S. |
1394 | return DT.dominates(Def: S, User: L) && |
1395 | DL.getTypeStoreSize(Ty: LTy).getFixedValue() <= |
1396 | DL.getTypeStoreSize(Ty: STy).getFixedValue(); |
1397 | })) |
1398 | return false; |
1399 | } |
1400 | // All loads have known dependences inside F, so the global can be localized. |
1401 | return true; |
1402 | } |
1403 | |
1404 | // For a global variable with one store, if the store dominates any loads, |
1405 | // those loads will always load the stored value (as opposed to the |
1406 | // initializer), even in the presence of recursion. |
1407 | static bool forwardStoredOnceStore( |
1408 | GlobalVariable *GV, const StoreInst *StoredOnceStore, |
1409 | function_ref<DominatorTree &(Function &)> LookupDomTree) { |
1410 | const Value *StoredOnceValue = StoredOnceStore->getValueOperand(); |
1411 | // We can do this optimization for non-constants in nosync + norecurse |
1412 | // functions, but globals used in exactly one norecurse functions are already |
1413 | // promoted to an alloca. |
1414 | if (!isa<Constant>(Val: StoredOnceValue)) |
1415 | return false; |
1416 | const Function *F = StoredOnceStore->getFunction(); |
1417 | SmallVector<LoadInst *> Loads; |
1418 | for (User *U : GV->users()) { |
1419 | if (auto *LI = dyn_cast<LoadInst>(Val: U)) { |
1420 | if (LI->getFunction() == F && |
1421 | LI->getType() == StoredOnceValue->getType() && LI->isSimple()) |
1422 | Loads.push_back(Elt: LI); |
1423 | } |
1424 | } |
1425 | // Only compute DT if we have any loads to examine. |
1426 | bool MadeChange = false; |
1427 | if (!Loads.empty()) { |
1428 | auto &DT = LookupDomTree(*const_cast<Function *>(F)); |
1429 | for (auto *LI : Loads) { |
1430 | if (DT.dominates(Def: StoredOnceStore, User: LI)) { |
1431 | LI->replaceAllUsesWith(V: const_cast<Value *>(StoredOnceValue)); |
1432 | LI->eraseFromParent(); |
1433 | MadeChange = true; |
1434 | } |
1435 | } |
1436 | } |
1437 | return MadeChange; |
1438 | } |
1439 | |
1440 | /// Analyze the specified global variable and optimize |
1441 | /// it if possible. If we make a change, return true. |
1442 | static bool |
1443 | processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS, |
1444 | function_ref<TargetTransformInfo &(Function &)> GetTTI, |
1445 | function_ref<TargetLibraryInfo &(Function &)> GetTLI, |
1446 | function_ref<DominatorTree &(Function &)> LookupDomTree) { |
1447 | auto &DL = GV->getParent()->getDataLayout(); |
1448 | // If this is a first class global and has only one accessing function and |
1449 | // this function is non-recursive, we replace the global with a local alloca |
1450 | // in this function. |
1451 | // |
1452 | // NOTE: It doesn't make sense to promote non-single-value types since we |
1453 | // are just replacing static memory to stack memory. |
1454 | // |
1455 | // If the global is in different address space, don't bring it to stack. |
1456 | if (!GS.HasMultipleAccessingFunctions && |
1457 | GS.AccessingFunction && |
1458 | GV->getValueType()->isSingleValueType() && |
1459 | GV->getType()->getAddressSpace() == DL.getAllocaAddrSpace() && |
1460 | !GV->isExternallyInitialized() && |
1461 | GS.AccessingFunction->doesNotRecurse() && |
1462 | isPointerValueDeadOnEntryToFunction(F: GS.AccessingFunction, GV, |
1463 | LookupDomTree)) { |
1464 | const DataLayout &DL = GV->getParent()->getDataLayout(); |
1465 | |
1466 | LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n" ); |
1467 | BasicBlock::iterator FirstI = |
1468 | GS.AccessingFunction->getEntryBlock().begin().getNonConst(); |
1469 | Type *ElemTy = GV->getValueType(); |
1470 | // FIXME: Pass Global's alignment when globals have alignment |
1471 | AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), |
1472 | nullptr, GV->getName(), FirstI); |
1473 | if (!isa<UndefValue>(Val: GV->getInitializer())) |
1474 | new StoreInst(GV->getInitializer(), Alloca, FirstI); |
1475 | |
1476 | GV->replaceAllUsesWith(V: Alloca); |
1477 | GV->eraseFromParent(); |
1478 | ++NumLocalized; |
1479 | return true; |
1480 | } |
1481 | |
1482 | bool Changed = false; |
1483 | |
1484 | // If the global is never loaded (but may be stored to), it is dead. |
1485 | // Delete it now. |
1486 | if (!GS.IsLoaded) { |
1487 | LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n" ); |
1488 | |
1489 | if (isLeakCheckerRoot(GV)) { |
1490 | // Delete any constant stores to the global. |
1491 | Changed = CleanupPointerRootUsers(GV, GetTLI); |
1492 | } else { |
1493 | // Delete any stores we can find to the global. We may not be able to |
1494 | // make it completely dead though. |
1495 | Changed = CleanupConstantGlobalUsers(GV, DL); |
1496 | } |
1497 | |
1498 | // If the global is dead now, delete it. |
1499 | if (GV->use_empty()) { |
1500 | GV->eraseFromParent(); |
1501 | ++NumDeleted; |
1502 | Changed = true; |
1503 | } |
1504 | return Changed; |
1505 | |
1506 | } |
1507 | if (GS.StoredType <= GlobalStatus::InitializerStored) { |
1508 | LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n" ); |
1509 | |
1510 | // Don't actually mark a global constant if it's atomic because atomic loads |
1511 | // are implemented by a trivial cmpxchg in some edge-cases and that usually |
1512 | // requires write access to the variable even if it's not actually changed. |
1513 | if (GS.Ordering == AtomicOrdering::NotAtomic) { |
1514 | assert(!GV->isConstant() && "Expected a non-constant global" ); |
1515 | GV->setConstant(true); |
1516 | Changed = true; |
1517 | } |
1518 | |
1519 | // Clean up any obviously simplifiable users now. |
1520 | Changed |= CleanupConstantGlobalUsers(GV, DL); |
1521 | |
1522 | // If the global is dead now, just nuke it. |
1523 | if (GV->use_empty()) { |
1524 | LLVM_DEBUG(dbgs() << " *** Marking constant allowed us to simplify " |
1525 | << "all users and delete global!\n" ); |
1526 | GV->eraseFromParent(); |
1527 | ++NumDeleted; |
1528 | return true; |
1529 | } |
1530 | |
1531 | // Fall through to the next check; see if we can optimize further. |
1532 | ++NumMarked; |
1533 | } |
1534 | if (!GV->getInitializer()->getType()->isSingleValueType()) { |
1535 | const DataLayout &DL = GV->getParent()->getDataLayout(); |
1536 | if (SRAGlobal(GV, DL)) |
1537 | return true; |
1538 | } |
1539 | Value *StoredOnceValue = GS.getStoredOnceValue(); |
1540 | if (GS.StoredType == GlobalStatus::StoredOnce && StoredOnceValue) { |
1541 | Function &StoreFn = |
1542 | const_cast<Function &>(*GS.StoredOnceStore->getFunction()); |
1543 | bool CanHaveNonUndefGlobalInitializer = |
1544 | GetTTI(StoreFn).canHaveNonUndefGlobalInitializerInAddressSpace( |
1545 | AS: GV->getType()->getAddressSpace()); |
1546 | // If the initial value for the global was an undef value, and if only |
1547 | // one other value was stored into it, we can just change the |
1548 | // initializer to be the stored value, then delete all stores to the |
1549 | // global. This allows us to mark it constant. |
1550 | // This is restricted to address spaces that allow globals to have |
1551 | // initializers. NVPTX, for example, does not support initializers for |
1552 | // shared memory (AS 3). |
1553 | auto *SOVConstant = dyn_cast<Constant>(Val: StoredOnceValue); |
1554 | if (SOVConstant && isa<UndefValue>(Val: GV->getInitializer()) && |
1555 | DL.getTypeAllocSize(Ty: SOVConstant->getType()) == |
1556 | DL.getTypeAllocSize(Ty: GV->getValueType()) && |
1557 | CanHaveNonUndefGlobalInitializer) { |
1558 | if (SOVConstant->getType() == GV->getValueType()) { |
1559 | // Change the initializer in place. |
1560 | GV->setInitializer(SOVConstant); |
1561 | } else { |
1562 | // Create a new global with adjusted type. |
1563 | auto *NGV = new GlobalVariable( |
1564 | *GV->getParent(), SOVConstant->getType(), GV->isConstant(), |
1565 | GV->getLinkage(), SOVConstant, "" , GV, GV->getThreadLocalMode(), |
1566 | GV->getAddressSpace()); |
1567 | NGV->takeName(V: GV); |
1568 | NGV->copyAttributesFrom(Src: GV); |
1569 | GV->replaceAllUsesWith(V: NGV); |
1570 | GV->eraseFromParent(); |
1571 | GV = NGV; |
1572 | } |
1573 | |
1574 | // Clean up any obviously simplifiable users now. |
1575 | CleanupConstantGlobalUsers(GV, DL); |
1576 | |
1577 | if (GV->use_empty()) { |
1578 | LLVM_DEBUG(dbgs() << " *** Substituting initializer allowed us to " |
1579 | << "simplify all users and delete global!\n" ); |
1580 | GV->eraseFromParent(); |
1581 | ++NumDeleted; |
1582 | } |
1583 | ++NumSubstitute; |
1584 | return true; |
1585 | } |
1586 | |
1587 | // Try to optimize globals based on the knowledge that only one value |
1588 | // (besides its initializer) is ever stored to the global. |
1589 | if (optimizeOnceStoredGlobal(GV, StoredOnceVal: StoredOnceValue, DL, GetTLI)) |
1590 | return true; |
1591 | |
1592 | // Try to forward the store to any loads. If we have more than one store, we |
1593 | // may have a store of the initializer between StoredOnceStore and a load. |
1594 | if (GS.NumStores == 1) |
1595 | if (forwardStoredOnceStore(GV, StoredOnceStore: GS.StoredOnceStore, LookupDomTree)) |
1596 | return true; |
1597 | |
1598 | // Otherwise, if the global was not a boolean, we can shrink it to be a |
1599 | // boolean. Skip this optimization for AS that doesn't allow an initializer. |
1600 | if (SOVConstant && GS.Ordering == AtomicOrdering::NotAtomic && |
1601 | (!isa<UndefValue>(Val: GV->getInitializer()) || |
1602 | CanHaveNonUndefGlobalInitializer)) { |
1603 | if (TryToShrinkGlobalToBoolean(GV, OtherVal: SOVConstant)) { |
1604 | ++NumShrunkToBool; |
1605 | return true; |
1606 | } |
1607 | } |
1608 | } |
1609 | |
1610 | return Changed; |
1611 | } |
1612 | |
1613 | /// Analyze the specified global variable and optimize it if possible. If we |
1614 | /// make a change, return true. |
1615 | static bool |
1616 | processGlobal(GlobalValue &GV, |
1617 | function_ref<TargetTransformInfo &(Function &)> GetTTI, |
1618 | function_ref<TargetLibraryInfo &(Function &)> GetTLI, |
1619 | function_ref<DominatorTree &(Function &)> LookupDomTree) { |
1620 | if (GV.getName().starts_with(Prefix: "llvm." )) |
1621 | return false; |
1622 | |
1623 | GlobalStatus GS; |
1624 | |
1625 | if (GlobalStatus::analyzeGlobal(V: &GV, GS)) |
1626 | return false; |
1627 | |
1628 | bool Changed = false; |
1629 | if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) { |
1630 | auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global |
1631 | : GlobalValue::UnnamedAddr::Local; |
1632 | if (NewUnnamedAddr != GV.getUnnamedAddr()) { |
1633 | GV.setUnnamedAddr(NewUnnamedAddr); |
1634 | NumUnnamed++; |
1635 | Changed = true; |
1636 | } |
1637 | } |
1638 | |
1639 | // Do more involved optimizations if the global is internal. |
1640 | if (!GV.hasLocalLinkage()) |
1641 | return Changed; |
1642 | |
1643 | auto *GVar = dyn_cast<GlobalVariable>(Val: &GV); |
1644 | if (!GVar) |
1645 | return Changed; |
1646 | |
1647 | if (GVar->isConstant() || !GVar->hasInitializer()) |
1648 | return Changed; |
1649 | |
1650 | return processInternalGlobal(GV: GVar, GS, GetTTI, GetTLI, LookupDomTree) || |
1651 | Changed; |
1652 | } |
1653 | |
1654 | /// Walk all of the direct calls of the specified function, changing them to |
1655 | /// FastCC. |
1656 | static void ChangeCalleesToFastCall(Function *F) { |
1657 | for (User *U : F->users()) { |
1658 | if (isa<BlockAddress>(Val: U)) |
1659 | continue; |
1660 | cast<CallBase>(Val: U)->setCallingConv(CallingConv::Fast); |
1661 | } |
1662 | } |
1663 | |
1664 | static AttributeList StripAttr(LLVMContext &C, AttributeList Attrs, |
1665 | Attribute::AttrKind A) { |
1666 | unsigned AttrIndex; |
1667 | if (Attrs.hasAttrSomewhere(Kind: A, Index: &AttrIndex)) |
1668 | return Attrs.removeAttributeAtIndex(C, Index: AttrIndex, Kind: A); |
1669 | return Attrs; |
1670 | } |
1671 | |
1672 | static void RemoveAttribute(Function *F, Attribute::AttrKind A) { |
1673 | F->setAttributes(StripAttr(C&: F->getContext(), Attrs: F->getAttributes(), A)); |
1674 | for (User *U : F->users()) { |
1675 | if (isa<BlockAddress>(Val: U)) |
1676 | continue; |
1677 | CallBase *CB = cast<CallBase>(Val: U); |
1678 | CB->setAttributes(StripAttr(C&: F->getContext(), Attrs: CB->getAttributes(), A)); |
1679 | } |
1680 | } |
1681 | |
1682 | /// Return true if this is a calling convention that we'd like to change. The |
1683 | /// idea here is that we don't want to mess with the convention if the user |
1684 | /// explicitly requested something with performance implications like coldcc, |
1685 | /// GHC, or anyregcc. |
1686 | static bool hasChangeableCCImpl(Function *F) { |
1687 | CallingConv::ID CC = F->getCallingConv(); |
1688 | |
1689 | // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc? |
1690 | if (CC != CallingConv::C && CC != CallingConv::X86_ThisCall) |
1691 | return false; |
1692 | |
1693 | if (F->isVarArg()) |
1694 | return false; |
1695 | |
1696 | // FIXME: Change CC for the whole chain of musttail calls when possible. |
1697 | // |
1698 | // Can't change CC of the function that either has musttail calls, or is a |
1699 | // musttail callee itself |
1700 | for (User *U : F->users()) { |
1701 | if (isa<BlockAddress>(Val: U)) |
1702 | continue; |
1703 | CallInst* CI = dyn_cast<CallInst>(Val: U); |
1704 | if (!CI) |
1705 | continue; |
1706 | |
1707 | if (CI->isMustTailCall()) |
1708 | return false; |
1709 | } |
1710 | |
1711 | for (BasicBlock &BB : *F) |
1712 | if (BB.getTerminatingMustTailCall()) |
1713 | return false; |
1714 | |
1715 | return !F->hasAddressTaken(); |
1716 | } |
1717 | |
1718 | using ChangeableCCCacheTy = SmallDenseMap<Function *, bool, 8>; |
1719 | static bool hasChangeableCC(Function *F, |
1720 | ChangeableCCCacheTy &ChangeableCCCache) { |
1721 | auto Res = ChangeableCCCache.try_emplace(Key: F, Args: false); |
1722 | if (Res.second) |
1723 | Res.first->second = hasChangeableCCImpl(F); |
1724 | return Res.first->second; |
1725 | } |
1726 | |
1727 | /// Return true if the block containing the call site has a BlockFrequency of |
1728 | /// less than ColdCCRelFreq% of the entry block. |
1729 | static bool isColdCallSite(CallBase &CB, BlockFrequencyInfo &CallerBFI) { |
1730 | const BranchProbability ColdProb(ColdCCRelFreq, 100); |
1731 | auto *CallSiteBB = CB.getParent(); |
1732 | auto CallSiteFreq = CallerBFI.getBlockFreq(BB: CallSiteBB); |
1733 | auto CallerEntryFreq = |
1734 | CallerBFI.getBlockFreq(BB: &(CB.getCaller()->getEntryBlock())); |
1735 | return CallSiteFreq < CallerEntryFreq * ColdProb; |
1736 | } |
1737 | |
1738 | // This function checks if the input function F is cold at all call sites. It |
1739 | // also looks each call site's containing function, returning false if the |
1740 | // caller function contains other non cold calls. The input vector AllCallsCold |
1741 | // contains a list of functions that only have call sites in cold blocks. |
1742 | static bool |
1743 | isValidCandidateForColdCC(Function &F, |
1744 | function_ref<BlockFrequencyInfo &(Function &)> GetBFI, |
1745 | const std::vector<Function *> &AllCallsCold) { |
1746 | |
1747 | if (F.user_empty()) |
1748 | return false; |
1749 | |
1750 | for (User *U : F.users()) { |
1751 | if (isa<BlockAddress>(Val: U)) |
1752 | continue; |
1753 | |
1754 | CallBase &CB = cast<CallBase>(Val&: *U); |
1755 | Function *CallerFunc = CB.getParent()->getParent(); |
1756 | BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc); |
1757 | if (!isColdCallSite(CB, CallerBFI)) |
1758 | return false; |
1759 | if (!llvm::is_contained(Range: AllCallsCold, Element: CallerFunc)) |
1760 | return false; |
1761 | } |
1762 | return true; |
1763 | } |
1764 | |
1765 | static void changeCallSitesToColdCC(Function *F) { |
1766 | for (User *U : F->users()) { |
1767 | if (isa<BlockAddress>(Val: U)) |
1768 | continue; |
1769 | cast<CallBase>(Val: U)->setCallingConv(CallingConv::Cold); |
1770 | } |
1771 | } |
1772 | |
1773 | // This function iterates over all the call instructions in the input Function |
1774 | // and checks that all call sites are in cold blocks and are allowed to use the |
1775 | // coldcc calling convention. |
1776 | static bool |
1777 | hasOnlyColdCalls(Function &F, |
1778 | function_ref<BlockFrequencyInfo &(Function &)> GetBFI, |
1779 | ChangeableCCCacheTy &ChangeableCCCache) { |
1780 | for (BasicBlock &BB : F) { |
1781 | for (Instruction &I : BB) { |
1782 | if (CallInst *CI = dyn_cast<CallInst>(Val: &I)) { |
1783 | // Skip over isline asm instructions since they aren't function calls. |
1784 | if (CI->isInlineAsm()) |
1785 | continue; |
1786 | Function *CalledFn = CI->getCalledFunction(); |
1787 | if (!CalledFn) |
1788 | return false; |
1789 | // Skip over intrinsics since they won't remain as function calls. |
1790 | // Important to do this check before the linkage check below so we |
1791 | // won't bail out on debug intrinsics, possibly making the generated |
1792 | // code dependent on the presence of debug info. |
1793 | if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic) |
1794 | continue; |
1795 | if (!CalledFn->hasLocalLinkage()) |
1796 | return false; |
1797 | // Check if it's valid to use coldcc calling convention. |
1798 | if (!hasChangeableCC(F: CalledFn, ChangeableCCCache)) |
1799 | return false; |
1800 | BlockFrequencyInfo &CallerBFI = GetBFI(F); |
1801 | if (!isColdCallSite(CB&: *CI, CallerBFI)) |
1802 | return false; |
1803 | } |
1804 | } |
1805 | } |
1806 | return true; |
1807 | } |
1808 | |
1809 | static bool hasMustTailCallers(Function *F) { |
1810 | for (User *U : F->users()) { |
1811 | CallBase *CB = dyn_cast<CallBase>(Val: U); |
1812 | if (!CB) { |
1813 | assert(isa<BlockAddress>(U) && |
1814 | "Expected either CallBase or BlockAddress" ); |
1815 | continue; |
1816 | } |
1817 | if (CB->isMustTailCall()) |
1818 | return true; |
1819 | } |
1820 | return false; |
1821 | } |
1822 | |
1823 | static bool hasInvokeCallers(Function *F) { |
1824 | for (User *U : F->users()) |
1825 | if (isa<InvokeInst>(Val: U)) |
1826 | return true; |
1827 | return false; |
1828 | } |
1829 | |
1830 | static void RemovePreallocated(Function *F) { |
1831 | RemoveAttribute(F, Attribute::Preallocated); |
1832 | |
1833 | auto *M = F->getParent(); |
1834 | |
1835 | IRBuilder<> Builder(M->getContext()); |
1836 | |
1837 | // Cannot modify users() while iterating over it, so make a copy. |
1838 | SmallVector<User *, 4> PreallocatedCalls(F->users()); |
1839 | for (User *U : PreallocatedCalls) { |
1840 | CallBase *CB = dyn_cast<CallBase>(Val: U); |
1841 | if (!CB) |
1842 | continue; |
1843 | |
1844 | assert( |
1845 | !CB->isMustTailCall() && |
1846 | "Shouldn't call RemotePreallocated() on a musttail preallocated call" ); |
1847 | // Create copy of call without "preallocated" operand bundle. |
1848 | SmallVector<OperandBundleDef, 1> OpBundles; |
1849 | CB->getOperandBundlesAsDefs(Defs&: OpBundles); |
1850 | CallBase *PreallocatedSetup = nullptr; |
1851 | for (auto *It = OpBundles.begin(); It != OpBundles.end(); ++It) { |
1852 | if (It->getTag() == "preallocated" ) { |
1853 | PreallocatedSetup = cast<CallBase>(Val: *It->input_begin()); |
1854 | OpBundles.erase(CI: It); |
1855 | break; |
1856 | } |
1857 | } |
1858 | assert(PreallocatedSetup && "Did not find preallocated bundle" ); |
1859 | uint64_t ArgCount = |
1860 | cast<ConstantInt>(Val: PreallocatedSetup->getArgOperand(i: 0))->getZExtValue(); |
1861 | |
1862 | assert((isa<CallInst>(CB) || isa<InvokeInst>(CB)) && |
1863 | "Unknown indirect call type" ); |
1864 | CallBase *NewCB = CallBase::Create(CB, Bundles: OpBundles, InsertPt: CB->getIterator()); |
1865 | CB->replaceAllUsesWith(V: NewCB); |
1866 | NewCB->takeName(V: CB); |
1867 | CB->eraseFromParent(); |
1868 | |
1869 | Builder.SetInsertPoint(PreallocatedSetup); |
1870 | auto *StackSave = Builder.CreateStackSave(); |
1871 | Builder.SetInsertPoint(NewCB->getNextNonDebugInstruction()); |
1872 | Builder.CreateStackRestore(Ptr: StackSave); |
1873 | |
1874 | // Replace @llvm.call.preallocated.arg() with alloca. |
1875 | // Cannot modify users() while iterating over it, so make a copy. |
1876 | // @llvm.call.preallocated.arg() can be called with the same index multiple |
1877 | // times. So for each @llvm.call.preallocated.arg(), we see if we have |
1878 | // already created a Value* for the index, and if not, create an alloca and |
1879 | // bitcast right after the @llvm.call.preallocated.setup() so that it |
1880 | // dominates all uses. |
1881 | SmallVector<Value *, 2> ArgAllocas(ArgCount); |
1882 | SmallVector<User *, 2> PreallocatedArgs(PreallocatedSetup->users()); |
1883 | for (auto *User : PreallocatedArgs) { |
1884 | auto *UseCall = cast<CallBase>(Val: User); |
1885 | assert(UseCall->getCalledFunction()->getIntrinsicID() == |
1886 | Intrinsic::call_preallocated_arg && |
1887 | "preallocated token use was not a llvm.call.preallocated.arg" ); |
1888 | uint64_t AllocArgIndex = |
1889 | cast<ConstantInt>(Val: UseCall->getArgOperand(i: 1))->getZExtValue(); |
1890 | Value *AllocaReplacement = ArgAllocas[AllocArgIndex]; |
1891 | if (!AllocaReplacement) { |
1892 | auto AddressSpace = UseCall->getType()->getPointerAddressSpace(); |
1893 | auto *ArgType = |
1894 | UseCall->getFnAttr(Attribute::Preallocated).getValueAsType(); |
1895 | auto *InsertBefore = PreallocatedSetup->getNextNonDebugInstruction(); |
1896 | Builder.SetInsertPoint(InsertBefore); |
1897 | auto *Alloca = |
1898 | Builder.CreateAlloca(ArgType, AddressSpace, nullptr, "paarg" ); |
1899 | ArgAllocas[AllocArgIndex] = Alloca; |
1900 | AllocaReplacement = Alloca; |
1901 | } |
1902 | |
1903 | UseCall->replaceAllUsesWith(V: AllocaReplacement); |
1904 | UseCall->eraseFromParent(); |
1905 | } |
1906 | // Remove @llvm.call.preallocated.setup(). |
1907 | cast<Instruction>(Val: PreallocatedSetup)->eraseFromParent(); |
1908 | } |
1909 | } |
1910 | |
1911 | static bool |
1912 | OptimizeFunctions(Module &M, |
1913 | function_ref<TargetLibraryInfo &(Function &)> GetTLI, |
1914 | function_ref<TargetTransformInfo &(Function &)> GetTTI, |
1915 | function_ref<BlockFrequencyInfo &(Function &)> GetBFI, |
1916 | function_ref<DominatorTree &(Function &)> LookupDomTree, |
1917 | SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats, |
1918 | function_ref<void(Function &F)> ChangedCFGCallback, |
1919 | function_ref<void(Function &F)> DeleteFnCallback) { |
1920 | |
1921 | bool Changed = false; |
1922 | |
1923 | ChangeableCCCacheTy ChangeableCCCache; |
1924 | std::vector<Function *> AllCallsCold; |
1925 | for (Function &F : llvm::make_early_inc_range(Range&: M)) |
1926 | if (hasOnlyColdCalls(F, GetBFI, ChangeableCCCache)) |
1927 | AllCallsCold.push_back(x: &F); |
1928 | |
1929 | // Optimize functions. |
1930 | for (Function &F : llvm::make_early_inc_range(Range&: M)) { |
1931 | // Don't perform global opt pass on naked functions; we don't want fast |
1932 | // calling conventions for naked functions. |
1933 | if (F.hasFnAttribute(Attribute::Naked)) |
1934 | continue; |
1935 | |
1936 | // Functions without names cannot be referenced outside this module. |
1937 | if (!F.hasName() && !F.isDeclaration() && !F.hasLocalLinkage()) |
1938 | F.setLinkage(GlobalValue::InternalLinkage); |
1939 | |
1940 | if (deleteIfDead(GV&: F, NotDiscardableComdats, DeleteFnCallback)) { |
1941 | Changed = true; |
1942 | continue; |
1943 | } |
1944 | |
1945 | // LLVM's definition of dominance allows instructions that are cyclic |
1946 | // in unreachable blocks, e.g.: |
1947 | // %pat = select i1 %condition, @global, i16* %pat |
1948 | // because any instruction dominates an instruction in a block that's |
1949 | // not reachable from entry. |
1950 | // So, remove unreachable blocks from the function, because a) there's |
1951 | // no point in analyzing them and b) GlobalOpt should otherwise grow |
1952 | // some more complicated logic to break these cycles. |
1953 | // Notify the analysis manager that we've modified the function's CFG. |
1954 | if (!F.isDeclaration()) { |
1955 | if (removeUnreachableBlocks(F)) { |
1956 | Changed = true; |
1957 | ChangedCFGCallback(F); |
1958 | } |
1959 | } |
1960 | |
1961 | Changed |= processGlobal(GV&: F, GetTTI, GetTLI, LookupDomTree); |
1962 | |
1963 | if (!F.hasLocalLinkage()) |
1964 | continue; |
1965 | |
1966 | // If we have an inalloca parameter that we can safely remove the |
1967 | // inalloca attribute from, do so. This unlocks optimizations that |
1968 | // wouldn't be safe in the presence of inalloca. |
1969 | // FIXME: We should also hoist alloca affected by this to the entry |
1970 | // block if possible. |
1971 | if (F.getAttributes().hasAttrSomewhere(Attribute::Kind: InAlloca) && |
1972 | !F.hasAddressTaken() && !hasMustTailCallers(F: &F) && !F.isVarArg()) { |
1973 | RemoveAttribute(&F, Attribute::InAlloca); |
1974 | Changed = true; |
1975 | } |
1976 | |
1977 | // FIXME: handle invokes |
1978 | // FIXME: handle musttail |
1979 | if (F.getAttributes().hasAttrSomewhere(Attribute::Kind: Preallocated)) { |
1980 | if (!F.hasAddressTaken() && !hasMustTailCallers(F: &F) && |
1981 | !hasInvokeCallers(F: &F)) { |
1982 | RemovePreallocated(F: &F); |
1983 | Changed = true; |
1984 | } |
1985 | continue; |
1986 | } |
1987 | |
1988 | if (hasChangeableCC(F: &F, ChangeableCCCache)) { |
1989 | NumInternalFunc++; |
1990 | TargetTransformInfo &TTI = GetTTI(F); |
1991 | // Change the calling convention to coldcc if either stress testing is |
1992 | // enabled or the target would like to use coldcc on functions which are |
1993 | // cold at all call sites and the callers contain no other non coldcc |
1994 | // calls. |
1995 | if (EnableColdCCStressTest || |
1996 | (TTI.useColdCCForColdCall(F) && |
1997 | isValidCandidateForColdCC(F, GetBFI, AllCallsCold))) { |
1998 | ChangeableCCCache.erase(Val: &F); |
1999 | F.setCallingConv(CallingConv::Cold); |
2000 | changeCallSitesToColdCC(F: &F); |
2001 | Changed = true; |
2002 | NumColdCC++; |
2003 | } |
2004 | } |
2005 | |
2006 | if (hasChangeableCC(F: &F, ChangeableCCCache)) { |
2007 | // If this function has a calling convention worth changing, is not a |
2008 | // varargs function, and is only called directly, promote it to use the |
2009 | // Fast calling convention. |
2010 | F.setCallingConv(CallingConv::Fast); |
2011 | ChangeCalleesToFastCall(F: &F); |
2012 | ++NumFastCallFns; |
2013 | Changed = true; |
2014 | } |
2015 | |
2016 | if (F.getAttributes().hasAttrSomewhere(Attribute::Kind: Nest) && |
2017 | !F.hasAddressTaken()) { |
2018 | // The function is not used by a trampoline intrinsic, so it is safe |
2019 | // to remove the 'nest' attribute. |
2020 | RemoveAttribute(&F, Attribute::Nest); |
2021 | ++NumNestRemoved; |
2022 | Changed = true; |
2023 | } |
2024 | } |
2025 | return Changed; |
2026 | } |
2027 | |
2028 | static bool |
2029 | OptimizeGlobalVars(Module &M, |
2030 | function_ref<TargetTransformInfo &(Function &)> GetTTI, |
2031 | function_ref<TargetLibraryInfo &(Function &)> GetTLI, |
2032 | function_ref<DominatorTree &(Function &)> LookupDomTree, |
2033 | SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { |
2034 | bool Changed = false; |
2035 | |
2036 | for (GlobalVariable &GV : llvm::make_early_inc_range(Range: M.globals())) { |
2037 | // Global variables without names cannot be referenced outside this module. |
2038 | if (!GV.hasName() && !GV.isDeclaration() && !GV.hasLocalLinkage()) |
2039 | GV.setLinkage(GlobalValue::InternalLinkage); |
2040 | // Simplify the initializer. |
2041 | if (GV.hasInitializer()) |
2042 | if (auto *C = dyn_cast<Constant>(Val: GV.getInitializer())) { |
2043 | auto &DL = M.getDataLayout(); |
2044 | // TLI is not used in the case of a Constant, so use default nullptr |
2045 | // for that optional parameter, since we don't have a Function to |
2046 | // provide GetTLI anyway. |
2047 | Constant *New = ConstantFoldConstant(C, DL, /*TLI*/ nullptr); |
2048 | if (New != C) |
2049 | GV.setInitializer(New); |
2050 | } |
2051 | |
2052 | if (deleteIfDead(GV, NotDiscardableComdats)) { |
2053 | Changed = true; |
2054 | continue; |
2055 | } |
2056 | |
2057 | Changed |= processGlobal(GV, GetTTI, GetTLI, LookupDomTree); |
2058 | } |
2059 | return Changed; |
2060 | } |
2061 | |
2062 | /// Evaluate static constructors in the function, if we can. Return true if we |
2063 | /// can, false otherwise. |
2064 | static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL, |
2065 | TargetLibraryInfo *TLI) { |
2066 | // Skip external functions. |
2067 | if (F->isDeclaration()) |
2068 | return false; |
2069 | // Call the function. |
2070 | Evaluator Eval(DL, TLI); |
2071 | Constant *RetValDummy; |
2072 | bool EvalSuccess = Eval.EvaluateFunction(F, RetVal&: RetValDummy, |
2073 | ActualArgs: SmallVector<Constant*, 0>()); |
2074 | |
2075 | if (EvalSuccess) { |
2076 | ++NumCtorsEvaluated; |
2077 | |
2078 | // We succeeded at evaluation: commit the result. |
2079 | auto NewInitializers = Eval.getMutatedInitializers(); |
2080 | LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" |
2081 | << F->getName() << "' to " << NewInitializers.size() |
2082 | << " stores.\n" ); |
2083 | for (const auto &Pair : NewInitializers) |
2084 | Pair.first->setInitializer(Pair.second); |
2085 | for (GlobalVariable *GV : Eval.getInvariants()) |
2086 | GV->setConstant(true); |
2087 | } |
2088 | |
2089 | return EvalSuccess; |
2090 | } |
2091 | |
2092 | static int compareNames(Constant *const *A, Constant *const *B) { |
2093 | Value *AStripped = (*A)->stripPointerCasts(); |
2094 | Value *BStripped = (*B)->stripPointerCasts(); |
2095 | return AStripped->getName().compare(RHS: BStripped->getName()); |
2096 | } |
2097 | |
2098 | static void setUsedInitializer(GlobalVariable &V, |
2099 | const SmallPtrSetImpl<GlobalValue *> &Init) { |
2100 | if (Init.empty()) { |
2101 | V.eraseFromParent(); |
2102 | return; |
2103 | } |
2104 | |
2105 | // Get address space of pointers in the array of pointers. |
2106 | const Type *UsedArrayType = V.getValueType(); |
2107 | const auto *VAT = cast<ArrayType>(Val: UsedArrayType); |
2108 | const auto *VEPT = cast<PointerType>(Val: VAT->getArrayElementType()); |
2109 | |
2110 | // Type of pointer to the array of pointers. |
2111 | PointerType *PtrTy = |
2112 | PointerType::get(C&: V.getContext(), AddressSpace: VEPT->getAddressSpace()); |
2113 | |
2114 | SmallVector<Constant *, 8> UsedArray; |
2115 | for (GlobalValue *GV : Init) { |
2116 | Constant *Cast = ConstantExpr::getPointerBitCastOrAddrSpaceCast(C: GV, Ty: PtrTy); |
2117 | UsedArray.push_back(Elt: Cast); |
2118 | } |
2119 | |
2120 | // Sort to get deterministic order. |
2121 | array_pod_sort(Start: UsedArray.begin(), End: UsedArray.end(), Compare: compareNames); |
2122 | ArrayType *ATy = ArrayType::get(ElementType: PtrTy, NumElements: UsedArray.size()); |
2123 | |
2124 | Module *M = V.getParent(); |
2125 | V.removeFromParent(); |
2126 | GlobalVariable *NV = |
2127 | new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage, |
2128 | ConstantArray::get(T: ATy, V: UsedArray), "" ); |
2129 | NV->takeName(V: &V); |
2130 | NV->setSection("llvm.metadata" ); |
2131 | delete &V; |
2132 | } |
2133 | |
2134 | namespace { |
2135 | |
2136 | /// An easy to access representation of llvm.used and llvm.compiler.used. |
2137 | class LLVMUsed { |
2138 | SmallPtrSet<GlobalValue *, 4> Used; |
2139 | SmallPtrSet<GlobalValue *, 4> CompilerUsed; |
2140 | GlobalVariable *UsedV; |
2141 | GlobalVariable *CompilerUsedV; |
2142 | |
2143 | public: |
2144 | LLVMUsed(Module &M) { |
2145 | SmallVector<GlobalValue *, 4> Vec; |
2146 | UsedV = collectUsedGlobalVariables(M, Vec, CompilerUsed: false); |
2147 | Used = {Vec.begin(), Vec.end()}; |
2148 | Vec.clear(); |
2149 | CompilerUsedV = collectUsedGlobalVariables(M, Vec, CompilerUsed: true); |
2150 | CompilerUsed = {Vec.begin(), Vec.end()}; |
2151 | } |
2152 | |
2153 | using iterator = SmallPtrSet<GlobalValue *, 4>::iterator; |
2154 | using used_iterator_range = iterator_range<iterator>; |
2155 | |
2156 | iterator usedBegin() { return Used.begin(); } |
2157 | iterator usedEnd() { return Used.end(); } |
2158 | |
2159 | used_iterator_range used() { |
2160 | return used_iterator_range(usedBegin(), usedEnd()); |
2161 | } |
2162 | |
2163 | iterator compilerUsedBegin() { return CompilerUsed.begin(); } |
2164 | iterator compilerUsedEnd() { return CompilerUsed.end(); } |
2165 | |
2166 | used_iterator_range compilerUsed() { |
2167 | return used_iterator_range(compilerUsedBegin(), compilerUsedEnd()); |
2168 | } |
2169 | |
2170 | bool usedCount(GlobalValue *GV) const { return Used.count(Ptr: GV); } |
2171 | |
2172 | bool compilerUsedCount(GlobalValue *GV) const { |
2173 | return CompilerUsed.count(Ptr: GV); |
2174 | } |
2175 | |
2176 | bool usedErase(GlobalValue *GV) { return Used.erase(Ptr: GV); } |
2177 | bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(Ptr: GV); } |
2178 | bool usedInsert(GlobalValue *GV) { return Used.insert(Ptr: GV).second; } |
2179 | |
2180 | bool compilerUsedInsert(GlobalValue *GV) { |
2181 | return CompilerUsed.insert(Ptr: GV).second; |
2182 | } |
2183 | |
2184 | void syncVariablesAndSets() { |
2185 | if (UsedV) |
2186 | setUsedInitializer(V&: *UsedV, Init: Used); |
2187 | if (CompilerUsedV) |
2188 | setUsedInitializer(V&: *CompilerUsedV, Init: CompilerUsed); |
2189 | } |
2190 | }; |
2191 | |
2192 | } // end anonymous namespace |
2193 | |
2194 | static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) { |
2195 | if (GA.use_empty()) // No use at all. |
2196 | return false; |
2197 | |
2198 | assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && |
2199 | "We should have removed the duplicated " |
2200 | "element from llvm.compiler.used" ); |
2201 | if (!GA.hasOneUse()) |
2202 | // Strictly more than one use. So at least one is not in llvm.used and |
2203 | // llvm.compiler.used. |
2204 | return true; |
2205 | |
2206 | // Exactly one use. Check if it is in llvm.used or llvm.compiler.used. |
2207 | return !U.usedCount(GV: &GA) && !U.compilerUsedCount(GV: &GA); |
2208 | } |
2209 | |
2210 | static bool mayHaveOtherReferences(GlobalValue &GV, const LLVMUsed &U) { |
2211 | if (!GV.hasLocalLinkage()) |
2212 | return true; |
2213 | |
2214 | return U.usedCount(GV: &GV) || U.compilerUsedCount(GV: &GV); |
2215 | } |
2216 | |
2217 | static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U, |
2218 | bool &RenameTarget) { |
2219 | RenameTarget = false; |
2220 | bool Ret = false; |
2221 | if (hasUseOtherThanLLVMUsed(GA, U)) |
2222 | Ret = true; |
2223 | |
2224 | // If the alias is externally visible, we may still be able to simplify it. |
2225 | if (!mayHaveOtherReferences(GV&: GA, U)) |
2226 | return Ret; |
2227 | |
2228 | // If the aliasee has internal linkage and no other references (e.g., |
2229 | // @llvm.used, @llvm.compiler.used), give it the name and linkage of the |
2230 | // alias, and delete the alias. This turns: |
2231 | // define internal ... @f(...) |
2232 | // @a = alias ... @f |
2233 | // into: |
2234 | // define ... @a(...) |
2235 | Constant *Aliasee = GA.getAliasee(); |
2236 | GlobalValue *Target = cast<GlobalValue>(Val: Aliasee->stripPointerCasts()); |
2237 | if (mayHaveOtherReferences(GV&: *Target, U)) |
2238 | return Ret; |
2239 | |
2240 | RenameTarget = true; |
2241 | return true; |
2242 | } |
2243 | |
2244 | static bool |
2245 | OptimizeGlobalAliases(Module &M, |
2246 | SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { |
2247 | bool Changed = false; |
2248 | LLVMUsed Used(M); |
2249 | |
2250 | for (GlobalValue *GV : Used.used()) |
2251 | Used.compilerUsedErase(GV); |
2252 | |
2253 | // Return whether GV is explicitly or implicitly dso_local and not replaceable |
2254 | // by another definition in the current linkage unit. |
2255 | auto IsModuleLocal = [](GlobalValue &GV) { |
2256 | return !GlobalValue::isInterposableLinkage(Linkage: GV.getLinkage()) && |
2257 | (GV.isDSOLocal() || GV.isImplicitDSOLocal()); |
2258 | }; |
2259 | |
2260 | for (GlobalAlias &J : llvm::make_early_inc_range(Range: M.aliases())) { |
2261 | // Aliases without names cannot be referenced outside this module. |
2262 | if (!J.hasName() && !J.isDeclaration() && !J.hasLocalLinkage()) |
2263 | J.setLinkage(GlobalValue::InternalLinkage); |
2264 | |
2265 | if (deleteIfDead(GV&: J, NotDiscardableComdats)) { |
2266 | Changed = true; |
2267 | continue; |
2268 | } |
2269 | |
2270 | // If the alias can change at link time, nothing can be done - bail out. |
2271 | if (!IsModuleLocal(J)) |
2272 | continue; |
2273 | |
2274 | Constant *Aliasee = J.getAliasee(); |
2275 | GlobalValue *Target = dyn_cast<GlobalValue>(Val: Aliasee->stripPointerCasts()); |
2276 | // We can't trivially replace the alias with the aliasee if the aliasee is |
2277 | // non-trivial in some way. We also can't replace the alias with the aliasee |
2278 | // if the aliasee may be preemptible at runtime. On ELF, a non-preemptible |
2279 | // alias can be used to access the definition as if preemption did not |
2280 | // happen. |
2281 | // TODO: Try to handle non-zero GEPs of local aliasees. |
2282 | if (!Target || !IsModuleLocal(*Target)) |
2283 | continue; |
2284 | |
2285 | Target->removeDeadConstantUsers(); |
2286 | |
2287 | // Make all users of the alias use the aliasee instead. |
2288 | bool RenameTarget; |
2289 | if (!hasUsesToReplace(GA&: J, U: Used, RenameTarget)) |
2290 | continue; |
2291 | |
2292 | J.replaceAllUsesWith(V: Aliasee); |
2293 | ++NumAliasesResolved; |
2294 | Changed = true; |
2295 | |
2296 | if (RenameTarget) { |
2297 | // Give the aliasee the name, linkage and other attributes of the alias. |
2298 | Target->takeName(V: &J); |
2299 | Target->setLinkage(J.getLinkage()); |
2300 | Target->setDSOLocal(J.isDSOLocal()); |
2301 | Target->setVisibility(J.getVisibility()); |
2302 | Target->setDLLStorageClass(J.getDLLStorageClass()); |
2303 | |
2304 | if (Used.usedErase(GV: &J)) |
2305 | Used.usedInsert(GV: Target); |
2306 | |
2307 | if (Used.compilerUsedErase(GV: &J)) |
2308 | Used.compilerUsedInsert(GV: Target); |
2309 | } else if (mayHaveOtherReferences(GV&: J, U: Used)) |
2310 | continue; |
2311 | |
2312 | // Delete the alias. |
2313 | M.eraseAlias(Alias: &J); |
2314 | ++NumAliasesRemoved; |
2315 | Changed = true; |
2316 | } |
2317 | |
2318 | Used.syncVariablesAndSets(); |
2319 | |
2320 | return Changed; |
2321 | } |
2322 | |
2323 | static Function * |
2324 | FindCXAAtExit(Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) { |
2325 | // Hack to get a default TLI before we have actual Function. |
2326 | auto FuncIter = M.begin(); |
2327 | if (FuncIter == M.end()) |
2328 | return nullptr; |
2329 | auto *TLI = &GetTLI(*FuncIter); |
2330 | |
2331 | LibFunc F = LibFunc_cxa_atexit; |
2332 | if (!TLI->has(F)) |
2333 | return nullptr; |
2334 | |
2335 | Function *Fn = M.getFunction(Name: TLI->getName(F)); |
2336 | if (!Fn) |
2337 | return nullptr; |
2338 | |
2339 | // Now get the actual TLI for Fn. |
2340 | TLI = &GetTLI(*Fn); |
2341 | |
2342 | // Make sure that the function has the correct prototype. |
2343 | if (!TLI->getLibFunc(FDecl: *Fn, F) || F != LibFunc_cxa_atexit) |
2344 | return nullptr; |
2345 | |
2346 | return Fn; |
2347 | } |
2348 | |
2349 | /// Returns whether the given function is an empty C++ destructor and can |
2350 | /// therefore be eliminated. |
2351 | /// Note that we assume that other optimization passes have already simplified |
2352 | /// the code so we simply check for 'ret'. |
2353 | static bool cxxDtorIsEmpty(const Function &Fn) { |
2354 | // FIXME: We could eliminate C++ destructors if they're readonly/readnone and |
2355 | // nounwind, but that doesn't seem worth doing. |
2356 | if (Fn.isDeclaration()) |
2357 | return false; |
2358 | |
2359 | for (const auto &I : Fn.getEntryBlock()) { |
2360 | if (I.isDebugOrPseudoInst()) |
2361 | continue; |
2362 | if (isa<ReturnInst>(Val: I)) |
2363 | return true; |
2364 | break; |
2365 | } |
2366 | return false; |
2367 | } |
2368 | |
2369 | static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) { |
2370 | /// Itanium C++ ABI p3.3.5: |
2371 | /// |
2372 | /// After constructing a global (or local static) object, that will require |
2373 | /// destruction on exit, a termination function is registered as follows: |
2374 | /// |
2375 | /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d ); |
2376 | /// |
2377 | /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the |
2378 | /// call f(p) when DSO d is unloaded, before all such termination calls |
2379 | /// registered before this one. It returns zero if registration is |
2380 | /// successful, nonzero on failure. |
2381 | |
2382 | // This pass will look for calls to __cxa_atexit where the function is trivial |
2383 | // and remove them. |
2384 | bool Changed = false; |
2385 | |
2386 | for (User *U : llvm::make_early_inc_range(Range: CXAAtExitFn->users())) { |
2387 | // We're only interested in calls. Theoretically, we could handle invoke |
2388 | // instructions as well, but neither llvm-gcc nor clang generate invokes |
2389 | // to __cxa_atexit. |
2390 | CallInst *CI = dyn_cast<CallInst>(Val: U); |
2391 | if (!CI) |
2392 | continue; |
2393 | |
2394 | Function *DtorFn = |
2395 | dyn_cast<Function>(Val: CI->getArgOperand(i: 0)->stripPointerCasts()); |
2396 | if (!DtorFn || !cxxDtorIsEmpty(Fn: *DtorFn)) |
2397 | continue; |
2398 | |
2399 | // Just remove the call. |
2400 | CI->replaceAllUsesWith(V: Constant::getNullValue(Ty: CI->getType())); |
2401 | CI->eraseFromParent(); |
2402 | |
2403 | ++NumCXXDtorsRemoved; |
2404 | |
2405 | Changed |= true; |
2406 | } |
2407 | |
2408 | return Changed; |
2409 | } |
2410 | |
2411 | static Function *hasSideeffectFreeStaticResolution(GlobalIFunc &IF) { |
2412 | if (IF.isInterposable()) |
2413 | return nullptr; |
2414 | |
2415 | Function *Resolver = IF.getResolverFunction(); |
2416 | if (!Resolver) |
2417 | return nullptr; |
2418 | |
2419 | if (Resolver->isInterposable()) |
2420 | return nullptr; |
2421 | |
2422 | // Only handle functions that have been optimized into a single basic block. |
2423 | auto It = Resolver->begin(); |
2424 | if (++It != Resolver->end()) |
2425 | return nullptr; |
2426 | |
2427 | BasicBlock &BB = Resolver->getEntryBlock(); |
2428 | |
2429 | if (any_of(Range&: BB, P: [](Instruction &I) { return I.mayHaveSideEffects(); })) |
2430 | return nullptr; |
2431 | |
2432 | auto *Ret = dyn_cast<ReturnInst>(Val: BB.getTerminator()); |
2433 | if (!Ret) |
2434 | return nullptr; |
2435 | |
2436 | return dyn_cast<Function>(Val: Ret->getReturnValue()); |
2437 | } |
2438 | |
2439 | /// Find IFuncs that have resolvers that always point at the same statically |
2440 | /// known callee, and replace their callers with a direct call. |
2441 | static bool OptimizeStaticIFuncs(Module &M) { |
2442 | bool Changed = false; |
2443 | for (GlobalIFunc &IF : M.ifuncs()) |
2444 | if (Function *Callee = hasSideeffectFreeStaticResolution(IF)) |
2445 | if (!IF.use_empty()) { |
2446 | IF.replaceAllUsesWith(V: Callee); |
2447 | NumIFuncsResolved++; |
2448 | Changed = true; |
2449 | } |
2450 | return Changed; |
2451 | } |
2452 | |
2453 | static bool |
2454 | DeleteDeadIFuncs(Module &M, |
2455 | SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) { |
2456 | bool Changed = false; |
2457 | for (GlobalIFunc &IF : make_early_inc_range(Range: M.ifuncs())) |
2458 | if (deleteIfDead(GV&: IF, NotDiscardableComdats)) { |
2459 | NumIFuncsDeleted++; |
2460 | Changed = true; |
2461 | } |
2462 | return Changed; |
2463 | } |
2464 | |
2465 | static bool |
2466 | optimizeGlobalsInModule(Module &M, const DataLayout &DL, |
2467 | function_ref<TargetLibraryInfo &(Function &)> GetTLI, |
2468 | function_ref<TargetTransformInfo &(Function &)> GetTTI, |
2469 | function_ref<BlockFrequencyInfo &(Function &)> GetBFI, |
2470 | function_ref<DominatorTree &(Function &)> LookupDomTree, |
2471 | function_ref<void(Function &F)> ChangedCFGCallback, |
2472 | function_ref<void(Function &F)> DeleteFnCallback) { |
2473 | SmallPtrSet<const Comdat *, 8> NotDiscardableComdats; |
2474 | bool Changed = false; |
2475 | bool LocalChange = true; |
2476 | std::optional<uint32_t> FirstNotFullyEvaluatedPriority; |
2477 | |
2478 | while (LocalChange) { |
2479 | LocalChange = false; |
2480 | |
2481 | NotDiscardableComdats.clear(); |
2482 | for (const GlobalVariable &GV : M.globals()) |
2483 | if (const Comdat *C = GV.getComdat()) |
2484 | if (!GV.isDiscardableIfUnused() || !GV.use_empty()) |
2485 | NotDiscardableComdats.insert(Ptr: C); |
2486 | for (Function &F : M) |
2487 | if (const Comdat *C = F.getComdat()) |
2488 | if (!F.isDefTriviallyDead()) |
2489 | NotDiscardableComdats.insert(Ptr: C); |
2490 | for (GlobalAlias &GA : M.aliases()) |
2491 | if (const Comdat *C = GA.getComdat()) |
2492 | if (!GA.isDiscardableIfUnused() || !GA.use_empty()) |
2493 | NotDiscardableComdats.insert(Ptr: C); |
2494 | |
2495 | // Delete functions that are trivially dead, ccc -> fastcc |
2496 | LocalChange |= OptimizeFunctions(M, GetTLI, GetTTI, GetBFI, LookupDomTree, |
2497 | NotDiscardableComdats, ChangedCFGCallback, |
2498 | DeleteFnCallback); |
2499 | |
2500 | // Optimize global_ctors list. |
2501 | LocalChange |= |
2502 | optimizeGlobalCtorsList(M, ShouldRemove: [&](uint32_t Priority, Function *F) { |
2503 | if (FirstNotFullyEvaluatedPriority && |
2504 | *FirstNotFullyEvaluatedPriority != Priority) |
2505 | return false; |
2506 | bool Evaluated = EvaluateStaticConstructor(F, DL, TLI: &GetTLI(*F)); |
2507 | if (!Evaluated) |
2508 | FirstNotFullyEvaluatedPriority = Priority; |
2509 | return Evaluated; |
2510 | }); |
2511 | |
2512 | // Optimize non-address-taken globals. |
2513 | LocalChange |= OptimizeGlobalVars(M, GetTTI, GetTLI, LookupDomTree, |
2514 | NotDiscardableComdats); |
2515 | |
2516 | // Resolve aliases, when possible. |
2517 | LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats); |
2518 | |
2519 | // Try to remove trivial global destructors if they are not removed |
2520 | // already. |
2521 | Function *CXAAtExitFn = FindCXAAtExit(M, GetTLI); |
2522 | if (CXAAtExitFn) |
2523 | LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); |
2524 | |
2525 | // Optimize IFuncs whose callee's are statically known. |
2526 | LocalChange |= OptimizeStaticIFuncs(M); |
2527 | |
2528 | // Remove any IFuncs that are now dead. |
2529 | LocalChange |= DeleteDeadIFuncs(M, NotDiscardableComdats); |
2530 | |
2531 | Changed |= LocalChange; |
2532 | } |
2533 | |
2534 | // TODO: Move all global ctors functions to the end of the module for code |
2535 | // layout. |
2536 | |
2537 | return Changed; |
2538 | } |
2539 | |
2540 | PreservedAnalyses GlobalOptPass::run(Module &M, ModuleAnalysisManager &AM) { |
2541 | auto &DL = M.getDataLayout(); |
2542 | auto &FAM = |
2543 | AM.getResult<FunctionAnalysisManagerModuleProxy>(IR&: M).getManager(); |
2544 | auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{ |
2545 | return FAM.getResult<DominatorTreeAnalysis>(IR&: F); |
2546 | }; |
2547 | auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { |
2548 | return FAM.getResult<TargetLibraryAnalysis>(IR&: F); |
2549 | }; |
2550 | auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & { |
2551 | return FAM.getResult<TargetIRAnalysis>(IR&: F); |
2552 | }; |
2553 | |
2554 | auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & { |
2555 | return FAM.getResult<BlockFrequencyAnalysis>(IR&: F); |
2556 | }; |
2557 | auto ChangedCFGCallback = [&FAM](Function &F) { |
2558 | FAM.invalidate(IR&: F, PA: PreservedAnalyses::none()); |
2559 | }; |
2560 | auto DeleteFnCallback = [&FAM](Function &F) { FAM.clear(IR&: F, Name: F.getName()); }; |
2561 | |
2562 | if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree, |
2563 | ChangedCFGCallback, DeleteFnCallback)) |
2564 | return PreservedAnalyses::all(); |
2565 | |
2566 | PreservedAnalyses PA = PreservedAnalyses::none(); |
2567 | // We made sure to clear analyses for deleted functions. |
2568 | PA.preserve<FunctionAnalysisManagerModuleProxy>(); |
2569 | // The only place we modify the CFG is when calling |
2570 | // removeUnreachableBlocks(), but there we make sure to invalidate analyses |
2571 | // for modified functions. |
2572 | PA.preserveSet<CFGAnalyses>(); |
2573 | return PA; |
2574 | } |
2575 | |