[SCCP] Keep track of functions that might contain undef values.

[fhahn]

Summary

This patch adds coarse grain tracking of functions which may contain
undefined values. It does so be keeping a SetVector of functions that
may containe undefined values. Whenever a new block is marked as
executable, the function is marked as containing possibly undefined
values.

To resolve undefined values, we just look at the last function in
PossiblyUndefinedFns and call ResolvedUndefsIn. If it returns false,
that means the function does not contain undefined values and we can
remote it from the set.

We use the fact that once we know the executable blocks of a function do
not contain undefined values, the only way the function can contain
undefined values is when a new block gets marked as executable.

The book-keeping overhead should be very small (we access
PossiblyUndefinedFns once per basic block in the module) and the gains
in terms of avoided ResolvedUndefsIn calls seem quite promising:

For -O3 build of SPEC2006,SPEC2000,MultiSource, we get the following
improvements for the number of times ResolvedUndefsIn is called. Below
the top15 improvements:

base    patch

test-suite...arks/BitBench/drop3/drop3.test 23.00 6.00 -73.9%
test-suite...arks/VersaBench/dbms/dbms.test 393.00 103.00 -73.8%
test-suite...patricia/network-patricia.test 42.00 12.00 -71.4%
test-suite...math/automotive-basicmath.test 34.00 10.00 -70.6%
test-suite...000/186.crafty/186.crafty.test 746.00 224.00 -70.0%
test-suite...rks/FreeBench/mason/mason.test 69.00 21.00 -69.6%
test-suite...lications/sqlite3/sqlite3.test 7253.00 2221.00 -69.4%
test-suite...ks/Prolangs-C/gnugo/gnugo.test 176.00 54.00 -69.3%
test-suite...TimberWolfMC/timberwolfmc.test 1472.00 452.00 -69.3%
test-suite...quoia/CrystalMk/CrystalMk.test 39.00 12.00 -69.2%
test-suite...s/ASC_Sequoia/IRSmk/IRSmk.test 32.00 10.00 -68.8%
test-suite...eeBench/analyzer/analyzer.test 98.00 32.00 -67.3%
test-suite...s/MallocBench/cfrac/cfrac.test 421.00 140.00 -66.7%
test-suite...lowfish/security-blowfish.test 58.00 20.00 -65.5%
test-suite...T2000/300.twolf/300.twolf.test 1102.00 382.00 -65.3%

For -O3 with LTO:

base    patch

test-suite...-typeset/consumer-typeset.test 14327.00 1541.00 -89.2%
test-suite...arks/BitBench/drop3/drop3.test 43.00 10.00 -76.7%
test-suite...CFP2000/177.mesa/177.mesa.test 13321.00 3465.00 -74.0%
test-suite...patricia/network-patricia.test 68.00 18.00 -73.5%
test-suite...TimberWolfMC/timberwolfmc.test 2386.00 673.00 -71.8%
test-suite...5/124.m88ksim/124.m88ksim.test 3023.00 861.00 -71.5%
test-suite...arks/VersaBench/dbms/dbms.test 576.00 165.00 -71.4%
test-suite...lications/sqlite3/sqlite3.test 10248.00 2968.00 -71.0%
test-suite...math/automotive-basicmath.test 51.00 15.00 -70.6%
test-suite...000/186.crafty/186.crafty.test 1277.00 382.00 -70.1%
test-suite.../Benchmarks/Ptrdist/ks/ks.test 123.00 37.00 -69.9%
test-suite...ks/McCat/04-bisect/bisect.test 63.00 20.00 -68.3%
test-suite...rks/FreeBench/mason/mason.test 85.00 27.00 -68.2%
test-suite...ks/Prolangs-C/gnugo/gnugo.test 280.00 89.00 -68.2%
test-suite.../CINT2006/403.gcc/403.gcc.test 54981.00 17523.00 -68.1%

llvm/lib/Transforms/Scalar/SCCP.cpp

 //   * Proves conditional branches to be unconditional
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/SCCP.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.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/ValueLattice.h"
 #include "llvm/Analysis/ValueLatticeUtils.h"
class SCCPSolver : public InstVisitor<SCCPSolver> {
   /// By having a separate worklist, we accomplish this because everything
   /// possibly overdefined will become overdefined at the soonest possible
   /// point.
   SmallVector<Value *, 64> OverdefinedInstWorkList;
   SmallVector<Value *, 64> InstWorkList;
 
   // The BasicBlock work list
   SmallVector<BasicBlock *, 64>  BBWorkList;
 
+
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   DenseSet<Edge> KnownFeasibleEdges;
 
   DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
   DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
 
 public:
+  SetVector<Function *> PossiblyUndefined;
   void addAnalysis(Function &F, AnalysisResultsForFn A) {
     AnalysisResults.insert({&F, std::move(A)});
   }
 
   const PredicateBase *getPredicateInfoFor(Instruction *I) {
     auto A = AnalysisResults.find(I->getParent()->getParent());
     if (A == AnalysisResults.end())
       return nullptr;
public:
   /// the blocks that are known to be intrinsically live in the processed unit.
   ///
   /// This returns true if the block was not considered live before.
   bool MarkBlockExecutable(BasicBlock *BB) {
     if (!BBExecutable.insert(BB).second)
       return false;
     LLVM_DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << '\n');
     BBWorkList.push_back(BB);  // Add the block to the work list!
+    PossiblyUndefined.insert(BB->getParent());
     return true;
   }
 
   /// TrackValueOfGlobalVariable - Clients can use this method to
   /// inform the SCCPSolver that it should track loads and stores to the
   /// specified global variable if it can.  This is only legal to call if
   /// performing Interprocedural SCCP.
   void TrackValueOfGlobalVariable(GlobalVariable *GV) {
bool llvm::runIPSCCP(
   }
 
   // Solve for constants.
   bool ResolvedUndefs = true;
   Solver.Solve();
   while (ResolvedUndefs) {
     LLVM_DEBUG(dbgs() << "RESOLVING UNDEFS\n");
     ResolvedUndefs = false;
-    for (Function &F : M)
+    while (!Solver.PossiblyUndefined.empty()) {
+      Function &F = *Solver.PossiblyUndefined.back();
       if (Solver.ResolvedUndefsIn(F)) {
         // We run Solve() after we resolved an undef in a function, because
         // we might deduce a fact that eliminates an undef in another function.
         Solver.Solve();
         ResolvedUndefs = true;
-      }
+      } else
+        Solver.PossiblyUndefined.pop_back();
   }
 
   bool MadeChanges = false;
 
   // Iterate over all of the instructions in the module, replacing them with
   // constants if we have found them to be of constant values.
 
   for (Function &F : M) {