-
Notifications
You must be signed in to change notification settings - Fork 12.8k
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
[VPlan] Introduce VPLoopInfo analysis.
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. Reviewers: fhahn, rengolin, mkuper, hfinkel, mssimpso Reviewed By: fhahn Differential Revision: https://reviews.llvm.org/D48816 llvm-svn: 338346
- Loading branch information
Showing
5 changed files
with
154 additions
and
1 deletion.
There are no files selected for viewing
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,45 @@ | ||
//===-- 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 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Original file line number | Diff line number | Diff line change |
---|---|---|
@@ -0,0 +1,87 @@ | ||
//===- 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 |