carbon-lang/toolchain/sem_ir/dominance_test.cpp

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

#include "toolchain/sem_ir/dominance.h"

#include <gmock/gmock.h>
#include <gtest/gtest.h>

#include <string>

#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Sequence.h"
#include "llvm/ADT/SmallVector.h"
#include "toolchain/parse/node_ids.h"
#include "toolchain/sem_ir/dominance_test_helpers.h"
#include "toolchain/sem_ir/ids.h"
#include "toolchain/sem_ir/typed_insts.h"

namespace Carbon::SemIR {
namespace {

using ::testing::HasSubstr;
using ::testing::IsEmpty;

class DominanceTest : public ::testing::Test, public DominanceTestFile {
 public:
  // Runs the dominance check, and returns the error message it produced, or an
  // empty string if it succeeded.
  auto Verify() -> std::string {
    ErrorOr<Success> result = VerifyDominance(file());
    return result.ok() ? "" : result.error().message();
  }

  // Adds an instruction that refers to `inst_id` as a `MetaInstId`, which names
  // the instruction rather than its value.
  auto AddMetaUse(InstId inst_id) -> InstId {
    return AddNonConstInst(AccessMemberAction{.type_id = TypeType::TypeId,
                                              .base_id = MetaInstId(inst_id),
                                              .name_id = NameId(0)});
  }

