[VPlan] Add VPlan based sinkInstructions utility.

[fhahn]

Summary

This patch introduces a sinkInstructions utility that sinks instructions
in a VPlan based on an Instruction -> Instruction mapping, as returned
by LoopVectorizationLegality::getSinkAfter. It also adds a
VPlanHCFGTransforms.cpp, for functions that do not rely on stuff
defined in LoopVectorize.cpp, to move to a more modular structure.

Once we migrated getSinkAfter to operate on a VPlan, we should change
this to not rely on the underlying values.

[dcaballe]

Hi Florian. Some comments, regardless my previous comments in D46827:

1. Location: Same as in D46827, we may need to find a better place. Maybe a VPlanHCFGTransforms class for now?
2. Just a thought for the future: I think sinkAfter could be one of those things that we may want to rethink/re-implement a bit in the VPlan native path. If it's only used for interleave groups, we may want to include the sinkAfter analysis and transformation steps as part of the future interleave groups VPlan-to-VPlan transformation.

Thanks,
Diego

lib/Transforms/Vectorize/LoopVectorizationPlanner.cpp

20

I'm using independent DEBUG_TYPE in D44338 for VPlan verifier and HCFGConstruction files. I guess we should be consistent. We could use 'loop-vectorize' for all of them or also use an independent one for this.

lib/Transforms/Vectorize/LoopVectorizationPlanner.h

258

Is \p still used for documenting parameters?

260

format: beyond 80 chars?

[fhahn]

Thanks Diego, LoopVectorizationPlanner is not the right place, initially I was not sure where to put it. I updated the patch to move sinkInstructions to VPlanHCFGTransforms. I've made this a class with static member functions, as sinkInstructions gets access to getUnderlyingVal via a friend class.

I agree that in the long term, we should migrate to a VPlan native handling of the interleave group handling. I suppose that would be something that could be done independently. Maybe it would be worth collecting a set of tasks/cleanups that aren't blocked on other changes.

[fhahn]

lib/Transforms/Vectorize/LoopVectorizationPlanner.cpp

20

I think using 'loop-vectorize' everywhere is that we can use -debug-only=loop-vectorize to get the complete picture.

unittests/Transforms/Vectorize/VPlanTest.cpp

55

This version leaks the created instructions. I will clean that up in the next update (or before committing).

[dcaballe]

Much better with this VPlanHCFGTransforms! Thanks a lot!
Just some minor comments. LGTM. Again, let's wait for D46827 to see if this code is still necessary.

Thanks!

lib/Transforms/Vectorize/VPlanHCFGTransforms.cpp

26 ↗

