1 //===- GraphPrinter.cpp - Create a DOT output describing the Scop. --------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Create a DOT output describing the Scop.
10 //
11 // For each function a dot file is created that shows the control flow graph of
12 // the function and highlights the detected Scops.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "polly/LinkAllPasses.h"
17 #include "polly/ScopDetection.h"
18 #include "polly/Support/ScopLocation.h"
19 #include "llvm/Analysis/DOTGraphTraitsPass.h"
20 #include "llvm/Analysis/RegionInfo.h"
21 #include "llvm/Analysis/RegionIterator.h"
22 #include "llvm/Support/CommandLine.h"
23 
24 using namespace polly;
25 using namespace llvm;
26 static cl::opt<std::string>
27     ViewFilter("polly-view-only",
28                cl::desc("Only view functions that match this pattern"),
29                cl::Hidden, cl::init(""), cl::ZeroOrMore);
30 
31 static cl::opt<bool> ViewAll("polly-view-all",
32                              cl::desc("Also show functions without any scops"),
33                              cl::Hidden, cl::init(false), cl::ZeroOrMore);
34 
35 namespace llvm {
36 template <>
37 struct GraphTraits<ScopDetection *> : public GraphTraits<RegionInfo *> {
38   static NodeRef getEntryNode(ScopDetection *SD) {
39     return GraphTraits<RegionInfo *>::getEntryNode(SD->getRI());
40   }
41   static nodes_iterator nodes_begin(ScopDetection *SD) {
42     return nodes_iterator::begin(getEntryNode(SD));
43   }
44   static nodes_iterator nodes_end(ScopDetection *SD) {
45     return nodes_iterator::end(getEntryNode(SD));
46   }
47 };
48 
49 template <>
50 struct GraphTraits<ScopDetectionWrapperPass *>
51     : public GraphTraits<ScopDetection *> {
52   static NodeRef getEntryNode(ScopDetectionWrapperPass *P) {
53     return GraphTraits<ScopDetection *>::getEntryNode(&P->getSD());
54   }
55   static nodes_iterator nodes_begin(ScopDetectionWrapperPass *P) {
56     return nodes_iterator::begin(getEntryNode(P));
57   }
58   static nodes_iterator nodes_end(ScopDetectionWrapperPass *P) {
59     return nodes_iterator::end(getEntryNode(P));
60   }
61 };
62 
63 template <> struct DOTGraphTraits<RegionNode *> : public DefaultDOTGraphTraits {
64   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
65 
66   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
67     if (!Node->isSubRegion()) {
68       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
69 
70       if (isSimple())
71         return DOTGraphTraits<const Function *>::getSimpleNodeLabel(
72             BB, BB->getParent());
73       else
74         return DOTGraphTraits<const Function *>::getCompleteNodeLabel(
75             BB, BB->getParent());
76     }
77 
78     return "Not implemented";
79   }
80 };
81 
82 template <>
83 struct DOTGraphTraits<ScopDetectionWrapperPass *>
84     : public DOTGraphTraits<RegionNode *> {
85   DOTGraphTraits(bool isSimple = false)
86       : DOTGraphTraits<RegionNode *>(isSimple) {}
87   static std::string getGraphName(ScopDetectionWrapperPass *SD) {
88     return "Scop Graph";
89   }
90 
91   std::string getEdgeAttributes(RegionNode *srcNode,
92                                 GraphTraits<RegionInfo *>::ChildIteratorType CI,
93                                 ScopDetectionWrapperPass *P) {
94     RegionNode *destNode = *CI;
95     auto *SD = &P->getSD();
96 
97     if (srcNode->isSubRegion() || destNode->isSubRegion())
98       return "";
99 
100     // In case of a backedge, do not use it to define the layout of the nodes.
101     BasicBlock *srcBB = srcNode->getNodeAs<BasicBlock>();
102     BasicBlock *destBB = destNode->getNodeAs<BasicBlock>();
103 
104     RegionInfo *RI = SD->getRI();
105     Region *R = RI->getRegionFor(destBB);
106 
107     while (R && R->getParent())
108       if (R->getParent()->getEntry() == destBB)
109         R = R->getParent();
110       else
111         break;
112 
113     if (R && R->getEntry() == destBB && R->contains(srcBB))
114       return "constraint=false";
115 
116     return "";
117   }
118 
119   std::string getNodeLabel(RegionNode *Node, ScopDetectionWrapperPass *P) {
120     return DOTGraphTraits<RegionNode *>::getNodeLabel(
121         Node, reinterpret_cast<RegionNode *>(
122                   P->getSD().getRI()->getTopLevelRegion()));
123   }
124 
125   static std::string escapeString(std::string String) {
126     std::string Escaped;
127 
128     for (const auto &C : String) {
129       if (C == '"')
130         Escaped += '\\';
131 
132       Escaped += C;
133     }
134     return Escaped;
135   }
136 
137   // Print the cluster of the subregions. This groups the single basic blocks
138   // and adds a different background color for each group.
139   static void printRegionCluster(const ScopDetection *SD, const Region *R,
140                                  raw_ostream &O, unsigned depth = 0) {
141     O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void *>(R)
142                         << " {\n";
143     unsigned LineBegin, LineEnd;
144     std::string FileName;
145 
146     getDebugLocation(R, LineBegin, LineEnd, FileName);
147 
148     std::string Location;
149     if (LineBegin != (unsigned)-1) {
150       Location = escapeString(FileName + ":" + std::to_string(LineBegin) + "-" +
151                               std::to_string(LineEnd) + "\n");
152     }
153 
154     std::string ErrorMessage = SD->regionIsInvalidBecause(R);
155     ErrorMessage = escapeString(ErrorMessage);
156     O.indent(2 * (depth + 1))
157         << "label = \"" << Location << ErrorMessage << "\";\n";
158 
159     if (SD->isMaxRegionInScop(*R)) {
160       O.indent(2 * (depth + 1)) << "style = filled;\n";
161 
162       // Set color to green.
163       O.indent(2 * (depth + 1)) << "color = 3";
164     } else {
165       O.indent(2 * (depth + 1)) << "style = solid;\n";
166 
167       int color = (R->getDepth() * 2 % 12) + 1;
168 
169       // We do not want green again.
170       if (color == 3)
171         color = 6;
172 
173       O.indent(2 * (depth + 1)) << "color = " << color << "\n";
174     }
175 
176     for (const auto &SubRegion : *R)
177       printRegionCluster(SD, SubRegion.get(), O, depth + 1);
178 
179     RegionInfo *RI = R->getRegionInfo();
180 
181     for (BasicBlock *BB : R->blocks())
182       if (RI->getRegionFor(BB) == R)
183         O.indent(2 * (depth + 1))
184             << "Node"
185             << static_cast<void *>(RI->getTopLevelRegion()->getBBNode(BB))
186             << ";\n";
187 
188     O.indent(2 * depth) << "}\n";
189   }
190   static void
191   addCustomGraphFeatures(const ScopDetectionWrapperPass *SD,
192                          GraphWriter<ScopDetectionWrapperPass *> &GW) {
193     raw_ostream &O = GW.getOStream();
194     O << "\tcolorscheme = \"paired12\"\n";
195     printRegionCluster(&SD->getSD(), SD->getSD().getRI()->getTopLevelRegion(),
196                        O, 4);
197   }
198 };
199 } // end namespace llvm
200 
201 struct ScopViewer
202     : public DOTGraphTraitsViewer<ScopDetectionWrapperPass, false> {
203   static char ID;
204   ScopViewer()
205       : DOTGraphTraitsViewer<ScopDetectionWrapperPass, false>("scops", ID) {}
206   bool processFunction(Function &F, ScopDetectionWrapperPass &SD) override {
207     if (ViewFilter != "" && !F.getName().count(ViewFilter))
208       return false;
209 
210     if (ViewAll)
211       return true;
212 
213     // Check that at least one scop was detected.
214     return std::distance(SD.getSD().begin(), SD.getSD().end()) > 0;
215   }
216 };
217 char ScopViewer::ID = 0;
218 
219 struct ScopOnlyViewer
220     : public DOTGraphTraitsViewer<ScopDetectionWrapperPass, true> {
221   static char ID;
222   ScopOnlyViewer()
223       : DOTGraphTraitsViewer<ScopDetectionWrapperPass, true>("scopsonly", ID) {}
224 };
225 char ScopOnlyViewer::ID = 0;
226 
227 struct ScopPrinter
228     : public DOTGraphTraitsPrinter<ScopDetectionWrapperPass, false> {
229   static char ID;
230   ScopPrinter()
231       : DOTGraphTraitsPrinter<ScopDetectionWrapperPass, false>("scops", ID) {}
232 };
233 char ScopPrinter::ID = 0;
234 
235 struct ScopOnlyPrinter
236     : public DOTGraphTraitsPrinter<ScopDetectionWrapperPass, true> {
237   static char ID;
238   ScopOnlyPrinter()
239       : DOTGraphTraitsPrinter<ScopDetectionWrapperPass, true>("scopsonly", ID) {
240   }
241 };
242 char ScopOnlyPrinter::ID = 0;
243 
244 static RegisterPass<ScopViewer> X("view-scops",
245                                   "Polly - View Scops of function");
246 
247 static RegisterPass<ScopOnlyViewer>
248     Y("view-scops-only",
249       "Polly - View Scops of function (with no function bodies)");
250 
251 static RegisterPass<ScopPrinter> M("dot-scops",
252                                    "Polly - Print Scops of function");
253 
254 static RegisterPass<ScopOnlyPrinter>
255     N("dot-scops-only",
256       "Polly - Print Scops of function (with no function bodies)");
257 
258 Pass *polly::createDOTViewerPass() { return new ScopViewer(); }
259 
260 Pass *polly::createDOTOnlyViewerPass() { return new ScopOnlyViewer(); }
261 
262 Pass *polly::createDOTPrinterPass() { return new ScopPrinter(); }
263 
264 Pass *polly::createDOTOnlyPrinterPass() { return new ScopOnlyPrinter(); }
265