  // Adds an instruction whose constant value is an `inst_value` naming
  // `target_id`. This is the form that the operand of a `splice_inst` takes.
  auto AddInstValue(InstId target_id) -> InstId {
    auto value_id = AddInst(InstValue{.type_id = TypeType::TypeId,
                                      .inst_id = MetaInstId(target_id)});
    file().constant_values().Set(value_id,
                                 ConstantId::ForConcreteConstant(value_id));

    auto use_id = AddInst(InstValue{.type_id = TypeType::TypeId,
                                    .inst_id = MetaInstId(target_id)});
    file().constant_values().Set(use_id,
                                 ConstantId::ForConcreteConstant(value_id));
    return use_id;
  }
};

TEST_F(DominanceTest, FunctionWithNoBody) {
  AddFunction();
  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, StraightLineUseAfterEvaluation) {
  auto value_id = AddValue();
  auto use_id = AddUse(value_id);
  AddFunction({AddBlock({value_id, use_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, StraightLineUseBeforeEvaluation) {
  auto value_id = AddValue();
  auto use_id = AddUse(value_id);
  AddFunction({AddBlock({use_id, value_id, AddReturn()})});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceTest, NeverEvaluatedValue) {
  // A non-constant value that is not evaluated anywhere in the body, as would
  // happen for a non-constant global or import, doesn't dominate its uses.
  auto global_id = AddValue();
  auto use_id = AddUse(global_id);
  AddFunction({AddBlock({use_id, AddReturn()})});

  EXPECT_THAT(Verify(),
              HasSubstr("not dominated by any evaluation and is not constant"));
}

TEST_F(DominanceTest, ConstantIsExempt) {
  auto constant_id = AddConstant();
  auto use_id = AddUse(constant_id);
  AddFunction({AddBlock({use_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

// The following three tests pin the allowlists for pre-existing dominance
// violations. Each of them fails if the corresponding allowlist is removed, so
// they should be removed, and the violations diagnosed, together with it.
// See `CollectDeclInsts` and `DominanceVerifier::VerifyOperand`.

TEST_F(DominanceTest, FileScopeInstIsAllowlisted) {
  // A file-scope instruction is evaluated in `__global_init`, if at all, so it
  // doesn't dominate uses in any other function.
  auto global_id = AddValue();
  file().set_top_inst_block_id(AddBlock({global_id}));

  auto use_id = AddUse(global_id);
  AddFunction({AddBlock({use_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, ClassBodyInstIsAllowlisted) {
  // A `let` in a class body produces a `wrapper_binding` that isn't evaluated
  // in any function, but `A.x` can name it from one. This mirrors the
  // `public_global_access` case in
  // `check/testdata/class/access/access_modifiers.carbon`:
  //
  //     class A { let x: i32 = 5; }
  //     let x: i32 = A.x;
  auto binding_id =
      AddNonConstInst(WrapperBinding{.type_id = TypeType::TypeId,
                                     .entity_name_id = EntityNameId::None,
                                     .value_id = AddConstant()});
  auto name_id = file().identifiers().Add("A");
  file().classes().Add({{.name_id = NameId::ForIdentifier(name_id),
                         .parent_scope_id = NameScopeId::Package,
                         .generic_id = GenericId::None,
                         .first_param_node_id = Parse::NodeId::None,
                         .last_param_node_id = Parse::NodeId::None,
                         .pattern_block_id = InstBlockId::Empty,
                         .implicit_param_patterns_id = InstBlockId::None,
                         .param_patterns_id = InstBlockId::Empty,
                         .is_extern = false,
                         .extern_library_id = LibraryNameId::None,
                         .non_owning_decl_id = InstId::None,
                         .first_owning_decl_id = InstId::None},
                        {.self_type_id = TypeType::TypeId,
                         .inheritance_kind = Class::Final,
                         .body_block_id = AddBlock({binding_id})}});

  auto use_id = AddUse(binding_id);
  AddFunction({AddBlock({use_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, ImportRefIsAllowlisted) {
  // A non-constant import isn't evaluated in the importing file at all.
  auto import_id =
      AddNonConstInst(ImportRefLoaded{.type_id = TypeType::TypeId,
                                      .import_ir_inst_id = ImportIRInstId::None,
                                      .entity_name_id = EntityNameId::None});
  auto use_id = AddUse(import_id);
  AddFunction({AddBlock({use_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, MetaInstIdOperandIsExempt) {
  // A `MetaInstId` names the identity of an instruction rather than its value,
  // so it needn't be dominated even though it's evaluated later.
  auto value_id = AddValue();
  auto use_id = AddMetaUse(value_id);
  AddFunction({AddBlock({use_id, value_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, ErroneousFileIsNotChecked) {
  auto value_id = AddValue();
  auto use_id = AddUse(value_id);
  AddFunction({AddBlock({use_id, value_id, AddReturn()})});
  file().set_has_errors(true);

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, FileVerifyChecksDominance) {
  // `File::Verify` should run the dominance check as well as its other checks.
  auto value_id = AddValue();
  auto use_id = AddUse(value_id);
  AddFunction({AddBlock({use_id, value_id, AddReturn()})});

  auto result = file().Verify();
  ASSERT_FALSE(result.ok());
  EXPECT_THAT(result.error().message(),
              HasSubstr("not dominated by any evaluation"));
}

// A fixture for tests over a diamond:
//
//     entry
//     /   \
//   then  else
//     \   /
//      exit
class DominanceDiamondTest : public DominanceTest {
 public:
  // Builds the diamond, prefixing each block with the given instructions.
  auto BuildDiamond(llvm::ArrayRef<InstId> entry_insts,
                    llvm::ArrayRef<InstId> then_insts,
                    llvm::ArrayRef<InstId> else_insts,
                    llvm::ArrayRef<InstId> exit_insts) -> void {
    auto entry_id = AddBlock();
    auto then_id = AddBlock();
    auto else_id = AddBlock();
    auto exit_id = AddBlock();

    SetBlock(entry_id, entry_insts, {AddBranchIf(then_id), AddBranch(else_id)});
    SetBlock(then_id, then_insts, {AddBranch(exit_id)});
    SetBlock(else_id, else_insts, {AddBranch(exit_id)});
    SetBlock(exit_id, exit_insts, {AddReturn()});

    AddFunction({entry_id, then_id, else_id, exit_id});
  }
};

TEST_F(DominanceDiamondTest, EvaluationInEntryDominatesAllBranches) {
  auto value_id = AddValue();
  BuildDiamond(/*entry_insts=*/{value_id}, /*then_insts=*/{AddUse(value_id)},
               /*else_insts=*/{AddUse(value_id)},
               /*exit_insts=*/{AddUse(value_id)});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceDiamondTest, EvaluationInOneBranchDoesNotDominateTheOther) {
  auto value_id = AddValue();
  BuildDiamond(/*entry_insts=*/{}, /*then_insts=*/{value_id},
               /*else_insts=*/{AddUse(value_id)}, /*exit_insts=*/{});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceDiamondTest, EvaluationInOneBranchDoesNotDominateJoin) {
  auto value_id = AddValue();
  BuildDiamond(/*entry_insts=*/{}, /*then_insts=*/{value_id},
               /*else_insts=*/{}, /*exit_insts=*/{AddUse(value_id)});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceDiamondTest, EvaluationInBothBranchesDoesNotDominateJoin) {
  // The same instruction can be evaluated in more than one block; a use is
  // dominated if it's dominated by any of the evaluations. Here neither
  // evaluation dominates the join, so this is still an error.
  auto value_id = AddValue();
  BuildDiamond(/*entry_insts=*/{}, /*then_insts=*/{value_id},
               /*else_insts=*/{value_id}, /*exit_insts=*/{AddUse(value_id)});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceDiamondTest, MultipleEvaluationsEachDominateTheirOwnUse) {
  auto value_id = AddValue();
  BuildDiamond(/*entry_insts=*/{},
               /*then_insts=*/{value_id, AddUse(value_id)},
               /*else_insts=*/{value_id, AddUse(value_id)},
               /*exit_insts=*/{});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, UnreachableBlock) {
  auto entry_id = AddBlock({AddReturn()});
  auto unreachable_id = AddBlock({AddReturn()});
  AddFunction({entry_id, unreachable_id});

  EXPECT_THAT(Verify(), HasSubstr("is unreachable from entry block"));
}

TEST_F(DominanceTest, BranchOutsideFunctionBody) {
  auto outside_id = AddBlock({AddReturn()});
  auto entry_id = AddBlock({AddBranch(outside_id)});
  AddFunction({entry_id});

  EXPECT_THAT(Verify(), HasSubstr("which is not in function body"));
}

TEST_F(DominanceTest, RepeatedBranchToSameBlock) {
  // A block can branch to the same block more than once, for example when both
  // arms of an `if` are empty. That produces a duplicate control flow edge,
  // which shouldn't disturb the dominance computation: the exit block is still
  // dominated by the entry block.
  auto entry_id = AddBlock();
  auto exit_id = AddBlock();

  auto value_id = AddValue();
  SetBlock(entry_id, {value_id, AddBranchIf(exit_id), AddBranch(exit_id)});
  SetBlock(exit_id, {AddUse(value_id), AddReturn()});
  AddFunction({entry_id, exit_id});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, LongChainOfBlocks) {
  // A function body long enough that walking it recursively would overflow the
  // stack. Each block uses a value evaluated in the block before it, so the
  // dominator tree is a single chain.
  constexpr int NumBlocks = 100'000;

  llvm::SmallVector<InstBlockId> block_ids;
  block_ids.reserve(NumBlocks);
  for (auto _ : llvm::seq(NumBlocks)) {
    block_ids.push_back(AddBlock());
  }

  auto value_id = AddValue();
  for (auto [i, block] : llvm::enumerate(block_ids)) {
    SetBlock(block,
             {i == 0 ? value_id : AddUse(value_id),
              i + 1 == NumBlocks ? AddReturn() : AddBranch(block_ids[i + 1])});
  }
  AddFunction(block_ids);

  EXPECT_THAT(Verify(), IsEmpty());
}

// A loop:
//
//   entry -> header -> body -> header
//                   -> exit
class DominanceLoopTest : public DominanceTest {
 public:
  // Builds the loop, prefixing the header and body blocks with the given
  // instructions.
  auto BuildLoop(llvm::ArrayRef<InstId> header_insts,
                 llvm::ArrayRef<InstId> body_insts) -> void {
    auto entry_id = AddBlock();
    auto header_id = AddBlock();
    auto body_id = AddBlock();
    auto exit_id = AddBlock();

    SetBlock(entry_id, {AddBranch(header_id)});
    SetBlock(header_id, header_insts,
             {AddBranchIf(body_id), AddBranch(exit_id)});
    SetBlock(body_id, body_insts, {AddBranch(header_id)});
    SetBlock(exit_id, {AddReturn()});

    AddFunction({entry_id, header_id, body_id, exit_id});
  }
};

TEST_F(DominanceLoopTest, HeaderEvaluationDominatesBody) {
  auto value_id = AddValue();
  BuildLoop(/*header_insts=*/{value_id}, /*body_insts=*/{AddUse(value_id)});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceLoopTest, BodyEvaluationDoesNotDominateHeader) {
  // The back edge means the body is executed before the header on some paths,
  // but not on the path that first reaches the header.
  auto value_id = AddValue();
  BuildLoop(/*header_insts=*/{AddUse(value_id)}, /*body_insts=*/{value_id});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceTest, SpliceBlockEvaluatesItsContents) {
  auto generic_id = AddGeneric();

  auto value_id = AddValue();

  // A spliced block that evaluates a use of `value_id` and produces it.
  auto inner_id = AddUse(value_id);
  auto splice_block_id =
      AddInst(SpliceBlock{.type_id = TypeType::TypeId,
                          .block_id = AbsoluteInstBlockId(AddBlock({inner_id})),
                          .result_id = inner_id});

  auto action_id = AddInstValue(splice_block_id);
  auto splice_id =
      AddInst(SpliceInst{.type_id = TypeType::TypeId, .inst_id = action_id});

  // The use after the splice sees the instructions the splice evaluated.
  auto late_use_id = AddUse(inner_id);
  AddFunction(
      {AddBlock({value_id, action_id, splice_id, late_use_id, AddReturn()})},
      generic_id);

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, SpliceBlockUsingLaterValue) {
  auto generic_id = AddGeneric();

  // A spliced block that uses a value evaluated after the splice.
  auto value_id = AddValue();
  auto inner_id = AddUse(value_id);
  auto splice_block_id =
      AddInst(SpliceBlock{.type_id = TypeType::TypeId,
                          .block_id = AbsoluteInstBlockId(AddBlock({inner_id})),
                          .result_id = inner_id});

  auto action_id = AddInstValue(splice_block_id);
  auto splice_id =
      AddInst(SpliceInst{.type_id = TypeType::TypeId, .inst_id = action_id});

  AddFunction({AddBlock({action_id, splice_id, value_id, AddReturn()})},
              generic_id);

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

// A generic function whose body contains a `splice_inst` whose operand is a
// symbolic constant, so that the splice resolves to a different instruction
// when the body is checked as a generic than when it's checked in the generic's
// specific.
class DominanceSpecificSpliceTest : public DominanceTest {
 protected:
  // Builds the function. Its body evaluates `early_id`, then splices in an
  // instruction, then evaluates `late_id`. The splice produces
  // `generic_spliced_id` when the body is checked as a generic, and
  // `specific_spliced_id` when it's checked in the specific.
  auto BuildFunction(InstId early_id, InstId late_id, InstId generic_spliced_id,
                     InstId specific_spliced_id) -> void {
    // In the specific, the splice's operand takes its value from the entry of
    // the specific's value block that its symbolic constant indexes.
    auto generic_id = AddGeneric(AddBlock({AddInstValue(specific_spliced_id)}));

    // In the generic, it takes the value of the unattached form of that
    // symbolic constant, which is the constant value of the instruction that
    // defines the constant.
    auto unattached_id =
        AddInst(InstValue{.type_id = TypeType::TypeId,
                          .inst_id = MetaInstId(generic_spliced_id)});
    file().constant_values().Set(
        unattached_id, file().constant_values().AddSymbolicConstant(
                           {.inst_id = unattached_id,
                            .generic_id = GenericId::None,
                            .index = GenericInstIndex::None,
                            .dependence = ConstantDependence::Checked}));

    auto action_id =
        AddInst(InstValue{.type_id = TypeType::TypeId,
                          .inst_id = MetaInstId(generic_spliced_id)});
    file().constant_values().Set(
        action_id,
        file().constant_values().AddSymbolicConstant(
            {.inst_id = unattached_id,
             .generic_id = generic_id,
             .index = GenericInstIndex(GenericInstIndex::Declaration, 0),
             .dependence = ConstantDependence::Checked}));

    auto splice_id =
        AddInst(SpliceInst{.type_id = TypeType::TypeId, .inst_id = action_id});
    AddFunction(
        {AddBlock({early_id, action_id, splice_id, late_id, AddReturn()})},
        generic_id);
  }
};

TEST_F(DominanceSpecificSpliceTest, SplicedUseInSpecificIsDominated) {
  auto early_id = AddValue();
  auto late_id = AddValue();
  BuildFunction(early_id, late_id, /*generic_spliced_id=*/AddUse(early_id),
                /*specific_spliced_id=*/AddUse(early_id));

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceSpecificSpliceTest, SplicedUseInSpecificIsNotDominated) {
  // The instruction that the specific splices in uses a value that isn't
  // evaluated until after the splice. That's only visible when the body is
  // checked in the specific, because the generic splices in a use of a value
  // that is evaluated before it.
  auto early_id = AddValue();
  auto late_id = AddValue();
  BuildFunction(early_id, late_id, /*generic_spliced_id=*/AddUse(early_id),
                /*specific_spliced_id=*/AddUse(late_id));

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

TEST_F(DominanceTest, SpecificInstDominatedByEvaluation) {
  auto generic_id = AddGeneric();
  auto specific_id = file().specifics().GetOrAdd(generic_id, InstBlockId::Empty,
                                                 /*identified=*/false);
  auto value_id = AddValue();
  auto specific_inst_id =
      AddNonConstInst(SpecificInst{.type_id = TypeType::TypeId,
                                   .inst_id = value_id,
                                   .specific_id = specific_id});
  AddFunction({AddBlock({value_id, specific_inst_id, AddReturn()})});

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceTest, SpecificInstNotDominated) {
  auto generic_id = AddGeneric();
  auto specific_id = file().specifics().GetOrAdd(generic_id, InstBlockId::Empty,
                                                 /*identified=*/false);
  auto value_id = AddValue();
  auto specific_inst_id =
      AddNonConstInst(SpecificInst{.type_id = TypeType::TypeId,
                                   .inst_id = value_id,
                                   .specific_id = specific_id});
  AddFunction({AddBlock({specific_inst_id, value_id, AddReturn()})});

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

// A generic function whose body uses an instruction that has a template
// symbolic constant value in the generic, which resolves to the first entry of
// the specific's declaration value block when checked in the specific.
class DominanceOperandConstantInSpecificTest : public DominanceTest {
 protected:
  auto MakeSymbolicInGeneric(GenericId generic_id) -> InstId {
    auto unattached_id = AddInst(
        BoolLiteral{.type_id = TypeType::TypeId, .value = BoolValue(false)});
    file().constant_values().Set(
        unattached_id, file().constant_values().AddSymbolicConstant(
                           {.inst_id = unattached_id,
                            .generic_id = GenericId::None,
                            .index = GenericInstIndex::None,
                            .dependence = ConstantDependence::Template}));

    auto inst_id = AddInst(
        BoolLiteral{.type_id = TypeType::TypeId, .value = BoolValue(false)});
    file().constant_values().Set(
        inst_id,
        file().constant_values().AddSymbolicConstant(
            {.inst_id = unattached_id,
             .generic_id = generic_id,
             .index = GenericInstIndex(GenericInstIndex::Declaration, 0),
             .dependence = ConstantDependence::Template}));
    return inst_id;
  }
};

TEST_F(DominanceOperandConstantInSpecificTest, ConstantInSpecificIsExempt) {
  // `sym_id` is a symbolic constant in the generic and is constant in the
  // specific, so using it before its evaluation passes verification in both.
  auto generic_id = AddGeneric(AddBlock({AddConstant()}));
  auto sym_id = MakeSymbolicInGeneric(generic_id);
  AddFunction({AddBlock({AddUse(sym_id), sym_id, AddReturn()})}, generic_id);

  EXPECT_THAT(Verify(), IsEmpty());
}

TEST_F(DominanceOperandConstantInSpecificTest,
       NonConstantInSpecificRequiresDominance) {
  // `sym_id` is a symbolic constant in the generic, so using it before its
  // evaluation passes generic verification, but in the specific it resolves to
  // a non-constant value (represented by `InstId::None` in the value block
  // below), so we require its evaluation to dominate the use.
  auto generic_id = AddGeneric(AddBlock({InstId::None}));
  auto sym_id = MakeSymbolicInGeneric(generic_id);
  AddFunction({AddBlock({AddUse(sym_id), sym_id, AddReturn()})}, generic_id);

  EXPECT_THAT(Verify(), HasSubstr("not dominated by any evaluation"));
}

}  // namespace
}  // namespace Carbon::SemIR