(On Diff #146858)

assert(isa) + cast?

35–36 ↗

(On Diff #146858)

same here? assert(isa) + cast?

lib/Transforms/Vectorize/VPlanValue.h

41

Hopefully this won't promote the use of the underlying IR for other VPlan-to-VPlan transformations when it's not necessary.

[rja]

LGTM

[fhahn]

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

[fhahn]

A more practical version of this is D90712, which is usable by the inner loop vectorizer and up-to-date.

lib/Transforms/Vectorize/CMakeLists.txt

 add_llvm_library(LLVMVectorize
   LoadStoreVectorizer.cpp
   LoopVectorizationLegality.cpp
+  LoopVectorizationPlanner.cpp
   LoopVectorize.cpp
   SLPVectorizer.cpp
   Vectorize.cpp
   VPlan.cpp
   VPlanHCFGBuilder.cpp
   VPlanVerifier.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/Transforms
 
   DEPENDS
   intrinsics_gen
   )

lib/Transforms/Vectorize/LoopVectorizationPlanner.h

public:
   /// best selected VPlan.
   void executePlan(InnerLoopVectorizer &LB, DominatorTree *DT);
 
   void printPlans(raw_ostream &O) {
     for (const auto &Plan : VPlans)
       O << *Plan;
   }
 
+  /// Sinks instructions in Plan, depending on their underlying values in
+  /// SinkAfter.
+  // FIXME: Migrate to using a VPlan based mapping, once LoopVectorizationLegality::getSinkAfter
+  //        is moved the VPlan.
+  static void
+  sinkInstructions(VPlanPtr &Plan,
+                   DenseMap<Instruction *, Instruction *> &SinkAfter);
+
 protected:
   /// Collect the instructions from the original loop that would be trivially
   /// dead in the vectorized loop if generated.
   void collectTriviallyDeadInstructions(
       SmallPtrSetImpl<Instruction *> &DeadInstructions);
 
   /// A range of powers-of-2 vectorization factors with fixed start and
   /// adjustable end. The range includes start and excludes end, e.g.,:

lib/Transforms/Vectorize/LoopVectorizationPlanner.cpp

+//===-- LoopVectorizationPlanner.cpp --------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file implements parts of the LoopVectorizationPlanner class.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/Support/Debug.h"
+#include "LoopVectorizationPlanner.h"
+
+namespace llvm {
+
+#define DEBUG_TYPE "loop-vectorize"
+
+void LoopVectorizationPlanner::sinkInstructions(
+    VPlanPtr &Plan, DenseMap<Instruction *, Instruction *> &SinkAfter) {
+  DenseMap<Instruction *, VPInstruction *> SinkAfterInverse;
+  VPRegionBlock *TopRegion = dyn_cast<VPRegionBlock>(Plan->getEntry());
+  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
+  for (VPBlockBase *Base : RPOT) {
+    VPBasicBlock *OriginalVPBB = Base->getEntryBasicBlock();
+    for (VPRecipeBase &Ingredient : *OriginalVPBB) {
+      VPInstruction *VPInst = dyn_cast<VPInstruction>(&Ingredient);
+      if (!VPInst)
+        continue;
+
+      Instruction *Instr = dyn_cast<Instruction>(VPInst->getUnderlyingValue());
+      assert(Instr && "Need Instruction as underlying value");
+
+      // Move instructions to handle first-order recurrences, step 1: avoid
+      // handling this instruction until after we've handled the instruction it
+      // should follow.
+      auto SAIt = SinkAfter.find(Instr);
+      if (SAIt != SinkAfter.end()) {
+        DEBUG(dbgs() << "Sinking" << *SAIt->first << " after" << *SAIt->second
+                     << " to vectorize a 1st order recurrence.\n");
+        SinkAfterInverse[SAIt->second] = VPInst;
+        continue;
+      }
+
+      // Move instructions to handle first-order recurrences, step 2: push the
+      // instruction to be sunk at its insertion point.
+      auto SAInvIt = SinkAfterInverse.find(Instr);
+      if (SAInvIt != SinkAfterInverse.end())
+        SAInvIt->second->moveAfter(VPInst);
+    }
+  }
+}
+
+} //end namespace llvm

lib/Transforms/Vectorize/VPlanValue.h

 class VPUser;
 
 // This is the base class of the VPlan Def/Use graph, used for modeling the data
 // flow into, within and out of the VPlan. VPValues can stand for live-ins
 // coming from the input IR, instructions which VPlan will generate if executed
 // and live-outs which the VPlan will need to fix accordingly.
 class VPValue {
   friend class VPBuilder;
+  friend class LoopVectorizationPlanner;
+
 private:
   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
 
   SmallVector<VPUser *, 1> Users;
 
 protected:
   // Hold the underlying Value, if any, attached to this VPValue.
   Value * UnderlyingVal;

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 "../lib/Transforms/Vectorize/LoopVectorizationPlanner.h"
+#include "llvm/IR/Instruction.h"
+#include "llvm/IR/Instructions.h"
 #include "gtest/gtest.h"
 
 namespace llvm {
 namespace {
 
 #define CHECK_ITERATOR(Range1, ...)                                            \
   do {                                                                         \
     std::vector<VPInstruction *> Tmp = {__VA_ARGS__};                          \
TEST(VPInstructionTest, moveAfter) {
   VPBB2.appendRecipe(I5);
 
   I3->moveAfter(I4);
 
   CHECK_ITERATOR(VPBB1, I2, I1);
   CHECK_ITERATOR(VPBB2, I4, I3, I5);
 }
 
+TEST(VPInstructionTest, sinkInstructions) {
+  // Create some dummy instructions, we need those for the SinkAfter mapping.
+  LLVMContext Context;
+  Value *V = new Argument(Type::getInt32Ty(Context));
+  Instruction *I1 = BinaryOperator::Create(Instruction::Add, V, V);
+  Instruction *I2 = BinaryOperator::Create(Instruction::Add, I1, V);
+  Instruction *I3 = BinaryOperator::Create(Instruction::Add, I2, V);
+  Instruction *I4 = BinaryOperator::Create(Instruction::Add, I3, V);
+  Instruction *I5 = BinaryOperator::Create(Instruction::Add, I4, V);
+
+  VPBuilder Builder;
+
+  VPBasicBlock *VPBB1 = new VPBasicBlock();
+  Builder.setInsertPoint(VPBB1);
+  VPInstruction *VI1 = dyn_cast<VPInstruction>(Builder.createNaryOp(1, {}, I1));
+  VPInstruction *VI2 = dyn_cast<VPInstruction>(Builder.createNaryOp(2, {}, I2));
+  VPInstruction *VI3 = dyn_cast<VPInstruction>(Builder.createNaryOp(3, {}, I3));
+
+  VPBasicBlock *VPBB2 = new VPBasicBlock();
+  Builder.setInsertPoint(VPBB2);
+  VPInstruction *VI4 = dyn_cast<VPInstruction>(Builder.createNaryOp(4, {}, I4));
+  VPInstruction *VI5 = dyn_cast<VPInstruction>(Builder.createNaryOp(5, {}, I5));
+
+  VPBB1->setOneSuccessor(VPBB2);
+
+  VPRegionBlock *TopRegion =
+      new VPRegionBlock("TopRegion", false /*isReplicator*/);
+  TopRegion->setEntry(VPBB1);
+  TopRegion->setExit(VPBB2);
+  auto Plan = llvm::make_unique<VPlan>(TopRegion);
+
+  DenseMap<Instruction *, Instruction *> SinkAfter;
+  SinkAfter[I1] = I3;
+  SinkAfter[I2] = I4;
+
+  LoopVectorizationPlanner::sinkInstructions(Plan, SinkAfter);
+
+  CHECK_ITERATOR((*VPBB1), VI3, VI1);
+  CHECK_ITERATOR((*VPBB2), VI4, VI2, VI5);
+}
+
 } // namespace
 } // namespace llvm