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