unittests/Analysis/SparsePropagation.cpp - llvm - Git at Google

 //===- 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 {
 /// To enable interprocedural analysis, we assign LLVM values to the following
 /// groups. The register group represents SSA registers, the return group
 /// represents the return values of functions, and the memory group represents
 /// in-memory values. An LLVM Value can technically be in more than one group.
 /// It's necessary to distinguish these groups so we can, for example, track a
 /// global variable separately from the value stored at its location.
 enum class IPOGrouping { Register, Return, Memory };

 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
 /// The PointerIntPair header provides a DenseMapInfo specialization, so using
 /// these as LatticeKeys is fine.
 using TestLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
 } // namespace

 namespace llvm {
 /// A specialization of LatticeKeyInfo for TestLatticeKeys. The generic solver
 /// must translate between LatticeKeys and LLVM Values when adding Values to
 /// its work list and inspecting the state of control-flow related values.
 template <> struct LatticeKeyInfo<TestLatticeKey> {
   static inline Value *getValueFromLatticeKey(TestLatticeKey Key) {
     return Key.getPointer();
   }
   static inline TestLatticeKey getLatticeKeyFromValue(Value *V) {
     return TestLatticeKey(V, IPOGrouping::Register);
   }
 };
 } // namespace llvm

 namespace {
 /// This class defines a simple test lattice value that could be used for
 /// solving problems similar to constant propagation. The value is maintained
 /// as a PointerIntPair.
 class TestLatticeVal {
 public:
   /// The states of the lattices value. Only the ConstantVal state is
   /// interesting; the rest are special states used by the generic solver. The
   /// UntrackedVal 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 UntrackedVal state, it's users are not notified.
   enum TestLatticeStateTy {
     UndefinedVal,
     ConstantVal,
     OverdefinedVal,
     UntrackedVal
   };

   TestLatticeVal() : LatticeVal(nullptr, UndefinedVal) {}
   TestLatticeVal(Constant *C, TestLatticeStateTy State)
       : LatticeVal(C, State) {}

   /// Return true if this lattice value is in the Constant state. This is used
   /// for checking the solver results.
   bool isConstant() const { return LatticeVal.getInt() == ConstantVal; }

   /// Return true if this lattice value is in the Overdefined state. This is
   /// used for checking the solver results.
   bool isOverdefined() const { return LatticeVal.getInt() == OverdefinedVal; }

   bool operator==(const TestLatticeVal &RHS) const {
     return LatticeVal == RHS.LatticeVal;
   }

   bool operator!=(const TestLatticeVal &RHS) const {
     return LatticeVal != RHS.LatticeVal;
   }

 private:
   /// A simple lattice value type for problems similar to constant propagation.
   /// It holds the constant value and the lattice state.
   PointerIntPair<const Constant *, 2, TestLatticeStateTy> LatticeVal;
 };

 /// 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<TestLatticeKey, TestLatticeVal> {
 public:
   /// Construct a new test lattice function with special values for the
   /// Undefined, Overdefined, and Untracked states.
   TestLatticeFunc()
       : AbstractLatticeFunction(
             TestLatticeVal(nullptr, TestLatticeVal::UndefinedVal),
             TestLatticeVal(nullptr, TestLatticeVal::OverdefinedVal),
             TestLatticeVal(nullptr, TestLatticeVal::UntrackedVal)) {}

   /// Compute and return a TestLatticeVal for the given TestLatticeKey. For the
   /// test analysis, a LatticeKey will begin in the undefined state, unless it
   /// represents an LLVM Constant in the register grouping.
   TestLatticeVal ComputeLatticeVal(TestLatticeKey Key) override {
     if (Key.getInt() == IPOGrouping::Register)
       if (auto *C = dyn_cast<Constant>(Key.getPointer()))
         return TestLatticeVal(C, TestLatticeVal::ConstantVal);
     return getUndefVal();
   }

   /// 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.
   TestLatticeVal MergeValues(TestLatticeVal X, TestLatticeVal 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, DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
       SparseSolver<TestLatticeKey, TestLatticeVal> &SS) override {
     switch (I.getOpcode()) {
     case Instruction::Call:
       return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
     case Instruction::Ret:
       return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
     case Instruction::Store:
       return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
     default:
       return visitInst(I, ChangedValues, SS);
     }
   }

 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,
                      DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
                      SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
     Function *F = CS.getCalledFunction();
     Instruction *I = CS.getInstruction();
     auto RegI = TestLatticeKey(I, IPOGrouping::Register);
     if (!F) {
       ChangedValues[RegI] = getOverdefinedVal();
       return;
     }
     SS.MarkBlockExecutable(&F->front());
     for (Argument &A : F->args()) {
       auto RegFormal = TestLatticeKey(&A, IPOGrouping::Register);
       auto RegActual =
           TestLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
       ChangedValues[RegFormal] =
           MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
     }
     auto RetF = TestLatticeKey(F, IPOGrouping::Return);
     ChangedValues[RegI] =
         MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
   }

   /// 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,
                    DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
                    SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
     Function *F = I.getParent()->getParent();
     if (F->getReturnType()->isVoidTy())
       return;
     auto RegR = TestLatticeKey(I.getReturnValue(), IPOGrouping::Register);
     auto RetF = TestLatticeKey(F, IPOGrouping::Return);
     ChangedValues[RetF] =
         MergeValues(SS.getValueState(RegR), SS.getValueState(RetF));
   }

   /// 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,
                   DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
                   SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
     auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
     if (!GV)
       return;
     auto RegVal = TestLatticeKey(I.getValueOperand(), IPOGrouping::Register);
     auto MemPtr = TestLatticeKey(GV, IPOGrouping::Memory);
     ChangedValues[MemPtr] =
         MergeValues(SS.getValueState(RegVal), SS.getValueState(MemPtr));
   }

   /// Handle all other instructions. All other instructions are marked
   /// overdefined.
   void visitInst(Instruction &I,
                  DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
                  SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
     auto RegI = TestLatticeKey(&I, IPOGrouping::Register);
     ChangedValues[RegI] = 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<TestLatticeKey, TestLatticeVal> Solver;

 public:
   SparsePropagationTest()
       : M("", Context), Builder(Context), Solver(&Lattice) {}
 };
 } // namespace

 /// 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, and the
 /// solver computes the lattice state of the global variable as constant.
 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();

   auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
   EXPECT_TRUE(Solver.getExistingValueState(MemGV).isConstant());
 }

 /// 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, and the
 /// solver computes the lattice state of the global variable as overdefined.
 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();

   auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
   EXPECT_TRUE(Solver.getExistingValueState(MemGV).isOverdefined());
 }

 /// 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 1
 ///
 /// else:
 ///   ret i64 1
 /// }
 ///
 /// For this test, we initially mark "f" executable, and the solver computes
 /// the return value of the function as constant.
 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();

   auto RetF = TestLatticeKey(F, IPOGrouping::Return);
   EXPECT_TRUE(Solver.getExistingValueState(RetF).isConstant());
 }

 /// 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, and the solver computes
 /// the return value of the function as overdefined.
 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();

   auto RetF = TestLatticeKey(F, IPOGrouping::Return);
   EXPECT_TRUE(Solver.getExistingValueState(RetF).isOverdefined());
 }

 /// 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.
 ///
 /// 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();

   auto RegA = TestLatticeKey(A, IPOGrouping::Register);
   auto RegB = TestLatticeKey(B, IPOGrouping::Register);
   EXPECT_TRUE(Solver.getExistingValueState(RegA).isOverdefined());
   EXPECT_TRUE(Solver.getExistingValueState(RegB).isConstant());
 }

 /// 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));
 }
	//===- 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 {
	/// To enable interprocedural analysis, we assign LLVM values to the following
	/// groups. The register group represents SSA registers, the return group
	/// represents the return values of functions, and the memory group represents
	/// in-memory values. An LLVM Value can technically be in more than one group.
	/// It's necessary to distinguish these groups so we can, for example, track a
	/// global variable separately from the value stored at its location.
	enum class IPOGrouping { Register, Return, Memory };

	/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
	/// The PointerIntPair header provides a DenseMapInfo specialization, so using
	/// these as LatticeKeys is fine.
	using TestLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
	} // namespace

	namespace llvm {
	/// A specialization of LatticeKeyInfo for TestLatticeKeys. The generic solver
	/// must translate between LatticeKeys and LLVM Values when adding Values to
	/// its work list and inspecting the state of control-flow related values.
	template <> struct LatticeKeyInfo<TestLatticeKey> {
	static inline Value *getValueFromLatticeKey(TestLatticeKey Key) {
	return Key.getPointer();
	}
	static inline TestLatticeKey getLatticeKeyFromValue(Value *V) {
	return TestLatticeKey(V, IPOGrouping::Register);
	}
	};
	} // namespace llvm

	namespace {
	/// This class defines a simple test lattice value that could be used for
	/// solving problems similar to constant propagation. The value is maintained
	/// as a PointerIntPair.
	class TestLatticeVal {
	public:
	/// The states of the lattices value. Only the ConstantVal state is
	/// interesting; the rest are special states used by the generic solver. The
	/// UntrackedVal 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 UntrackedVal state, it's users are not notified.
	enum TestLatticeStateTy {
	UndefinedVal,
	ConstantVal,
	OverdefinedVal,
	UntrackedVal
	};

	TestLatticeVal() : LatticeVal(nullptr, UndefinedVal) {}
	TestLatticeVal(Constant *C, TestLatticeStateTy State)
	: LatticeVal(C, State) {}

	/// Return true if this lattice value is in the Constant state. This is used
	/// for checking the solver results.
	bool isConstant() const { return LatticeVal.getInt() == ConstantVal; }

	/// Return true if this lattice value is in the Overdefined state. This is
	/// used for checking the solver results.
	bool isOverdefined() const { return LatticeVal.getInt() == OverdefinedVal; }

	bool operator==(const TestLatticeVal &RHS) const {
	return LatticeVal == RHS.LatticeVal;
	}

	bool operator!=(const TestLatticeVal &RHS) const {
	return LatticeVal != RHS.LatticeVal;
	}

	private:
	/// A simple lattice value type for problems similar to constant propagation.
	/// It holds the constant value and the lattice state.
	PointerIntPair<const Constant *, 2, TestLatticeStateTy> LatticeVal;
	};

	/// 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<TestLatticeKey, TestLatticeVal> {
	public:
	/// Construct a new test lattice function with special values for the
	/// Undefined, Overdefined, and Untracked states.
	TestLatticeFunc()
	: AbstractLatticeFunction(
	TestLatticeVal(nullptr, TestLatticeVal::UndefinedVal),
	TestLatticeVal(nullptr, TestLatticeVal::OverdefinedVal),
	TestLatticeVal(nullptr, TestLatticeVal::UntrackedVal)) {}

	/// Compute and return a TestLatticeVal for the given TestLatticeKey. For the
	/// test analysis, a LatticeKey will begin in the undefined state, unless it
	/// represents an LLVM Constant in the register grouping.
	TestLatticeVal ComputeLatticeVal(TestLatticeKey Key) override {
	if (Key.getInt() == IPOGrouping::Register)
	if (auto *C = dyn_cast<Constant>(Key.getPointer()))
	return TestLatticeVal(C, TestLatticeVal::ConstantVal);
	return getUndefVal();
	}

	/// 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.
	TestLatticeVal MergeValues(TestLatticeVal X, TestLatticeVal 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, DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
	SparseSolver<TestLatticeKey, TestLatticeVal> &SS) override {
	switch (I.getOpcode()) {
	case Instruction::Call:
	return visitCallSite(cast<CallInst>(&I), ChangedValues, SS);
	case Instruction::Ret:
	return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
	case Instruction::Store:
	return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
	default:
	return visitInst(I, ChangedValues, SS);
	}
	}

	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,
	DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
	SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
	Function *F = CS.getCalledFunction();
	Instruction *I = CS.getInstruction();
	auto RegI = TestLatticeKey(I, IPOGrouping::Register);
	if (!F) {
	ChangedValues[RegI] = getOverdefinedVal();
	return;
	}
	SS.MarkBlockExecutable(&F->front());
	for (Argument &A : F->args()) {
	auto RegFormal = TestLatticeKey(&A, IPOGrouping::Register);
	auto RegActual =
	TestLatticeKey(CS.getArgument(A.getArgNo()), IPOGrouping::Register);
	ChangedValues[RegFormal] =
	MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
	}
	auto RetF = TestLatticeKey(F, IPOGrouping::Return);
	ChangedValues[RegI] =
	MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
	}

	/// 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,
	DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
	SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
	Function *F = I.getParent()->getParent();
	if (F->getReturnType()->isVoidTy())
	return;
	auto RegR = TestLatticeKey(I.getReturnValue(), IPOGrouping::Register);
	auto RetF = TestLatticeKey(F, IPOGrouping::Return);
	ChangedValues[RetF] =
	MergeValues(SS.getValueState(RegR), SS.getValueState(RetF));
	}

	/// 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,
	DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
	SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
	auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
	if (!GV)
	return;
	auto RegVal = TestLatticeKey(I.getValueOperand(), IPOGrouping::Register);
	auto MemPtr = TestLatticeKey(GV, IPOGrouping::Memory);
	ChangedValues[MemPtr] =
	MergeValues(SS.getValueState(RegVal), SS.getValueState(MemPtr));
	}

	/// Handle all other instructions. All other instructions are marked
	/// overdefined.
	void visitInst(Instruction &I,
	DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
	SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
	auto RegI = TestLatticeKey(&I, IPOGrouping::Register);
	ChangedValues[RegI] = 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<TestLatticeKey, TestLatticeVal> Solver;

	public:
	SparsePropagationTest()
	: M("", Context), Builder(Context), Solver(&Lattice) {}
	};
	} // namespace

	/// 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, and the
	/// solver computes the lattice state of the global variable as constant.
	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();

	auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
	EXPECT_TRUE(Solver.getExistingValueState(MemGV).isConstant());
	}

	/// 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, and the
	/// solver computes the lattice state of the global variable as overdefined.
	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();

	auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
	EXPECT_TRUE(Solver.getExistingValueState(MemGV).isOverdefined());
	}

	/// 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 1
	///
	/// else:
	/// ret i64 1
	/// }
	///
	/// For this test, we initially mark "f" executable, and the solver computes
	/// the return value of the function as constant.
	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();

	auto RetF = TestLatticeKey(F, IPOGrouping::Return);
	EXPECT_TRUE(Solver.getExistingValueState(RetF).isConstant());
	}

	/// 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, and the solver computes
	/// the return value of the function as overdefined.
	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();

	auto RetF = TestLatticeKey(F, IPOGrouping::Return);
	EXPECT_TRUE(Solver.getExistingValueState(RetF).isOverdefined());
	}

	/// 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.
	///
	/// 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();

	auto RegA = TestLatticeKey(A, IPOGrouping::Register);
	auto RegB = TestLatticeKey(B, IPOGrouping::Register);
	EXPECT_TRUE(Solver.getExistingValueState(RegA).isOverdefined());
	EXPECT_TRUE(Solver.getExistingValueState(RegB).isConstant());
	}

	/// 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));
	}