[VPlan] Add GraphTraits impl to traverse through VPRegionBlock.

[fhahn]

Summary

This patch adds a new iterator to traverse through VPRegionBlocks and a
GraphTraits specialization using the iterator to traverse through
VPRegionBlocks.

Because there is already a GraphTraits specialization for VPBlockBase *
and co, a new VPBlockRecursiveTraversalWrapper helper is introduced.
This allows us to provide a new GraphTraits specialization for that
type. Users can use the new recursive traversal by using this wrapper.

The graph trait visits both the entry block of a region, as well as all
its successors. Exit blocks of a region implicitly have their parent
region's successors. This ensures all blocks in a region are visited
before any blocks in a successor region when doing a reverse post-order
traversal of the graph.

[a.elovikov]

llvm/lib/Transforms/Vectorize/VPlan.h

1757

IMO, having a work "successors" in the name would help in understanding the logic behind this. I've caught myself on a though that at some point reading the code below I've forgotten that we only go through the "successors" of a a block and not through the whole graph.

1760

I'd probably spell it as

`BlockTy const Block`

or

`BlockTy * const Block`

1761

Can we rename it to SuccessorIdx? Do I understand the purpose of the field correctly?

1789

What if the block's parent is a region that is an exit as well? Shouldn't we recursively go up the chain of such exits? Same throughout other methods (e.g. end).

1803

I'd prefer to use const_cast magic here, instead of duplicating the code.

1832

Wow, that is nice. I was only aware of the approach with named traits and then defining helper function to pass that trait explicitly to traversal. Your approach is much clearer.

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

346

nit:

llvm::copy(depth_first(...), std::back_inserter(FromIterator));

380

Can you please add an ASCII graph drawing here similar to the one above?

434

Can we either modify this test or add another one with some non-linear CFG inside R2?

467

nit: I think llvm::copy or outlining the region into a temporary auto variable would help with readability here.

[a.elovikov]

llvm/lib/Transforms/Vectorize/VPlan.h

1870

Would it be possible to pass just const VPBlockBase * here? Is the argument here what is usually defined as using GraphType = <something>?

[fhahn]

Addressed comments, thanks!

llvm/lib/Transforms/Vectorize/VPlan.h

1757

I changed the name to VPAllSuccessorsIterator. WDY?

1760

Unfortunately it looks like the RPOT helpers uses std::copy, which requires the assignment operator, which is not compatible with making Block const, but I may be missing some workaround?

1789

Yep, that's not handled properly at the moment! I also realized that the case where the region is the last block in the graph was not handled properly, as we would not enter the region itself. Both issues should be fixed now.

1803

Using const_cast did not seem to work well with the graph traits, so I added a templated version. WDYT?

1870

I think this needs to match the type GraphTraits is defined for. Otherwise this cannot be used directly with the wrapper object and it may cause additional problems because there's a GraphTraits specialization for const VPBlockBase *.

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

434

I added another block and a cycle.

467

I simplified and unified the construction.

[a.elovikov]

I think it's functionally correct now, just have a few suggestions to simplify the code a little bit.

Thanks for the updates!

llvm/lib/Transforms/Vectorize/VPlan.h

1767

[pedantic]
Strictly speaking, returning Current isn't returning any parents
[/pedantic]

Maybe rename to getBlockWithSuccs?

1773

I don't understand the purpose of T1 here yet. I'll continue reading assuming

template <typename T>
static auto deref(T *Ptr)

1775

nit: Ptr->Block is used three times, might be beneficial to outline to a variable with explicit type (VPBlockBase?)

1784

I think doing this unconditionally would just work. The current implementation of getFirstParentWithSuccs returns Ptr->block if it has successors.

1803

That would work, but please add the comment near the templated version what this template paramter is used for (to support const/non-const versions). I assume it would be the deref function, right?

1803

I think it should be just ParentWithSuccs ? ParentWithSuccs->getNumSuccessors() : 0 after implementing the suggestion above about renaming the method.

