Home | History | Annotate | Download | only in optimizing 
      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: ")
     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).
     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?
     56   bool IsValid() const {
     57     return errors_.empty();
     58   }
     59 
     60   // Get the list of detected errors.
     61   const std::vector<std::string>& GetErrors() const {
     62     return errors_;
     63   }
     64 
     65   // Print detected errors on output stream `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.
     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.
     99   SSAChecker(ArenaAllocator* allocator, HGraph* graph)
    100     : GraphChecker(allocator, graph, "art::SSAChecker: ") {}
    101 
    102   // Check the whole graph (in reverse post-order).
    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