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