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   GraphChecker(ArenaAllocator* allocator, HGraph* graph,
30                const char* dump_prefix = "art::GraphChecker: ")
HGraphDelegateVisitor(graph)31     : HGraphDelegateVisitor(graph),
32       allocator_(allocator),
33       dump_prefix_(dump_prefix),
34       seen_ids_(allocator, graph->GetCurrentInstructionId(), false) {}
35 
36   // Check the whole graph (in insertion order).
Run()37   virtual void Run() { VisitInsertionOrder(); }
38 
39   // Check `block`.
40   void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
41 
42   // Check `instruction`.
43   void VisitInstruction(HInstruction* instruction) OVERRIDE;
44 
45   // Perform control-flow graph checks on instruction.
46   void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE;
47 
48   // Check that the HasBoundsChecks() flag is set for bounds checks.
49   void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE;
50 
51   // Check that HCheckCast and HInstanceOf have HLoadClass as second input.
52   void VisitCheckCast(HCheckCast* check) OVERRIDE;
53   void VisitInstanceOf(HInstanceOf* check) OVERRIDE;
54 
55   // Was the last visit of the graph valid?
IsValid()56   bool IsValid() const {
57     return errors_.empty();
58   }
59 
60   // Get the list of detected errors.
GetErrors()61   const std::vector<std::string>& GetErrors() const {
62     return errors_;
63   }
64 
65   // Print detected errors on output stream `os`.
Dump(std::ostream & os)66   void Dump(std::ostream& os) const {
67     for (size_t i = 0, e = errors_.size(); i < e; ++i) {
68       os << dump_prefix_ << errors_[i] << std::endl;
69     }
70   }
71 
72  protected:
73   // Report a new error.
AddError(const std::string & error)74   void AddError(const std::string& error) {
75     errors_.push_back(error);
76   }
77 
78   ArenaAllocator* const allocator_;
79   // The block currently visited.
80   HBasicBlock* current_block_ = nullptr;
81   // Errors encountered while checking the graph.
82   std::vector<std::string> errors_;
83 
84  private:
85   // String displayed before dumped errors.
86   const char* const dump_prefix_;
87   ArenaBitVector seen_ids_;
88 
89   DISALLOW_COPY_AND_ASSIGN(GraphChecker);
90 };
91 
92 
93 // An SSA graph visitor performing various checks.
94 class SSAChecker : public GraphChecker {
95  public:
96   typedef GraphChecker super_type;
97 
98   // TODO: There's no need to pass a separate allocator as we could get it from the graph.
SSAChecker(ArenaAllocator * allocator,HGraph * graph)99   SSAChecker(ArenaAllocator* allocator, HGraph* graph)
100     : GraphChecker(allocator, graph, "art::SSAChecker: ") {}
101 
102   // Check the whole graph (in reverse post-order).
Run()103   void Run() OVERRIDE {
104     // VisitReversePostOrder is used instead of VisitInsertionOrder,
105     // as the latter might visit dead blocks removed by the dominator
106     // computation.
107     VisitReversePostOrder();
108   }
109 
110   // Perform SSA form checks on `block`.
111   void VisitBasicBlock(HBasicBlock* block) OVERRIDE;
112   // Loop-related checks from block `loop_header`.
113   void CheckLoop(HBasicBlock* loop_header);
114 
115   // Perform SSA form checks on instructions.
116   void VisitInstruction(HInstruction* instruction) OVERRIDE;
117   void VisitPhi(HPhi* phi) OVERRIDE;
118   void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE;
119   void VisitCondition(HCondition* op) OVERRIDE;
120   void VisitIf(HIf* instruction) OVERRIDE;
121   void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE;
122   void VisitConstant(HConstant* instruction) OVERRIDE;
123 
124   void HandleBooleanInput(HInstruction* instruction, size_t input_index);
125 
126  private:
127   DISALLOW_COPY_AND_ASSIGN(SSAChecker);
128 };
129 
130 }  // namespace art
131 
132 #endif  // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_
133