Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 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 | |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 22 | #include <ostream> |
| 23 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 24 | namespace art { |
| 25 | |
| 26 | // A control-flow graph visitor performing various checks. |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 27 | class GraphChecker : public HGraphDelegateVisitor { |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 28 | public: |
Vladimir Marko | 655e585 | 2015-10-12 10:38:28 +0100 | [diff] [blame] | 29 | explicit GraphChecker(HGraph* graph, const char* dump_prefix = "art::GraphChecker: ") |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 30 | : HGraphDelegateVisitor(graph), |
Vladimir Marko | 655e585 | 2015-10-12 10:38:28 +0100 | [diff] [blame] | 31 | errors_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)), |
Nicolas Geoffray | 7c5367b | 2014-12-17 10:13:46 +0000 | [diff] [blame] | 32 | dump_prefix_(dump_prefix), |
Vladimir Marko | f6a35de | 2016-03-21 12:01:50 +0000 | [diff] [blame] | 33 | seen_ids_(graph->GetArena(), |
| 34 | graph->GetCurrentInstructionId(), |
| 35 | false, |
Vladimir Marko | 947eb70 | 2016-03-25 15:31:35 +0000 | [diff] [blame] | 36 | kArenaAllocGraphChecker), |
| 37 | blocks_storage_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)), |
| 38 | visited_storage_(graph->GetArena(), 0u, true, kArenaAllocGraphChecker) {} |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 39 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 40 | // Check the whole graph (in reverse post-order). |
| 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 | } |
Roland Levillain | 633021e | 2014-10-01 14:12:25 +0100 | [diff] [blame] | 47 | |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 48 | void VisitBasicBlock(HBasicBlock* block) OVERRIDE; |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 49 | |
Nicolas Geoffray | 3159674 | 2014-11-24 15:28:45 +0000 | [diff] [blame] | 50 | void VisitInstruction(HInstruction* instruction) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 51 | void VisitPhi(HPhi* phi) OVERRIDE; |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 52 | |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 53 | void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE; |
| 54 | void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE; |
| 55 | void VisitBoundType(HBoundType* instruction) OVERRIDE; |
Mark Mendell | 1152c92 | 2015-04-24 17:06:35 -0400 | [diff] [blame] | 56 | void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE; |
Nicolas Geoffray | f9a1995 | 2015-06-29 13:43:54 +0100 | [diff] [blame] | 57 | void VisitCheckCast(HCheckCast* check) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 58 | void VisitCondition(HCondition* op) OVERRIDE; |
| 59 | void VisitConstant(HConstant* instruction) OVERRIDE; |
| 60 | void VisitIf(HIf* instruction) OVERRIDE; |
Nicolas Geoffray | f9a1995 | 2015-06-29 13:43:54 +0100 | [diff] [blame] | 61 | void VisitInstanceOf(HInstanceOf* check) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 62 | void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE; |
| 63 | void VisitLoadException(HLoadException* load) OVERRIDE; |
Roland Levillain | 937e6cd | 2016-03-22 11:54:37 +0000 | [diff] [blame] | 64 | void VisitNeg(HNeg* instruction) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 65 | void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE; |
David Brazdil | fc6a86a | 2015-06-26 10:33:45 +0000 | [diff] [blame] | 66 | void VisitReturn(HReturn* ret) OVERRIDE; |
| 67 | void VisitReturnVoid(HReturnVoid* ret) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 68 | void VisitSelect(HSelect* instruction) OVERRIDE; |
| 69 | void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE; |
Roland Levillain | f355c3f | 2016-03-30 19:09:03 +0100 | [diff] [blame] | 70 | void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; |
David Brazdil | badd826 | 2016-02-02 16:28:56 +0000 | [diff] [blame] | 71 | |
| 72 | void HandleLoop(HBasicBlock* loop_header); |
| 73 | void HandleBooleanInput(HInstruction* instruction, size_t input_index); |
David Brazdil | fc6a86a | 2015-06-26 10:33:45 +0000 | [diff] [blame] | 74 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 75 | // Was the last visit of the graph valid? |
| 76 | bool IsValid() const { |
Andreas Gampe | 91356c0 | 2014-11-07 10:34:36 -0800 | [diff] [blame] | 77 | return errors_.empty(); |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 78 | } |
| 79 | |
| 80 | // Get the list of detected errors. |
Vladimir Marko | 655e585 | 2015-10-12 10:38:28 +0100 | [diff] [blame] | 81 | const ArenaVector<std::string>& GetErrors() const { |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 82 | return errors_; |
| 83 | } |
| 84 | |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 85 | // Print detected errors on output stream `os`. |
Ian Rogers | c7dd295 | 2014-10-21 23:31:19 -0700 | [diff] [blame] | 86 | void Dump(std::ostream& os) const { |
Andreas Gampe | 91356c0 | 2014-11-07 10:34:36 -0800 | [diff] [blame] | 87 | for (size_t i = 0, e = errors_.size(); i < e; ++i) { |
| 88 | os << dump_prefix_ << errors_[i] << std::endl; |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 89 | } |
| 90 | } |
| 91 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 92 | protected: |
Roland Levillain | 5c4405e | 2015-01-21 11:39:58 +0000 | [diff] [blame] | 93 | // Report a new error. |
| 94 | void AddError(const std::string& error) { |
| 95 | errors_.push_back(error); |
| 96 | } |
| 97 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 98 | // The block currently visited. |
| 99 | HBasicBlock* current_block_ = nullptr; |
| 100 | // Errors encountered while checking the graph. |
Vladimir Marko | 655e585 | 2015-10-12 10:38:28 +0100 | [diff] [blame] | 101 | ArenaVector<std::string> errors_; |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 102 | |
| 103 | private: |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 104 | // String displayed before dumped errors. |
Ian Rogers | c7dd295 | 2014-10-21 23:31:19 -0700 | [diff] [blame] | 105 | const char* const dump_prefix_; |
Nicolas Geoffray | 7c5367b | 2014-12-17 10:13:46 +0000 | [diff] [blame] | 106 | ArenaBitVector seen_ids_; |
Roland Levillain | 75be283 | 2014-10-17 17:02:00 +0100 | [diff] [blame] | 107 | |
Vladimir Marko | 947eb70 | 2016-03-25 15:31:35 +0000 | [diff] [blame] | 108 | // To reduce the total arena memory allocation, we reuse the same storage. |
| 109 | ArenaVector<HBasicBlock*> blocks_storage_; |
| 110 | ArenaBitVector visited_storage_; |
| 111 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 112 | DISALLOW_COPY_AND_ASSIGN(GraphChecker); |
| 113 | }; |
| 114 | |
Roland Levillain | ccc07a9 | 2014-09-16 14:48:16 +0100 | [diff] [blame] | 115 | } // namespace art |
| 116 | |
| 117 | #endif // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ |