Home | History | Annotate | Download | only in compiler 
      1 // Copyright 2015 the V8 project authors. All rights reserved.
      2 // Use of this source code is governed by a BSD-style license that can be
      3 // found in the LICENSE file.
      4 
      5 #include "src/compiler/bytecode-branch-analysis.h"
      6 
      7 #include "src/interpreter/bytecode-array-iterator.h"
      8 #include "src/objects-inl.h"
      9 
     10 namespace v8 {
     11 namespace internal {
     12 namespace compiler {
     13 
     14 // The class contains all of the sites that contain
     15 // branches to a particular target (bytecode offset).
     16 class BytecodeBranchInfo final : public ZoneObject {
     17  public:
     18   explicit BytecodeBranchInfo(Zone* zone)
     19       : back_edge_offsets_(zone), fore_edge_offsets_(zone) {}
     20 
     21   void AddBranch(int source_offset, int target_offset);
     22 
     23   // The offsets of bytecodes that refer to this bytecode as
     24   // a back-edge predecessor.
     25   const ZoneVector<int>* back_edge_offsets() { return &back_edge_offsets_; }
     26 
     27   // The offsets of bytecodes that refer to this bytecode as
     28   // a forwards-edge predecessor.
     29   const ZoneVector<int>* fore_edge_offsets() { return &fore_edge_offsets_; }
     30 
     31  private:
     32   ZoneVector<int> back_edge_offsets_;
     33   ZoneVector<int> fore_edge_offsets_;
     34 
     35   DISALLOW_COPY_AND_ASSIGN(BytecodeBranchInfo);
     36 };
     37 
     38 
     39 void BytecodeBranchInfo::AddBranch(int source_offset, int target_offset) {
     40   if (source_offset < target_offset) {
     41     fore_edge_offsets_.push_back(source_offset);
     42   } else {
     43     back_edge_offsets_.push_back(source_offset);
     44   }
     45 }
     46 
     47 
     48 BytecodeBranchAnalysis::BytecodeBranchAnalysis(
     49     Handle<BytecodeArray> bytecode_array, Zone* zone)
     50     : branch_infos_(zone),
     51       bytecode_array_(bytecode_array),
     52       reachable_(bytecode_array->length(), zone),
     53       zone_(zone) {}
     54 
     55 
     56 void BytecodeBranchAnalysis::Analyze() {
     57   interpreter::BytecodeArrayIterator iterator(bytecode_array());
     58   bool reachable = true;
     59   while (!iterator.done()) {
     60     interpreter::Bytecode bytecode = iterator.current_bytecode();
     61     int current_offset = iterator.current_offset();
     62     // All bytecode basic blocks are generated to be forward reachable
     63     // and may also be backward reachable. Hence if there's a forward
     64     // branch targetting here the code becomes reachable.
     65     reachable = reachable || forward_branches_target(current_offset);
     66     if (reachable) {
     67       reachable_.Add(current_offset);
     68       if (interpreter::Bytecodes::IsConditionalJump(bytecode)) {
     69         // Only the branch is recorded, the forward path falls through
     70         // and is handled as normal bytecode data flow.
     71         AddBranch(current_offset, iterator.GetJumpTargetOffset());
     72       } else if (interpreter::Bytecodes::IsJump(bytecode)) {
     73         // Unless the branch targets the next bytecode it's not
     74         // reachable. If it targets the next bytecode the check at the
     75         // start of the loop will set the reachable flag.
     76         AddBranch(current_offset, iterator.GetJumpTargetOffset());
     77         reachable = false;
     78       } else if (interpreter::Bytecodes::IsJumpOrReturn(bytecode)) {
     79         DCHECK_EQ(bytecode, interpreter::Bytecode::kReturn);
     80         reachable = false;
     81       }
     82     }
     83     iterator.Advance();
     84   }
     85 }
     86 
     87 
     88 const ZoneVector<int>* BytecodeBranchAnalysis::BackwardBranchesTargetting(
     89     int offset) const {
     90   auto iterator = branch_infos_.find(offset);
     91   if (branch_infos_.end() != iterator) {
     92     return iterator->second->back_edge_offsets();
     93   } else {
     94     return nullptr;
     95   }
     96 }
     97 
     98 
     99 const ZoneVector<int>* BytecodeBranchAnalysis::ForwardBranchesTargetting(
    100     int offset) const {
    101   auto iterator = branch_infos_.find(offset);
    102   if (branch_infos_.end() != iterator) {
    103     return iterator->second->fore_edge_offsets();
    104   } else {
    105     return nullptr;
    106   }
    107 }
    108 
    109 
    110 void BytecodeBranchAnalysis::AddBranch(int source_offset, int target_offset) {
    111   BytecodeBranchInfo* branch_info = nullptr;
    112   auto iterator = branch_infos_.find(target_offset);
    113   if (branch_infos_.end() == iterator) {
    114     branch_info = new (zone()) BytecodeBranchInfo(zone());
    115     branch_infos_.insert(std::make_pair(target_offset, branch_info));
    116   } else {
    117     branch_info = iterator->second;
    118   }
    119   branch_info->AddBranch(source_offset, target_offset);
    120 }
    121 
    122 
    123 }  // namespace compiler
    124 }  // namespace internal
    125 }  // namespace v8
    126