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 "polly/Support/ScopLocation.h"
20 #include "llvm/Analysis/DOTGraphTraitsPass.h"
21 #include "llvm/Analysis/RegionInfo.h"
22 #include "llvm/Analysis/RegionIterator.h"
23 #include "llvm/Support/CommandLine.h"
24 
25 using namespace polly;
26 using namespace llvm;
27 static cl::opt<std::string>
28     ViewFilter("polly-view-only",
29                cl::desc("Only view functions that match this pattern"),
30                cl::Hidden, cl::init(""), cl::ZeroOrMore);
31 
32 namespace llvm {
33 template <>
34 struct GraphTraits<ScopDetection *> : public GraphTraits<RegionInfo *> {
35   static NodeType *getEntryNode(ScopDetection *SD) {
36     return GraphTraits<RegionInfo *>::getEntryNode(SD->getRI());
37   }
38   static nodes_iterator nodes_begin(ScopDetection *SD) {
39     return nodes_iterator::begin(getEntryNode(SD));
40   }
41   static nodes_iterator nodes_end(ScopDetection *SD) {
42     return nodes_iterator::end(getEntryNode(SD));
43   }
44 };
45 
46 template <> struct DOTGraphTraits<RegionNode *> : public DefaultDOTGraphTraits {
47   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
48 
49   std::string getNodeLabel(RegionNode *Node, RegionNode *Graph) {
50     if (!Node->isSubRegion()) {
51       BasicBlock *BB = Node->getNodeAs<BasicBlock>();
52 
53       if (isSimple())
54         return DOTGraphTraits<const Function *>::getSimpleNodeLabel(
55             BB, BB->getParent());
56       else
57         return DOTGraphTraits<const Function *>::getCompleteNodeLabel(
58             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) { return "Scop Graph"; }
70 
71   std::string getEdgeAttributes(RegionNode *srcNode,
72                                 GraphTraits<RegionInfo *>::ChildIteratorType CI,
73                                 ScopDetection *SD) {
74     RegionNode *destNode = *CI;
75 
76     if (srcNode->isSubRegion() || destNode->isSubRegion())
77       return "";
78 
79     // In case of a backedge, do not use it to define the layout of the nodes.
80     BasicBlock *srcBB = srcNode->getNodeAs<BasicBlock>();
81     BasicBlock *destBB = destNode->getNodeAs<BasicBlock>();
82 
83     RegionInfo *RI = SD->getRI();
84     Region *R = RI->getRegionFor(destBB);
85 
86     while (R && R->getParent())
87       if (R->getParent()->getEntry() == destBB)
88         R = R->getParent();
89       else
90         break;
91 
92     if (R && R->getEntry() == destBB && R->contains(srcBB))
93       return "constraint=false";
94 
95     return "";
96   }
97 
98   std::string getNodeLabel(RegionNode *Node, ScopDetection *SD) {
99     return DOTGraphTraits<RegionNode *>::getNodeLabel(
100         Node, reinterpret_cast<RegionNode *>(SD->getRI()->getTopLevelRegion()));
101   }
102 
103   static std::string escapeString(std::string String) {
104     std::string Escaped;
105 
106     for (const auto &C : String) {
107       if (C == '"')
108         Escaped += '\\';
109 
110       Escaped += C;
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     unsigned LineBegin, LineEnd;
122     std::string FileName;
123 
124     getDebugLocation(R, LineBegin, LineEnd, FileName);
125 
126     std::string Location;
127     if (LineBegin != (unsigned)-1) {
128       Location = escapeString(FileName + ":" + std::to_string(LineBegin) + "-" +
129                               std::to_string(LineEnd) + "\n");
130     }
131 
132     std::string ErrorMessage = SD->regionIsInvalidBecause(R);
133     ErrorMessage = escapeString(ErrorMessage);
134     O.indent(2 * (depth + 1)) << "label = \"" << Location << ErrorMessage
135                               << "\";\n";
136 
137     if (SD->isMaxRegionInScop(*R)) {
138       O.indent(2 * (depth + 1)) << "style = filled;\n";
139 
140       // Set color to green.
141       O.indent(2 * (depth + 1)) << "color = 3";
142     } else {
143       O.indent(2 * (depth + 1)) << "style = solid;\n";
144 
145       int color = (R->getDepth() * 2 % 12) + 1;
146 
147       // We do not want green again.
148       if (color == 3)
149         color = 6;
150 
151       O.indent(2 * (depth + 1)) << "color = " << color << "\n";
152     }
153 
154     for (const auto &SubRegion : *R)
155       printRegionCluster(SD, SubRegion.get(), O, depth + 1);
156 
157     RegionInfo *RI = R->getRegionInfo();
158 
159     for (const auto &BB : R->blocks())
160       if (RI->getRegionFor(BB) == R)
161         O.indent(2 * (depth + 1))
162             << "Node"
163             << static_cast<void *>(RI->getTopLevelRegion()->getBBNode(BB))
164             << ";\n";
165 
166     O.indent(2 * depth) << "}\n";
167   }
168   static void addCustomGraphFeatures(const ScopDetection *SD,
169                                      GraphWriter<ScopDetection *> &GW) {
170     raw_ostream &O = GW.getOStream();
171     O << "\tcolorscheme = \"paired12\"\n";
172     printRegionCluster(SD, SD->getRI()->getTopLevelRegion(), O, 4);
173   }
174 };
175 
176 } // end namespace llvm
177 
178 struct ScopViewer : public DOTGraphTraitsViewer<ScopDetection, false> {
179   static char ID;
180   ScopViewer() : DOTGraphTraitsViewer<ScopDetection, false>("scops", ID) {}
181   bool processFunction(Function &F) override {
182     if (ViewFilter == "")
183       return true;
184 
185     if (F.getName().count(ViewFilter))
186       return true;
187 
188     return false;
189   }
190 };
191 char ScopViewer::ID = 0;
192 
193 struct ScopOnlyViewer : public DOTGraphTraitsViewer<ScopDetection, true> {
194   static char ID;
195   ScopOnlyViewer()
196       : DOTGraphTraitsViewer<ScopDetection, true>("scopsonly", ID) {}
197 };
198 char ScopOnlyViewer::ID = 0;
199 
200 struct ScopPrinter : public DOTGraphTraitsPrinter<ScopDetection, false> {
201   static char ID;
202   ScopPrinter() : DOTGraphTraitsPrinter<ScopDetection, false>("scops", ID) {}
203 };
204 char ScopPrinter::ID = 0;
205 
206 struct ScopOnlyPrinter : public DOTGraphTraitsPrinter<ScopDetection, true> {
207   static char ID;
208   ScopOnlyPrinter()
209       : DOTGraphTraitsPrinter<ScopDetection, true>("scopsonly", ID) {}
210 };
211 char ScopOnlyPrinter::ID = 0;
212 
213 static RegisterPass<ScopViewer> X("view-scops",
214                                   "Polly - View Scops of function");
215 
216 static RegisterPass<ScopOnlyViewer>
217     Y("view-scops-only",
218       "Polly - View Scops of function (with no function bodies)");
219 
220 static RegisterPass<ScopPrinter> M("dot-scops",
221                                    "Polly - Print Scops of function");
222 
223 static RegisterPass<ScopOnlyPrinter>
224     N("dot-scops-only",
225       "Polly - Print Scops of function (with no function bodies)");
226 
227 Pass *polly::createDOTViewerPass() { return new ScopViewer(); }
228 
229 Pass *polly::createDOTOnlyViewerPass() { return new ScopOnlyViewer(); }
230 
231 Pass *polly::createDOTPrinterPass() { return new ScopPrinter(); }
232 
233 Pass *polly::createDOTOnlyPrinterPass() { return new ScopOnlyPrinter(); }
234