[SparsePropagation] Enable interprocedural analysis

[mssimpso]

Summary

This patch adds IPSCCP-like interprocedural analysis to the generic sparse conditional propagation solver. It allows the tracking of function return values and the values stored in global variables. It also gives clients the ability to mark basic blocks executable. The patch introduces separate state maps, distinct from the existing value state map, for maintaining function return values and values stored in global variables. This allows clients to distinguish, for example, a global variable from it's in-memory value and a function from the values it returns.

[mssimpso]

Separated comment groups.

[mssimpso]

Fixed a bug in MarkBlockExecutable

[lebedev.ri]

Tests?

[mssimpso]

In D37353#866950, @lebedev.ri wrote:

Tests?

The sparse propagation utility isn't currently used by any passes, so it can't really be tested by itself. I'm attempting to use it as the solver in D37355. I split these changes out to make the review of that patch easier. I've added some tests there for the review, but I expect I'll add some more as the review of that pass progresses.

[davide]

If it's not too hard, you may consider adding some unit tests for the sparse engine.

[mssimpso]

In D37353#867090, @davide wrote:

If it's not too hard, you may consider adding some unit tests for the sparse engine.

Ah, I didn't think about adding tests to unittests/. That makes sense - I'll give it a shot. I do wonder if it'd be easier to just move SCCP over to the generic engine, though.

[davide]

In D37353#867141, @mssimpso wrote:

In D37353#867090, @davide wrote:

If it's not too hard, you may consider adding some unit tests for the sparse engine.

Ah, I didn't think about adding tests to unittests/. That makes sense - I'll give it a shot. I do wonder if it'd be easier to just move SCCP over to the generic engine, though.

That wouldn't be a bad idea at all :)

[mssimpso]

Added some unit tests. Thanks for the suggestion. I briefly considered moving SCCP over to the generic solver (as a simple way to re-purpose the existing tests), but this might not be that straightforward after all. The re-solving for undef values will need to be considered. In the end, adding unit tests for this patch wasn't that difficult to do.

[davide]

In D37353#871147, @mssimpso wrote:

Added some unit tests. Thanks for the suggestion. I briefly considered moving SCCP over to the generic solver (as a simple way to re-purpose the existing tests), but this might not be that straightforward after all. The re-solving for undef values will need to be considered. In the end, adding unit tests for this patch wasn't that difficult to do.

Ideally we should consider moving to a model where the resolver doesn't really exist.
There are lots of subtleties in the way solver and resolver work in lockstep.
I'm pretty sure the only reason why SCCP didn't fall apart as GVN (the old one) or many other passes in tree is because Zhendong didn't fire up his fuzzer engine on it :)
I didn't have time to work on this (I had a couple of prototypes) and it's unlikely things will change in the near future (1-2 months).
So, for now I'm fine to leave the constant solver where it is but I'd still like to point out you just uncovered the tip of the iceberg.

[mssimpso]

In D37353#871186, @davide wrote:

Ideally we should consider moving to a model where the resolver doesn't really exist.
There are lots of subtleties in the way solver and resolver work in lockstep.
I'm pretty sure the only reason why SCCP didn't fall apart as GVN (the old one) or many other passes in tree is because Zhendong didn't fire up his fuzzer engine on it :)
I didn't have time to work on this (I had a couple of prototypes) and it's unlikely things will change in the near future (1-2 months).
So, for now I'm fine to leave the constant solver where it is but I'd still like to point out you just uncovered the tip of the iceberg.

Yes, and I just found your post about this very issue on llvm-dev from many months ago. Thanks!

[• dberlin]

It's worth noting: You can make propagation much faster by keeping a separate worklist for overdefined , and prioritizing it over the normal one.
This will move things to overdefined as quickly as possible.
(Because anything meet overdefined is just about always overdefined).

This is what SCCP does.
Again, just recording it here, i can do it in a followup.

include/llvm/Analysis/SparsePropagation.h

48

Is this, and the associated changes you make to do the mapping, still needed if lattice values can be something other than void pointers?

167

SmallVector please

171

SmallVector please

lib/Analysis/SparsePropagation.cpp

58

auto

58

Given this occurs so often, can you please just pull it out into a templated helper.

template <class T, class V>
LatticeVal findOrReturnUntracked(T Mapping, V Value)
{
auto I = Mapping.find(V);
return I != Mapping.end() ? I->second : LatticeFunc->getUntrackedVal;
}

or whatever.

64

auto

70

auto

[mssimpso]

In D37353#886179, @dberlin wrote:

It's worth noting: You can make propagation much faster by keeping a separate worklist for overdefined , and prioritizing it over the normal one.
This will move things to overdefined as quickly as possible.
(Because anything meet overdefined is just about always overdefined).

This is what SCCP does.
Again, just recording it here, i can do it in a followup.

Thanks again for taking a look at this! Right, we should eventually make a separate worklist for overdefined, like SCCP does.

include/llvm/Analysis/SparsePropagation.h

48

I added StateTy here only as shorthand - it's not really needed, especially with the auto suggestions you have. The main changes I'm making to the mapping are adding distinct maps for values loaded-from/stored-to global variables and function return values. I also changed the existing mapping from Instruction -> LatticeVal to Value -> LatticeVal to handle arguments. This mimics the behavior of IPSCCP.

167

Sounds good.

171

Sounds good.

lib/Analysis/SparsePropagation.cpp

58

Sounds good.

[• dberlin]

FYI: I'm about to rename getOrInitValueState to getValueState.
That is what SCCP calls it, and IMHO, we should be consistent.

I think you should do roughly the same (IE name the return-only ones as getExisting or getLattice, and not add "orInit" to the initializing ones)

[mssimpso]

In D37353#886435, @dberlin wrote:

FYI: I'm about to rename getOrInitValueState to getValueState.
That is what SCCP calls it, and IMHO, we should be consistent.

I think you should do roughly the same (IE name the return-only ones as getExisting or getLattice, and not add "orInit" to the initializing ones)

Sounds good to me.

[mssimpso]

Addressed comments form Danny.

• Because AbstractLatticeFunction and SparseSolver are now templates, I had to move the member functions from the .cpp file over to the header. The patch that does that is D38561.

[mssimpso]

Rebased.

[• dberlin]

lib/Analysis/SparsePropagation.cpp

318

This assumes a very specific set of lattices being used here.
The ret seems pretty generic. The store one, ....

I guess i feel like this kind of mapping function should provide, not something part of the sparse solver.

IE maybe you need SparseSolverTraits, and this is one of those functions.

(that would avoid the overhead of virtual calling).

Essentially, i feel like this is one step too specific.

I'm not sure it's worth going all the way to having the clients own *all* the state maps, and do their initialization.
But i definitely don't think you should need to special case store here (and not, say, load).
For example, use case wise, the sparse solver should be able to be used easily replace GlobalsModRef if you wanted to.

Maybe halfway? The function and value states are managed by the sparse solver, and other state maps are owned/initialized by the client, and this function is the only interface to get the right map?

[• dberlin]

(I think this needs a little thought)

[mssimpso]

I agree, getStateMapForInstruction is a bit strange. I've been thinking about what to do here. And one of the simplest things I came up with was to just define a custom LatticeKey type like we do a LatticeVal. This would allow the solver to maintain a single map (meaning we no longer need something like getStateMapForInstruction), and give the client the flexibility to separate the kinds of values it cares about.

