llvm/unittests/Analysis/SparsePropagation.cpp

   1 //===- SparsePropagation.cpp - Unit tests for the generic solver ----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/Analysis/SparsePropagation.h"
  10 #include "llvm/ADT/PointerIntPair.h"
  11 #include "llvm/IR/IRBuilder.h"
  12 #include "llvm/IR/Module.h"
  13 #include "gtest/gtest.h"
  14 using namespace llvm;
  15
  16 namespace {
  17 /// To enable interprocedural analysis, we assign LLVM values to the following
  18 /// groups. The register group represents SSA registers, the return group
  19 /// represents the return values of functions, and the memory group represents
  20 /// in-memory values. An LLVM Value can technically be in more than one group.
  21 /// It's necessary to distinguish these groups so we can, for example, track a
  22 /// global variable separately from the value stored at its location.
  23 enum class IPOGrouping { Register, Return, Memory };
  24
  25 /// Our LatticeKeys are PointerIntPairs composed of LLVM values and groupings.
  26 /// The PointerIntPair header provides a DenseMapInfo specialization, so using
  27 /// these as LatticeKeys is fine.
  28 using TestLatticeKey = PointerIntPair<Value *, 2, IPOGrouping>;
  29 } // namespace
  30
  31 namespace llvm {
  32 /// A specialization of LatticeKeyInfo for TestLatticeKeys. The generic solver
  33 /// must translate between LatticeKeys and LLVM Values when adding Values to
  34 /// its work list and inspecting the state of control-flow related values.
  35 template <> struct LatticeKeyInfo<TestLatticeKey> {
  36   static inline Value *getValueFromLatticeKey(TestLatticeKey Key) {
  37     return Key.getPointer();
  38   }
  39   static inline TestLatticeKey getLatticeKeyFromValue(Value *V) {
  40     return TestLatticeKey(V, IPOGrouping::Register);
  41   }
  42 };
  43 } // namespace llvm
  44
  45 namespace {
  46 /// This class defines a simple test lattice value that could be used for
  47 /// solving problems similar to constant propagation. The value is maintained
  48 /// as a PointerIntPair.
  49 class TestLatticeVal {
  50 public:
  51   /// The states of the lattices value. Only the ConstantVal state is
  52   /// interesting; the rest are special states used by the generic solver. The
  53   /// UntrackedVal state differs from the other three in that the generic
  54   /// solver uses it to avoid doing unnecessary work. In particular, when a
  55   /// value moves to the UntrackedVal state, it's users are not notified.
  56   enum TestLatticeStateTy {
  57     UndefinedVal,
  58     ConstantVal,
  59     OverdefinedVal,
  60     UntrackedVal
  61   };
  62
  63   TestLatticeVal() : LatticeVal(nullptr, UndefinedVal) {}
  64   TestLatticeVal(Constant *C, TestLatticeStateTy State)
  65       : LatticeVal(C, State) {}
  66
  67   /// Return true if this lattice value is in the Constant state. This is used
  68   /// for checking the solver results.
  69   bool isConstant() const { return LatticeVal.getInt() == ConstantVal; }
  70
  71   /// Return true if this lattice value is in the Overdefined state. This is
  72   /// used for checking the solver results.
  73   bool isOverdefined() const { return LatticeVal.getInt() == OverdefinedVal; }
  74
  75   bool operator==(const TestLatticeVal &RHS) const {
  76     return LatticeVal == RHS.LatticeVal;
  77   }
  78
  79   bool operator!=(const TestLatticeVal &RHS) const {
  80     return LatticeVal != RHS.LatticeVal;
  81   }
  82
  83 private:
  84   /// A simple lattice value type for problems similar to constant propagation.
  85   /// It holds the constant value and the lattice state.
  86   PointerIntPair<const Constant *, 2, TestLatticeStateTy> LatticeVal;
  87 };
  88
  89 /// This class defines a simple test lattice function that could be used for
  90 /// solving problems similar to constant propagation. The test lattice differs
  91 /// from a "real" lattice in a few ways. First, it initializes all return
  92 /// values, values stored in global variables, and arguments in the undefined
  93 /// state. This means that there are no limitations on what we can track
  94 /// interprocedurally. For simplicity, all global values in the tests will be
  95 /// given internal linkage, since this is not something this lattice function
  96 /// tracks. Second, it only handles the few instructions necessary for the
  97 /// tests.
  98 class TestLatticeFunc
  99     : public AbstractLatticeFunction<TestLatticeKey, TestLatticeVal> {
 100 public:
 101   /// Construct a new test lattice function with special values for the
 102   /// Undefined, Overdefined, and Untracked states.
 103   TestLatticeFunc()
 104       : AbstractLatticeFunction(
 105             TestLatticeVal(nullptr, TestLatticeVal::UndefinedVal),
 106             TestLatticeVal(nullptr, TestLatticeVal::OverdefinedVal),
 107             TestLatticeVal(nullptr, TestLatticeVal::UntrackedVal)) {}
 108
 109   /// Compute and return a TestLatticeVal for the given TestLatticeKey. For the
 110   /// test analysis, a LatticeKey will begin in the undefined state, unless it
 111   /// represents an LLVM Constant in the register grouping.
 112   TestLatticeVal ComputeLatticeVal(TestLatticeKey Key) override {
 113     if (Key.getInt() == IPOGrouping::Register)
 114       if (auto *C = dyn_cast<Constant>(Key.getPointer()))
 115         return TestLatticeVal(C, TestLatticeVal::ConstantVal);
 116     return getUndefVal();
 117   }
 118
 119   /// Merge the two given lattice values. This merge should be equivalent to
 120   /// what is done for constant propagation. That is, the resulting lattice
 121   /// value is constant only if the two given lattice values are constant and
 122   /// hold the same value.
 123   TestLatticeVal MergeValues(TestLatticeVal X, TestLatticeVal Y) override {
 124     if (X == getUntrackedVal() || Y == getUntrackedVal())
 125       return getUntrackedVal();
 126     if (X == getOverdefinedVal() || Y == getOverdefinedVal())
 127       return getOverdefinedVal();
 128     if (X == getUndefVal() && Y == getUndefVal())
 129       return getUndefVal();
 130     if (X == getUndefVal())
 131       return Y;
 132     if (Y == getUndefVal())
 133       return X;
 134     if (X == Y)
 135       return X;
 136     return getOverdefinedVal();
 137   }
 138
 139   /// Compute the lattice values that change as a result of executing the given
 140   /// instruction. We only handle the few instructions needed for the tests.
 141   void ComputeInstructionState(
 142       Instruction &I, DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
 143       SparseSolver<TestLatticeKey, TestLatticeVal> &SS) override {
 144     switch (I.getOpcode()) {
 145     case Instruction::Call:
 146       return visitCallBase(cast<CallBase>(I), ChangedValues, SS);
 147     case Instruction::Ret:
 148       return visitReturn(*cast<ReturnInst>(&I), ChangedValues, SS);
 149     case Instruction::Store:
 150       return visitStore(*cast<StoreInst>(&I), ChangedValues, SS);
 151     default:
 152       return visitInst(I, ChangedValues, SS);
 153     }
 154   }
 155
 156 private:
 157   /// Handle call sites. The state of a called function's argument is the merge
 158   /// of the current formal argument state with the call site's corresponding
 159   /// actual argument state. The call site state is the merge of the call site
 160   /// state with the returned value state of the called function.
 161   void visitCallBase(CallBase &I,
 162                      DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
 163                      SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
 164     Function *F = I.getCalledFunction();
 165     auto RegI = TestLatticeKey(&I, IPOGrouping::Register);
 166     if (!F) {
 167       ChangedValues[RegI] = getOverdefinedVal();
 168       return;
 169     }
 170     SS.MarkBlockExecutable(&F->front());
 171     for (Argument &A : F->args()) {
 172       auto RegFormal = TestLatticeKey(&A, IPOGrouping::Register);
 173       auto RegActual =
 174           TestLatticeKey(I.getArgOperand(A.getArgNo()), IPOGrouping::Register);
 175       ChangedValues[RegFormal] =
 176           MergeValues(SS.getValueState(RegFormal), SS.getValueState(RegActual));
 177     }
 178     auto RetF = TestLatticeKey(F, IPOGrouping::Return);
 179     ChangedValues[RegI] =
 180         MergeValues(SS.getValueState(RegI), SS.getValueState(RetF));
 181   }
 182
 183   /// Handle return instructions. The function's return state is the merge of
 184   /// the returned value state and the function's current return state.
 185   void visitReturn(ReturnInst &I,
 186                    DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
 187                    SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
 188     Function *F = I.getParent()->getParent();
 189     if (F->getReturnType()->isVoidTy())
 190       return;
 191     auto RegR = TestLatticeKey(I.getReturnValue(), IPOGrouping::Register);
 192     auto RetF = TestLatticeKey(F, IPOGrouping::Return);
 193     ChangedValues[RetF] =
 194         MergeValues(SS.getValueState(RegR), SS.getValueState(RetF));
 195   }
 196
 197   /// Handle store instructions. If the pointer operand of the store is a
 198   /// global variable, we attempt to track the value. The global variable state
 199   /// is the merge of the stored value state with the current global variable
 200   /// state.
 201   void visitStore(StoreInst &I,
 202                   DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
 203                   SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
 204     auto *GV = dyn_cast<GlobalVariable>(I.getPointerOperand());
 205     if (!GV)
 206       return;
 207     auto RegVal = TestLatticeKey(I.getValueOperand(), IPOGrouping::Register);
 208     auto MemPtr = TestLatticeKey(GV, IPOGrouping::Memory);
 209     ChangedValues[MemPtr] =
 210         MergeValues(SS.getValueState(RegVal), SS.getValueState(MemPtr));
 211   }
 212
 213   /// Handle all other instructions. All other instructions are marked
 214   /// overdefined.
 215   void visitInst(Instruction &I,
 216                  DenseMap<TestLatticeKey, TestLatticeVal> &ChangedValues,
 217                  SparseSolver<TestLatticeKey, TestLatticeVal> &SS) {
 218     auto RegI = TestLatticeKey(&I, IPOGrouping::Register);
 219     ChangedValues[RegI] = getOverdefinedVal();
 220   }
 221 };
 222
 223 /// This class defines the common data used for all of the tests. The tests
 224 /// should add code to the module and then run the solver.
 225 class SparsePropagationTest : public testing::Test {
 226 protected:
 227   LLVMContext Context;
 228   Module M;
 229   IRBuilder<> Builder;
 230   TestLatticeFunc Lattice;
 231   SparseSolver<TestLatticeKey, TestLatticeVal> Solver;
 232
 233 public:
 234   SparsePropagationTest()
 235       : M("", Context), Builder(Context), Solver(&Lattice) {}
 236 };
 237 } // namespace
 238
 239 /// Test that we mark discovered functions executable.
 240 ///
 241 /// define internal void @f() {
 242 ///   call void @g()
 243 ///   ret void
 244 /// }
 245 ///
 246 /// define internal void @g() {
 247 ///   call void @f()
 248 ///   ret void
 249 /// }
 250 ///
 251 /// For this test, we initially mark "f" executable, and the solver discovers
 252 /// "g" because of the call in "f". The mutually recursive call in "g" also
 253 /// tests that we don't add a block to the basic block work list if it is
 254 /// already executable. Doing so would put the solver into an infinite loop.
 255 TEST_F(SparsePropagationTest, MarkBlockExecutable) {
 256   Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 257                                  GlobalValue::InternalLinkage, "f", &M);
 258   Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 259                                  GlobalValue::InternalLinkage, "g", &M);
 260   BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
 261   BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
 262   Builder.SetInsertPoint(FEntry);
 263   Builder.CreateCall(G);
 264   Builder.CreateRetVoid();
 265   Builder.SetInsertPoint(GEntry);
 266   Builder.CreateCall(F);
 267   Builder.CreateRetVoid();
 268
 269   Solver.MarkBlockExecutable(FEntry);
 270   Solver.Solve();
 271
 272   EXPECT_TRUE(Solver.isBlockExecutable(GEntry));
 273 }
 274
 275 /// Test that we propagate information through global variables.
 276 ///
 277 /// @gv = internal global i64
 278 ///
 279 /// define internal void @f() {
 280 ///   store i64 1, i64* @gv
 281 ///   ret void
 282 /// }
 283 ///
 284 /// define internal void @g() {
 285 ///   store i64 1, i64* @gv
 286 ///   ret void
 287 /// }
 288 ///
 289 /// For this test, we initially mark both "f" and "g" executable, and the
 290 /// solver computes the lattice state of the global variable as constant.
 291 TEST_F(SparsePropagationTest, GlobalVariableConstant) {
 292   Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 293                                  GlobalValue::InternalLinkage, "f", &M);
 294   Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 295                                  GlobalValue::InternalLinkage, "g", &M);
 296   GlobalVariable *GV =
 297       new GlobalVariable(M, Builder.getInt64Ty(), false,
 298                          GlobalValue::InternalLinkage, nullptr, "gv");
 299   BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
 300   BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
 301   Builder.SetInsertPoint(FEntry);
 302   Builder.CreateStore(Builder.getInt64(1), GV);
 303   Builder.CreateRetVoid();
 304   Builder.SetInsertPoint(GEntry);
 305   Builder.CreateStore(Builder.getInt64(1), GV);
 306   Builder.CreateRetVoid();
 307
 308   Solver.MarkBlockExecutable(FEntry);
 309   Solver.MarkBlockExecutable(GEntry);
 310   Solver.Solve();
 311
 312   auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
 313   EXPECT_TRUE(Solver.getExistingValueState(MemGV).isConstant());
 314 }
 315
 316 /// Test that we propagate information through global variables.
 317 ///
 318 /// @gv = internal global i64
 319 ///
 320 /// define internal void @f() {
 321 ///   store i64 0, i64* @gv
 322 ///   ret void
 323 /// }
 324 ///
 325 /// define internal void @g() {
 326 ///   store i64 1, i64* @gv
 327 ///   ret void
 328 /// }
 329 ///
 330 /// For this test, we initially mark both "f" and "g" executable, and the
 331 /// solver computes the lattice state of the global variable as overdefined.
 332 TEST_F(SparsePropagationTest, GlobalVariableOverDefined) {
 333   Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 334                                  GlobalValue::InternalLinkage, "f", &M);
 335   Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 336                                  GlobalValue::InternalLinkage, "g", &M);
 337   GlobalVariable *GV =
 338       new GlobalVariable(M, Builder.getInt64Ty(), false,
 339                          GlobalValue::InternalLinkage, nullptr, "gv");
 340   BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
 341   BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
 342   Builder.SetInsertPoint(FEntry);
 343   Builder.CreateStore(Builder.getInt64(0), GV);
 344   Builder.CreateRetVoid();
 345   Builder.SetInsertPoint(GEntry);
 346   Builder.CreateStore(Builder.getInt64(1), GV);
 347   Builder.CreateRetVoid();
 348
 349   Solver.MarkBlockExecutable(FEntry);
 350   Solver.MarkBlockExecutable(GEntry);
 351   Solver.Solve();
 352
 353   auto MemGV = TestLatticeKey(GV, IPOGrouping::Memory);
 354   EXPECT_TRUE(Solver.getExistingValueState(MemGV).isOverdefined());
 355 }
 356
 357 /// Test that we propagate information through function returns.
 358 ///
 359 /// define internal i64 @f(i1* %cond) {
 360 /// if:
 361 ///   %0 = load i1, i1* %cond
 362 ///   br i1 %0, label %then, label %else
 363 ///
 364 /// then:
 365 ///   ret i64 1
 366 ///
 367 /// else:
 368 ///   ret i64 1
 369 /// }
 370 ///
 371 /// For this test, we initially mark "f" executable, and the solver computes
 372 /// the return value of the function as constant.
 373 TEST_F(SparsePropagationTest, FunctionDefined) {
 374   Function *F =
 375       Function::Create(FunctionType::get(Builder.getInt64Ty(),
 376                                          {PointerType::get(Context, 0)}, false),
 377                        GlobalValue::InternalLinkage, "f", &M);
 378   BasicBlock *If = BasicBlock::Create(Context, "if", F);
 379   BasicBlock *Then = BasicBlock::Create(Context, "then", F);
 380   BasicBlock *Else = BasicBlock::Create(Context, "else", F);
 381   F->arg_begin()->setName("cond");
 382   Builder.SetInsertPoint(If);
 383   LoadInst *Cond = Builder.CreateLoad(Type::getInt1Ty(Context), F->arg_begin());
 384   Builder.CreateCondBr(Cond, Then, Else);
 385   Builder.SetInsertPoint(Then);
 386   Builder.CreateRet(Builder.getInt64(1));
 387   Builder.SetInsertPoint(Else);
 388   Builder.CreateRet(Builder.getInt64(1));
 389
 390   Solver.MarkBlockExecutable(If);
 391   Solver.Solve();
 392
 393   auto RetF = TestLatticeKey(F, IPOGrouping::Return);
 394   EXPECT_TRUE(Solver.getExistingValueState(RetF).isConstant());
 395 }
 396
 397 /// Test that we propagate information through function returns.
 398 ///
 399 /// define internal i64 @f(i1* %cond) {
 400 /// if:
 401 ///   %0 = load i1, i1* %cond
 402 ///   br i1 %0, label %then, label %else
 403 ///
 404 /// then:
 405 ///   ret i64 0
 406 ///
 407 /// else:
 408 ///   ret i64 1
 409 /// }
 410 ///
 411 /// For this test, we initially mark "f" executable, and the solver computes
 412 /// the return value of the function as overdefined.
 413 TEST_F(SparsePropagationTest, FunctionOverDefined) {
 414   Function *F =
 415       Function::Create(FunctionType::get(Builder.getInt64Ty(),
 416                                          {PointerType::get(Context, 0)}, false),
 417                        GlobalValue::InternalLinkage, "f", &M);
 418   BasicBlock *If = BasicBlock::Create(Context, "if", F);
 419   BasicBlock *Then = BasicBlock::Create(Context, "then", F);
 420   BasicBlock *Else = BasicBlock::Create(Context, "else", F);
 421   F->arg_begin()->setName("cond");
 422   Builder.SetInsertPoint(If);
 423   LoadInst *Cond = Builder.CreateLoad(Type::getInt1Ty(Context), F->arg_begin());
 424   Builder.CreateCondBr(Cond, Then, Else);
 425   Builder.SetInsertPoint(Then);
 426   Builder.CreateRet(Builder.getInt64(0));
 427   Builder.SetInsertPoint(Else);
 428   Builder.CreateRet(Builder.getInt64(1));
 429
 430   Solver.MarkBlockExecutable(If);
 431   Solver.Solve();
 432
 433   auto RetF = TestLatticeKey(F, IPOGrouping::Return);
 434   EXPECT_TRUE(Solver.getExistingValueState(RetF).isOverdefined());
 435 }
 436
 437 /// Test that we propagate information through arguments.
 438 ///
 439 /// define internal void @f() {
 440 ///   call void @g(i64 0, i64 1)
 441 ///   call void @g(i64 1, i64 1)
 442 ///   ret void
 443 /// }
 444 ///
 445 /// define internal void @g(i64 %a, i64 %b) {
 446 ///   ret void
 447 /// }
 448 ///
 449 /// For this test, we initially mark "f" executable, and the solver discovers
 450 /// "g" because of the calls in "f". The solver computes the state of argument
 451 /// "a" as overdefined and the state of "b" as constant.
 452 ///
 453 /// In addition, this test demonstrates that ComputeInstructionState can alter
 454 /// the state of multiple lattice values, in addition to the one associated
 455 /// with the instruction definition. Each call instruction in this test updates
 456 /// the state of arguments "a" and "b".
 457 TEST_F(SparsePropagationTest, ComputeInstructionState) {
 458   Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 459                                  GlobalValue::InternalLinkage, "f", &M);
 460   Function *G = Function::Create(
 461       FunctionType::get(Builder.getVoidTy(),
 462                         {Builder.getInt64Ty(), Builder.getInt64Ty()}, false),
 463       GlobalValue::InternalLinkage, "g", &M);
 464   Argument *A = G->arg_begin();
 465   Argument *B = std::next(G->arg_begin());
 466   A->setName("a");
 467   B->setName("b");
 468   BasicBlock *FEntry = BasicBlock::Create(Context, "", F);
 469   BasicBlock *GEntry = BasicBlock::Create(Context, "", G);
 470   Builder.SetInsertPoint(FEntry);
 471   Builder.CreateCall(G, {Builder.getInt64(0), Builder.getInt64(1)});
 472   Builder.CreateCall(G, {Builder.getInt64(1), Builder.getInt64(1)});
 473   Builder.CreateRetVoid();
 474   Builder.SetInsertPoint(GEntry);
 475   Builder.CreateRetVoid();
 476
 477   Solver.MarkBlockExecutable(FEntry);
 478   Solver.Solve();
 479
 480   auto RegA = TestLatticeKey(A, IPOGrouping::Register);
 481   auto RegB = TestLatticeKey(B, IPOGrouping::Register);
 482   EXPECT_TRUE(Solver.getExistingValueState(RegA).isOverdefined());
 483   EXPECT_TRUE(Solver.getExistingValueState(RegB).isConstant());
 484 }
 485
 486 /// Test that we can handle exceptional terminator instructions.
 487 ///
 488 /// declare internal void @p()
 489 ///
 490 /// declare internal void @g()
 491 ///
 492 /// define internal void @f() personality ptr @p {
 493 /// entry:
 494 ///   invoke void @g()
 495 ///           to label %exit unwind label %catch.pad
 496 ///
 497 /// catch.pad:
 498 ///   %0 = catchswitch within none [label %catch.body] unwind to caller
 499 ///
 500 /// catch.body:
 501 ///   %1 = catchpad within %0 []
 502 ///   catchret from %1 to label %exit
 503 ///
 504 /// exit:
 505 ///   ret void
 506 /// }
 507 ///
 508 /// For this test, we initially mark the entry block executable. The solver
 509 /// then discovers the rest of the blocks in the function are executable.
 510 TEST_F(SparsePropagationTest, ExceptionalTerminatorInsts) {
 511   Function *P = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 512                                  GlobalValue::InternalLinkage, "p", &M);
 513   Function *G = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 514                                  GlobalValue::InternalLinkage, "g", &M);
 515   Function *F = Function::Create(FunctionType::get(Builder.getVoidTy(), false),
 516                                  GlobalValue::InternalLinkage, "f", &M);
 517   F->setPersonalityFn(P);
 518   BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
 519   BasicBlock *Pad = BasicBlock::Create(Context, "catch.pad", F);
 520   BasicBlock *Body = BasicBlock::Create(Context, "catch.body", F);
 521   BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
 522   Builder.SetInsertPoint(Entry);
 523   Builder.CreateInvoke(G, Exit, Pad);
 524   Builder.SetInsertPoint(Pad);
 525   CatchSwitchInst *CatchSwitch =
 526       Builder.CreateCatchSwitch(ConstantTokenNone::get(Context), nullptr, 1);
 527   CatchSwitch->addHandler(Body);
 528   Builder.SetInsertPoint(Body);
 529   CatchPadInst *CatchPad = Builder.CreateCatchPad(CatchSwitch, {});
 530   Builder.CreateCatchRet(CatchPad, Exit);
 531   Builder.SetInsertPoint(Exit);
 532   Builder.CreateRetVoid();
 533
 534   Solver.MarkBlockExecutable(Entry);
 535   Solver.Solve();
 536
 537   EXPECT_TRUE(Solver.isBlockExecutable(Pad));
 538   EXPECT_TRUE(Solver.isBlockExecutable(Body));
 539   EXPECT_TRUE(Solver.isBlockExecutable(Exit));
 540 }