Index: include/llvm/Analysis/ValueLatticeUtils.h =================================================================== --- /dev/null +++ include/llvm/Analysis/ValueLatticeUtils.h @@ -0,0 +1,41 @@ +//===-- ValueLatticeUtils.h - Utils for solving lattices --------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file declares common functions useful for performing data-flow analyses +// that propagate values across function boundaries. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_VALUELATTICEUTILS_H +#define LLVM_ANALYSIS_VALUELATTICEUTILS_H + +namespace llvm { + +class Function; +class GlobalVariable; + +/// Determine if the values of the given function's arguments can be tracked +/// interprocedurally. The value of an argument can be tracked if the function +/// has local linkage and its address is not taken. +bool canTrackArgumentsInterprocedurally(Function *F); + +/// Determine if the values of the given function's returns can be tracked +/// interprocedurally. Return values can be tracked if the function has an +/// exact definition and it doesn't have the "naked" attribute. Naked functions +/// may contain assembly code that returns untrackable values. +bool canTrackReturnsInterprocedurally(Function *F); + +/// Determine if the value maintained in the given global variable can be +/// tracked interprocedurally. A value can be tracked if the global variable +/// has local linkage and is only used by non-volatile loads and stores. +bool canTrackGlobalVariableInterprocedurally(GlobalVariable *GV); + +} // end namespace llvm + +#endif // LLVM_ANALYSIS_VALUELATTICEUTILS_H Index: lib/Analysis/CMakeLists.txt =================================================================== --- lib/Analysis/CMakeLists.txt +++ lib/Analysis/CMakeLists.txt @@ -81,6 +81,7 @@ TypeMetadataUtils.cpp ScopedNoAliasAA.cpp ValueLattice.cpp + ValueLatticeUtils.cpp ValueTracking.cpp VectorUtils.cpp Index: lib/Analysis/ValueLatticeUtils.cpp =================================================================== --- /dev/null +++ lib/Analysis/ValueLatticeUtils.cpp @@ -0,0 +1,44 @@ +//===-- ValueLatticeUtils.cpp - Utils for solving lattices ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements common functions useful for performing data-flow +// analyses that propagate values across function boundaries. +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/ValueLatticeUtils.h" +#include "llvm/IR/GlobalVariable.h" +#include "llvm/IR/Instructions.h" +using namespace llvm; + +bool llvm::canTrackArgumentsInterprocedurally(Function *F) { + return F->hasLocalLinkage() && !F->hasAddressTaken(); +} + +bool llvm::canTrackReturnsInterprocedurally(Function *F) { + return F->hasExactDefinition() && !F->hasFnAttribute(Attribute::Naked); +} + +bool llvm::canTrackGlobalVariableInterprocedurally(GlobalVariable *GV) { + if (GV->isConstant() || !GV->hasLocalLinkage() || + !GV->hasDefinitiveInitializer()) + return false; + return !any_of(GV->users(), [&](User *U) { + if (auto *Store = dyn_cast(U)) { + if (Store->getValueOperand() == GV || Store->isVolatile()) + return true; + } else if (auto *Load = dyn_cast(U)) { + if (Load->isVolatile()) + return true; + } else { + return true; + } + return false; + }); +} Index: lib/Transforms/Scalar/SCCP.cpp =================================================================== --- lib/Transforms/Scalar/SCCP.cpp +++ lib/Transforms/Scalar/SCCP.cpp @@ -27,6 +27,7 @@ #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/TargetLibraryInfo.h" +#include "llvm/Analysis/ValueLatticeUtils.h" #include "llvm/IR/CallSite.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" @@ -263,6 +264,12 @@ TrackingIncomingArguments.insert(F); } + /// Returns true if the given function is in the solver's set of + /// argument-tracked functions. + bool isArgumentTrackedFunction(Function *F) { + return TrackingIncomingArguments.count(F); + } + /// Solve - Solve for constants and executable blocks. /// void Solve(); @@ -1699,38 +1706,11 @@ // createSCCPPass - This is the public interface to this file. FunctionPass *llvm::createSCCPPass() { return new SCCPLegacyPass(); } -static bool AddressIsTaken(const GlobalValue *GV) { - // Delete any dead constantexpr klingons. - GV->removeDeadConstantUsers(); - - for (const Use &U : GV->uses()) { - const User *UR = U.getUser(); - if (const auto *SI = dyn_cast(UR)) { - if (SI->getOperand(0) == GV || SI->isVolatile()) - return true; // Storing addr of GV. - } else if (isa(UR) || isa(UR)) { - // Make sure we are calling the function, not passing the address. - ImmutableCallSite CS(cast(UR)); - if (!CS.isCallee(&U)) - return true; - } else if (const auto *LI = dyn_cast(UR)) { - if (LI->isVolatile()) - return true; - } else if (isa(UR)) { - // blockaddress doesn't take the address of the function, it takes addr - // of label. - } else { - return true; - } - } - return false; -} - static void findReturnsToZap(Function &F, - SmallPtrSet &AddressTakenFunctions, - SmallVector &ReturnsToZap) { + SmallVector &ReturnsToZap, + SCCPSolver &Solver) { // We can only do this if we know that nothing else can call the function. - if (!F.hasLocalLinkage() || AddressTakenFunctions.count(&F)) + if (!Solver.isArgumentTrackedFunction(&F)) return; for (BasicBlock &BB : F) @@ -1743,13 +1723,6 @@ const TargetLibraryInfo *TLI) { SCCPSolver Solver(DL, TLI); - // AddressTakenFunctions - This set keeps track of the address-taken functions - // that are in the input. As IPSCCP runs through and simplifies code, - // functions that were address taken can end up losing their - // address-taken-ness. Because of this, we keep track of their addresses from - // the first pass so we can use them for the later simplification pass. - SmallPtrSet AddressTakenFunctions; - // Loop over all functions, marking arguments to those with their addresses // taken or that are external as overdefined. // @@ -1757,25 +1730,16 @@ if (F.isDeclaration()) continue; - // If this is an exact definition of this function, then we can propagate - // information about its result into callsites of it. - // Don't touch naked functions. They may contain asm returning a - // value we don't see, so we may end up interprocedurally propagating - // the return value incorrectly. - if (F.hasExactDefinition() && !F.hasFnAttribute(Attribute::Naked)) + // Determine if we can track the function's return values. If so, add the + // function to the solver's set of return-tracked functions. + if (canTrackReturnsInterprocedurally(&F)) Solver.AddTrackedFunction(&F); - // If this function only has direct calls that we can see, we can track its - // arguments and return value aggressively, and can assume it is not called - // unless we see evidence to the contrary. - if (F.hasLocalLinkage()) { - if (F.hasAddressTaken()) { - AddressTakenFunctions.insert(&F); - } - else { - Solver.AddArgumentTrackedFunction(&F); - continue; - } + // Determine if we can track the function's arguments. If so, add the + // function to the solver's set of argument-tracked functions. + if (canTrackArgumentsInterprocedurally(&F)) { + Solver.AddArgumentTrackedFunction(&F); + continue; } // Assume the function is called. @@ -1786,13 +1750,14 @@ Solver.markOverdefined(&AI); } - // Loop over global variables. We inform the solver about any internal global - // variables that do not have their 'addresses taken'. If they don't have - // their addresses taken, we can propagate constants through them. - for (GlobalVariable &G : M.globals()) - if (!G.isConstant() && G.hasLocalLinkage() && - G.hasDefinitiveInitializer() && !AddressIsTaken(&G)) + // Determine if we can track any of the module's global variables. If so, add + // the global variables we can track to the solver's set of tracked global + // variables. + for (GlobalVariable &G : M.globals()) { + G.removeDeadConstantUsers(); + if (canTrackGlobalVariableInterprocedurally(&G)) Solver.TrackValueOfGlobalVariable(&G); + } // Solve for constants. bool ResolvedUndefs = true; @@ -1897,7 +1862,7 @@ Function *F = I.first; if (I.second.isOverdefined() || F->getReturnType()->isVoidTy()) continue; - findReturnsToZap(*F, AddressTakenFunctions, ReturnsToZap); + findReturnsToZap(*F, ReturnsToZap, Solver); } for (const auto &F : Solver.getMRVFunctionsTracked()) { @@ -1905,7 +1870,7 @@ "The return type should be a struct"); StructType *STy = cast(F->getReturnType()); if (Solver.isStructLatticeConstant(F, STy)) - findReturnsToZap(*F, AddressTakenFunctions, ReturnsToZap); + findReturnsToZap(*F, ReturnsToZap, Solver); } // Zap all returns which we've identified as zap to change.