So for example, to replicate what I currently have, the LatticeKey could be a PointerIntPair of a Value* and an enum indicating the grouping (value, function, global variable). getValueState(Value *V) and the family of functions I added for functions and global variables that may not exist yet in the map would be replaced by a single getValueState(LatticeKey Key). If Key doesn't exist in the map it would delegate to a single LatticeFunc->ComputeLatticeValue(LatticeKey Key) that would produce a new LatticeVal for Key. Currently, we have separate compute methods for arguments, functions, global variables, etc., which would also go away. It seems reasonable to move that complexity out of the generic classes. Additionally, the ComputeInstructionState functions would then be responsible for coming up with the right key. For example, visitStore would look something like:

auto *GV = dyn_cast<GlobalVariable>(Store.getPointerOperand());
if (!GV)
  return;
LatticeKey Key(GV, LatticeKey::GlobalVariable);
ChangedValues[Key] = MergeValues(...);

What do you think?

[• dberlin]

This actually sounds like a great idea, IMHO.
Let's try it and see how well it works in practice.
It certainly would address my current concerns.

I believe most users should be able to construct effective and cheap keys without real trouble.

[mssimpso]

Implement the previously discussed approach using generic LatticeKeys. A few things to note about this version of the patch:

First, there's a requirement that LatticeKeys are able to be the key_type of whatever mapping structure the generic solver uses internally (i.e., DenseMap). If a client uses a non-trivial type for LatticeKey, it will have to provide a specialization of DenseMapInfo. But we already have specializations for pointers and PointerIntPairs, which I think probably covers most potential clients. I've added a comment at the top of AbstractLatticeFunction mentioning this.

Second, there are cases when the generic solver needs to translate between LatticeKeys and their corresponding LLVM Values. One case is when it needs to add LLVM Values to the work list after the state of a LatticeKey changes. Another case is when the solver tries to determine the executable blocks, and needs to get the state of an LLVM Value (e.g., a branch or switch condition or phi node). It needs to know the LatticeKey of a Value before it can get its associated state. I originally thought about adding two virtual functions to AbstractLatticeFunction that would let the client define the conversions between LatticeKeys and LLVM Values. But I thought the overhead of the calls might be too large, especially for simple cases, like when the LatticeKey is just an LLVM Value. I instead went with a LatticeKeyInfo template that clients can specialize for their chosen LatticeKey type.

The test cases show how this works for simple ipa-cp-like problems. If the approach looks good, I'll update the summary and the CalledValuePropagation pass (D37355).

[• dberlin]

In D37353#896220, @mssimpso wrote:

Implement the previously discussed approach using generic LatticeKeys. A few things to note about this version of the patch:

First, there's a requirement that LatticeKeys are able to be the key_type of whatever mapping structure the generic solver uses internally (i.e., DenseMap). If a client uses a non-trivial type for LatticeKey, it will have to provide a specialization of DenseMapInfo. But we already have specializations for pointers and PointerIntPairs, which I think probably covers most potential clients. I've added a comment at the top of AbstractLatticeFunction mentioning this.

This seems a reasonable restriction, it's true in other parts of llvm as well anyway, so ..

Second, there are cases when the generic solver needs to translate between LatticeKeys and their corresponding LLVM Values. One case is when it needs to add LLVM Values to the work list after the state of a LatticeKey changes. Another case is when the solver tries to determine the executable blocks, and needs to get the state of an LLVM Value (e.g., a branch or switch condition or phi node). It needs to know the LatticeKey of a Value before it can get its associated state. I originally thought about adding two virtual functions to AbstractLatticeFunction that would let the client define the conversions between LatticeKeys and LLVM Values. But I thought the overhead of the calls might be too large, especially for simple cases, like when the LatticeKey is just an LLVM Value. I instead went with a LatticeKeyInfo template that clients can specialize for their chosen LatticeKey type.

SGTM

The test cases show how this works for simple ipa-cp-like problems. If the approach looks good, I'll update the summary and the CalledValuePropagation pass (D37355).

At this point, i think it looks great to start. I don't think it's worth making any more changes until their are more clients. Thanks for working through this, i think the sparse propagation solver is a *lot* more useful thanks to your work.

[mssimpso]

Thanks very much for the reviews!

include/llvm/Analysis/SparsePropagation.h

 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
 #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/IR/Instruction.h"
 #include <set>
 #include <utility>
 #include <vector>
 
 namespace llvm {
 
 class Argument;
 class BasicBlock;
 class Constant;
 class Function;
-class Instruction;
 class PHINode;
 class raw_ostream;
 class SparseSolver;
 class TerminatorInst;
 class Value;
 template <typename T> class SmallVectorImpl;
 
 /// AbstractLatticeFunction - This class is implemented by the dataflow instance
 /// to specify what the lattice values are and how they handle merges etc.
 /// This gives the client the power to compute lattice values from instructions,
 /// constants, etc.  The requirement is that lattice values must all fit into
 /// a void*.  If a void* is not sufficient, the implementation should use this
 /// pointer to be a pointer into a uniquing set or something.
 ///
 class AbstractLatticeFunction {
 public:
-  using LatticeVal = void *;
+  using LatticeVal = const void *;
+  using StateTy = DenseMap<Value *, LatticeVal>;
 
 private:
   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
 
 public:
   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
                           LatticeVal untrackedVal) {
     UndefVal = undefVal;
     OverdefinedVal = overdefinedVal;
     UntrackedVal = untrackedVal;
   }
 
   virtual ~AbstractLatticeFunction();
 
   LatticeVal getUndefVal()       const { return UndefVal; }
   LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
   LatticeVal getUntrackedVal()   const { return UntrackedVal; }
 
-  /// IsUntrackedValue - If the specified Value is something that is obviously
-  /// uninteresting to the analysis (and would always return UntrackedVal),
-  /// this function can return true to avoid pointless work.
+  /// IsUntrackedValue - If the specified value is obviously uninteresting to
+  /// the analysis (i.e., it would always return UntrackedVal), this function
+  /// can return true to avoid pointless work.
   virtual bool IsUntrackedValue(Value *V) { return false; }
 
+  /// IsUntrackedGlobalVariable - If the specified global variable holds values
+  /// that are obviously uninteresting to the analysis (i.e., they would always
+  /// return UntrackedVal), this function can return true to avoid pointless
+  /// work.
+  virtual bool IsUntrackedGlobalVariable(GlobalVariable *V) { return false; }
+
+  /// IsUntrackedFunction - If the specified function returns values that are
+  /// obviously uninteresting to the analysis (i.e., they would always return
+  /// UntrackedVal), this function can return true to avoid pointless work.
+  virtual bool IsUntrackedFunction(Function *V) { return false; }
+
   /// ComputeConstant - Given a constant value, compute and return a lattice
   /// value corresponding to the specified constant.
   virtual LatticeVal ComputeConstant(Constant *C) {
     return getOverdefinedVal(); // always safe
   }
 
   /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
   /// one that the we want to handle through ComputeInstructionState.
   virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
 
   /// GetConstant - If the specified lattice value is representable as an LLVM
   /// constant value, return it.  Otherwise return null.  The returned value
   /// must be in the same LLVM type as Val.
   virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
     return nullptr;
   }
 
   /// ComputeArgument - Given a formal argument value, compute and return a
   /// lattice value corresponding to the specified argument.
   virtual LatticeVal ComputeArgument(Argument *I) {
     return getOverdefinedVal(); // always safe
   }
 
