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 #ifndef ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
18 #define ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
19 
20 #include "nodes.h"
21 
22 #include <ostream>
23 
24 namespace art {
25 
26 // A control-flow graph visitor performing various checks.
27 class GraphChecker : public HGraphDelegateVisitor {
28  public:
29   explicit GraphChecker(HGraph* graph, const char* dump_prefix = "art::GraphChecker: ")
HGraphDelegateVisitor(graph)30     : HGraphDelegateVisitor(graph),
31       errors_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)),
32       dump_prefix_(dump_prefix),
33       seen_ids_(graph->GetArena(),
34                 graph->GetCurrentInstructionId(),
35                 false,
36                 kArenaAllocGraphChecker),
37       blocks_storage_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)),
38       visited_storage_(graph->GetArena(), 0u, true, kArenaAllocGraphChecker) {}
39 
40   // Check the whole graph (in reverse post-order).
Run()41   void Run() {
42     // VisitReversePostOrder is used instead of VisitInsertionOrder,
43     // as the latter might visit dead blocks removed by the dominator
44     // computation.
45     VisitReversePostOrder();
46   }
47 
48   void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
49 
50   void VisitInstruction(HInstruction* instruction) OVERRIDE;
51   void VisitPhi(HPhi* phi) OVERRIDE;
52 
53   void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
54   void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE;
55   void VisitBoundType(HBoundType* instruction) OVERRIDE;
56   void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
57   void VisitCheckCast(HCheckCast* check) OVERRIDE;
58   void VisitCondition(HCondition* op) OVERRIDE;
59   void VisitConstant(HConstant* instruction) OVERRIDE;
60   void VisitDeoptimize(HDeoptimize* instruction) OVERRIDE;
61   void VisitIf(HIf* instruction) OVERRIDE;
62   void VisitInstanceOf(HInstanceOf* check) OVERRIDE;
63   void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE;
64   void VisitLoadException(HLoadException* load) OVERRIDE;
65   void VisitNeg(HNeg* instruction) OVERRIDE;
66   void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE;
67   void VisitReturn(HReturn* ret) OVERRIDE;
68   void VisitReturnVoid(HReturnVoid* ret) OVERRIDE;
69   void VisitSelect(HSelect* instruction) OVERRIDE;
70   void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE;
71   void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE;
72 
73   void HandleLoop(HBasicBlock* loop_header);
74   void HandleBooleanInput(HInstruction* instruction, size_t input_index);
75 
76   // Was the last visit of the graph valid?
IsValid()77   bool IsValid() const {
78     return errors_.empty();
79   }
80 
81   // Get the list of detected errors.
GetErrors()82   const ArenaVector<std::string>& GetErrors() const {
83     return errors_;
84   }
85 
86   // Print detected errors on output stream `os`.
Dump(std::ostream & os)87   void Dump(std::ostream& os) const {
88     for (size_t i = 0, e = errors_.size(); i < e; ++i) {
89       os << dump_prefix_ << errors_[i] << std::endl;
90     }
91   }
92 
93  protected:
94   // Report a new error.
AddError(const std::string & error)95   void AddError(const std::string& error) {
96     errors_.push_back(error);
97   }
98 
99   // The block currently visited.
100   HBasicBlock* current_block_ = nullptr;
101   // Errors encountered while checking the graph.
102   ArenaVector<std::string> errors_;
103 
104  private:
105   // String displayed before dumped errors.
106   const char* const dump_prefix_;
107   ArenaBitVector seen_ids_;
108 
109   // To reduce the total arena memory allocation, we reuse the same storage.
110   ArenaVector<HBasicBlock*> blocks_storage_;
111   ArenaBitVector visited_storage_;
112 
113   DISALLOW_COPY_AND_ASSIGN(GraphChecker);
114 };
115 
116 }  // namespace art
117 
118 #endif  // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
119