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