+  /// ComputeGlobalVariable - Given a global variable, compute and return a
+  /// lattice value corresponding to the value stored in the global.
+  virtual LatticeVal ComputeGlobalVariable(GlobalVariable *GV) {
+    return getOverdefinedVal(); // always safe
+  }
+
+  /// ComputeFunction - Given a function, compute and return a lattice value
+  /// corresponding to the function's return value.
+  virtual LatticeVal ComputeFunction(Function *F) {
+    return getOverdefinedVal(); // always safe
+  }
+
   /// MergeValues - Compute and return the merge of the two specified lattice
   /// values.  Merging should only move one direction down the lattice to
   /// guarantee convergence (toward overdefined).
   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
     return getOverdefinedVal(); // always safe, never useful.
   }
 
-  /// ComputeInstructionState - Given an instruction and a vector of its operand
-  /// values, compute the result value of the instruction.
-  virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
-    return getOverdefinedVal(); // always safe, never useful.
+  /// ComputeInstructionState - Compute the lattice values that change as a
+  /// result of executing instruction \p I. The changed values are store in \p
+  /// CV.
+  virtual void ComputeInstructionState(Instruction &I, StateTy &CV,
+                                       SparseSolver &S) {
+    CV[&I] = getOverdefinedVal(); // always safe, never useful.
   }
 
   /// PrintValue - Render the specified lattice value to the specified stream.
   virtual void PrintValue(LatticeVal V, raw_ostream &OS);
 };
 
 /// SparseSolver - This class is a general purpose solver for Sparse Conditional
 /// Propagation with a programmable lattice function.
 class SparseSolver {
   using LatticeVal = AbstractLatticeFunction::LatticeVal;
+  using StateTy = AbstractLatticeFunction::StateTy;
 
   /// LatticeFunc - This is the object that knows the lattice and how to do
   /// compute transfer functions.
   AbstractLatticeFunction *LatticeFunc;
 
-  DenseMap<Value *, LatticeVal> ValueState;   // The state each value is in.
-  SmallPtrSet<BasicBlock *, 16> BBExecutable; // The bbs that are executable.
+  /// ValueState - Holds the lattice state associated with LLVM values.
+  StateTy ValueState;
 
-  std::vector<Instruction *> InstWorkList; // Worklist of insts to process.
+  /// FunctionState - Holds the lattice state for function return values. We
+  /// maintain a separate map for returns because functions can return more
+  /// than one value (i.e., there's no key with which to associate the return
+  /// lattice state other than the function itself). LLVM functions can also be
+  /// tracked independently in the ValueState map, so we need a separate one
+  /// for returns.
+  StateTy FunctionState;
+
+  /// GlobalVariableState - Holds the lattice state for values stored in global
+  /// variables. Similar to function returns, we maintain a separate map for
+  /// global variables because a global variable is the only key with which to
+  /// associate the values stored at its location. Additionally, LLVM global
+  /// variables can also be tracked independently in the ValueState map. This
+  /// map maintains the state of in-memory values, not their addresses.
+  StateTy GlobalVariableState;
+
+  /// BBWorkList - Holds basic blocks that should be processed.
+  std::vector<BasicBlock *> BBWorkList;
+
+  /// ValueWorkList - Holds values (i.e., instructions and global variables)
+  /// that should be processed.
+  std::vector<Value *> ValueWorkList;
 
-  std::vector<BasicBlock *> BBWorkList; // The BasicBlock work list
+  /// BBExecutable - Holds the basic blocks that are executable.
+  SmallPtrSet<BasicBlock *, 16> BBExecutable;
 
   /// KnownFeasibleEdges - Entries in this set are edges which have already had
   /// PHI nodes retriggered.
   using Edge = std::pair<BasicBlock *, BasicBlock *>;
   std::set<Edge> KnownFeasibleEdges;
 
 public:
   explicit SparseSolver(AbstractLatticeFunction *Lattice)
       : LatticeFunc(Lattice) {}
   SparseSolver(const SparseSolver &) = delete;
   SparseSolver &operator=(const SparseSolver &) = delete;
-  ~SparseSolver() { delete LatticeFunc; }
 
   /// Solve - Solve for constants and executable blocks.
-  void Solve(Function &F);
+  void Solve();
 
-  void Print(Function &F, raw_ostream &OS) const;
+  /// Print - Print the contents of each of the states maps.
+  void Print(raw_ostream &OS) const;
 
-  /// getLatticeState - Return the LatticeVal object that corresponds to the
-  /// value.  If an value is not in the map, it is returned as untracked,
-  /// unlike the getOrInitValueState method.
-  LatticeVal getLatticeState(Value *V) const {
-    DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
-    return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
-  }
-
-  /// getOrInitValueState - Return the LatticeVal object that corresponds to the
-  /// value, initializing the value's state if it hasn't been entered into the
-  /// map yet.   This function is necessary because not all values should start
-  /// out in the underdefined state... Arguments should be overdefined, and
-  /// constants should be marked as constants.
+  /// getValueState - Return the LatticeVal object corresponding to the given
+  /// value from the ValueState map. If the value is not in the map,
+  /// UntrackedVal is returned.
+  LatticeVal getValueState(Value *V) const;
+
+  /// getGlobalVariableState - Return the LatticeVal object corresponding to
+  /// the given global variable from the GlobalVariableState map. If the global
+  /// variable is not in the map, UntrackedVal is returned.
+  LatticeVal getGlobalVariableState(GlobalVariable *GV) const;
+
+  /// getFunctionState - Return the LatticeVal object corresponding to the
+  /// given function from the FunctionState map. If the function is not in the
+  /// map, UntrackedVal is returned.
+  LatticeVal getFunctionState(Function *F) const;
+
+  /// getOrInitValueState - Return the LatticeVal object corresponding to the
+  /// given value from the ValueState map. If the value is not in the map, its
+  /// state is initialized.
   LatticeVal getOrInitValueState(Value *V);
 
+  /// getOrInitGlobalVariableState - Return the LatticeVal object corresponding
+  /// to the given global variable from the GlobalVariableState map. If the
+  /// global variable is not in the map, its state is initialized.
+  LatticeVal getOrInitGlobalVariableState(GlobalVariable *GV);
+
+  /// getOrInitFunctionState - Return the LatticeVal object corresponding to
+  /// the given function from the FunctionState map. If the function is not in
+  /// the map, its state is initialized.
+  LatticeVal getOrInitFunctionState(Function *F);
+
   /// isEdgeFeasible - Return true if the control flow edge from the 'From'
   /// basic block to the 'To' basic block is currently feasible.  If
   /// AggressiveUndef is true, then this treats values with unknown lattice
   /// values as undefined.  This is generally only useful when solving the
   /// lattice, not when querying it.
   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
                       bool AggressiveUndef = false);
 
   /// isBlockExecutable - Return true if there are any known feasible
   /// edges into the basic block.  This is generally only useful when
   /// querying the lattice.
   bool isBlockExecutable(BasicBlock *BB) const {
     return BBExecutable.count(BB);
   }
 
