1 /*
2  * Copyright (C) 2014 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #include "graph_visualizer.h"
18 
19 #include "code_generator.h"
20 #include "dead_code_elimination.h"
21 #include "licm.h"
22 #include "nodes.h"
23 #include "optimization.h"
24 #include "register_allocator.h"
25 #include "ssa_liveness_analysis.h"
26 
27 namespace art {
28 
29 /**
30  * HGraph visitor to generate a file suitable for the c1visualizer tool and IRHydra.
31  */
32 class HGraphVisualizerPrinter : public HGraphVisitor {
33  public:
HGraphVisualizerPrinter(HGraph * graph,std::ostream & output,const char * pass_name,bool is_after_pass,const CodeGenerator & codegen)34   HGraphVisualizerPrinter(HGraph* graph,
35                           std::ostream& output,
36                           const char* pass_name,
37                           bool is_after_pass,
38                           const CodeGenerator& codegen)
39       : HGraphVisitor(graph),
40         output_(output),
41         pass_name_(pass_name),
42         is_after_pass_(is_after_pass),
43         codegen_(codegen),
44         indent_(0) {}
45 
StartTag(const char * name)46   void StartTag(const char* name) {
47     AddIndent();
48     output_ << "begin_" << name << std::endl;
49     indent_++;
50   }
51 
EndTag(const char * name)52   void EndTag(const char* name) {
53     indent_--;
54     AddIndent();
55     output_ << "end_" << name << std::endl;
56   }
57 
PrintProperty(const char * name,const char * property)58   void PrintProperty(const char* name, const char* property) {
59     AddIndent();
60     output_ << name << " \"" << property << "\"" << std::endl;
61   }
62 
PrintProperty(const char * name,const char * property,int id)63   void PrintProperty(const char* name, const char* property, int id) {
64     AddIndent();
65     output_ << name << " \"" << property << id << "\"" << std::endl;
66   }
67 
PrintEmptyProperty(const char * name)68   void PrintEmptyProperty(const char* name) {
69     AddIndent();
70     output_ << name << std::endl;
71   }
72 
PrintTime(const char * name)73   void PrintTime(const char* name) {
74     AddIndent();
75     output_ << name << " " << time(nullptr) << std::endl;
76   }
77 
PrintInt(const char * name,int value)78   void PrintInt(const char* name, int value) {
79     AddIndent();
80     output_ << name << " " << value << std::endl;
81   }
82 
AddIndent()83   void AddIndent() {
84     for (size_t i = 0; i < indent_; ++i) {
85       output_ << "  ";
86     }
87   }
88 
GetTypeId(Primitive::Type type)89   char GetTypeId(Primitive::Type type) {
90     // Note that Primitive::Descriptor would not work for us
91     // because it does not handle reference types (that is kPrimNot).
92     switch (type) {
93       case Primitive::kPrimBoolean: return 'z';
94       case Primitive::kPrimByte: return 'b';
95       case Primitive::kPrimChar: return 'c';
96       case Primitive::kPrimShort: return 's';
97       case Primitive::kPrimInt: return 'i';
98       case Primitive::kPrimLong: return 'j';
99       case Primitive::kPrimFloat: return 'f';
100       case Primitive::kPrimDouble: return 'd';
101       case Primitive::kPrimNot: return 'l';
102       case Primitive::kPrimVoid: return 'v';
103     }
104     LOG(FATAL) << "Unreachable";
105     return 'v';
106   }
107 
PrintPredecessors(HBasicBlock * block)108   void PrintPredecessors(HBasicBlock* block) {
109     AddIndent();
110     output_ << "predecessors";
111     for (size_t i = 0, e = block->GetPredecessors().Size(); i < e; ++i) {
112       HBasicBlock* predecessor = block->GetPredecessors().Get(i);
113       output_ << " \"B" << predecessor->GetBlockId() << "\" ";
114     }
115     output_<< std::endl;
116   }
117 
PrintSuccessors(HBasicBlock * block)118   void PrintSuccessors(HBasicBlock* block) {
119     AddIndent();
120     output_ << "successors";
121     for (size_t i = 0, e = block->GetSuccessors().Size(); i < e; ++i) {
122       HBasicBlock* successor = block->GetSuccessors().Get(i);
123       output_ << " \"B" << successor->GetBlockId() << "\" ";
124     }
125     output_<< std::endl;
126   }
127 
DumpLocation(Location location)128   void DumpLocation(Location location) {
129     if (location.IsRegister()) {
130       codegen_.DumpCoreRegister(output_, location.reg());
131     } else if (location.IsFpuRegister()) {
132       codegen_.DumpFloatingPointRegister(output_, location.reg());
133     } else if (location.IsConstant()) {
134       output_ << "constant";
135       HConstant* constant = location.GetConstant();
136       if (constant->IsIntConstant()) {
137         output_ << " " << constant->AsIntConstant()->GetValue();
138       } else if (constant->IsLongConstant()) {
139         output_ << " " << constant->AsLongConstant()->GetValue();
140       }
141     } else if (location.IsInvalid()) {
142       output_ << "invalid";
143     } else if (location.IsStackSlot()) {
144       output_ << location.GetStackIndex() << "(sp)";
145     } else if (location.IsFpuRegisterPair()) {
146       codegen_.DumpFloatingPointRegister(output_, location.low());
147       output_ << " and ";
148       codegen_.DumpFloatingPointRegister(output_, location.high());
149     } else if (location.IsRegisterPair()) {
150       codegen_.DumpCoreRegister(output_, location.low());
151       output_ << " and ";
152       codegen_.DumpCoreRegister(output_, location.high());
153     } else if (location.IsUnallocated()) {
154       output_ << "<U>";
155     } else {
156       DCHECK(location.IsDoubleStackSlot());
157       output_ << "2x" << location.GetStackIndex() << "(sp)";
158     }
159   }
160 
VisitParallelMove(HParallelMove * instruction)161   void VisitParallelMove(HParallelMove* instruction) OVERRIDE {
162     output_ << " (";
163     for (size_t i = 0, e = instruction->NumMoves(); i < e; ++i) {
164       MoveOperands* move = instruction->MoveOperandsAt(i);
165       DumpLocation(move->GetSource());
166       output_ << " -> ";
167       DumpLocation(move->GetDestination());
168       if (i + 1 != e) {
169         output_ << ", ";
170       }
171     }
172     output_ << ")";
173     output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
174   }
175 
VisitIntConstant(HIntConstant * instruction)176   void VisitIntConstant(HIntConstant* instruction) OVERRIDE {
177     output_ << " " << instruction->GetValue();
178   }
179 
VisitLongConstant(HLongConstant * instruction)180   void VisitLongConstant(HLongConstant* instruction) OVERRIDE {
181     output_ << " " << instruction->GetValue();
182   }
183 
VisitFloatConstant(HFloatConstant * instruction)184   void VisitFloatConstant(HFloatConstant* instruction) OVERRIDE {
185     output_ << " " << instruction->GetValue();
186   }
187 
VisitDoubleConstant(HDoubleConstant * instruction)188   void VisitDoubleConstant(HDoubleConstant* instruction) OVERRIDE {
189     output_ << " " << instruction->GetValue();
190   }
191 
VisitPhi(HPhi * phi)192   void VisitPhi(HPhi* phi) OVERRIDE {
193     output_ << " " << phi->GetRegNumber();
194   }
195 
VisitMemoryBarrier(HMemoryBarrier * barrier)196   void VisitMemoryBarrier(HMemoryBarrier* barrier) OVERRIDE {
197     output_ << " " << barrier->GetBarrierKind();
198   }
199 
IsPass(const char * name)200   bool IsPass(const char* name) {
201     return strcmp(pass_name_, name) == 0;
202   }
203 
PrintInstruction(HInstruction * instruction)204   void PrintInstruction(HInstruction* instruction) {
205     output_ << instruction->DebugName();
206     instruction->Accept(this);
207     if (instruction->InputCount() > 0) {
208       output_ << " [ ";
209       for (HInputIterator inputs(instruction); !inputs.Done(); inputs.Advance()) {
210         output_ << GetTypeId(inputs.Current()->GetType()) << inputs.Current()->GetId() << " ";
211       }
212       output_ << "]";
213     }
214     if (instruction->HasEnvironment()) {
215       output_ << " (env:";
216       for (HEnvironment* environment = instruction->GetEnvironment();
217            environment != nullptr;
218            environment = environment->GetParent()) {
219         output_ << " [ ";
220         for (size_t i = 0, e = environment->Size(); i < e; ++i) {
221           HInstruction* insn = environment->GetInstructionAt(i);
222           if (insn != nullptr) {
223             output_ << GetTypeId(insn->GetType()) << insn->GetId() << " ";
224           } else {
225             output_ << " _ ";
226           }
227         }
228         output_ << "]";
229       }
230       output_ << ")";
231     }
232     if (IsPass(SsaLivenessAnalysis::kLivenessPassName)
233         && is_after_pass_
234         && instruction->GetLifetimePosition() != kNoLifetime) {
235       output_ << " (liveness: " << instruction->GetLifetimePosition();
236       if (instruction->HasLiveInterval()) {
237         output_ << " ";
238         const LiveInterval& interval = *instruction->GetLiveInterval();
239         interval.Dump(output_);
240       }
241       output_ << ")";
242     } else if (IsPass(RegisterAllocator::kRegisterAllocatorPassName) && is_after_pass_) {
243       LocationSummary* locations = instruction->GetLocations();
244       if (locations != nullptr) {
245         output_ << " ( ";
246         for (size_t i = 0; i < instruction->InputCount(); ++i) {
247           DumpLocation(locations->InAt(i));
248           output_ << " ";
249         }
250         output_ << ")";
251         if (locations->Out().IsValid()) {
252           output_ << " -> ";
253           DumpLocation(locations->Out());
254         }
255       }
256       output_ << " (liveness: " << instruction->GetLifetimePosition() << ")";
257     } else if (IsPass(LICM::kLoopInvariantCodeMotionPassName)
258                || IsPass(HDeadCodeElimination::kFinalDeadCodeEliminationPassName)) {
259       output_ << " ( loop_header:";
260       HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
261       if (info == nullptr) {
262         output_ << "null )";
263       } else {
264         output_ << "B" << info->GetHeader()->GetBlockId() << " )";
265       }
266     }
267   }
268 
PrintInstructions(const HInstructionList & list)269   void PrintInstructions(const HInstructionList& list) {
270     const char* kEndInstructionMarker = "<|@";
271     for (HInstructionIterator it(list); !it.Done(); it.Advance()) {
272       HInstruction* instruction = it.Current();
273       int bci = 0;
274       size_t num_uses = 0;
275       for (HUseIterator<HInstruction*> use_it(instruction->GetUses());
276            !use_it.Done();
277            use_it.Advance()) {
278         ++num_uses;
279       }
280       AddIndent();
281       output_ << bci << " " << num_uses << " "
282               << GetTypeId(instruction->GetType()) << instruction->GetId() << " ";
283       PrintInstruction(instruction);
284       output_ << kEndInstructionMarker << std::endl;
285     }
286   }
287 
Run()288   void Run() {
289     StartTag("cfg");
290     std::string pass_desc = std::string(pass_name_) + (is_after_pass_ ? " (after)" : " (before)");
291     PrintProperty("name", pass_desc.c_str());
292     VisitInsertionOrder();
293     EndTag("cfg");
294   }
295 
VisitBasicBlock(HBasicBlock * block)296   void VisitBasicBlock(HBasicBlock* block) OVERRIDE {
297     StartTag("block");
298     PrintProperty("name", "B", block->GetBlockId());
299     if (block->GetLifetimeStart() != kNoLifetime) {
300       // Piggy back on these fields to show the lifetime of the block.
301       PrintInt("from_bci", block->GetLifetimeStart());
302       PrintInt("to_bci", block->GetLifetimeEnd());
303     } else {
304       PrintInt("from_bci", -1);
305       PrintInt("to_bci", -1);
306     }
307     PrintPredecessors(block);
308     PrintSuccessors(block);
309     PrintEmptyProperty("xhandlers");
310     PrintEmptyProperty("flags");
311     if (block->GetDominator() != nullptr) {
312       PrintProperty("dominator", "B", block->GetDominator()->GetBlockId());
313     }
314 
315     StartTag("states");
316     StartTag("locals");
317     PrintInt("size", 0);
318     PrintProperty("method", "None");
319     for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
320       AddIndent();
321       HInstruction* instruction = it.Current();
322       output_ << instruction->GetId() << " " << GetTypeId(instruction->GetType())
323               << instruction->GetId() << "[ ";
324       for (HInputIterator inputs(instruction); !inputs.Done(); inputs.Advance()) {
325         output_ << inputs.Current()->GetId() << " ";
326       }
327       output_ << "]" << std::endl;
328     }
329     EndTag("locals");
330     EndTag("states");
331 
332     StartTag("HIR");
333     PrintInstructions(block->GetPhis());
334     PrintInstructions(block->GetInstructions());
335     EndTag("HIR");
336     EndTag("block");
337   }
338 
339  private:
340   std::ostream& output_;
341   const char* pass_name_;
342   const bool is_after_pass_;
343   const CodeGenerator& codegen_;
344   size_t indent_;
345 
346   DISALLOW_COPY_AND_ASSIGN(HGraphVisualizerPrinter);
347 };
348 
HGraphVisualizer(std::ostream * output,HGraph * graph,const CodeGenerator & codegen)349 HGraphVisualizer::HGraphVisualizer(std::ostream* output,
350                                    HGraph* graph,
351                                    const CodeGenerator& codegen)
352   : output_(output), graph_(graph), codegen_(codegen) {}
353 
PrintHeader(const char * method_name) const354 void HGraphVisualizer::PrintHeader(const char* method_name) const {
355   DCHECK(output_ != nullptr);
356   HGraphVisualizerPrinter printer(graph_, *output_, "", true, codegen_);
357   printer.StartTag("compilation");
358   printer.PrintProperty("name", method_name);
359   printer.PrintProperty("method", method_name);
360   printer.PrintTime("date");
361   printer.EndTag("compilation");
362 }
363 
DumpGraph(const char * pass_name,bool is_after_pass) const364 void HGraphVisualizer::DumpGraph(const char* pass_name, bool is_after_pass) const {
365   DCHECK(output_ != nullptr);
366   if (!graph_->GetBlocks().IsEmpty()) {
367     HGraphVisualizerPrinter printer(graph_, *output_, pass_name, is_after_pass, codegen_);
368     printer.Run();
369   }
370 }
371 
372 }  // namespace art
373