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