-private:
-  /// UpdateState - When the state for some instruction is potentially updated,
-  /// this function notices and adds I to the worklist if needed.
-  void UpdateState(Instruction &Inst, LatticeVal V);
-
   /// MarkBlockExecutable - This method can be used by clients to mark all of
   /// the blocks that are known to be intrinsically live in the processed unit.
   void MarkBlockExecutable(BasicBlock *BB);
 
+private:
+  /// UpdateState - When the state for some value is potentially updated, this
+  /// function notices and adds V to the worklist if needed.
+  void UpdateState(Value &V, LatticeVal LV, StateTy &State);
+
+  /// getStateMapForInstruction - Return a reference to the state map
+  /// appropriate for the given instruction.
+  StateTy &getStateMapForInstruction(Instruction &I);
+
+  /// printStateMap - Print the contents of the given state map.
+  void printStateMap(const StateTy &State, raw_ostream &OS) const;
+
   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
   /// work list if it is not already executable.
   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
 
   /// getFeasibleSuccessors - Return a vector of booleans to indicate which
   /// successors are reachable from a given terminator instruction.
   void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
                              bool AggressiveUndef);

lib/Analysis/SparsePropagation.cpp

 #include "llvm/Analysis/SparsePropagation.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/GlobalVariable.h"
 #include "llvm/IR/InstrTypes.h"
-#include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/User.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
void AbstractLatticeFunction::PrintValue(LatticeVal V, raw_ostream &OS) {
   else
     OS << "unknown lattice value";
 }
 
 //===----------------------------------------------------------------------===//
 //                          SparseSolver Implementation
 //===----------------------------------------------------------------------===//
 
-/// getOrInitValueState - Return the LatticeVal object that corresponds to the
-/// value, initializing the value's state if it hasn't been entered into the
-/// map yet.   This function is necessary because not all values should start
-/// out in the underdefined state... Arguments should be overdefined, and
-/// constants should be marked as constants.
+SparseSolver::LatticeVal SparseSolver::getValueState(Value *V) const {
+  StateTy::const_iterator I = ValueState.find(V);
+  return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
+}
+
+SparseSolver::LatticeVal
+SparseSolver::getGlobalVariableState(GlobalVariable *GV) const {
+  StateTy::const_iterator I = GlobalVariableState.find(GV);
+  return I != GlobalVariableState.end() ? I->second
+                                        : LatticeFunc->getUntrackedVal();
+}
+
+SparseSolver::LatticeVal SparseSolver::getFunctionState(Function *F) const {
+  StateTy::const_iterator I = FunctionState.find(F);
+  return I != FunctionState.end() ? I->second : LatticeFunc->getUntrackedVal();
+}
+
 SparseSolver::LatticeVal SparseSolver::getOrInitValueState(Value *V) {
-  DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(V);
+  StateTy::iterator I = ValueState.find(V);
   if (I != ValueState.end()) return I->second;  // Common case, in the map
   
   LatticeVal LV;
   if (LatticeFunc->IsUntrackedValue(V))
     return LatticeFunc->getUntrackedVal();
   else if (Constant *C = dyn_cast<Constant>(V))
     LV = LatticeFunc->ComputeConstant(C);
   else if (Argument *A = dyn_cast<Argument>(V))
     LV = LatticeFunc->ComputeArgument(A);
   else if (!isa<Instruction>(V))
     // All other non-instructions are overdefined.
     LV = LatticeFunc->getOverdefinedVal();
   else
     // All instructions are underdefined by default.
     LV = LatticeFunc->getUndefVal();
   
   // If this value is untracked, don't add it to the map.
   if (LV == LatticeFunc->getUntrackedVal())
     return LV;
   return ValueState[V] = LV;
 }
 
+SparseSolver::LatticeVal
+SparseSolver::getOrInitGlobalVariableState(GlobalVariable *GV) {
+  StateTy::iterator I = GlobalVariableState.find(GV);
+  if (I != GlobalVariableState.end())
+    return I->second;
+  if (LatticeFunc->IsUntrackedGlobalVariable(GV))
+    return LatticeFunc->getUntrackedVal();
+  return GlobalVariableState[GV] = LatticeFunc->ComputeGlobalVariable(GV);
+}
+
+SparseSolver::LatticeVal SparseSolver::getOrInitFunctionState(Function *F) {
+  StateTy::iterator I = FunctionState.find(F);
+  if (I != FunctionState.end())
+    return I->second;
+  if (LatticeFunc->IsUntrackedFunction(F))
+    return LatticeFunc->getUntrackedVal();
+  return FunctionState[F] = LatticeFunc->ComputeFunction(F);
+}
+
 /// UpdateState - When the state for some instruction is potentially updated,
 /// this function notices and adds I to the worklist if needed.
-void SparseSolver::UpdateState(Instruction &Inst, LatticeVal V) {
-  DenseMap<Value*, LatticeVal>::iterator I = ValueState.find(&Inst);
-  if (I != ValueState.end() && I->second == V)
+void SparseSolver::UpdateState(Value &V, LatticeVal LV, StateTy &State) {
+  StateTy::iterator I = State.find(&V);
+  if (I != State.end() && I->second == LV)
     return;  // No change.
   
   // An update.  Visit uses of I.
-  ValueState[&Inst] = V;
-  InstWorkList.push_back(&Inst);
+  State[&V] = LV;
+  ValueWorkList.push_back(&V);
 }
 
 /// MarkBlockExecutable - This method can be used by clients to mark all of
 /// the blocks that are known to be intrinsically live in the processed unit.
 void SparseSolver::MarkBlockExecutable(BasicBlock *BB) {
+  if (!BBExecutable.insert(BB).second)
+    return;
   DEBUG(dbgs() << "Marking Block Executable: " << BB->getName() << "\n");
-  BBExecutable.insert(BB);   // Basic block is executable!
   BBWorkList.push_back(BB);  // Add the block to the work list!
 }
 
 /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
 /// work list if it is not already executable...
 void SparseSolver::markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest) {
   if (!KnownFeasibleEdges.insert(Edge(Source, Dest)).second)
     return;  // This edge is already known to be executable!
if (BI->isUnconditional()) {
       Succs[0] = true;
       return;
     }
     
     LatticeVal BCValue;
     if (AggressiveUndef)
       BCValue = getOrInitValueState(BI->getCondition());
     else
-      BCValue = getLatticeState(BI->getCondition());
+      BCValue = getValueState(BI->getCondition());
     
     if (BCValue == LatticeFunc->getOverdefinedVal() ||
         BCValue == LatticeFunc->getUntrackedVal()) {
       // Overdefined condition variables can branch either way.
       Succs[0] = Succs[1] = true;
       return;
     }
 
     // If undefined, neither is feasible yet.
     if (BCValue == LatticeFunc->getUndefVal())
       return;
 
     Constant *C = LatticeFunc->GetConstant(BCValue, BI->getCondition(), *this);
     if (!C || !isa<ConstantInt>(C)) {
       // Non-constant values can go either way.
       Succs[0] = Succs[1] = true;
       return;
     }
 
     // Constant condition variables mean the branch can only go a single way
     Succs[C->isNullValue()] = true;
     return;
   }
   
