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