-
Notifications
You must be signed in to change notification settings - Fork 12.9k
Commit
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
[GSoC] Add PolyhedralInfo pass - new interface to polly analysis
Adding a new pass PolyhedralInfo. This pass will be the interface to Polly.
Initially, we will provide the following interface:
- #IsParallel(Loop *L) - return a bool depending on whether the loop is
parallel or not for the given program order.
Patch by Utpal Bora <cs14mtech11017@iith.ac.in>
Differential Revision: https://reviews.llvm.org/D21486
llvm-svn: 276637- Loading branch information
Johannes Doerfert
committed
Jul 25, 2016
1 parent
13c78e4
commit 8031238
Showing
24 changed files
with
349 additions
and
16 deletions.
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
| Original file line number | Diff line number | Diff line change |
|---|---|---|
| @@ -0,0 +1,101 @@ | ||
| //===- polly/PolyhedralInfo.h - PolyhedralInfo class definition -*- C++ -*-===// | ||
| // | ||
| // The LLVM Compiler Infrastructure | ||
| // | ||
| // This file is distributed under the University of Illinois Open Source | ||
| // License. See LICENSE.TXT for details. | ||
| // | ||
| //===----------------------------------------------------------------------===// | ||
| /// | ||
| /// This file contains the declaration of the PolyhedralInfo class, which will | ||
| /// provide an interface to expose polyhedral analysis information of Polly. | ||
| /// | ||
| /// This is work in progress. We will add more API's as an when deemed required. | ||
| //===----------------------------------------------------------------------===/// | ||
|
|
||
| #ifndef POLLY_POLYHEDRAL_INFO_H | ||
| #define POLLY_POLYHEDRAL_INFO_H | ||
|
|
||
| #include "llvm/Pass.h" | ||
| #include "isl/ctx.h" | ||
| #include "isl/union_map.h" | ||
|
|
||
| namespace llvm { | ||
| class Loop; | ||
| } | ||
|
|
||
| namespace polly { | ||
|
|
||
| class Scop; | ||
| class ScopInfoWrapperPass; | ||
| class DependenceInfoWrapperPass; | ||
|
|
||
| class PolyhedralInfo : public llvm::FunctionPass { | ||
| public: | ||
| static char ID; // Pass identification, replacement for typeid | ||
|
|
||
| /// @brief Construct a new PolyhedralInfo pass. | ||
| PolyhedralInfo() : FunctionPass(ID) {} | ||
| ~PolyhedralInfo() {} | ||
|
|
||
| /// @brief Check if a given loop is parallel. | ||
| /// | ||
| /// @param L The loop. | ||
| /// | ||
| /// @return Returns true, if loop is parallel false otherwise. | ||
| bool isParallel(llvm::Loop *L) const; | ||
|
|
||
| /// @brief Return the SCoP containing the @p L loop. | ||
| /// | ||
| /// @param L The loop. | ||
| /// | ||
| /// @return Returns the SCoP containing the given loop. | ||
| /// Returns null if the loop is not contained in any SCoP. | ||
| const Scop *getScopContainingLoop(llvm::Loop *L) const; | ||
|
|
||
| /// @brief Computes the partial schedule for the given @p L loop. | ||
| /// | ||
| /// @param S The SCoP containing the given loop | ||
| /// @param L The loop. | ||
| /// | ||
| /// @return Returns the partial schedule for the given loop | ||
| __isl_give isl_union_map *getScheduleForLoop(const Scop *S, | ||
| llvm::Loop *L) const; | ||
|
|
||
| /// @brief Get the SCoP and dependence analysis information for @p F. | ||
| bool runOnFunction(llvm::Function &F) override; | ||
|
|
||
| /// @brief Release the internal memory. | ||
| void releaseMemory() override {} | ||
|
|
||
| /// @brief Print to @p OS if each dimension of a loop nest is parallel or not. | ||
| void print(llvm::raw_ostream &OS, | ||
| const llvm::Module *M = nullptr) const override; | ||
|
|
||
| /// @brief Register all analyses and transformation required. | ||
| void getAnalysisUsage(llvm::AnalysisUsage &AU) const override; | ||
|
|
||
| private: | ||
| /// @brief Check if a given loop is parallel or vectorizable. | ||
| /// | ||
| /// @param L The loop. | ||
| /// @param MinDepDistPtr If not nullptr, the minimal dependence distance will | ||
| /// be returned at the address of that pointer | ||
| /// | ||
| /// @return Returns true if loop is parallel or vectorizable, false | ||
| /// otherwise. | ||
| bool checkParallel(llvm::Loop *L, | ||
| __isl_give isl_pw_aff **MinDepDistPtr = nullptr) const; | ||
|
|
||
| ScopInfoWrapperPass *SI; | ||
| DependenceInfoWrapperPass *DI; | ||
| }; | ||
|
|
||
| } // end namespace polly | ||
|
|
||
| namespace llvm { | ||
| class PassRegistry; | ||
| void initializePolyhedralInfoPass(llvm::PassRegistry &); | ||
| } | ||
|
|
||
| #endif |
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,162 @@ | ||
| //===--------- PolyhedralInfo.cpp - Create Scops from LLVM IR-------------===// | ||
| /// | ||
| /// The LLVM Compiler Infrastructure | ||
| /// | ||
| /// This file is distributed under the University of Illinois Open Source | ||
| /// License. See LICENSE.TXT for details. | ||
| /// | ||
| //===----------------------------------------------------------------------===// | ||
| /// | ||
| /// An interface to the Polyhedral analysis engine(Polly) of LLVM. | ||
| /// | ||
| /// This pass provides an interface to the polyhedral analysis performed by | ||
| /// Polly. | ||
| /// | ||
| /// This interface provides basic interface like isParallel, isVectorizable | ||
| /// that can be used in LLVM transformation passes. | ||
| /// | ||
| /// Work in progress, this file is subject to change. | ||
| //===----------------------------------------------------------------------===// | ||
|
|
||
| #include "polly/PolyhedralInfo.h" | ||
| #include "polly/DependenceInfo.h" | ||
| #include "polly/LinkAllPasses.h" | ||
| #include "polly/Options.h" | ||
| #include "polly/ScopInfo.h" | ||
| #include "polly/Support/GICHelper.h" | ||
| #include "llvm/Analysis/LoopInfo.h" | ||
| #include "llvm/Support/Debug.h" | ||
| #include <isl/map.h> | ||
| #include <isl/union_map.h> | ||
|
|
||
| using namespace llvm; | ||
| using namespace polly; | ||
|
|
||
| #define DEBUG_TYPE "polyhedral-info" | ||
|
|
||
| static cl::opt<bool> CheckParallel("polly-check-parallel", | ||
| cl::desc("Check for parallel loops"), | ||
| cl::Hidden, cl::init(false), cl::ZeroOrMore, | ||
| cl::cat(PollyCategory)); | ||
|
|
||
| static cl::opt<bool> CheckVectorizable("polly-check-vectorizable", | ||
| cl::desc("Check for vectorizable loops"), | ||
| cl::Hidden, cl::init(false), | ||
| cl::ZeroOrMore, cl::cat(PollyCategory)); | ||
|
|
||
| void PolyhedralInfo::getAnalysisUsage(AnalysisUsage &AU) const { | ||
| AU.addRequiredTransitive<DependenceInfoWrapperPass>(); | ||
| AU.addRequired<LoopInfoWrapperPass>(); | ||
| AU.addRequiredTransitive<ScopInfoWrapperPass>(); | ||
| AU.setPreservesAll(); | ||
| } | ||
|
|
||
| bool PolyhedralInfo::runOnFunction(Function &F) { | ||
| DI = &getAnalysis<DependenceInfoWrapperPass>(); | ||
| SI = &getAnalysis<ScopInfoWrapperPass>(); | ||
| return false; | ||
| } | ||
|
|
||
| void PolyhedralInfo::print(raw_ostream &OS, const Module *) const { | ||
| auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | ||
| for (auto *TopLevelLoop : LI) { | ||
| for (auto *L : depth_first(TopLevelLoop)) { | ||
| OS.indent(2) << L->getHeader()->getName() << ":\t"; | ||
| if (CheckParallel && isParallel(L)) | ||
| OS << "Loop is parallel.\n"; | ||
| else if (CheckParallel) | ||
| OS << "Loop is not parallel.\n"; | ||
| } | ||
| } | ||
| } | ||
|
|
||
| bool PolyhedralInfo::checkParallel(Loop *L, isl_pw_aff **MinDepDistPtr) const { | ||
| bool IsParallel; | ||
| const Scop *S = getScopContainingLoop(L); | ||
| if (!S) | ||
| return false; | ||
| const Dependences &D = | ||
| DI->getDependences(const_cast<Scop *>(S), Dependences::AL_Access); | ||
| if (!D.hasValidDependences()) | ||
| return false; | ||
| DEBUG(dbgs() << "Loop :\t" << L->getHeader()->getName() << ":\n"); | ||
|
|
||
| isl_union_map *Deps = | ||
| D.getDependences(Dependences::TYPE_RAW | Dependences::TYPE_WAW | | ||
| Dependences::TYPE_WAR | Dependences::TYPE_RED); | ||
| DEBUG(dbgs() << "Dependences :\t" << stringFromIslObj(Deps) << "\n"); | ||
|
|
||
| isl_union_map *Schedule = getScheduleForLoop(S, L); | ||
| DEBUG(dbgs() << "Schedule: \t" << stringFromIslObj(Schedule) << "\n"); | ||
|
|
||
| IsParallel = D.isParallel(Schedule, Deps, MinDepDistPtr); | ||
| isl_union_map_free(Schedule); | ||
| return IsParallel; | ||
| } | ||
|
|
||
| bool PolyhedralInfo::isParallel(Loop *L) const { return checkParallel(L); } | ||
|
|
||
| const Scop *PolyhedralInfo::getScopContainingLoop(Loop *L) const { | ||
| assert((SI) && "ScopInfoWrapperPass is required by PolyhedralInfo pass!\n"); | ||
| for (auto &It : *SI) { | ||
| Region *R = It.first; | ||
| if (R->contains(L)) | ||
| return It.second.get(); | ||
| } | ||
| return nullptr; | ||
| } | ||
|
|
||
| // Given a Loop and the containing SCoP, we compute the partial schedule | ||
| // by taking union of individual schedules of each ScopStmt within the loop | ||
| // and projecting out the inner dimensions from the range of the schedule. | ||
| // for (i = 0; i < n; i++) | ||
| // for (j = 0; j < n; j++) | ||
| // A[j] = 1; //Stmt | ||
| // | ||
| // The original schedule will be | ||
| // Stmt[i0, i1] -> [i0, i1] | ||
| // The schedule for the outer loop will be | ||
| // Stmt[i0, i1] -> [i0] | ||
| // The schedule for the inner loop will be | ||
| // Stmt[i0, i1] -> [i0, i1] | ||
| __isl_give isl_union_map *PolyhedralInfo::getScheduleForLoop(const Scop *S, | ||
| Loop *L) const { | ||
| isl_union_map *Schedule = isl_union_map_empty(S->getParamSpace()); | ||
| int CurrDim = S->getRelativeLoopDepth(L); | ||
| DEBUG(dbgs() << "Relative loop depth:\t" << CurrDim << "\n"); | ||
| assert(CurrDim >= 0 && "Loop in region should have at least depth one"); | ||
|
|
||
| for (auto *BB : L->blocks()) { | ||
| auto *SS = S->getStmtFor(BB); | ||
| if (!SS) | ||
| continue; | ||
|
|
||
| unsigned int MaxDim = SS->getNumIterators(); | ||
| DEBUG(dbgs() << "Maximum depth of Stmt:\t" << MaxDim << "\n"); | ||
| auto *ScheduleMap = SS->getSchedule(); | ||
|
|
||
| ScheduleMap = isl_map_project_out(ScheduleMap, isl_dim_out, CurrDim + 1, | ||
| MaxDim - CurrDim - 1); | ||
| ScheduleMap = | ||
| isl_map_set_tuple_id(ScheduleMap, isl_dim_in, SS->getDomainId()); | ||
| Schedule = | ||
| isl_union_map_union(Schedule, isl_union_map_from_map(ScheduleMap)); | ||
| } | ||
|
|
||
| Schedule = isl_union_map_coalesce(Schedule); | ||
| return Schedule; | ||
| } | ||
|
|
||
| char PolyhedralInfo::ID = 0; | ||
|
|
||
| Pass *polly::createPolyhedralInfoPass() { return new PolyhedralInfo(); } | ||
|
|
||
| INITIALIZE_PASS_BEGIN(PolyhedralInfo, "polyhedral-info", | ||
| "Polly - Interface to polyhedral analysis engine", false, | ||
| false); | ||
| INITIALIZE_PASS_DEPENDENCY(DependenceInfoWrapperPass); | ||
| INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); | ||
| INITIALIZE_PASS_DEPENDENCY(ScopInfoWrapperPass); | ||
| INITIALIZE_PASS_END(PolyhedralInfo, "polyhedral-info", | ||
| "Polly - Interface to polyhedral analysis engine", false, | ||
| false) |
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
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
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
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
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
9 changes: 6 additions & 3 deletions
9
polly/test/Isl/Ast/dependence_distance_varying_in_outer_loop.ll
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
12 changes: 8 additions & 4 deletions
12
polly/test/Isl/Ast/reduction_clauses_multidimensional_access.ll
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
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