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