1ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain/* 2ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Copyright (C) 2014 The Android Open Source Project 3ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 4ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Licensed under the Apache License, Version 2.0 (the "License"); 5ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * you may not use this file except in compliance with the License. 6ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * You may obtain a copy of the License at 7ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 8ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * http://www.apache.org/licenses/LICENSE-2.0 9ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * 10ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * Unless required by applicable law or agreed to in writing, software 11ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * distributed under the License is distributed on an "AS IS" BASIS, 12ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * See the License for the specific language governing permissions and 14ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain * limitations under the License. 15ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain */ 16ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 17ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#ifndef ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ 18ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#define ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ 19ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 20ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#include "nodes.h" 21ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 2275be28332b278cff9039b54bfb228ac72f539cccRoland Levillain#include <ostream> 2375be28332b278cff9039b54bfb228ac72f539cccRoland Levillain 24ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillainnamespace art { 25ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 26ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain// A control-flow graph visitor performing various checks. 273159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffrayclass GraphChecker : public HGraphDelegateVisitor { 28ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain public: 29655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko explicit GraphChecker(HGraph* graph, const char* dump_prefix = "art::GraphChecker: ") 303159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray : HGraphDelegateVisitor(graph), 31655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko errors_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)), 327c5367badfe61b96c5836d495d286cee64861579Nicolas Geoffray dump_prefix_(dump_prefix), 33f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko seen_ids_(graph->GetArena(), 34f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko graph->GetCurrentInstructionId(), 35f6a35de9eeefb20f6446f1b4815b4dcb0161d09cVladimir Marko false, 36947eb700bec9e214a72d4747864398dc238da60cVladimir Marko kArenaAllocGraphChecker), 37947eb700bec9e214a72d4747864398dc238da60cVladimir Marko blocks_storage_(graph->GetArena()->Adapter(kArenaAllocGraphChecker)), 38947eb700bec9e214a72d4747864398dc238da60cVladimir Marko visited_storage_(graph->GetArena(), 0u, true, kArenaAllocGraphChecker) {} 39ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 40badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // Check the whole graph (in reverse post-order). 41badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void Run() { 42badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // VisitReversePostOrder is used instead of VisitInsertionOrder, 43badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // as the latter might visit dead blocks removed by the dominator 44badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil // computation. 45badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil VisitReversePostOrder(); 46badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil } 47633021e6ff6b9a57a374a994e74cfd69275ce100Roland Levillain 483159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray void VisitBasicBlock(HBasicBlock* block) OVERRIDE; 49ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 503159674c0863f53cfbc1913d493550221ac47f02Nicolas Geoffray void VisitInstruction(HInstruction* instruction) OVERRIDE; 51badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitPhi(HPhi* phi) OVERRIDE; 52ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 53badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitBinaryOperation(HBinaryOperation* op) OVERRIDE; 54badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitBooleanNot(HBooleanNot* instruction) OVERRIDE; 55badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitBoundType(HBoundType* instruction) OVERRIDE; 561152c926076a760490085c4497c3f117fa8da891Mark Mendell void VisitBoundsCheck(HBoundsCheck* check) OVERRIDE; 57f9a199571417b5a5a62d94d05a064077e14dd2c4Nicolas Geoffray void VisitCheckCast(HCheckCast* check) OVERRIDE; 58badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitCondition(HCondition* op) OVERRIDE; 59badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitConstant(HConstant* instruction) OVERRIDE; 6019b5021a49285627485675ef31276b8194269600Nicolas Geoffray void VisitDeoptimize(HDeoptimize* instruction) OVERRIDE; 61badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitIf(HIf* instruction) OVERRIDE; 62f9a199571417b5a5a62d94d05a064077e14dd2c4Nicolas Geoffray void VisitInstanceOf(HInstanceOf* check) OVERRIDE; 63badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitInvokeStaticOrDirect(HInvokeStaticOrDirect* invoke) OVERRIDE; 64badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitLoadException(HLoadException* load) OVERRIDE; 65937e6cd515bbe7ff2f255c8fcd40bf1a575a9a16Roland Levillain void VisitNeg(HNeg* instruction) OVERRIDE; 66badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitPackedSwitch(HPackedSwitch* instruction) OVERRIDE; 67fc6a86ab2b70781e72b807c1798b83829ca7f931David Brazdil void VisitReturn(HReturn* ret) OVERRIDE; 68fc6a86ab2b70781e72b807c1798b83829ca7f931David Brazdil void VisitReturnVoid(HReturnVoid* ret) OVERRIDE; 69badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitSelect(HSelect* instruction) OVERRIDE; 70badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void VisitTryBoundary(HTryBoundary* try_boundary) OVERRIDE; 71f355c3ff08710ac2eba3aac2aacc5e65caa06b4cRoland Levillain void VisitTypeConversion(HTypeConversion* instruction) OVERRIDE; 72badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil 73badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void HandleLoop(HBasicBlock* loop_header); 74badd826664896d4a9628a5a89b78016894aa414bDavid Brazdil void HandleBooleanInput(HInstruction* instruction, size_t input_index); 75fc6a86ab2b70781e72b807c1798b83829ca7f931David Brazdil 76ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Was the last visit of the graph valid? 77ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain bool IsValid() const { 7891356c028022180dfbe54ed7f5f465041c8b23ffAndreas Gampe return errors_.empty(); 79ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain } 80ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 81ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Get the list of detected errors. 82655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko const ArenaVector<std::string>& GetErrors() const { 83ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain return errors_; 84ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain } 85ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 8675be28332b278cff9039b54bfb228ac72f539cccRoland Levillain // Print detected errors on output stream `os`. 87c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers void Dump(std::ostream& os) const { 8891356c028022180dfbe54ed7f5f465041c8b23ffAndreas Gampe for (size_t i = 0, e = errors_.size(); i < e; ++i) { 8991356c028022180dfbe54ed7f5f465041c8b23ffAndreas Gampe os << dump_prefix_ << errors_[i] << std::endl; 9075be28332b278cff9039b54bfb228ac72f539cccRoland Levillain } 9175be28332b278cff9039b54bfb228ac72f539cccRoland Levillain } 9275be28332b278cff9039b54bfb228ac72f539cccRoland Levillain 93ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain protected: 945c4405e8ca4a0c1ee2d7759e650530c9aff77fd0Roland Levillain // Report a new error. 955c4405e8ca4a0c1ee2d7759e650530c9aff77fd0Roland Levillain void AddError(const std::string& error) { 965c4405e8ca4a0c1ee2d7759e650530c9aff77fd0Roland Levillain errors_.push_back(error); 975c4405e8ca4a0c1ee2d7759e650530c9aff77fd0Roland Levillain } 985c4405e8ca4a0c1ee2d7759e650530c9aff77fd0Roland Levillain 99ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // The block currently visited. 100ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain HBasicBlock* current_block_ = nullptr; 101ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain // Errors encountered while checking the graph. 102655e585073ac271cc9afa7c9d6ff5ab4dbe4b72eVladimir Marko ArenaVector<std::string> errors_; 103ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 104ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain private: 10575be28332b278cff9039b54bfb228ac72f539cccRoland Levillain // String displayed before dumped errors. 106c7dd295a4e0cc1d15c0c96088e55a85389bade74Ian Rogers const char* const dump_prefix_; 1077c5367badfe61b96c5836d495d286cee64861579Nicolas Geoffray ArenaBitVector seen_ids_; 10875be28332b278cff9039b54bfb228ac72f539cccRoland Levillain 109947eb700bec9e214a72d4747864398dc238da60cVladimir Marko // To reduce the total arena memory allocation, we reuse the same storage. 110947eb700bec9e214a72d4747864398dc238da60cVladimir Marko ArenaVector<HBasicBlock*> blocks_storage_; 111947eb700bec9e214a72d4747864398dc238da60cVladimir Marko ArenaBitVector visited_storage_; 112947eb700bec9e214a72d4747864398dc238da60cVladimir Marko 113ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain DISALLOW_COPY_AND_ASSIGN(GraphChecker); 114ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain}; 115ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 116ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain} // namespace art 117ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain 118ccc07a9579c554443cd03a306ca9b4f943fd2a93Roland Levillain#endif // ART_COMPILER_OPTIMIZING_GRAPH_CHECKER_H_ 119