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/branch-elimination.h"
      6 
      7 #include "src/compiler/js-graph.h"
      8 #include "src/compiler/node-properties.h"
      9 #include "src/compiler/simplified-operator.h"
     10 
     11 namespace v8 {
     12 namespace internal {
     13 namespace compiler {
     14 
     15 BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
     16                                      Zone* zone)
     17     : AdvancedReducer(editor),
     18       node_conditions_(zone, js_graph->graph()->NodeCount()),
     19       zone_(zone),
     20       dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {}
     21 
     22 
     23 BranchElimination::~BranchElimination() {}
     24 
     25 
     26 Reduction BranchElimination::Reduce(Node* node) {
     27   switch (node->opcode()) {
     28     case IrOpcode::kDead:
     29       return NoChange();
     30     case IrOpcode::kMerge:
     31       return ReduceMerge(node);
     32     case IrOpcode::kLoop:
     33       return ReduceLoop(node);
     34     case IrOpcode::kBranch:
     35       return ReduceBranch(node);
     36     case IrOpcode::kIfFalse:
     37       return ReduceIf(node, false);
     38     case IrOpcode::kIfTrue:
     39       return ReduceIf(node, true);
     40     case IrOpcode::kStart:
     41       return ReduceStart(node);
     42     default:
     43       if (node->op()->ControlOutputCount() > 0) {
     44         return ReduceOtherControl(node);
     45       }
     46       break;
     47   }
     48   return NoChange();
     49 }
     50 
     51 
     52 Reduction BranchElimination::ReduceBranch(Node* node) {
     53   Node* condition = node->InputAt(0);
     54   Node* control_input = NodeProperties::GetControlInput(node, 0);
     55   const ControlPathConditions* from_input = node_conditions_.Get(control_input);
     56   if (from_input != nullptr) {
     57     Maybe<bool> condition_value = from_input->LookupCondition(condition);
     58     // If we know the condition we can discard the branch.
     59     if (condition_value.IsJust()) {
     60       bool known_value = condition_value.FromJust();
     61       for (Node* const use : node->uses()) {
     62         switch (use->opcode()) {
     63           case IrOpcode::kIfTrue:
     64             Replace(use, known_value ? control_input : dead());
     65             break;
     66           case IrOpcode::kIfFalse:
     67             Replace(use, known_value ? dead() : control_input);
     68             break;
     69           default:
     70             UNREACHABLE();
     71         }
     72       }
     73       return Replace(dead());
     74     }
     75   }
     76   return TakeConditionsFromFirstControl(node);
     77 }
     78 
     79 
     80 Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
     81   // Add the condition to the list arriving from the input branch.
     82   Node* branch = NodeProperties::GetControlInput(node, 0);
     83   const ControlPathConditions* from_branch = node_conditions_.Get(branch);
     84   // If we do not know anything about the predecessor, do not propagate just
     85   // yet because we will have to recompute anyway once we compute the
     86   // predecessor.
     87   if (from_branch == nullptr) {
     88     DCHECK(node_conditions_.Get(node) == nullptr);
     89     return NoChange();
     90   }
     91   Node* condition = branch->InputAt(0);
     92   return UpdateConditions(
     93       node, from_branch->AddCondition(zone_, condition, is_true_branch));
     94 }
     95 
     96 
     97 Reduction BranchElimination::ReduceLoop(Node* node) {
     98   // Here we rely on having only reducible loops:
     99   // The loop entry edge always dominates the header, so we can just use
    100   // the information from the loop entry edge.
    101   return TakeConditionsFromFirstControl(node);
    102 }
    103 
    104 
    105 Reduction BranchElimination::ReduceMerge(Node* node) {
    106   // Shortcut for the case when we do not know anything about some
    107   // input.
    108   for (int i = 0; i < node->InputCount(); i++) {
    109     if (node_conditions_.Get(node->InputAt(i)) == nullptr) {
    110       DCHECK(node_conditions_.Get(node) == nullptr);
    111       return NoChange();
    112     }
    113   }
    114 
    115   const ControlPathConditions* first = node_conditions_.Get(node->InputAt(0));
    116   // Make a copy of the first input's conditions and merge with the conditions
    117   // from other inputs.
    118   ControlPathConditions* conditions =
    119       new (zone_->New(sizeof(ControlPathConditions)))
    120           ControlPathConditions(*first);
    121   for (int i = 1; i < node->InputCount(); i++) {
    122     conditions->Merge(*(node_conditions_.Get(node->InputAt(i))));
    123   }
    124 
    125   return UpdateConditions(node, conditions);
    126 }
    127 
    128 
    129 Reduction BranchElimination::ReduceStart(Node* node) {
    130   return UpdateConditions(node, ControlPathConditions::Empty(zone_));
    131 }
    132 
    133 
    134 const BranchElimination::ControlPathConditions*
    135 BranchElimination::PathConditionsForControlNodes::Get(Node* node) {
    136   if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
    137     return info_for_node_[node->id()];
    138   }
    139   return nullptr;
    140 }
    141 
    142 
    143 void BranchElimination::PathConditionsForControlNodes::Set(
    144     Node* node, const ControlPathConditions* conditions) {
    145   size_t index = static_cast<size_t>(node->id());
    146   if (index >= info_for_node_.size()) {
    147     info_for_node_.resize(index + 1, nullptr);
    148   }
    149   info_for_node_[index] = conditions;
    150 }
    151 
    152 
    153 Reduction BranchElimination::ReduceOtherControl(Node* node) {
    154   DCHECK_EQ(1, node->op()->ControlInputCount());
    155   return TakeConditionsFromFirstControl(node);
    156 }
    157 
    158 
    159 Reduction BranchElimination::TakeConditionsFromFirstControl(Node* node) {
    160   // We just propagate the information from the control input (ideally,
    161   // we would only revisit control uses if there is change).
    162   const ControlPathConditions* from_input =
    163       node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
    164   return UpdateConditions(node, from_input);
    165 }
    166 
    167 
    168 Reduction BranchElimination::UpdateConditions(
    169     Node* node, const ControlPathConditions* conditions) {
    170   const ControlPathConditions* original = node_conditions_.Get(node);
    171   // Only signal that the node has Changed if the condition information has
    172   // changed.
    173   if (conditions != original) {
    174     if (original == nullptr || *conditions != *original) {
    175       node_conditions_.Set(node, conditions);
    176       return Changed(node);
    177     }
    178   }
    179   return NoChange();
    180 }
    181 
    182 
    183 // static
    184 const BranchElimination::ControlPathConditions*
    185 BranchElimination::ControlPathConditions::Empty(Zone* zone) {
    186   return new (zone->New(sizeof(ControlPathConditions)))
    187       ControlPathConditions(nullptr, 0);
    188 }
    189 
    190 
    191 void BranchElimination::ControlPathConditions::Merge(
    192     const ControlPathConditions& other) {
    193   // Change the current condition list to a longest common tail
    194   // of this condition list and the other list. (The common tail
    195   // should correspond to the list from the common dominator.)
    196 
    197   // First, we throw away the prefix of the longer list, so that
    198   // we have lists of the same length.
    199   size_t other_size = other.condition_count_;
    200   BranchCondition* other_condition = other.head_;
    201   while (other_size > condition_count_) {
    202     other_condition = other_condition->next;
    203     other_size--;
    204   }
    205   while (condition_count_ > other_size) {
    206     head_ = head_->next;
    207     condition_count_--;
    208   }
    209 
    210   // Then we go through both lists in lock-step until we find
    211   // the common tail.
    212   while (head_ != other_condition) {
    213     DCHECK(condition_count_ > 0);
    214     condition_count_--;
    215     other_condition = other_condition->next;
    216     head_ = head_->next;
    217   }
    218 }
    219 
    220 
    221 const BranchElimination::ControlPathConditions*
    222 BranchElimination::ControlPathConditions::AddCondition(Zone* zone,
    223                                                        Node* condition,
    224                                                        bool is_true) const {
    225   DCHECK(LookupCondition(condition).IsNothing());
    226 
    227   BranchCondition* new_head = new (zone->New(sizeof(BranchCondition)))
    228       BranchCondition(condition, is_true, head_);
    229 
    230   ControlPathConditions* conditions =
    231       new (zone->New(sizeof(ControlPathConditions)))
    232           ControlPathConditions(new_head, condition_count_ + 1);
    233   return conditions;
    234 }
    235 
    236 
    237 Maybe<bool> BranchElimination::ControlPathConditions::LookupCondition(
    238     Node* condition) const {
    239   for (BranchCondition* current = head_; current != nullptr;
    240        current = current->next) {
    241     if (current->condition == condition) {
    242       return Just<bool>(current->is_true);
    243     }
    244   }
    245   return Nothing<bool>();
    246 }
    247 
    248 
    249 bool BranchElimination::ControlPathConditions::operator==(
    250     const ControlPathConditions& other) const {
    251   if (condition_count_ != other.condition_count_) return false;
    252   BranchCondition* this_condition = head_;
    253   BranchCondition* other_condition = other.head_;
    254   while (true) {
    255     if (this_condition == other_condition) return true;
    256     if (this_condition->condition != other_condition->condition ||
    257         this_condition->is_true != other_condition->is_true) {
    258       return false;
    259     }
    260     this_condition = this_condition->next;
    261     other_condition = other_condition->next;
    262   }
    263   UNREACHABLE();
    264   return false;
    265 }
    266 
    267 }  // namespace compiler
    268 }  // namespace internal
    269 }  // namespace v8
    270