[VPlan] Introduce VPLoopInfo analysis.

[dcaballe]

Summary

Context: Patch Series #1 for outer loop vectorization support in LV
using VPlan. (RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

The patch introduces loop analysis (VPLoopInfo/VPLoop) for VPBlockBases.
This analysis will be necessary to perform some H-CFG transformations and
detect and introduce regions representing a loop in the H-CFG.

[dcaballe]

Rebasing this patch on top of D49032.

[fhahn]

lib/Transforms/Vectorize/VPlan.h

1115

Could the VPlan just store a VPLoopInfo object instead of using a raw pointer?

It would have the advantage of not needing dynamic memory management and it would be clear that each VPlan owns its VPLoopInfo. Instead having setVPLoopInfo we would have something like analyze() which would compute the DT and LoopInfo.

[dcaballe]

lib/Transforms/Vectorize/VPlan.h

1115

Store an object instead is much better, definitely! Thanks!

However, I'm not too sure about the analyze() part. Some analyses will be computed at different times. Some others, such as as DT for the plain CFG, are temporal (DT becomes invalid once regions are introduced so we don't even want to store it in VPlan). Would it be acceptable to keep the analysis computation of VPLoopInfo as is, at least, for now?

[dcaballe]

Making VPLoopInfo object a member of VPlan.

[fhahn]

LGTM, thanks

[dcaballe]

Thanks for the review, Florian!
I'll commit this once D48815 is approved and committed.

lib/Transforms/Vectorize/VPlan.h

 /// 6. The VPlanPrinter class providing a way to print a plan in dot format;
 /// These are documented in docs/VectorizationPlan.rst.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_H
 
+#include "VPlanLoopInfo.h"
 #include "VPlanValue.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/SmallVector.h"

 namespace llvm {
 
 class LoopVectorizationLegality;
 class LoopVectorizationCostModel;
 class BasicBlock;
 class DominatorTree;
 class InnerLoopVectorizer;
 class InterleaveGroup;
-class LoopInfo;
 class raw_ostream;
 class Value;
 class VPBasicBlock;
 class VPRegionBlock;
 class VPlan;
 
 /// A range of powers-of-2 vectorization factors with fixed start and
 /// adjustable end. The range includes start and excludes end, e.g.,:
void printAsOperand(raw_ostream &OS, bool PrintType) const {
     OS << getName();
   }
 
   void print(raw_ostream &OS) const {
     // TODO: Only printing VPBB name for now since we only have dot printing
     // support for VPInstructions/Recipes.
     printAsOperand(OS, false);
   }
+
+  /// Return true if it is legal to hoist instructions into this block.
+  bool isLegalToHoistInto() {
+    // There are currently no constraints that prevent an instruction to be
+    // hoisted into a VPBlockBase.
+    return true;
+  }
 };
 
 /// VPRecipeBase is a base class modeling a sequence of one or more output IR
 /// instructions.
 class VPRecipeBase : public ilist_node_with_parent<VPRecipeBase, VPBasicBlock> {
   friend VPBasicBlock;
 
 private:
private:
   // underlying IR that will be used to implement its structural comparison
   // (operators '==' and '<').
   SmallPtrSet<VPValue *, 16> VPExternalDefs;
 
   /// Holds a mapping between Values and their corresponding VPValue inside
   /// VPlan.
   Value2VPValueTy Value2VPValue;
 
+  /// Holds the VPLoopInfo analysis for this VPlan.
+  VPLoopInfo VPLInfo;
+
 public:
   VPlan(VPBlockBase *Entry = nullptr) : Entry(Entry) {}
 
   ~VPlan() {
     if (Entry)
       VPBlockBase::deleteCFG(Entry);
     for (auto &MapEntry : Value2VPValue)
       delete MapEntry.second;
public:
   }
 
   VPValue *getVPValue(Value *V) {
     assert(V && "Trying to get the VPValue of a null Value");
     assert(Value2VPValue.count(V) && "Value does not exist in VPlan");
     return Value2VPValue[V];
   }
 
+  /// Return the VPLoopInfo analysis for this VPlan.
+  VPLoopInfo &getVPLoopInfo() { return VPLInfo; }
+  const VPLoopInfo &getVPLoopInfo() const { return VPLInfo; }
+
 private:
   /// Add to the given dominator tree the header block and every new basic block
   /// that was created between it and the latch block, inclusive.
   static void updateDominatorTree(DominatorTree *DT,
                                   BasicBlock *LoopPreHeaderBB,
                                   BasicBlock *LoopLatchBB);
 };
 

lib/Transforms/Vectorize/VPlanHCFGBuilder.cpp

void VPlanHCFGBuilder::buildHierarchicalCFG() {
   LLVM_DEBUG(Plan.setName("HCFGBuilder: Plain CFG\n"); dbgs() << Plan);
 
   Verifier.verifyHierarchicalCFG(TopRegion);
 
   // Compute plain CFG dom tree for VPLInfo.
   VPDomTree.recalculate(*TopRegion);
   LLVM_DEBUG(dbgs() << "Dominator Tree after building the plain CFG.\n";
              VPDomTree.print(dbgs()));
+
+  // Compute VPLInfo and keep it in Plan.
+  VPLoopInfo &VPLInfo = Plan.getVPLoopInfo();
+  VPLInfo.analyze(VPDomTree);
+  LLVM_DEBUG(dbgs() << "VPLoop Info After buildPlainCFG:\n";
+             VPLInfo.print(dbgs()));
 }

lib/Transforms/Vectorize/VPlanLoopInfo.h

