Index: polly/include/polly/LinkAllPasses.h =================================================================== --- polly/include/polly/LinkAllPasses.h +++ polly/include/polly/LinkAllPasses.h @@ -35,10 +35,10 @@ llvm::Pass *createDependenceInfoWrapperPassPass(); llvm::Pass * createDependenceInfoPrinterLegacyFunctionPass(llvm::raw_ostream &OS); -llvm::Pass *createDOTOnlyPrinterPass(); -llvm::Pass *createDOTOnlyViewerPass(); -llvm::Pass *createDOTPrinterPass(); -llvm::Pass *createDOTViewerPass(); +llvm::Pass *createDOTOnlyPrinterWrapperPass(); +llvm::Pass *createDOTOnlyViewerWrapperPass(); +llvm::Pass *createDOTPrinterWrapperPass(); +llvm::Pass *createDOTViewerWrapperPass(); llvm::Pass *createJSONExporterPass(); llvm::Pass *createJSONImporterPass(); llvm::Pass *createJSONImporterPrinterLegacyPass(llvm::raw_ostream &OS); @@ -94,10 +94,10 @@ polly::createDependenceInfoPrinterLegacyPass(llvm::outs()); polly::createDependenceInfoWrapperPassPass(); polly::createDependenceInfoPrinterLegacyFunctionPass(llvm::outs()); - polly::createDOTOnlyPrinterPass(); - polly::createDOTOnlyViewerPass(); - polly::createDOTPrinterPass(); - polly::createDOTViewerPass(); + polly::createDOTOnlyPrinterWrapperPass(); + polly::createDOTOnlyViewerWrapperPass(); + polly::createDOTPrinterWrapperPass(); + polly::createDOTViewerWrapperPass(); polly::createJSONExporterPass(); polly::createJSONImporterPass(); polly::createJSONImporterPrinterLegacyPass(llvm::outs()); Index: polly/include/polly/ScopGraphPrinter.h =================================================================== --- /dev/null +++ polly/include/polly/ScopGraphPrinter.h @@ -0,0 +1,100 @@ +//===- GraphPrinter.h - Create a DOT output describing the Scop. ----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Create a DOT output describing the Scop. +// +// For each function a dot file is created that shows the control flow graph of +// the function and highlights the detected Scops. +// +//===----------------------------------------------------------------------===// + +#ifndef POLLY_SCOP_GRAPH_PRINTER_H +#define POLLY_SCOP_GRAPH_PRINTER_H + +#include "polly/ScopDetection.h" +#include "polly/Support/ScopLocation.h" +#include "llvm/Analysis/DOTGraphTraitsPass.h" +#include "llvm/Analysis/RegionInfo.h" +#include "llvm/Analysis/RegionIterator.h" +#include "llvm/IR/PassManager.h" + +using namespace polly; +using namespace llvm; + +namespace llvm { + +template <> +struct GraphTraits : public GraphTraits { + static NodeRef getEntryNode(const ScopDetection &SD) { + return GraphTraits::getEntryNode(SD.getRI()); + } + static nodes_iterator nodes_begin(const ScopDetection &SD) { + return nodes_iterator::begin(getEntryNode(SD)); + } + static nodes_iterator nodes_end(const ScopDetection &SD) { + return nodes_iterator::end(getEntryNode(SD)); + } +}; + +// this class has been implemented in LLVM RegionPrinter.cpp +template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { + DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} + + std::string getNodeLabel(RegionNode *Node, RegionNode *Graph); +}; + +template <> +struct DOTGraphTraits : public DOTGraphTraits { + DOTGraphTraits(bool isSimple = false) + : DOTGraphTraits(isSimple) {} + static std::string getGraphName(ScopDetection *SD) { return "Scop Graph"; } + + std::string getEdgeAttributes(RegionNode *srcNode, + GraphTraits::ChildIteratorType CI, + ScopDetection *SD); + + std::string getNodeLabel(RegionNode *Node, ScopDetection *SD) { + return DOTGraphTraits::getNodeLabel( + Node, reinterpret_cast(SD->getRI()->getTopLevelRegion())); + } + + static std::string escapeString(std::string String); + + // Print the cluster of the subregions. This groups the single basic blocks + // and adds a different background color for each group. + static void printRegionCluster(ScopDetection *SD, const Region *R, + raw_ostream &O, unsigned depth); + + static void addCustomGraphFeatures(ScopDetection *SD, + GraphWriter &GW); +}; +} // end namespace llvm + +namespace polly { + +struct ScopViewer : public DOTGraphTraitsViewer { + ScopViewer() : DOTGraphTraitsViewer("scops") {} + + bool processFunction(Function &F, const ScopDetection &SD) override; +}; + +struct ScopOnlyViewer : public DOTGraphTraitsViewer { + ScopOnlyViewer() : DOTGraphTraitsViewer("scops-only") {} +}; + +struct ScopPrinter : public DOTGraphTraitsPrinter { + ScopPrinter() : DOTGraphTraitsPrinter("scops") {} +}; + +struct ScopOnlyPrinter : public DOTGraphTraitsPrinter { + ScopOnlyPrinter() : DOTGraphTraitsPrinter("scopsonly") {} +}; + +} // end namespace polly + +#endif /* POLLY_SCOP_GRAPH_PRINTER_H */ Index: polly/lib/Analysis/ScopGraphPrinter.cpp =================================================================== --- polly/lib/Analysis/ScopGraphPrinter.cpp +++ polly/lib/Analysis/ScopGraphPrinter.cpp @@ -13,12 +13,9 @@ // //===----------------------------------------------------------------------===// +#include "polly/ScopGraphPrinter.h" #include "polly/LinkAllPasses.h" #include "polly/ScopDetection.h" -#include "polly/Support/ScopLocation.h" -#include "llvm/Analysis/DOTGraphTraitsPass.h" -#include "llvm/Analysis/RegionInfo.h" -#include "llvm/Analysis/RegionIterator.h" #include "llvm/Support/CommandLine.h" using namespace polly; @@ -33,175 +30,124 @@ cl::Hidden, cl::init(false), cl::ZeroOrMore); namespace llvm { -template <> -struct GraphTraits : public GraphTraits { - static NodeRef getEntryNode(ScopDetection *SD) { - return GraphTraits::getEntryNode(SD->getRI()); - } - static nodes_iterator nodes_begin(ScopDetection *SD) { - return nodes_iterator::begin(getEntryNode(SD)); - } - static nodes_iterator nodes_end(ScopDetection *SD) { - return nodes_iterator::end(getEntryNode(SD)); - } -}; - -template <> -struct GraphTraits - : public GraphTraits { - static NodeRef getEntryNode(ScopDetectionWrapperPass *P) { - return GraphTraits::getEntryNode(&P->getSD()); - } - static nodes_iterator nodes_begin(ScopDetectionWrapperPass *P) { - return nodes_iterator::begin(getEntryNode(P)); - } - static nodes_iterator nodes_end(ScopDetectionWrapperPass *P) { - return nodes_iterator::end(getEntryNode(P)); - } -}; - -template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { - DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} - - std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) { - if (!Node->isSubRegion()) { - BasicBlock *BB = Node->getNodeAs(); - if (isSimple()) - return DOTGraphTraits::getSimpleNodeLabel(BB, nullptr); +std::string DOTGraphTraits::getEdgeAttributes( + RegionNode *srcNode, GraphTraits::ChildIteratorType CI, + ScopDetection *SD) { + RegionNode *destNode = *CI; - else - return DOTGraphTraits::getCompleteNodeLabel(BB, nullptr); - } - - return "Not implemented"; - } -}; + if (srcNode->isSubRegion() || destNode->isSubRegion()) + return ""; -template <> -struct DOTGraphTraits - : public DOTGraphTraits { - DOTGraphTraits(bool isSimple = false) - : DOTGraphTraits(isSimple) {} - static std::string getGraphName(ScopDetectionWrapperPass *SD) { - return "Scop Graph"; - } + // In case of a backedge, do not use it to define the layout of the nodes. + BasicBlock *srcBB = srcNode->getNodeAs(); + BasicBlock *destBB = destNode->getNodeAs(); - std::string getEdgeAttributes(RegionNode *srcNode, - GraphTraits::ChildIteratorType CI, - ScopDetectionWrapperPass *P) { - RegionNode *destNode = *CI; - auto *SD = &P->getSD(); + RegionInfo *RI = SD->getRI(); + Region *R = RI->getRegionFor(destBB); - if (srcNode->isSubRegion() || destNode->isSubRegion()) - return ""; + while (R && R->getParent()) + if (R->getParent()->getEntry() == destBB) + R = R->getParent(); + else + break; - // In case of a backedge, do not use it to define the layout of the nodes. - BasicBlock *srcBB = srcNode->getNodeAs(); - BasicBlock *destBB = destNode->getNodeAs(); + if (R && R->getEntry() == destBB && R->contains(srcBB)) + return "constraint=false"; - RegionInfo *RI = SD->getRI(); - Region *R = RI->getRegionFor(destBB); + return ""; +} - while (R && R->getParent()) - if (R->getParent()->getEntry() == destBB) - R = R->getParent(); - else - break; +std::string DOTGraphTraits::escapeString(std::string String) { + std::string Escaped; - if (R && R->getEntry() == destBB && R->contains(srcBB)) - return "constraint=false"; + for (const auto &C : String) { + if (C == '"') + Escaped += '\\'; - return ""; + Escaped += C; } - - std::string getNodeLabel(RegionNode *Node, ScopDetectionWrapperPass *P) { - return DOTGraphTraits::getNodeLabel( - Node, reinterpret_cast( - P->getSD().getRI()->getTopLevelRegion())); + return Escaped; +} + +void DOTGraphTraits::printRegionCluster(ScopDetection *SD, + const Region *R, + raw_ostream &O, + unsigned depth = 0) { + O.indent(2 * depth) << "subgraph cluster_" << static_cast(R) + << " {\n"; + unsigned LineBegin, LineEnd; + std::string FileName; + + getDebugLocation(R, LineBegin, LineEnd, FileName); + + std::string Location; + if (LineBegin != (unsigned)-1) { + Location = escapeString(FileName + ":" + std::to_string(LineBegin) + "-" + + std::to_string(LineEnd) + "\n"); } - static std::string escapeString(std::string String) { - std::string Escaped; - - for (const auto &C : String) { - if (C == '"') - Escaped += '\\'; - - Escaped += C; - } - return Escaped; - } + std::string ErrorMessage = SD->regionIsInvalidBecause(R); + ErrorMessage = escapeString(ErrorMessage); + O.indent(2 * (depth + 1)) + << "label = \"" << Location << ErrorMessage << "\";\n"; - // Print the cluster of the subregions. This groups the single basic blocks - // and adds a different background color for each group. - static void printRegionCluster(ScopDetection *SD, const Region *R, - raw_ostream &O, unsigned depth = 0) { - O.indent(2 * depth) << "subgraph cluster_" << static_cast(R) - << " {\n"; - unsigned LineBegin, LineEnd; - std::string FileName; + if (SD->isMaxRegionInScop(*R)) { + O.indent(2 * (depth + 1)) << "style = filled;\n"; - getDebugLocation(R, LineBegin, LineEnd, FileName); + // Set color to green. + O.indent(2 * (depth + 1)) << "color = 3"; + } else { + O.indent(2 * (depth + 1)) << "style = solid;\n"; - std::string Location; - if (LineBegin != (unsigned)-1) { - Location = escapeString(FileName + ":" + std::to_string(LineBegin) + "-" + - std::to_string(LineEnd) + "\n"); - } + int color = (R->getDepth() * 2 % 12) + 1; - std::string ErrorMessage = SD->regionIsInvalidBecause(R); - ErrorMessage = escapeString(ErrorMessage); - O.indent(2 * (depth + 1)) - << "label = \"" << Location << ErrorMessage << "\";\n"; + // We do not want green again. + if (color == 3) + color = 6; - if (SD->isMaxRegionInScop(*R)) { - O.indent(2 * (depth + 1)) << "style = filled;\n"; - - // Set color to green. - O.indent(2 * (depth + 1)) << "color = 3"; - } else { - O.indent(2 * (depth + 1)) << "style = solid;\n"; + O.indent(2 * (depth + 1)) << "color = " << color << "\n"; + } - int color = (R->getDepth() * 2 % 12) + 1; + for (const auto &SubRegion : *R) + printRegionCluster(SD, SubRegion.get(), O, depth + 1); - // We do not want green again. - if (color == 3) - color = 6; + RegionInfo *RI = R->getRegionInfo(); - O.indent(2 * (depth + 1)) << "color = " << color << "\n"; - } + for (BasicBlock *BB : R->blocks()) + if (RI->getRegionFor(BB) == R) + O.indent(2 * (depth + 1)) + << "Node" + << static_cast(RI->getTopLevelRegion()->getBBNode(BB)) + << ";\n"; - for (const auto &SubRegion : *R) - printRegionCluster(SD, SubRegion.get(), O, depth + 1); + O.indent(2 * depth) << "}\n"; +} - RegionInfo *RI = R->getRegionInfo(); +void DOTGraphTraits::addCustomGraphFeatures( + ScopDetection *SD, GraphWriter &GW) { + raw_ostream &O = GW.getOStream(); + O << "\tcolorscheme = \"paired12\"\n"; + printRegionCluster(SD, SD->getRI()->getTopLevelRegion(), O, 4); +} - for (BasicBlock *BB : R->blocks()) - if (RI->getRegionFor(BB) == R) - O.indent(2 * (depth + 1)) - << "Node" - << static_cast(RI->getTopLevelRegion()->getBBNode(BB)) - << ";\n"; +} // namespace llvm - O.indent(2 * depth) << "}\n"; - } - static void - addCustomGraphFeatures(const ScopDetectionWrapperPass *SD, - GraphWriter &GW) { - raw_ostream &O = GW.getOStream(); - O << "\tcolorscheme = \"paired12\"\n"; - printRegionCluster(&SD->getSD(), SD->getSD().getRI()->getTopLevelRegion(), - O, 4); +struct ScopDetectionAnalysisGraphTraits { + static ScopDetection &getGraph(ScopDetectionWrapperPass *Analysis) { + return Analysis->getSD(); } }; -} // end namespace llvm -struct ScopViewer - : public DOTGraphTraitsViewerWrapperPass { +struct ScopViewerWrapperPass + : public DOTGraphTraitsViewerWrapperPass { static char ID; - ScopViewer() - : DOTGraphTraitsViewerWrapperPass( + ScopViewerWrapperPass() + : DOTGraphTraitsViewerWrapperPass( "scops", ID) {} bool processFunction(Function &F, ScopDetectionWrapperPass &SD) override { if (ViewFilter != "" && !F.getName().count(ViewFilter)) @@ -214,53 +160,84 @@ return std::distance(SD.getSD().begin(), SD.getSD().end()) > 0; } }; -char ScopViewer::ID = 0; +char ScopViewerWrapperPass::ID = 0; -struct ScopOnlyViewer - : public DOTGraphTraitsViewerWrapperPass { +struct ScopOnlyViewerWrapperPass + : public DOTGraphTraitsViewerWrapperPass { static char ID; - ScopOnlyViewer() - : DOTGraphTraitsViewerWrapperPass( + ScopOnlyViewerWrapperPass() + : DOTGraphTraitsViewerWrapperPass( "scopsonly", ID) {} }; -char ScopOnlyViewer::ID = 0; +char ScopOnlyViewerWrapperPass::ID = 0; -struct ScopPrinter - : public DOTGraphTraitsPrinterWrapperPass { +struct ScopPrinterWrapperPass + : public DOTGraphTraitsPrinterWrapperPass< + ScopDetectionWrapperPass, false, ScopDetection &, + ScopDetectionAnalysisGraphTraits> { static char ID; - ScopPrinter() - : DOTGraphTraitsPrinterWrapperPass( + ScopPrinterWrapperPass() + : DOTGraphTraitsPrinterWrapperPass( "scops", ID) {} }; -char ScopPrinter::ID = 0; +char ScopPrinterWrapperPass::ID = 0; -struct ScopOnlyPrinter - : public DOTGraphTraitsPrinterWrapperPass { +struct ScopOnlyPrinterWrapperPass + : public DOTGraphTraitsPrinterWrapperPass< + ScopDetectionWrapperPass, true, ScopDetection &, + ScopDetectionAnalysisGraphTraits> { static char ID; - ScopOnlyPrinter() - : DOTGraphTraitsPrinterWrapperPass( + ScopOnlyPrinterWrapperPass() + : DOTGraphTraitsPrinterWrapperPass( "scopsonly", ID) {} }; -char ScopOnlyPrinter::ID = 0; +char ScopOnlyPrinterWrapperPass::ID = 0; -static RegisterPass X("view-scops", - "Polly - View Scops of function"); +static RegisterPass X("view-scops", + "Polly - View Scops of function"); -static RegisterPass +static RegisterPass Y("view-scops-only", "Polly - View Scops of function (with no function bodies)"); -static RegisterPass M("dot-scops", - "Polly - Print Scops of function"); +static RegisterPass + M("dot-scops", "Polly - Print Scops of function"); -static RegisterPass +static RegisterPass N("dot-scops-only", "Polly - Print Scops of function (with no function bodies)"); -Pass *polly::createDOTViewerPass() { return new ScopViewer(); } +Pass *polly::createDOTViewerWrapperPass() { + return new ScopViewerWrapperPass(); +} + +Pass *polly::createDOTOnlyViewerWrapperPass() { + return new ScopOnlyViewerWrapperPass(); +} + +Pass *polly::createDOTPrinterWrapperPass() { + return new ScopPrinterWrapperPass(); +} + +Pass *polly::createDOTOnlyPrinterWrapperPass() { + return new ScopOnlyPrinterWrapperPass(); +} -Pass *polly::createDOTOnlyViewerPass() { return new ScopOnlyViewer(); } +bool ScopViewer::processFunction(Function &F, const ScopDetection &SD) { + if (ViewFilter != "" && !F.getName().count(ViewFilter)) + return false; -Pass *polly::createDOTPrinterPass() { return new ScopPrinter(); } + if (ViewAll) + return true; -Pass *polly::createDOTOnlyPrinterPass() { return new ScopOnlyPrinter(); } + // Check that at least one scop was detected. + return std::distance(SD.begin(), SD.end()) > 0; +} Index: polly/lib/Support/PollyPasses.def =================================================================== --- polly/lib/Support/PollyPasses.def +++ polly/lib/Support/PollyPasses.def @@ -11,6 +11,10 @@ FUNCTION_PASS("polly-prepare", CodePreparationPass()) FUNCTION_PASS("print", ScopAnalysisPrinterPass(llvm::errs())) FUNCTION_PASS("print", ScopInfoPrinterPass(llvm::errs())) +FUNCTION_PASS("polly-scop-viewer", ScopViewer()) +FUNCTION_PASS("polly-scop-only-viewer", ScopOnlyViewer()) +FUNCTION_PASS("polly-scop-printer", ScopPrinter()) +FUNCTION_PASS("polly-scop-only-printer", ScopOnlyPrinter()) #undef FUNCTION_PASS #ifndef SCOP_ANALYSIS Index: polly/lib/Support/RegisterPasses.cpp =================================================================== --- polly/lib/Support/RegisterPasses.cpp +++ polly/lib/Support/RegisterPasses.cpp @@ -34,6 +34,7 @@ #include "polly/PruneUnprofitable.h" #include "polly/ScheduleOptimizer.h" #include "polly/ScopDetection.h" +#include "polly/ScopGraphPrinter.h" #include "polly/ScopInfo.h" #include "polly/Simplify.h" #include "polly/Support/DumpFunctionPass.h" @@ -331,14 +332,13 @@ return; if (PollyViewer) - PM.add(polly::createDOTViewerPass()); + PM.add(polly::createDOTViewerWrapperPass()); if (PollyOnlyViewer) - PM.add(polly::createDOTOnlyViewerPass()); + PM.add(polly::createDOTOnlyViewerWrapperPass()); if (PollyPrinter) - PM.add(polly::createDOTPrinterPass()); + PM.add(polly::createDOTPrinterWrapperPass()); if (PollyOnlyPrinter) - PM.add(polly::createDOTOnlyPrinterPass()); - + PM.add(polly::createDOTOnlyPrinterWrapperPass()); PM.add(polly::createScopInfoRegionPassPass()); if (EnablePolyhedralInfo) PM.add(polly::createPolyhedralInfoPass()); @@ -509,16 +509,13 @@ } if (PollyViewer) - llvm::report_fatal_error("Option -polly-show not supported with NPM", - false); + PM.addPass(ScopViewer()); if (PollyOnlyViewer) - llvm::report_fatal_error("Option -polly-show-only not supported with NPM", - false); + PM.addPass(ScopOnlyViewer()); if (PollyPrinter) - llvm::report_fatal_error("Option -polly-dot not supported with NPM", false); + PM.addPass(ScopPrinter()); if (PollyOnlyPrinter) - llvm::report_fatal_error("Option -polly-dot-only not supported with NPM", - false); + PM.addPass(ScopOnlyPrinter()); if (EnablePolyhedralInfo) llvm::report_fatal_error( "Option -polly-enable-polyhedralinfo not supported with NPM", false); Index: polly/test/ScopDetect/dot-scops-npm.ll =================================================================== --- /dev/null +++ polly/test/ScopDetect/dot-scops-npm.ll @@ -0,0 +1,47 @@ +; RUN: opt %loadPolly "-passes=polly-scop-viewer" -disable-output < %s +; +; Check that the ScopPrinter does not crash. +; ScopPrinter needs the ScopDetection pass, which should depend on +; ScalarEvolution transitively. + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @func(i32 %n, i32 %m, double* noalias nonnull %A) { +entry: + br label %outer.for + +outer.for: + %j = phi i32 [0, %entry], [%j.inc, %outer.inc] + %j.cmp = icmp slt i32 %j, %n + br i1 %j.cmp, label %inner.for, label %outer.exit + + inner.for: + %i = phi i32 [1, %outer.for], [%i.inc, %inner.inc] + %b = phi double [0.0, %outer.for], [%a, %inner.inc] + %i.cmp = icmp slt i32 %i, %m + br i1 %i.cmp, label %body1, label %inner.exit + + body1: + %A_idx = getelementptr inbounds double, double* %A, i32 %i + %a = load double, double* %A_idx + store double %a, double* %A_idx + br label %inner.inc + + inner.inc: + %i.inc = add nuw nsw i32 %i, 1 + br label %inner.for + + inner.exit: + br label %outer.inc + +outer.inc: + store double %b, double* %A + %j.inc = add nuw nsw i32 %j, 1 + br label %outer.for + +outer.exit: + br label %return + +return: + ret void +}