Lines Matching +full:all +full:- +full:inputs
1 //===- GlobalsModRef.cpp - Simple Mod/Ref Analysis for Globals ------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
14 //===----------------------------------------------------------------------===//
34 #define DEBUG_TYPE "globalsmodref-aa"
44 // When enabled, GlobalsModRef will provide no-alias results which in extremely
51 // re-enable them for users of LLVM that have a particular performance
55 "enable-unsafe-globalsmodref-alias-results", cl::init(false), cl::Hidden);
66 /// Build a wrapper struct that has 8-byte alignment. All heap allocations
107 // pointer-int pair.
160 auto I = P->Map.find(&GV); in getModRefInfoForGlobal()
161 if (I != P->Map.end()) in getModRefInfoForGlobal()
162 GlobalMRI |= I->second; in getModRefInfoForGlobal()
176 for (const auto &G : P->Map) in addFunctionInfo()
186 auto &GlobalMRI = P->Map[&GV]; in addModRefInfoForGlobal()
194 P->Map.erase(&GV); in eraseModRefInfoForGlobal()
198 /// All of the information is encoded into a single pointer, with a three bit
201 /// the pointer, when non-null, points to a map from GlobalValue to
209 GAR->FunctionInfos.erase(F); in deleted()
212 if (GAR->NonAddressTakenGlobals.erase(GV)) { in deleted()
215 if (GAR->IndirectGlobals.erase(GV)) { in deleted()
217 for (auto I = GAR->AllocsForIndirectGlobals.begin(), in deleted()
218 E = GAR->AllocsForIndirectGlobals.end(); in deleted()
220 if (I->second == GV) in deleted()
221 GAR->AllocsForIndirectGlobals.erase(I); in deleted()
225 // from all of them. in deleted()
226 for (auto &FIPair : GAR->FunctionInfos) in deleted()
232 GAR->AllocsForIndirectGlobals.erase(V); in deleted()
236 GAR->Handles.erase(I); in deleted()
242 return MemoryEffects(FI->getModRefInfo()); in getMemoryEffects()
253 return &I->second; in getFunctionInfo()
257 /// AnalyzeGlobals - Scan through the users of all of the internal
305 if (GV.getValueType()->isPointerTy() && in AnalyzeGlobals()
314 /// AnalyzeUsesOfPointer - Look at all of the users of the specified pointer.
319 /// If OkayStoreDest is non-null, stores into this global are allowed.
324 if (!V->getType()->isPointerTy()) in AnalyzeUsesOfPointer()
327 for (Use &U : V->uses()) { in AnalyzeUsesOfPointer()
331 Readers->insert(LI->getParent()->getParent()); in AnalyzeUsesOfPointer()
333 if (V == SI->getOperand(1)) { in AnalyzeUsesOfPointer()
335 Writers->insert(SI->getParent()->getParent()); in AnalyzeUsesOfPointer()
336 } else if (SI->getOperand(1) != OkayStoreDest) { in AnalyzeUsesOfPointer()
348 if (II->getIntrinsicID() == Intrinsic::threadlocal_address && in AnalyzeUsesOfPointer()
349 V == II->getArgOperand(0)) { in AnalyzeUsesOfPointer()
357 if (Call->isDataOperand(&U)) { in AnalyzeUsesOfPointer()
359 if (Call->isArgOperand(&U) && in AnalyzeUsesOfPointer()
360 getFreedOperand(Call, &GetTLI(*Call->getFunction())) == U) { in AnalyzeUsesOfPointer()
362 Writers->insert(Call->getParent()->getParent()); in AnalyzeUsesOfPointer()
367 auto *F = Call->getCalledFunction(); in AnalyzeUsesOfPointer()
370 // and collect the mod-ref effects. This information will in AnalyzeUsesOfPointer()
372 if (!F || !F->isDeclaration()) in AnalyzeUsesOfPointer()
378 if (!Call->hasFnAttr(Attribute::NoCallback) || in AnalyzeUsesOfPointer()
379 !Call->isArgOperand(&U) || in AnalyzeUsesOfPointer()
380 !Call->doesNotCapture(Call->getArgOperandNo(&U))) in AnalyzeUsesOfPointer()
386 Readers->insert(Call->getParent()->getParent()); in AnalyzeUsesOfPointer()
388 Writers->insert(Call->getParent()->getParent()); in AnalyzeUsesOfPointer()
392 if (!isa<ConstantPointerNull>(ICI->getOperand(1))) in AnalyzeUsesOfPointer()
396 if (isa<GlobalValue>(C) || C->isConstantUsed()) in AnalyzeUsesOfPointer()
406 /// AnalyzeIndirectGlobalMemory - We found an non-address-taken global variable
407 /// which holds a pointer type. See if the global always points to non-aliased
408 /// heap memory: that is, all initializers of the globals store a value known
410 /// Further, all loads out of GV must directly use the memory, not store the
419 if (Constant *C = GV->getInitializer()) in AnalyzeIndirectGlobalMemory()
420 if (!C->isNullValue()) in AnalyzeIndirectGlobalMemory()
425 for (User *U : GV->users()) { in AnalyzeIndirectGlobalMemory()
435 if (SI->getOperand(0) == GV) in AnalyzeIndirectGlobalMemory()
439 if (isa<ConstantPointerNull>(SI->getOperand(0))) in AnalyzeIndirectGlobalMemory()
443 Value *Ptr = getUnderlyingObject(SI->getOperand(0)); in AnalyzeIndirectGlobalMemory()
448 // Analyze all uses of the allocation. If any of them are used in a in AnalyzeIndirectGlobalMemory()
449 // non-simple way (e.g. stored to another global) bail out. in AnalyzeIndirectGlobalMemory()
462 // Okay, this is an indirect global. Remember all of the allocations for in AnalyzeIndirectGlobalMemory()
477 // We do a bottom-up SCC traversal of the call graph. In other words, we in CollectSCCMembership()
478 // visit all callees before callers (leaf-first). in CollectSCCMembership()
485 if (Function *F = CGN->getFunction()) in CollectSCCMembership()
491 /// AnalyzeCallGraph - At this point, we know the functions where globals are
493 /// graph to all callers and compute the mod/ref info for all memory for each
496 // We do a bottom-up SCC traversal of the call graph. In other words, we in AnalyzeCallGraph()
497 // visit all callees before callers (leaf-first). in AnalyzeCallGraph()
502 Function *F = SCC[0]->getFunction(); in AnalyzeCallGraph()
504 if (!F || !F->isDefinitionExact()) { in AnalyzeCallGraph()
505 // Calls externally or not exact - can't say anything useful. Remove any in AnalyzeCallGraph()
509 FunctionInfos.erase(Node->getFunction()); in AnalyzeCallGraph()
531 // one mod-ref set. in AnalyzeCallGraph()
538 if (F->isDeclaration() || F->hasOptNone()) { in AnalyzeCallGraph()
540 if (F->doesNotAccessMemory()) { in AnalyzeCallGraph()
542 } else if (F->onlyReadsMemory()) { in AnalyzeCallGraph()
544 if (!F->onlyAccessesArgMemory() && MaySyncOrCallIntoModule(*F)) in AnalyzeCallGraph()
545 // This function might call back into the module and read a global - in AnalyzeCallGraph()
550 if (!F->onlyAccessesArgMemory()) in AnalyzeCallGraph()
560 for (CallGraphNode::iterator CI = SCC[i]->begin(), E = SCC[i]->end(); in AnalyzeCallGraph()
562 if (Function *Callee = CI->second->getFunction()) { in AnalyzeCallGraph()
578 // If we can't say anything useful about this SCC, remove all SCC functions in AnalyzeCallGraph()
582 FunctionInfos.erase(Node->getFunction()); in AnalyzeCallGraph()
594 if (Node->getFunction()->hasOptNone()) in AnalyzeCallGraph()
597 for (Instruction &I : instructions(Node->getFunction())) { in AnalyzeCallGraph()
601 // We handle calls specially because the graph-relevant aspects are in AnalyzeCallGraph()
606 // All non-call instructions we use the primary predicates for whether in AnalyzeCallGraph()
623 // get invalidated if DenseMap decides to re-hash. in AnalyzeCallGraph()
626 FunctionInfos[SCC[i]->getFunction()] = CachedFI; in AnalyzeCallGraph()
630 // GV is a non-escaping global. V is a pointer address that has been loaded from.
638 SmallVector<const Value *, 8> Inputs; in isNonEscapingGlobalNoAliasWithLoad() local
640 Inputs.push_back(V); in isNonEscapingGlobalNoAliasWithLoad()
642 const Value *Input = Inputs.pop_back_val(); in isNonEscapingGlobalNoAliasWithLoad()
648 // non-addr-taken globals. in isNonEscapingGlobalNoAliasWithLoad()
650 // (Transitive) loads from a global are also safe - if this aliased in isNonEscapingGlobalNoAliasWithLoad()
662 Inputs.push_back(getUnderlyingObject(LI->getPointerOperand())); in isNonEscapingGlobalNoAliasWithLoad()
666 const Value *LHS = getUnderlyingObject(SI->getTrueValue()); in isNonEscapingGlobalNoAliasWithLoad()
667 const Value *RHS = getUnderlyingObject(SI->getFalseValue()); in isNonEscapingGlobalNoAliasWithLoad()
669 Inputs.push_back(LHS); in isNonEscapingGlobalNoAliasWithLoad()
671 Inputs.push_back(RHS); in isNonEscapingGlobalNoAliasWithLoad()
675 for (const Value *Op : PN->incoming_values()) { in isNonEscapingGlobalNoAliasWithLoad()
678 Inputs.push_back(Op); in isNonEscapingGlobalNoAliasWithLoad()
684 } while (!Inputs.empty()); in isNonEscapingGlobalNoAliasWithLoad()
686 // All inputs were known to be no-alias. in isNonEscapingGlobalNoAliasWithLoad()
690 // There are particular cases where we can conclude no-alias between
691 // a non-addr-taken global and some other underlying object. Specifically,
692 // a non-addr-taken global is known to not be escaped from any function. It is
697 // function is never safe. If the observation is made through non-atomic
698 // operations on different threads, it is a data-race and UB. If the
713 // active, or to be forced to operate as a module pass that cannot co-exist
718 // non-addr-taken global, we must know that it would have to be an escape. in isNonEscapingGlobalNoAlias()
721 // recurse through PHI nodes and select nodes provided all of their inputs in isNonEscapingGlobalNoAlias()
722 // resolve to one of these known-escaping roots. in isNonEscapingGlobalNoAlias()
724 SmallVector<const Value *, 8> Inputs; in isNonEscapingGlobalNoAlias() local
726 Inputs.push_back(V); in isNonEscapingGlobalNoAlias()
729 const Value *Input = Inputs.pop_back_val(); in isNonEscapingGlobalNoAlias()
733 // conclude no-alias. in isNonEscapingGlobalNoAlias()
737 // Distinct GlobalVariables never alias, unless overriden or zero-sized. in isNonEscapingGlobalNoAlias()
742 !GVar->isDeclaration() && !InputGVar->isDeclaration() && in isNonEscapingGlobalNoAlias()
743 !GVar->isInterposable() && !InputGVar->isInterposable()) { in isNonEscapingGlobalNoAlias()
744 Type *GVType = GVar->getInitializer()->getType(); in isNonEscapingGlobalNoAlias()
745 Type *InputGVType = InputGVar->getInitializer()->getType(); in isNonEscapingGlobalNoAlias()
746 if (GVType->isSized() && InputGVType->isSized() && in isNonEscapingGlobalNoAlias()
761 // non-addr-taken globals. in isNonEscapingGlobalNoAlias()
774 // that the global is non-escaping, so no alias. in isNonEscapingGlobalNoAlias()
775 const Value *Ptr = getUnderlyingObject(LI->getPointerOperand()); in isNonEscapingGlobalNoAlias()
783 const Value *LHS = getUnderlyingObject(SI->getTrueValue()); in isNonEscapingGlobalNoAlias()
784 const Value *RHS = getUnderlyingObject(SI->getFalseValue()); in isNonEscapingGlobalNoAlias()
786 Inputs.push_back(LHS); in isNonEscapingGlobalNoAlias()
788 Inputs.push_back(RHS); in isNonEscapingGlobalNoAlias()
792 for (const Value *Op : PN->incoming_values()) { in isNonEscapingGlobalNoAlias()
795 Inputs.push_back(Op); in isNonEscapingGlobalNoAlias()
800 // FIXME: It would be good to handle other obvious no-alias cases here, but in isNonEscapingGlobalNoAlias()
804 } while (!Inputs.empty()); in isNonEscapingGlobalNoAlias()
806 // If all the inputs to V were definitively no-alias, then V is no-alias. in isNonEscapingGlobalNoAlias()
818 /// alias - If one of the pointers is to a global that we are tracking, and the
826 getUnderlyingObject(LocA.Ptr->stripPointerCastsForAliasAnalysis()); in alias()
828 getUnderlyingObject(LocB.Ptr->stripPointerCastsForAliasAnalysis()); in alias()
830 // If either of the underlying values is a global, they may be non-addr-taken in alias()
842 // If the two pointers are derived from two different non-addr-taken in alias()
854 // Check for a special case where a non-escaping global can be used to in alias()
855 // conclude no-alias. in alias()
863 // Otherwise if they are both derived from the same addr-taken global, we in alias()
872 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0))) in alias()
876 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(LI->getOperand(0))) in alias()
906 if (Call->doesNotAccessMemory()) in getModRefInfoForArgument()
909 Call->onlyReadsMemory() ? ModRefInfo::Ref : ModRefInfo::ModRef; in getModRefInfoForArgument()
911 // Iterate through all the arguments to the called function. If any argument in getModRefInfoForArgument()
913 for (const auto &A : Call->args()) { in getModRefInfoForArgument()
917 // All objects must be identified. in getModRefInfoForArgument()
919 // Try ::alias to see if all objects are known not to alias GV. in getModRefInfoForArgument()
921 return this->alias(MemoryLocation::getBeforeOrAfter(V), in getModRefInfoForArgument()
931 // We identified all objects in the argument list, and none of them were GV. in getModRefInfoForArgument()
946 if (GV->hasLocalLinkage() && !UnknownFunctionsWithLocalLinkage) in getModRefInfo()
947 if (const Function *F = Call->getCalledFunction()) in getModRefInfo()
950 Known = FI->getModRefInfoForGlobal(*GV) | in getModRefInfo()
985 // Find non-addr taken globals. in analyzeModule()
999 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & { in run()
1010 G->NonAddressTakenGlobals.clear(); in run()
1011 G->UnknownFunctionsWithLocalLinkage = false; in run()
1012 G->IndirectGlobals.clear(); in run()
1013 G->AllocsForIndirectGlobals.clear(); in run()
1014 G->FunctionInfos.clear(); in run()
1015 G->FunctionToSCCMap.clear(); in run()
1016 G->Handles.clear(); in run()
1017 G->CollectSCCMembership(CG); in run()
1018 G->AnalyzeGlobals(M); in run()
1019 G->AnalyzeCallGraph(CG, M); in run()
1021 return PreservedAnalyses::all(); in run()
1025 INITIALIZE_PASS_BEGIN(GlobalsAAWrapperPass, "globals-aa",
1029 INITIALIZE_PASS_END(GlobalsAAWrapperPass, "globals-aa", in INITIALIZE_PASS_DEPENDENCY()
1041 auto GetTLI = [this](Function &F) -> TargetLibraryInfo & { in runOnModule()
1042 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); in runOnModule()