-  if (isa<InvokeInst>(TI)) {
-    // Invoke instructions successors are always executable.
-    // TODO: Could ask the lattice function if the value can throw.
-    Succs[0] = Succs[1] = true;
+  if (TI.isExceptional()) {
+    Succs.assign(Succs.size(), true);
     return;
   }
   
   if (isa<IndirectBrInst>(TI)) {
     Succs.assign(Succs.size(), true);
     return;
   }
   
   SwitchInst &SI = cast<SwitchInst>(TI);
   LatticeVal SCValue;
   if (AggressiveUndef)
     SCValue = getOrInitValueState(SI.getCondition());
   else
-    SCValue = getLatticeState(SI.getCondition());
+    SCValue = getValueState(SI.getCondition());
   
   if (SCValue == LatticeFunc->getOverdefinedVal() ||
       SCValue == LatticeFunc->getUntrackedVal()) {
     // All destinations are executable!
     Succs.assign(TI.getNumSuccessors(), true);
     return;
   }
   
if (SuccFeasible[i])
       markEdgeExecutable(BB, TI.getSuccessor(i));
 }
 
 void SparseSolver::visitPHINode(PHINode &PN) {
   // The lattice function may store more information on a PHINode than could be
   // computed from its incoming values.  For example, SSI form stores its sigma
   // functions as PHINodes with a single incoming value.
   if (LatticeFunc->IsSpecialCasedPHI(&PN)) {
-    LatticeVal IV = LatticeFunc->ComputeInstructionState(PN, *this);
-    if (IV != LatticeFunc->getUntrackedVal())
-      UpdateState(PN, IV);
+    StateTy ChangedValues;
+    LatticeFunc->ComputeInstructionState(PN, ChangedValues, *this);
+    for (auto &ChangedValue : ChangedValues) {
+      if (ChangedValue.second != LatticeFunc->getUntrackedVal())
+        UpdateState(*ChangedValue.first, ChangedValue.second, ValueState);
+    }
     return;
   }
 
   LatticeVal PNIV = getOrInitValueState(&PN);
   LatticeVal Overdefined = LatticeFunc->getOverdefinedVal();
   
   // If this value is already overdefined (common) just return.
   if (PNIV == Overdefined || PNIV == LatticeFunc->getUntrackedVal())
     return;  // Quick exit
   
   // Super-extra-high-degree PHI nodes are unlikely to ever be interesting,
   // and slow us down a lot.  Just mark them overdefined.
   if (PN.getNumIncomingValues() > 64) {
-    UpdateState(PN, Overdefined);
+    UpdateState(PN, Overdefined, ValueState);
     return;
   }
   
   // Look at all of the executable operands of the PHI node.  If any of them
   // are overdefined, the PHI becomes overdefined as well.  Otherwise, ask the
   // transfer function to give us the merge of the incoming values.
   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
     // If the edge is not yet known to be feasible, it doesn't impact the PHI.
     if (!isEdgeFeasible(PN.getIncomingBlock(i), PN.getParent(), true))
       continue;
     
     // Merge in this value.
     LatticeVal OpVal = getOrInitValueState(PN.getIncomingValue(i));
     if (OpVal != PNIV)
       PNIV = LatticeFunc->MergeValues(PNIV, OpVal);
     
     if (PNIV == Overdefined)
       break;  // Rest of input values don't matter.
   }
 
   // Update the PHI with the compute value, which is the merge of the inputs.
-  UpdateState(PN, PNIV);
+  UpdateState(PN, PNIV, ValueState);
+}
+
+SparseSolver::StateTy &SparseSolver::getStateMapForInstruction(Instruction &I) {
+  switch (I.getOpcode()) {
+  case Instruction::Ret:   return FunctionState;
+  case Instruction::Store: return GlobalVariableState;
+  default:                 return ValueState;
+  }
 }
 
 void SparseSolver::visitInst(Instruction &I) {
   // PHIs are handled by the propagation logic, they are never passed into the
   // transfer functions.
   if (PHINode *PN = dyn_cast<PHINode>(&I))
     return visitPHINode(*PN);
   
   // Otherwise, ask the transfer function what the result is.  If this is
   // something that we care about, remember it.
-  LatticeVal IV = LatticeFunc->ComputeInstructionState(I, *this);
-  if (IV != LatticeFunc->getUntrackedVal())
-    UpdateState(I, IV);
-  
+  StateTy ChangedValues;
+  LatticeFunc->ComputeInstructionState(I, ChangedValues, *this);
+  for (auto &ChangedValue : ChangedValues) {
+    if (ChangedValue.second != LatticeFunc->getUntrackedVal())
+      UpdateState(*ChangedValue.first, ChangedValue.second,
+                  getStateMapForInstruction(I));
+  }
   if (TerminatorInst *TI = dyn_cast<TerminatorInst>(&I))
     visitTerminatorInst(*TI);
 }
 
