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