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