-void SparseSolver::Solve(Function &F) {
-  MarkBlockExecutable(&F.getEntryBlock());
-  
+void SparseSolver::Solve() {
   // Process the work lists until they are empty!
-  while (!BBWorkList.empty() || !InstWorkList.empty()) {
-    // Process the instruction work list.
-    while (!InstWorkList.empty()) {
-      Instruction *I = InstWorkList.back();
-      InstWorkList.pop_back();
+  while (!BBWorkList.empty() || !ValueWorkList.empty()) {
+    // Process the value work list.
+    while (!ValueWorkList.empty()) {
+      Value *I = ValueWorkList.back();
+      ValueWorkList.pop_back();
 
       DEBUG(dbgs() << "\nPopped off I-WL: " << *I << "\n");
 
       // "I" got into the work list because it made a transition.  See if any
       // users are both live and in need of updating.
       for (User *U : I->users()) {
-        Instruction *UI = cast<Instruction>(U);
-        if (BBExecutable.count(UI->getParent()))   // Inst is executable?
+        if (Instruction *UI = dyn_cast<Instruction>(U))
+          if (BBExecutable.count(UI->getParent())) // Inst is executable?
             visitInst(*UI);
       }
     }
 
     // Process the basic block work list.
     while (!BBWorkList.empty()) {
       BasicBlock *BB = BBWorkList.back();
       BBWorkList.pop_back();
 
       DEBUG(dbgs() << "\nPopped off BBWL: " << *BB);
 
       // Notify all instructions in this basic block that they are newly
       // executable.
       for (Instruction &I : *BB)
         visitInst(I);
     }
   }
 }
 
-void SparseSolver::Print(Function &F, raw_ostream &OS) const {
-  OS << "\nFUNCTION: " << F.getName() << "\n";
-  for (auto &BB : F) {
-    if (!BBExecutable.count(&BB))
-      OS << "INFEASIBLE: ";
+void SparseSolver::printStateMap(const StateTy &State, raw_ostream &OS) const {
+  if (State.empty())
+    return;
+
+  LatticeVal LV;
+  Value *V;
+
+  if (&State == &FunctionState)
+    OS << "FunctionState:\n";
+  else if (&State == &GlobalVariableState)
+    OS << "GlobalVariableState:\n";
+  else if (&State == &ValueState)
+    OS << "ValueState:\n";
+  else
+    llvm_unreachable("Unknown state map");
+
+  for (auto &StateEntry : State) {
+    std::tie(V, LV) = StateEntry;
+    if (LV == LatticeFunc->getUntrackedVal())
+      continue;
     OS << "\t";
-    if (BB.hasName())
-      OS << BB.getName() << ":\n";
+    LatticeFunc->PrintValue(LV, OS);
+    OS << ": ";
+    if (isa<Function>(V))
+      OS << V->getName() << "\n";
     else
-      OS << "; anon bb\n";
-    for (auto &I : BB) {
-      LatticeFunc->PrintValue(getLatticeState(&I), OS);
-      OS << I << "\n";
-    }
-    
-    OS << "\n";
-  }
+      OS << *V << "\n";
+
+void SparseSolver::Print(raw_ostream &OS) const {
+  printStateMap(FunctionState, OS);
+  printStateMap(GlobalVariableState, OS);
+  printStateMap(ValueState, OS);
 }

unittests/Analysis/CMakeLists.txt

add_llvm_unittest(AnalysisTests
   GlobalsModRefTest.cpp
   LazyCallGraphTest.cpp
   LoopInfoTest.cpp
   MemoryBuiltinsTest.cpp
   MemorySSA.cpp
   OrderedBasicBlockTest.cpp
   ProfileSummaryInfoTest.cpp
   ScalarEvolutionTest.cpp
+  SparsePropagation.cpp
   TargetLibraryInfoTest.cpp
   TBAATest.cpp
   UnrollAnalyzer.cpp
   ValueTrackingTest.cpp
   )

unittests/Analysis/SparsePropagation.cpp

+//===- SparsePropagation.cpp - Unit tests for the generic solver ----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/SparsePropagation.h"
+#include "llvm/ADT/PointerIntPair.h"
+#include "llvm/IR/CallSite.h"
+#include "llvm/IR/IRBuilder.h"
+#include "gtest/gtest.h"
+using namespace llvm;
+
+namespace {
+
+/// This class defines a simple test lattice function that could be used for
+/// solving problems similar to constant propagation. The test lattice differs
+/// from a "real" lattice in a few ways. First, it initializes all return
+/// values, values stored in global variables, and arguments in the undefined
+/// state. This means that there are no limitations on what we can track
+/// interprocedurally. For simplicity, all global values in the tests will be
+/// given internal linkage, since this is not something this lattice function
+/// tracks. Second, it only handles the few instructions necessary for the
+/// tests.
+class TestLatticeFunc : public AbstractLatticeFunction {
+
+  /// The states of the lattices values. Only the Constant state is
+  /// interesting; the rest are special states used by the generic solver. The
+  /// Untracked state differs from the other three in that the generic solver
+  /// uses it to avoid doing unnecessary work. In particular, when a value
+  /// moves to the Untracked state, it's users are not be notified.
+  enum class TestLatticeValTy : unsigned {
+    Undefined,
+    Constant,
+    Overdefined,
+    Untracked
+  };
+
+  /// A simple lattice value type for problems similar to constant propagation.
+  /// It holds the constant value and the lattice state.
+  using TestLatticeVal = PointerIntPair<const Constant *, 2, TestLatticeValTy>;
+
+public:
+  /// Construct a new test lattice function with special values for the
+  /// Undefined, Overdefined, and Untracked states.
+  TestLatticeFunc()
+      : AbstractLatticeFunction(
+            TestLatticeVal(nullptr, TestLatticeValTy::Undefined)
+                .getOpaqueValue(),
+            TestLatticeVal(nullptr, TestLatticeValTy::Overdefined)
+                .getOpaqueValue(),
+            TestLatticeVal(nullptr, TestLatticeValTy::Untracked)
+                .getOpaqueValue()) {}
+
+  /// Return true if the given lattice value is in the Constant state. This is
+  /// used for checking the solver results.
+  bool isConstant(LatticeVal LV) const {
+    return TestLatticeVal::getFromOpaqueValue(LV).getInt() ==
+           TestLatticeValTy::Constant;
+  }
+
+  /// Return true if the given lattice value is in the Overdefined state. This
+  /// is used for checking the solver results.
+  bool isOverdefined(LatticeVal LV) const {
+    return TestLatticeVal::getFromOpaqueValue(LV).getInt() ==
+           TestLatticeValTy::Overdefined;
+  }
+
+  /// Return true if the given lattice value is in the Untracked state. This is
+  /// used for checking the solver results.
+  bool isUntracked(LatticeVal LV) const {
+    return TestLatticeVal::getFromOpaqueValue(LV).getInt() ==
+           TestLatticeValTy::Untracked;
+  }
+
+  /// Compute a new lattice value for the given argument. We assume all
+  /// arguments can be tracked.
+  LatticeVal ComputeArgument(Argument *A) override { return getUndefVal(); }
+
+  /// Compute a new lattice value to track the values stored in the given
+  /// global variable. We assume all global variables can be tracked.
+  LatticeVal ComputeGlobalVariable(GlobalVariable *GV) override {
+    return getUndefVal();
+  }
+
+  /// Compute a new lattice value to track the return values of the given
+  /// function. We assume all functions can be tracked.
+  LatticeVal ComputeFunction(Function *F) override { return getUndefVal(); }
+
+  /// Compute a new lattice value for the given constant.
+  LatticeVal ComputeConstant(Constant *C) override {
+    return TestLatticeVal(C, TestLatticeValTy::Constant).getOpaqueValue();
+  }
+
+  /// Merge the two given lattice values. This merge should be equivalent to
+  /// what is done for constant propagation. That is, the resulting lattice
+  /// value is constant only if the two given lattice values are constant and
+  /// hold the same value.
+  LatticeVal MergeValues(LatticeVal X, LatticeVal Y) override {
+    if (X == getUntrackedVal() || Y == getUntrackedVal())
+      return getUntrackedVal();
+    if (X == getOverdefinedVal() || Y == getOverdefinedVal())
+      return getOverdefinedVal();
+    if (X == getUndefVal() && Y == getUndefVal())
+      return getUndefVal();
+    if (X == getUndefVal())
+      return Y;
+    if (Y == getUndefVal())
+      return X;
+    if (X == Y)
+      return X;
+    return getOverdefinedVal();
+  }
+
+  /// Compute the lattice values that change as a result of executing the given
+  /// instruction. We only handle the few instructions needed for the tests.
+  void ComputeInstructionState(Instruction &I, StateTy &CV,
+                               SparseSolver &S) override {
+    switch (I.getOpcode()) {
+    case Instruction::Call:  return visitCallSite(cast<CallInst>(&I), CV, S);
+    case Instruction::Ret:   return visitReturn(*cast<ReturnInst>(&I), CV, S);
+    case Instruction::Store: return visitStore(*cast<StoreInst>(&I), CV, S);
+    default:                 return visitInst(I, CV, S);
+    }
+  }
+
+private:
+  /// Handle call sites. The state of a called function's argument is the merge
+  /// of the current formal argument state with the call site's corresponding
+  /// actual argument state. The call site state is the merge of the call site
+  /// state with the returned value state of the called function.
+  void visitCallSite(CallSite CS, StateTy &CV, SparseSolver &S) {
+    Function *F = CS.getCalledFunction();
+    Instruction *I = CS.getInstruction();
+    if (!F) {
+      CV[I] = getOverdefinedVal();
+      return;
+    }
+    S.MarkBlockExecutable(&F->front());
+    for (Argument &A : F->args())
+      CV[&A] = MergeValues(S.getOrInitValueState(&A),
+                           S.getOrInitValueState(CS.getArgument(A.getArgNo())));
+    CV[I] = MergeValues(S.getOrInitValueState(I), S.getOrInitFunctionState(F));
+  }
+
+  /// Handle return instructions. The function's return state is the merge of
+  /// the returned value state and the function's current return state.
+  void visitReturn(ReturnInst &I, StateTy &CV, SparseSolver &S) {
+    Function *F = I.getParent()->getParent();
+    if (!F->getReturnType()->isVoidTy())
+      CV[F] = MergeValues(S.getOrInitValueState(I.getReturnValue()),
+                          S.getOrInitFunctionState(F));
+  }
+
+  /// Handle store instructions. If the pointer operand of the store is a
+  /// global variable, we attempt to track the value. The global variable state
+  /// is the merge of the stored value state with the current global variable
+  /// state.
+  void visitStore(StoreInst &I, StateTy &CV, SparseSolver &S) {
+    auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
+    if (!GV)
+      return;
+    CV[GV] = MergeValues(S.getOrInitValueState(I.getValueOperand()),
+                         S.getOrInitGlobalVariableState(GV));
+  }
+
+  /// Handle all other instructions. All other instructions are marked
+  /// overdefined.
+  void visitInst(Instruction &I, StateTy &CV, SparseSolver &S) {
+    CV[&I] = getOverdefinedVal();
+  }
+};
+
+/// This class defines the common data used for all of the tests. The tests
+/// should add code to the module and then run the solver.
+class SparsePropagationTest : public testing::Test {
+protected:
+  LLVMContext Context;
+  Module M;
+  IRBuilder<> Builder;
+  TestLatticeFunc Lattice;
+  SparseSolver Solver;
+
+public:
+  SparsePropagationTest()
+      : M("", Context), Builder(Context), Solver(&Lattice) {}
+};
+}
+
+/// Test that we mark discovered functions executable.
+///
+/// define internal void @f() {
+///   call void @g()
+///   ret void
+/// }
+///
+/// define internal void @g() {
+///   call void @f()
+///   ret void
+/// }
+///
+/// For this test, we initially mark "f" executable, and the solver discovers
+/// "g" because of the call in "f". The mutually recursive call in "g" also
+/// tests that we don't add a block to the basic block work list if it is
+/// already executable. Doing so would put the solver into an infinite loop.
+TEST_F(SparsePropagationTest, MarkBlockExecutable) {
+  Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "f", &M);
+  Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "g", &M);
+  BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
+  BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
+  Builder.SetInsertPoint(FEntry);
+  Builder.CreateCall(G);
+  Builder.CreateRetVoid();
+  Builder.SetInsertPoint(GEntry);
+  Builder.CreateCall(F);
+  Builder.CreateRetVoid();
+
+  Solver.MarkBlockExecutable(FEntry);
+  Solver.Solve();
+
+  EXPECT_TRUE(Solver.isBlockExecutable(GEntry));
+}
+
+/// Test that we propagate information through global variables.
+///
+/// @gv = internal global i64
+///
+/// define internal void @f() {
+///   store i64 1, i64* @gv
+///   ret void
+/// }
+///
+/// define internal void @g() {
+///   store i64 1, i64* @gv
+///   ret void
+/// }
+///
+/// For this test, we initially mark both "f" and "g" executable. The solver
+/// computes the lattice state of the global variable as constant. The test
+/// ensures that the solver uses the correct state map (i.e., the one for
+/// in-memory values) for the store instruction. Thus, "gv" should be constant
+/// in the global variable state map but untracked in the value state map.
+TEST_F(SparsePropagationTest, GlobalVariableConstant) {
+  Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "f", &M);
+  Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "g", &M);
+  GlobalVariable *GV =
+      new GlobalVariable(M, Builder.getInt64Ty(), false,
+                         GlobalValue::InternalLinkage, nullptr, "gv");
+  BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
+  BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
+  Builder.SetInsertPoint(FEntry);
+  Builder.CreateStore(Builder.getInt64(1), GV);
+  Builder.CreateRetVoid();
+  Builder.SetInsertPoint(GEntry);
+  Builder.CreateStore(Builder.getInt64(1), GV);
+  Builder.CreateRetVoid();
+
+  Solver.MarkBlockExecutable(FEntry);
+  Solver.MarkBlockExecutable(GEntry);
+  Solver.Solve();
+
+  EXPECT_TRUE(Lattice.isUntracked(Solver.getValueState(GV)));
+  EXPECT_TRUE(Lattice.isConstant(Solver.getGlobalVariableState(GV)));
+}
+
+/// Test that we propagate information through global variables.
+///
+/// @gv = internal global i64
+///
+/// define internal void @f() {
+///   store i64 0, i64* @gv
+///   ret void
+/// }
+///
+/// define internal void @g() {
+///   store i64 1, i64* @gv
+///   ret void
+/// }
+///
+/// For this test, we initially mark both "f" and "g" executable. The solver
+/// computes the lattice state of the global variable as overdefined. The test
+/// ensures that the solver uses the correct state map (i.e., the one for
+/// in-memory values) for the store instruction. Thus, "gv" should be
+/// overdefined in the global variable state map but untracked in the value
+/// state map.
+TEST_F(SparsePropagationTest, GlobalVariableOverDefined) {
+  Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "f", &M);
+  Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "g", &M);
+  GlobalVariable *GV =
+      new GlobalVariable(M, Builder.getInt64Ty(), false,
+                         GlobalValue::InternalLinkage, nullptr, "gv");
+  BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
+  BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
+  Builder.SetInsertPoint(FEntry);
+  Builder.CreateStore(Builder.getInt64(0), GV);
+  Builder.CreateRetVoid();
+  Builder.SetInsertPoint(GEntry);
+  Builder.CreateStore(Builder.getInt64(1), GV);
+  Builder.CreateRetVoid();
+
+  Solver.MarkBlockExecutable(FEntry);
+  Solver.MarkBlockExecutable(GEntry);
+  Solver.Solve();
+
+  EXPECT_TRUE(Lattice.isUntracked(Solver.getValueState(GV)));
+  EXPECT_TRUE(Lattice.isOverdefined(Solver.getGlobalVariableState(GV)));
+}
+
+/// Test that we propagate information through function returns.
+///
+/// define internal i64 @f(i1* %cond) {
+/// if:
+///   %0 = load i1, i1* %cond
+///   br i1 %0, label %then, label %else
+///
+/// then:
+///   ret i64 0
+///
+/// else:
+///   ret i64 1
+/// }
+///
+/// For this test, we initially mark "f" executable. The solver computes the
+/// return value of the function as constant. The test ensures that the solver
+/// uses the correct state map (i.e., the one for functions) for the return
+/// instructions. Thus, "f" should be constant in the function state map, but
+/// untracked in the value state map.
+TEST_F(SparsePropagationTest, FunctionDefined) {
+  Function *F =
+      Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                         {Type::getInt1PtrTy(Context)}, false),
+                       GlobalValue::InternalLinkage, "f", &M);
+  BasicBlock *If = BasicBlock::Create(Context, "if", F);
+  BasicBlock *Then = BasicBlock::Create(Context, "then", F);
+  BasicBlock *Else = BasicBlock::Create(Context, "else", F);
+  F->arg_begin()->setName("cond");
+  Builder.SetInsertPoint(If);
+  LoadInst *Cond = Builder.CreateLoad(F->arg_begin());
+  Builder.CreateCondBr(Cond, Then, Else);
+  Builder.SetInsertPoint(Then);
+  Builder.CreateRet(Builder.getInt64(1));
+  Builder.SetInsertPoint(Else);
+  Builder.CreateRet(Builder.getInt64(1));
+
+  Solver.MarkBlockExecutable(If);
+  Solver.Solve();
+
+  EXPECT_TRUE(Lattice.isUntracked(Solver.getValueState(F)));
+  EXPECT_TRUE(Lattice.isConstant(Solver.getFunctionState(F)));
+}
+
+/// Test that we propagate information through function returns.
+///
+/// define internal i64 @f(i1* %cond) {
+/// if:
+///   %0 = load i1, i1* %cond
+///   br i1 %0, label %then, label %else
+///
+/// then:
+///   ret i64 0
+///
+/// else:
+///   ret i64 1
+/// }
+///
+/// For this test, we initially mark "f" executable. The solver computes the
+/// return value of the function as overdefined. The test ensures that the
+/// solver uses the correct state map (i.e., the one for functions) for the
+/// return instructions. Thus, "f" should be overdefined in the function state
+/// map, but untracked in the value state map.
+TEST_F(SparsePropagationTest, FunctionOverDefined) {
+  Function *F =
+      Function::Create(FunctionType::get(Builder.getInt64Ty(),
+                                         {Type::getInt1PtrTy(Context)}, false),
+                       GlobalValue::InternalLinkage, "f", &M);
+  BasicBlock *If = BasicBlock::Create(Context, "if", F);
+  BasicBlock *Then = BasicBlock::Create(Context, "then", F);
+  BasicBlock *Else = BasicBlock::Create(Context, "else", F);
+  F->arg_begin()->setName("cond");
+  Builder.SetInsertPoint(If);
+  LoadInst *Cond = Builder.CreateLoad(F->arg_begin());
+  Builder.CreateCondBr(Cond, Then, Else);
+  Builder.SetInsertPoint(Then);
+  Builder.CreateRet(Builder.getInt64(0));
+  Builder.SetInsertPoint(Else);
+  Builder.CreateRet(Builder.getInt64(1));
+
+  Solver.MarkBlockExecutable(If);
+  Solver.Solve();
+
+  EXPECT_TRUE(Lattice.isUntracked(Solver.getValueState(F)));
+  EXPECT_TRUE(Lattice.isOverdefined(Solver.getFunctionState(F)));
+}
+
+/// Test that we propagate information through arguments.
+///
+/// define internal void @f() {
+///   call void @g(i64 0, i64 1)
+///   call void @g(i64 1, i64 1)
+///   ret void
+/// }
+///
+/// define internal void @g(i64 %a, i64 %b) {
+///   ret void
+/// }
+///
+/// For this test, we initially mark "f" executable, and the solver discovers
+/// "g" because of the calls in "f". The solver computes the state of argument
+/// "a" as overdefined and the state of "b" as constant. The test ensures that
+/// the solver uses the value state map for the arguments, instead of the
+/// function or global variable maps.
+///
+/// In addition, this test demonstrates that ComputeInstructionState can alter
+/// the state of multiple lattice values, in addition to the one associated
+/// with the instruction definition. Each call instruction in this test updates
+/// the state of arguments "a" and "b".
+TEST_F(SparsePropagationTest, ComputeInstructionState) {
+  Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "f", &M);
+  Function *G = Function::Create(
+      FunctionType::get(Builder.getVoidTy(),
+                        {Builder.getInt64Ty(), Builder.getInt64Ty()}, false),
+      GlobalValue::InternalLinkage, "g", &M);
+  Argument *A = G->arg_begin();
+  Argument *B = std::next(G->arg_begin());
+  A->setName("a");
+  B->setName("b");
+  BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
+  BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
+  Builder.SetInsertPoint(FEntry);
+  Builder.CreateCall(G, {Builder.getInt64(0), Builder.getInt64(1)});
+  Builder.CreateCall(G, {Builder.getInt64(1), Builder.getInt64(1)});
+  Builder.CreateRetVoid();
+  Builder.SetInsertPoint(GEntry);
+  Builder.CreateRetVoid();
+
+  Solver.MarkBlockExecutable(FEntry);
+  Solver.Solve();
+
+  EXPECT_TRUE(Lattice.isOverdefined(Solver.getValueState(A)));
+  EXPECT_TRUE(Lattice.isConstant(Solver.getValueState(B)));
+}
+
+/// Test that we can handle exceptional terminator instructions.
+///
+/// declare internal void @p()
+///
+/// declare internal void @g()
+///
+/// define internal void @f() personality i8* bitcast (void ()* @p to i8*) {
+/// entry:
+///   invoke void @g()
+///           to label %exit unwind label %catch.pad
+///
+/// catch.pad:
+///   %0 = catchswitch within none [label %catch.body] unwind to caller
+///
+/// catch.body:
+///   %1 = catchpad within %0 []
+///   catchret from %1 to label %exit
+///
+/// exit:
+///   ret void
+/// }
+///
+/// For this test, we initially mark the entry block executable. The solver
+/// then discovers the rest of the blocks in the function are executable.
+TEST_F(SparsePropagationTest, ExceptionalTerminatorInsts) {
+  Function *P = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "p", &M);
+  Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "g", &M);
+  Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
+                                 GlobalValue::InternalLinkage, "f", &M);
+  Constant *C =
+      ConstantExpr::getCast(Instruction::BitCast, P, Builder.getInt8PtrTy());
+  F->setPersonalityFn(C);
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Pad = BasicBlock::Create(Context, "catch.pad", F);
+  BasicBlock *Body = BasicBlock::Create(Context, "catch.body", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+  Builder.SetInsertPoint(Entry);
+  Builder.CreateInvoke(G, Exit, Pad);
+  Builder.SetInsertPoint(Pad);
+  CatchSwitchInst *CatchSwitch =
+      Builder.CreateCatchSwitch(ConstantTokenNone::get(Context), nullptr, 1);
+  CatchSwitch->addHandler(Body);
+  Builder.SetInsertPoint(Body);
+  CatchPadInst *CatchPad = Builder.CreateCatchPad(CatchSwitch, {});
+  Builder.CreateCatchRet(CatchPad, Exit);
+  Builder.SetInsertPoint(Exit);
+  Builder.CreateRetVoid();
+
+  Solver.MarkBlockExecutable(Entry);
+  Solver.Solve();
+
+  EXPECT_TRUE(Solver.isBlockExecutable(Pad));
+  EXPECT_TRUE(Solver.isBlockExecutable(Body));
+  EXPECT_TRUE(Solver.isBlockExecutable(Exit));
+}