[fhahn]

Address comments, thanks!

[fhahn]

Remove unneeded explicit types when calling deref.

llvm/lib/Transforms/Vectorize/VPlan.h

1767

Thanks, I updated the name as suggested.

1773

I think this was needed to make things build, because otherwise Clang failed to determine the correct return type of the function. But I updated the code now to pass the block and index in directly, requiring only one template argument.

1775

Block is passed in directly now, so the template can be simplified.

[a.elovikov]

LGTM, thanks!

[fhahn]

In D100175#2709028, @a.elovikov wrote:

LGTM, thanks!

Thank you very much for taking a look!

llvm/lib/Transforms/Vectorize/VPlan.h

struct GraphTraits<Inverse<VPRegionBlock *>>
 
   static nodes_iterator nodes_end(GraphRef N) {
     // df_iterator::end() returns an empty iterator so the node used doesn't
     // matter.
     return nodes_iterator::end(N);
   }
 };
 
+/// Iterator to traverse all successors of a VPBlockBase node. This includes the
+/// entry node of VPRegionBlocks. Exit blocks of a region implicitly have their
+/// parent region's successors. This ensures all blocks in a region are visited
+/// before any blocks in a successor region when doing a reverse post-order
+// traversal of the graph.
+template <typename BlockPtrTy>
+class VPAllSuccessorsIterator
+    : public iterator_facade_base<VPAllSuccessorsIterator<BlockPtrTy>,
+                                  std::forward_iterator_tag, VPBlockBase> {
+  BlockPtrTy Block;
+  /// Index of the current successor. For VPBasicBlock nodes, this simply is the
+  /// index for the successor array. For VPRegionBlock, SuccessorIdx == 0 is
+  /// used for the region's entry block, and SuccessorIdx - 1 are the indices
+  /// for the successor array.
+  size_t SuccessorIdx;
+
+  static BlockPtrTy getBlockWithSuccs(BlockPtrTy Current) {
+    while (Current && Current->getNumSuccessors() == 0)
+      Current = Current->getParent();
+    return Current;
+  }
+
+  /// Templated helper to dereference successor \p SuccIdx of \p Block. Used by
+  /// both the const and non-const operator* implementations.
+  template <typename T1> static T1 deref(T1 Block, unsigned SuccIdx) {
+    if (auto *R = dyn_cast<VPRegionBlock>(Block)) {
+      if (SuccIdx == 0)
+        return R->getEntry();
+      SuccIdx--;
+    }
+
+    // For exit blocks, use the next parent region with successors.
+    return getBlockWithSuccs(Block)->getSuccessors()[SuccIdx];
+  }
+
+public:
+  VPAllSuccessorsIterator(BlockPtrTy Block, size_t Idx = 0)
+      : Block(Block), SuccessorIdx(Idx) {}
+  VPAllSuccessorsIterator(const VPAllSuccessorsIterator &Other)
+      : Block(Other.Block), SuccessorIdx(Other.SuccessorIdx) {}
+
+  VPAllSuccessorsIterator &operator=(const VPAllSuccessorsIterator &R) {
+    Block = R.Block;
+    SuccessorIdx = R.SuccessorIdx;
+    return *this;
+  }
+
+  static VPAllSuccessorsIterator end(BlockPtrTy Block) {
+    BlockPtrTy ParentWithSuccs = getBlockWithSuccs(Block);
+    unsigned NumSuccessors = ParentWithSuccs
+                                 ? ParentWithSuccs->getNumSuccessors()
+                                 : Block->getNumSuccessors();
+
+    if (auto *R = dyn_cast<VPRegionBlock>(Block))
+      return {R, NumSuccessors + 1};
+    return {Block, NumSuccessors};
+  }
+
+  bool operator==(const VPAllSuccessorsIterator &R) const {
+    return Block == R.Block && SuccessorIdx == R.SuccessorIdx;
+  }
+
+  const VPBlockBase *operator*() const { return deref(Block, SuccessorIdx); }
+
+  BlockPtrTy operator*() { return deref(Block, SuccessorIdx); }
+
+  VPAllSuccessorsIterator &operator++() {
+    SuccessorIdx++;
+    return *this;
+  }
+
+  VPAllSuccessorsIterator operator++(int X) {
+    VPAllSuccessorsIterator Orig = *this;
+    SuccessorIdx++;
+    return Orig;
+  }
+};
+
+/// Helper for GraphTraits specialization that traverses through VPRegionBlocks.
+template <typename BlockTy> class VPBlockRecursiveTraversalWrapper {
+  BlockTy Entry;
+
+public:
+  VPBlockRecursiveTraversalWrapper(BlockTy Entry) : Entry(Entry) {}
+  BlockTy getEntry() { return Entry; }
+};
+
+/// GraphTraits specialization to recursively traverse VPBlockBase nodes,
+/// including traversing through VPRegionBlocks.  Exit blocks of a region
+/// implicitly have their parent region's successors. This ensures all blocks in
+/// a region are visited before any blocks in a successor region when doing a
+/// reverse post-order traversal of the graph.
+template <>
+struct GraphTraits<VPBlockRecursiveTraversalWrapper<VPBlockBase *>> {
+  using NodeRef = VPBlockBase *;
+  using ChildIteratorType = VPAllSuccessorsIterator<VPBlockBase *>;
+
+  static NodeRef
+  getEntryNode(VPBlockRecursiveTraversalWrapper<VPBlockBase *> N) {
+    return N.getEntry();
+  }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N);
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType::end(N);
+  }
+};
+
+template <>
+struct GraphTraits<VPBlockRecursiveTraversalWrapper<const VPBlockBase *>> {
+  using NodeRef = const VPBlockBase *;
+  using ChildIteratorType = VPAllSuccessorsIterator<const VPBlockBase *>;
+
+  static NodeRef
+  getEntryNode(VPBlockRecursiveTraversalWrapper<const VPBlockBase *> N) {
+    return N.getEntry();
+  }
+
+  static inline ChildIteratorType child_begin(NodeRef N) {
+    return ChildIteratorType(N);
+  }
+
+  static inline ChildIteratorType child_end(NodeRef N) {
+    return ChildIteratorType::end(N);
+  }
+};
+
 /// VPlan models a candidate for vectorization, encoding various decisions take
 /// to produce efficient output IR, including which branches, basic-blocks and
 /// output IR instructions to generate, and their cost. VPlan holds a
 /// Hierarchical-CFG of VPBasicBlocks and VPRegionBlocks rooted at an Entry
 /// VPBlock.
 class VPlan {
   friend class VPlanPrinter;
   friend class VPSlotTracker;

llvm/unittests/Transforms/Vectorize/VPlanTest.cpp

TEST(VPBasicBlockTest, getPlan) {
     EXPECT_EQ(&Plan, R1BB2->getPlan());
     EXPECT_EQ(&Plan, R2->getPlan());
     EXPECT_EQ(&Plan, R2BB1->getPlan());
     EXPECT_EQ(&Plan, R2BB2->getPlan());
     EXPECT_EQ(&Plan, VPBB2->getPlan());
   }
 }
 
