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