SparsePropagation.cpp | Explore in Territory

//===- SparsePropagation.cpp - Unit tests for the generic solver ----------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/SparsePropagation.h"
#include "llvm/ADT/PointerIntPair.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Module.h"
#include "gtest/gtest.h"
usingnamespacellvm;

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 { … };

/// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
/// The PointerIntPair header provides a DenseMapInfo specialization, so using
/// these as LatticeKeys is fine.
TestLatticeKey;
} // 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> { … };
} // 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 { … };

/// 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> { … };

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

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// 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) { … }

/// Test that we can handle exceptional terminator instructions.
///
/// declare internal void @p()
///
/// declare internal void @g()
///
/// define internal void @f() personality ptr @p {
/// 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) { … }
llvm/llvm/unittests/Analysis/SparsePropagation.cpp
