[VPlan] Add moveAfter to VPRecipeBase.

[fhahn]

Summary

This patch adds a moveAfter method to VPRecipeBase, which can be used to
move elements after other elements, across VPBasicBlocks, if necessary.

It also adds an initial unittest for VPlan.

[dcaballe]

Thanks for the unittest, Florian! I will be very useful!

lib/Transforms/Vectorize/VPlan.h

543

instruction -> recipe
VPBasicBloack -> VPBasicBlock

I wonder if it would be better to start a VPInstructionUtils and move this utility there, similar to what I did with VPBlockUtils in D44338.

916

Just for my understanding, wouldn't it be possible to use getSublistAccess?

[fhahn]

Thanks Diego. I think we should be able to use unit tests extensively for VPlan, as it should be quite lightweight to construct a VPlan, run a transformation and check the resulting VPlan.

lib/Transforms/Vectorize/VPlan.h

543

I added it as member function here because there is a similar Instruction::moveAfter function. I think having a similar member function here makes it easier for people being used to the existing APIs.

916

Yes I guess we could use getSublistAccess, but I am not entirely sure what the use case of this function is? Its comment says it returns a pointer to a member of the recipe list, but then it ignores the parameter.

IMO it would be better, safer to return a reference (BasicBlock has a similar getInstList function). Maybe getRecipes should be renamed to getRecipeList and we could remove getSublistAccess, as it is not used anywhere?

[fhahn]

Thank

[dcaballe]

Only minor comments! LGTM.
Thanks!

lib/Transforms/Vectorize/VPlan.h

543

I think having a similar member function here makes it easier for people being used to the existing APIs.

Ok, if that's the case for Instruction let's go with this.

916

Agreed. Yes, please, remove getSublistAccess and let's use getRecipeList.
Thanks!

unittests/Transforms/Vectorize/VPlanTest.cpp

26

delete all the new Instructions and VPInstruction will also be necessary here?

[dcaballe]

Just make sure that in the final version of D46827 this code is still necessary.
Thanks!

[fhahn]

After the recent changes to D46827, this patch is not really necessary for now, but it may be useful in the future.

lib/Transforms/Vectorize/VPlan.h

public:
   const VPBasicBlock *getParent() const { return Parent; }
 
   /// The method which generates the output IR instructions that correspond to
   /// this VPRecipe, thereby "executing" the VPlan.
   virtual void execute(struct VPTransformState &State) = 0;
 
   /// Each recipe prints itself.
   virtual void print(raw_ostream &O, const Twine &Indent) const = 0;
+
+  /// Unlink this recipe from its current VPBasicBlock and insert it into
+  /// the VPBasicBlock that MovePos lives in, right after MovePos.
+  void moveAfter(VPRecipeBase *MovePos);
 };
 
 /// This is a concrete Recipe that models a single VPlan-level instruction.
 /// While as any Recipe it may generate a sequence of IR instructions when
 /// executed, these instructions would always form a single-def expression as
 /// the VPInstruction is also a single def-use vertex.
 class VPInstruction : public VPUser, public VPRecipeBase {
 public:
public:
 
   inline size_t size() const { return Recipes.size(); }
   inline bool empty() const { return Recipes.empty(); }
   inline const VPRecipeBase &front() const { return Recipes.front(); }
   inline VPRecipeBase &front() { return Recipes.front(); }
   inline const VPRecipeBase &back() const { return Recipes.back(); }
   inline VPRecipeBase &back() { return Recipes.back(); }
 
+  /// Returns a reference to the list of recipes.
+  RecipeListTy &getRecipeList() { return Recipes; }
+
   /// Returns a pointer to a member of the recipe list.
   static RecipeListTy VPBasicBlock::*getSublistAccess(VPRecipeBase *) {
     return &VPBasicBlock::Recipes;
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPBlockBase *V) {
     return V->getVPBlockID() == VPBlockBase::VPBasicBlockSC;

lib/Transforms/Vectorize/VPlan.cpp

for (unsigned Lane = 0, VF = State->VF; Lane < VF; ++Lane) {
       }
     }
   }
 
   // Exit replicating mode.
   State->Instance.reset();
 }
 
+void VPRecipeBase::moveAfter(VPRecipeBase *InsertPos) {
+  InsertPos->getParent()->getRecipeList().splice(
+      std::next(InsertPos->getIterator()), getParent()->getRecipeList(),
+      getIterator());
+}
+
 void VPInstruction::generateInstruction(VPTransformState &State,
                                         unsigned Part) {
   IRBuilder<> &Builder = State.Builder;
 
   if (Instruction::isBinaryOp(getOpcode())) {
     Value *A = State.get(getOperand(0), Part);
     Value *B = State.get(getOperand(1), Part);
     Value *V = Builder.CreateBinOp((Instruction::BinaryOps)getOpcode(), A, B);

unittests/Transforms/CMakeLists.txt

 add_subdirectory(IPO)
 add_subdirectory(Scalar)
 add_subdirectory(Utils)
+add_subdirectory(Vectorize)

unittests/Transforms/Vectorize/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Vectorize
+  )
+
+add_llvm_unittest(VectorizeTests
+  VPlanTest.cpp
+  )

unittests/Transforms/Vectorize/VPlanTest.cpp

+//===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "../lib/Transforms/Vectorize/VPlan.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+#define CHECK_ITERATOR(Range1, ...)                                            \
+  do {                                                                         \
+    std::vector<VPInstruction *> Tmp = {__VA_ARGS__};                          \
+    EXPECT_EQ((size_t)std::distance(Range1.begin(), Range1.end()),             \
+              Tmp.size());                                                     \
+    for (auto Pair : zip(Range1, make_range(Tmp.begin(), Tmp.end())))          \
+      EXPECT_EQ(&std::get<0>(Pair), std::get<1>(Pair));                        \
+  } while (0)
+
+TEST(VPInstructionTest, moveAfter) {
+  VPInstruction *I1 = new VPInstruction(0, {});
+  VPInstruction *I2 = new VPInstruction(1, {});
+  VPInstruction *I3 = new VPInstruction(2, {});
+
+  VPBasicBlock VPBB1;
+  VPBB1.appendRecipe(I1);
+  VPBB1.appendRecipe(I2);
+  VPBB1.appendRecipe(I3);
+
+  I1->moveAfter(I2);
+
+  CHECK_ITERATOR(VPBB1, I2, I1, I3);
+
+  VPInstruction *I4 = new VPInstruction(4, {});
+  VPInstruction *I5 = new VPInstruction(5, {});
+  VPBasicBlock VPBB2;
+  VPBB2.appendRecipe(I4);
+  VPBB2.appendRecipe(I5);
+
+  I3->moveAfter(I4);
+
+  CHECK_ITERATOR(VPBB1, I2, I1);
+  CHECK_ITERATOR(VPBB2, I4, I3, I5);
+}
+
+} // namespace
+} // namespace llvm