+//===-- VPLoopInfo.h --------------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file defines VPLoopInfo analysis and VPLoop class. VPLoopInfo is a
+/// specialization of LoopInfoBase for VPBlockBase. VPLoops is a specialization
+/// of LoopBase that is used to hold loop metadata from VPLoopInfo. Further
+/// information can be found in VectorizationPlanner.rst.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H
+#define LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H
+
+#include "llvm/Analysis/LoopInfoImpl.h"
+
+namespace llvm {
+class VPBlockBase;
+
+/// Hold analysis information for every loop detected by VPLoopInfo. It is an
+/// instantiation of LoopBase.
+class VPLoop : public LoopBase<VPBlockBase, VPLoop> {
+private:
+  friend class LoopInfoBase<VPBlockBase, VPLoop>;
+  explicit VPLoop(VPBlockBase *VPB) : LoopBase<VPBlockBase, VPLoop>(VPB) {}
+};
+
+/// VPLoopInfo provides analysis of natural loop for VPBlockBase-based
+/// Hierarchical CFG. It is a specialization of LoopInfoBase class.
+// TODO: VPLoopInfo is initially computed on top of the VPlan plain CFG, which
+// is the same as the incoming IR CFG. If it's more efficient than running the
+// whole loop detection algorithm, we may want to create a mechanism to
+// translate LoopInfo into VPLoopInfo. However, that would require significant
+// changes in LoopInfoBase class.
+typedef LoopInfoBase<VPBlockBase, VPLoop> VPLoopInfo;
+
+} // namespace llvm
+
+#endif // LLVM_TRANSFORMS_VECTORIZE_VPLOOPINFO_H

unittests/Transforms/Vectorize/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   Core
   Vectorize
   AsmParser
   )
 
 add_llvm_unittest(VectorizeTests
   VPlanDominatorTreeTest.cpp
+  VPlanLoopInfoTest.cpp
   VPlanTest.cpp
   VPlanHCFGTest.cpp
   )

unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp

+//===- llvm/unittests/Transforms/Vectorize/VPlanLoopInfoTest.cpp -----===//
+//
+//                     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/VPlanLoopInfo.h"
+#include "VPlanTestBase.h"
+#include "gtest/gtest.h"
+
+namespace llvm {
+namespace {
+
+class VPlanLoopInfo : public VPlanTestBase {};
+
+TEST_F(VPlanLoopInfo, BasicLoopInfoTest) {
+  const char *ModuleString =
+      "define void @f(i32* %a, i32* %b, i32* %c, i32 %N, i32 %M, i32 %K) {\n"
+      "entry:\n"
+      "  br label %for.body\n"
+      "for.body:\n"
+      "  %iv = phi i64 [ 0, %entry ], [ %iv.next, %for.inc ]\n"
+      "  br i1 true, label %if.then, label %if.else\n"
+      "if.then:\n"
+      "  br label %for.inc\n"
+      "if.else:\n"
+      "  br label %for.inc\n"
+      "for.inc:\n"
+      "  %iv.next = add nuw nsw i64 %iv, 1\n"
+      "  %exitcond = icmp eq i64 %iv.next, 300\n"
+      "  br i1 %exitcond, label %for.end, label %for.body\n"
+      "for.end:\n"
+      "  ret void\n"
+      "}\n";
+
+  Module &M = parseModule(ModuleString);
+
+  Function *F = M.getFunction("f");
+  BasicBlock *LoopHeader = F->getEntryBlock().getSingleSuccessor();
+  auto Plan = buildHCFG(LoopHeader);
+
+  // Build VPlan domination tree and loop info analyses.
+  VPRegionBlock *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
+  VPDominatorTree VPDT;
+  VPDT.recalculate(*TopRegion);
+  VPLoopInfo VPLI;
+  VPLI.analyze(VPDT);
+
+  VPBlockBase *PH = TopRegion->getEntry();
+  VPBlockBase *H = PH->getSingleSuccessor();
+  VPBlockBase *IfThen = H->getSuccessors()[0];
+  VPBlockBase *IfElse = H->getSuccessors()[1];
+  VPBlockBase *Latch = IfThen->getSingleSuccessor();
+  VPBlockBase *Exit = Latch->getSuccessors()[0] != H
+                          ? Latch->getSuccessors()[0]
+                          : Latch->getSuccessors()[1];
+
+  // Number of loops.
+  EXPECT_EQ(1, std::distance(VPLI.begin(), VPLI.end()));
+  VPLoop *VPLp = *VPLI.begin();
+
+  // VPBBs contained in VPLoop.
+  EXPECT_FALSE(VPLp->contains(PH));
+  EXPECT_EQ(nullptr, VPLI.getLoopFor(PH));
+  EXPECT_TRUE(VPLp->contains(H));
+  EXPECT_EQ(VPLp, VPLI.getLoopFor(H));
+  EXPECT_TRUE(VPLp->contains(IfThen));
+  EXPECT_EQ(VPLp, VPLI.getLoopFor(IfThen));
+  EXPECT_TRUE(VPLp->contains(IfElse));
+  EXPECT_EQ(VPLp, VPLI.getLoopFor(IfElse));
+  EXPECT_TRUE(VPLp->contains(Latch));
+  EXPECT_EQ(VPLp, VPLI.getLoopFor(Latch));
+  EXPECT_FALSE(VPLp->contains(Exit));
+  EXPECT_EQ(nullptr, VPLI.getLoopFor(Exit));
+
+  // VPLoop's parts.
+  EXPECT_EQ(PH, VPLp->getLoopPreheader());
+  EXPECT_EQ(H, VPLp->getHeader());
+  EXPECT_EQ(Latch, VPLp->getLoopLatch());
+  EXPECT_EQ(Latch, VPLp->getExitingBlock());
+  EXPECT_EQ(Exit, VPLp->getExitBlock());
+}
+} // namespace
+} // namespace llvm