[IPSCCP] Move common functions to IPOUtils (NFC)

[mssimpso]

Summary

This patch moves some common utility functions out of IPSCCP and makes them available globally. The functions determine if interprocedural data-flow analyses can propagate information through function returns, arguments, and global variables.

This refactoring was suggested in the review of D37335.

[mssimpso]

Some updates.

• I moved the functions over to Analysis. This makes more sense to me since they don't modify the code at all. They'll also be able to be used by other analyses that way.
• I added back the removeDeadConstantUsers call in IPSCCP. This was an omission from the last version of the patch.

[• dberlin]

So, i can't find what the suggestion was, but these are fairly specific to value lattices and don't belong being used by most other things.
There are lattices where they are correct, and lattices where they make no sense.
It's also kinda conservative.

IMHO, these aren't generic enough to want to be used by a lot other things (plus at least one of them would lead to N^2 usage).
They definitely don't belong in something called "IPOUtils", because it implies they should be used broadly.

If you renamed it to ValueLatticeUtils or something, i'd be okay with it.

lib/Analysis/IPOUtils.cpp

32 ↗

(On Diff #115416)

this is just any_of.

It's also super-conservative.

[mssimpso]

Addressed Danny's comments.

• Rename to ValueLatticeUtils
• Use any_of
• I'll retitle the patch when committing to avoid starting a new thread on llvm-commits.

I think Davide originally suggested moving these helpers out of IPSCCP. I had essentially duplicated them for the CalledValuePropagation pass, and the idea was to eliminate the duplication. However, I do recall that we were unsure of the broader usefulness of the global variables function in particular. I think renaming to ValueLatticeUtils helps address this, though.

llvm/trunk/include/llvm/Analysis/ValueLatticeUtils.h

+//===-- 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

llvm/trunk/lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   ScalarEvolutionNormalization.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   Trace.cpp
   TypeBasedAliasAnalysis.cpp
   TypeMetadataUtils.cpp
   ScopedNoAliasAA.cpp
   ValueLattice.cpp
+  ValueLatticeUtils.cpp
   ValueTracking.cpp
   VectorUtils.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Analysis
 
   DEPENDS
   intrinsics_gen
   )

llvm/trunk/lib/Analysis/ValueLatticeUtils.cpp

+//===-- 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<StoreInst>(U)) {
+      if (Store->getValueOperand() == GV || Store->isVolatile())
+        return true;
+    } else if (auto *Load = dyn_cast<LoadInst>(U)) {
+      if (Load->isVolatile())
+        return true;
+    } else {
+      return true;
+    }
+    return false;
+  });
+}

llvm/trunk/lib/Transforms/Scalar/SCCP.cpp

 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #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"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
void AddTrackedFunction(Function *F) {
     } else
       TrackedRetVals.insert(std::make_pair(F, LatticeVal()));
   }
 
   void AddArgumentTrackedFunction(Function *F) {
     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();
 
   /// ResolvedUndefsIn - While solving the dataflow for a function, we assume
   /// that branches on undef values cannot reach any of their successors.
   /// However, this is not a safe assumption.  After we solve dataflow, this
   /// method should be use to handle this.  If this returns true, the solver
INITIALIZE_PASS_BEGIN(SCCPLegacyPass, "sccp",
                       "Sparse Conditional Constant Propagation", false, false)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_END(SCCPLegacyPass, "sccp",
                     "Sparse Conditional Constant Propagation", false, false)
 
 // 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<StoreInst>(UR)) {
-      if (SI->getOperand(0) == GV || SI->isVolatile())
-        return true;  // Storing addr of GV.
-    } else if (isa<InvokeInst>(UR) || isa<CallInst>(UR)) {
-      // Make sure we are calling the function, not passing the address.
-      ImmutableCallSite CS(cast<Instruction>(UR));
-      if (!CS.isCallee(&U))
-        return true;
-    } else if (const auto *LI = dyn_cast<LoadInst>(UR)) {
-      if (LI->isVolatile())
-        return true;
-    } else if (isa<BlockAddress>(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<Function *, 32> &AddressTakenFunctions,
-                             SmallVector<ReturnInst *, 8> &ReturnsToZap) {
+                             SmallVector<ReturnInst *, 8> &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)
     if (auto *RI = dyn_cast<ReturnInst>(BB.getTerminator()))
       if (!isa<UndefValue>(RI->getOperand(0)))
         ReturnsToZap.push_back(RI);
 }
 
 static bool runIPSCCP(Module &M, const DataLayout &DL,
                       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<Function*, 32> AddressTakenFunctions;
-
   // Loop over all functions, marking arguments to those with their addresses
   // taken or that are external as overdefined.
   //
   for (Function &F : M) {
     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)) {
 
     // Assume the function is called.
     Solver.MarkBlockExecutable(&F.front());
 
     // Assume nothing about the incoming arguments.
     for (Argument &AI : F.args())
       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;
   while (ResolvedUndefs) {
     Solver.Solve();
 
     DEBUG(dbgs() << "RESOLVING UNDEFS\n");
     ResolvedUndefs = false;
static bool runIPSCCP(Module &M, const DataLayout &DL,
   // whether other functions are optimizable.
   SmallVector<ReturnInst*, 8> ReturnsToZap;
 
   const DenseMap<Function*, LatticeVal> &RV = Solver.getTrackedRetVals();
   for (const auto &I : RV) {
     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()) {
     assert(F->getReturnType()->isStructTy() &&
            "The return type should be a struct");
     StructType *STy = cast<StructType>(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.
   for (unsigned i = 0, e = ReturnsToZap.size(); i != e; ++i) {
     Function *F = ReturnsToZap[i]->getParent()->getParent();
     ReturnsToZap[i]->setOperand(0, UndefValue::get(F->getReturnType()));
   }