+TEST(VPBasicBlockTest, TraversingIteratorTest) {
+  {
+    // VPBasicBlocks only
+    //     VPBB1
+    //     /   \
+    // VPBB2  VPBB3
+    //    \    /
+    //    VPBB4
+    //
+    VPBasicBlock *VPBB1 = new VPBasicBlock();
+    VPBasicBlock *VPBB2 = new VPBasicBlock();
+    VPBasicBlock *VPBB3 = new VPBasicBlock();
+    VPBasicBlock *VPBB4 = new VPBasicBlock();
+
+    VPBlockUtils::connectBlocks(VPBB1, VPBB2);
+    VPBlockUtils::connectBlocks(VPBB1, VPBB3);
+    VPBlockUtils::connectBlocks(VPBB2, VPBB4);
+    VPBlockUtils::connectBlocks(VPBB3, VPBB4);
+
+    VPBlockRecursiveTraversalWrapper<const VPBlockBase *> Start(VPBB1);
+    SmallVector<const VPBlockBase *> FromIterator(depth_first(Start));
+    EXPECT_EQ(4u, FromIterator.size());
+    EXPECT_EQ(VPBB1, FromIterator[0]);
+    EXPECT_EQ(VPBB2, FromIterator[1]);
+
+    // Use Plan to properly clean up created blocks.
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+  }
+
+  {
+    // 2 consecutive regions.
+    // R1 {
+    //     \
+    //     R1BB1
+    //    /     \   |--|
+    //  R1BB2   R1BB3 -|
+    //    \      /
+    //     R1BB4
+    //  }
+    //   |
+    // R2 {
+    //   \
+    //    R2BB1
+    //      |
+    //    R2BB2
+    //
+    VPBasicBlock *R1BB1 = new VPBasicBlock();
+    VPBasicBlock *R1BB2 = new VPBasicBlock();
+    VPBasicBlock *R1BB3 = new VPBasicBlock();
+    VPBasicBlock *R1BB4 = new VPBasicBlock();
+    VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB4, "R1");
+    R1BB2->setParent(R1);
+    R1BB3->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB2);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB3);
+    VPBlockUtils::connectBlocks(R1BB2, R1BB4);
+    VPBlockUtils::connectBlocks(R1BB3, R1BB4);
+    // Cycle.
+    VPBlockUtils::connectBlocks(R1BB3, R1BB3);
+
+    VPBasicBlock *R2BB1 = new VPBasicBlock();
+    VPBasicBlock *R2BB2 = new VPBasicBlock();
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
+    VPBlockUtils::connectBlocks(R2BB1, R2BB2);
+    VPBlockUtils::connectBlocks(R1, R2);
+
+    // Depth-first.
+    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(R1);
+    SmallVector<const VPBlockBase *> FromIterator(df_begin(Start),
+                                                  df_end(Start));
+    EXPECT_EQ(8u, FromIterator.size());
+    EXPECT_EQ(R1, FromIterator[0]);
+    EXPECT_EQ(R1BB1, FromIterator[1]);
+    EXPECT_EQ(R1BB2, FromIterator[2]);
+    EXPECT_EQ(R1BB4, FromIterator[3]);
+    EXPECT_EQ(R2, FromIterator[4]);
+    EXPECT_EQ(R2BB1, FromIterator[5]);
+    EXPECT_EQ(R2BB2, FromIterator[6]);
+    EXPECT_EQ(R1BB3, FromIterator[7]);
+
+    // Post-order.
+    FromIterator.clear();
+    copy(post_order(Start), std::back_inserter(FromIterator));
+    EXPECT_EQ(8u, FromIterator.size());
+    EXPECT_EQ(R2BB2, FromIterator[0]);
+    EXPECT_EQ(R2BB1, FromIterator[1]);
+    EXPECT_EQ(R2, FromIterator[2]);
+    EXPECT_EQ(R1BB4, FromIterator[3]);
+    EXPECT_EQ(R1BB2, FromIterator[4]);
+    EXPECT_EQ(R1BB3, FromIterator[5]);
+    EXPECT_EQ(R1BB1, FromIterator[6]);
+    EXPECT_EQ(R1, FromIterator[7]);
+
+    // Use Plan to properly clean up created blocks.
+    VPlan Plan;
+    Plan.setEntry(R1);
+  }
+
+  {
+    // 2 nested regions.
+    //  VPBB1
+    //    |
+    //  R1 {
+    //         R1BB1
+    //       /        \
+    //   R2 {          |
+    //     \           |
+    //     R2BB1       |
+    //       |   \    R1BB2
+    //     R2BB2-|     |
+    //        \        |
+    //         R2BB3   |
+    //   }            /
+    //      \        /
+    //        R1BB3
+    //  }
+    //   |
+    //  VPBB2
+    //
+    VPBasicBlock *R1BB1 = new VPBasicBlock("R1BB1");
+    VPBasicBlock *R1BB2 = new VPBasicBlock("R1BB2");
+    VPBasicBlock *R1BB3 = new VPBasicBlock("R1BB3");
+    VPRegionBlock *R1 = new VPRegionBlock(R1BB1, R1BB3, "R1");
+
+    VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
+    VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
+    VPBasicBlock *R2BB3 = new VPBasicBlock("R2BB3");
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB3, "R2");
+    R2BB2->setParent(R2);
+    VPBlockUtils::connectBlocks(R2BB1, R2BB2);
+    VPBlockUtils::connectBlocks(R2BB2, R2BB1);
+    VPBlockUtils::connectBlocks(R2BB2, R2BB3);
+
+    R2->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R2);
+    R1BB2->setParent(R1);
+    VPBlockUtils::connectBlocks(R1BB1, R1BB2);
+    VPBlockUtils::connectBlocks(R1BB2, R1BB3);
+    VPBlockUtils::connectBlocks(R2, R1BB3);
+
+    VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
+    VPBlockUtils::connectBlocks(VPBB1, R1);
+    VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
+    VPBlockUtils::connectBlocks(R1, VPBB2);
+
+    // Depth-first.
+    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
+    EXPECT_EQ(10u, FromIterator.size());
+    EXPECT_EQ(VPBB1, FromIterator[0]);
+    EXPECT_EQ(R1, FromIterator[1]);
+    EXPECT_EQ(R1BB1, FromIterator[2]);
+    EXPECT_EQ(R2, FromIterator[3]);
+    EXPECT_EQ(R2BB1, FromIterator[4]);
+    EXPECT_EQ(R2BB2, FromIterator[5]);
+    EXPECT_EQ(R2BB3, FromIterator[6]);
+    EXPECT_EQ(R1BB3, FromIterator[7]);
+    EXPECT_EQ(VPBB2, FromIterator[8]);
+    EXPECT_EQ(R1BB2, FromIterator[9]);
+
+    // Post-order.
+    FromIterator.clear();
+    FromIterator.append(po_begin(Start), po_end(Start));
+    EXPECT_EQ(10u, FromIterator.size());
+    EXPECT_EQ(VPBB2, FromIterator[0]);
+    EXPECT_EQ(R1BB3, FromIterator[1]);
+    EXPECT_EQ(R2BB3, FromIterator[2]);
+    EXPECT_EQ(R2BB2, FromIterator[3]);
+    EXPECT_EQ(R2BB1, FromIterator[4]);
+    EXPECT_EQ(R2, FromIterator[5]);
+    EXPECT_EQ(R1BB2, FromIterator[6]);
+    EXPECT_EQ(R1BB1, FromIterator[7]);
+    EXPECT_EQ(R1, FromIterator[8]);
+    EXPECT_EQ(VPBB1, FromIterator[9]);
+
+    // Use Plan to properly clean up created blocks.
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+  }
+
+  {
+    //  VPBB1
+    //    |
+    //  R1 {
+    //    \
+    //     R2 {
+    //      R2BB1
+    //        |
+    //      R2BB2
+    //   }
+    //
+    VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
+    VPBasicBlock *R2BB2 = new VPBasicBlock("R2BB2");
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R2BB2, "R2");
+    VPBlockUtils::connectBlocks(R2BB1, R2BB2);
+
+    VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
+    R2->setParent(R1);
+
+    VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
+    VPBlockUtils::connectBlocks(VPBB1, R1);
+
+    // Depth-first.
+    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
+    EXPECT_EQ(5u, FromIterator.size());
+    EXPECT_EQ(VPBB1, FromIterator[0]);
+    EXPECT_EQ(R1, FromIterator[1]);
+    EXPECT_EQ(R2, FromIterator[2]);
+    EXPECT_EQ(R2BB1, FromIterator[3]);
+    EXPECT_EQ(R2BB2, FromIterator[4]);
+
+    // Post-order.
+    FromIterator.clear();
+    FromIterator.append(po_begin(Start), po_end(Start));
+    EXPECT_EQ(5u, FromIterator.size());
+    EXPECT_EQ(R2BB2, FromIterator[0]);
+    EXPECT_EQ(R2BB1, FromIterator[1]);
+    EXPECT_EQ(R2, FromIterator[2]);
+    EXPECT_EQ(R1, FromIterator[3]);
+    EXPECT_EQ(VPBB1, FromIterator[4]);
+
+    // Use Plan to properly clean up created blocks.
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+  }
+
+  {
+    //  Nested regions with both R3 and R2 being exit nodes without successors.
+    //  The successors of R1 should be used.
+    //
+    //  VPBB1
+    //    |
+    //  R1 {
+    //    \
+    //     R2 {
+    //      \
+    //      R2BB1
+    //        |
+    //       R3 {
+    //          R3BB1
+    //      }
+    //   }
+    //   |
+    //  VPBB2
+    //
+    VPBasicBlock *R3BB1 = new VPBasicBlock("R3BB1");
+    VPRegionBlock *R3 = new VPRegionBlock(R3BB1, R3BB1, "R3");
+
+    VPBasicBlock *R2BB1 = new VPBasicBlock("R2BB1");
+    VPRegionBlock *R2 = new VPRegionBlock(R2BB1, R3, "R2");
+    R3->setParent(R2);
+    VPBlockUtils::connectBlocks(R2BB1, R3);
+
+    VPRegionBlock *R1 = new VPRegionBlock(R2, R2, "R1");
+    R2->setParent(R1);
+
+    VPBasicBlock *VPBB1 = new VPBasicBlock("VPBB1");
+    VPBasicBlock *VPBB2 = new VPBasicBlock("VPBB2");
+    VPBlockUtils::connectBlocks(VPBB1, R1);
+    VPBlockUtils::connectBlocks(R1, VPBB2);
+
+    // Depth-first.
+    VPBlockRecursiveTraversalWrapper<VPBlockBase *> Start(VPBB1);
+    SmallVector<VPBlockBase *> FromIterator(depth_first(Start));
+    EXPECT_EQ(7u, FromIterator.size());
+    EXPECT_EQ(VPBB1, FromIterator[0]);
+    EXPECT_EQ(R1, FromIterator[1]);
+    EXPECT_EQ(R2, FromIterator[2]);
+    EXPECT_EQ(R2BB1, FromIterator[3]);
+    EXPECT_EQ(R3, FromIterator[4]);
+    EXPECT_EQ(R3BB1, FromIterator[5]);
+    EXPECT_EQ(VPBB2, FromIterator[6]);
+
+    // Post-order.
+    FromIterator.clear();
+    copy(post_order(Start), std::back_inserter(FromIterator));
+    EXPECT_EQ(7u, FromIterator.size());
+    EXPECT_EQ(VPBB2, FromIterator[0]);
+    EXPECT_EQ(R3BB1, FromIterator[1]);
+    EXPECT_EQ(R3, FromIterator[2]);
+    EXPECT_EQ(R2BB1, FromIterator[3]);
+    EXPECT_EQ(R2, FromIterator[4]);
+    EXPECT_EQ(R1, FromIterator[5]);
+    EXPECT_EQ(VPBB1, FromIterator[6]);
+
+    // Use Plan to properly clean up created blocks.
+    VPlan Plan;
+    Plan.setEntry(VPBB1);
+  }
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 TEST(VPBasicBlockTest, print) {
   VPInstruction *I1 = new VPInstruction(Instruction::Add, {});
   VPInstruction *I2 = new VPInstruction(Instruction::Sub, {I1});
   VPInstruction *I3 = new VPInstruction(Instruction::Br, {I1, I2});
 
   VPBasicBlock *VPBB1 = new VPBasicBlock();
   VPBB1->appendRecipe(I1);