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