LCOV - code coverage report
Current view: top level - src/compiler - branch-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 97 113 85.8 %
Date: 2017-04-26 Functions: 14 22 63.6 %

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

Generated by: LCOV version 1.10