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   // Print the cluster of the subregions. This groups the single basic blocks
105   // and adds a different background color for each group.
106   static void printRegionCluster(const ScopDetection *SD, const Region *R,
107                                  raw_ostream &O, unsigned depth = 0) {
108     O.indent(2 * depth) << "subgraph cluster_" << static_cast<const void*>(R)
109       << " {\n";
110     std::string ErrorMessage = SD->regionIsInvalidBecause(R);
111     O.indent(2 * (depth + 1)) << "label = \"" << ErrorMessage << "\";\n";
112 
113     if (SD->isMaxRegionInScop(*R)) {
114       O.indent(2 * (depth + 1)) << "style = filled;\n";
115 
116       // Set color to green.
117       O.indent(2 * (depth + 1)) << "color = 3";
118     } else {
119       O.indent(2 * (depth + 1)) << "style = solid;\n";
120 
121       int color = (R->getDepth() * 2 % 12) + 1;
122 
123       // We do not want green again.
124       if (color == 3)
125         color = 6;
126 
127       O.indent(2 * (depth + 1)) << "color = "
128       << color << "\n";
129     }
130 
131     for (Region::const_iterator RI = R->begin(), RE = R->end(); RI != RE; ++RI)
132       printRegionCluster(SD, *RI, O, depth + 1);
133 
134     RegionInfo *RI = R->getRegionInfo();
135 
136     for (Region::const_block_iterator BI = R->block_begin(),
137          BE = R->block_end(); BI != BE; ++BI) {
138       BasicBlock *BB = (*BI)->getNodeAs<BasicBlock>();
139       if (RI->getRegionFor(BB) == R)
140         O.indent(2 * (depth + 1)) << "Node"
141           << static_cast<const void*>(RI->getTopLevelRegion()->getBBNode(BB))
142           << ";\n";
143     }
144 
145     O.indent(2 * depth) << "}\n";
146   }
147   static void addCustomGraphFeatures(const ScopDetection* SD,
148                                      GraphWriter<ScopDetection*> &GW) {
149     raw_ostream &O = GW.getOStream();
150     O << "\tcolorscheme = \"paired12\"\n";
151     printRegionCluster(SD, SD->getRI()->getTopLevelRegion(), O, 4);
152   }
153 };
154 
155 } //end namespace llvm
156 
157 struct ScopViewer
158   : public DOTGraphTraitsViewer<ScopDetection, false> {
159   static char ID;
160   ScopViewer() : DOTGraphTraitsViewer<ScopDetection, false>("scops", ID){}
161 };
162 char ScopViewer::ID = 0;
163 
164 struct ScopOnlyViewer
165   : public DOTGraphTraitsViewer<ScopDetection, true> {
166   static char ID;
167   ScopOnlyViewer()
168     : DOTGraphTraitsViewer<ScopDetection, true>("scopsonly", ID){}
169 };
170 char ScopOnlyViewer::ID = 0;
171 
172 struct ScopPrinter
173   : public DOTGraphTraitsPrinter<ScopDetection, false> {
174   static char ID;
175   ScopPrinter() :
176     DOTGraphTraitsPrinter<ScopDetection, false>("scops", ID) {}
177 };
178 char ScopPrinter::ID = 0;
179 
180 struct ScopOnlyPrinter
181   : public DOTGraphTraitsPrinter<ScopDetection, true> {
182   static char ID;
183   ScopOnlyPrinter() :
184     DOTGraphTraitsPrinter<ScopDetection, true>("scopsonly", ID) {}
185 };
186 char ScopOnlyPrinter::ID = 0;
187 
188 static RegisterPass<ScopViewer>
189 X("view-scops","Polly - View Scops of function");
190 
191 static RegisterPass<ScopOnlyViewer>
192 Y("view-scops-only",
193   "Polly - View Scops of function (with no function bodies)");
194 
195 static RegisterPass<ScopPrinter>
196 M("dot-scops", "Polly - Print Scops of function");
197 
198 static RegisterPass<ScopOnlyPrinter>
199 N("dot-scops-only",
200   "Polly - Print Scops of function (with no function bodies)");
201 
202 Pass* polly::createDOTViewerPass() {
203   return new ScopViewer();
204 }
205 
206 Pass* polly::createDOTOnlyViewerPass() {
207   return new ScopOnlyViewer();
208 }
209 
210 Pass* polly::createDOTPrinterPass() {
211   return new ScopPrinter();
212 }
213 
214 Pass* polly::createDOTOnlyPrinterPass() {
215   return new ScopOnlyPrinter();
216 }
217