LCOV - code coverage report
Current view: top level - src/compiler - branch-elimination.cc (source / functions) Hit Total Coverage
Test: app.info Lines: 69 84 82.1 %
Date: 2019-04-17 Functions: 10 18 55.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      995587 : BranchElimination::BranchElimination(Editor* editor, JSGraph* js_graph,
      16             :                                      Zone* zone)
      17             :     : AdvancedReducer(editor),
      18             :       jsgraph_(js_graph),
      19             :       node_conditions_(js_graph->graph()->NodeCount(), zone),
      20             :       reduced_(js_graph->graph()->NodeCount(), zone),
      21             :       zone_(zone),
      22     1991180 :       dead_(js_graph->Dead()) {}
      23             : 
      24             : BranchElimination::~BranchElimination() = default;
      25             : 
      26             : 
      27   131253029 : Reduction BranchElimination::Reduce(Node* node) {
      28   131253029 :   switch (node->opcode()) {
      29             :     case IrOpcode::kDead:
      30             :       return NoChange();
      31             :     case IrOpcode::kDeoptimizeIf:
      32             :     case IrOpcode::kDeoptimizeUnless:
      33      398580 :       return ReduceDeoptimizeConditional(node);
      34             :     case IrOpcode::kMerge:
      35     3315838 :       return ReduceMerge(node);
      36             :     case IrOpcode::kLoop:
      37             :       return ReduceLoop(node);
      38             :     case IrOpcode::kBranch:
      39     4836075 :       return ReduceBranch(node);
      40             :     case IrOpcode::kIfFalse:
      41     4711596 :       return ReduceIf(node, false);
      42             :     case IrOpcode::kIfTrue:
      43     4753129 :       return ReduceIf(node, true);
      44             :     case IrOpcode::kStart:
      45             :       return ReduceStart(node);
      46             :     default:
      47   110872858 :       if (node->op()->ControlOutputCount() > 0) {
      48             :         return ReduceOtherControl(node);
      49             :       }
      50             :       break;
      51             :   }
      52             :   return NoChange();
      53             : }
      54             : 
      55             : 
      56     4836057 : Reduction BranchElimination::ReduceBranch(Node* node) {
      57             :   Node* condition = node->InputAt(0);
      58     4836057 :   Node* control_input = NodeProperties::GetControlInput(node, 0);
      59             :   ControlPathConditions from_input = node_conditions_.Get(control_input);
      60             :   Node* branch;
      61             :   bool condition_value;
      62             :   // If we know the condition we can discard the branch.
      63     4836006 :   if (from_input.LookupCondition(condition, &branch, &condition_value)) {
      64             :     // Mark the branch as a safety check if necessary.
      65             :     // Check if {branch} is dead because we might have a stale side-table entry.
      66       34252 :     if (!branch->IsDead() && branch->opcode() != IrOpcode::kDead) {
      67       17119 :       IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
      68             :       IsSafetyCheck combined_safety =
      69       17119 :           CombineSafetyChecks(branch_safety, IsSafetyCheckOf(node->op()));
      70       17119 :       if (branch_safety != combined_safety) {
      71         408 :         NodeProperties::ChangeOp(
      72         408 :             branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
      73             :       }
      74             :     }
      75             : 
      76       51378 :     for (Node* const use : node->uses()) {
      77       34252 :       switch (use->opcode()) {
      78             :         case IrOpcode::kIfTrue:
      79       17126 :           Replace(use, condition_value ? control_input : dead());
      80             :           break;
      81             :         case IrOpcode::kIfFalse:
      82       17126 :           Replace(use, condition_value ? dead() : control_input);
      83             :           break;
      84             :         default:
      85           0 :           UNREACHABLE();
      86             :       }
      87             :     }
      88             :     return Replace(dead());
      89             :   }
      90     4818880 :   return TakeConditionsFromFirstControl(node);
      91             : }
      92             : 
      93      398577 : Reduction BranchElimination::ReduceDeoptimizeConditional(Node* node) {
      94             :   DCHECK(node->opcode() == IrOpcode::kDeoptimizeIf ||
      95             :          node->opcode() == IrOpcode::kDeoptimizeUnless);
      96      398577 :   bool condition_is_true = node->opcode() == IrOpcode::kDeoptimizeUnless;
      97      398577 :   DeoptimizeParameters p = DeoptimizeParametersOf(node->op());
      98      398579 :   Node* condition = NodeProperties::GetValueInput(node, 0);
      99      398573 :   Node* frame_state = NodeProperties::GetValueInput(node, 1);
     100      398572 :   Node* effect = NodeProperties::GetEffectInput(node);
     101      398574 :   Node* control = NodeProperties::GetControlInput(node);
     102             :   // If we do not know anything about the predecessor, do not propagate just
     103             :   // yet because we will have to recompute anyway once we compute the
     104             :   // predecessor.
     105      398574 :   if (!reduced_.Get(control)) {
     106             :     return NoChange();
     107             :   }
     108             : 
     109             :   ControlPathConditions conditions = node_conditions_.Get(control);
     110             :   bool condition_value;
     111             :   Node* branch;
     112      344557 :   if (conditions.LookupCondition(condition, &branch, &condition_value)) {
     113             :     // Mark the branch as a safety check.
     114        8783 :     IsSafetyCheck branch_safety = IsSafetyCheckOf(branch->op());
     115             :     IsSafetyCheck combined_safety =
     116        8783 :         CombineSafetyChecks(branch_safety, p.is_safety_check());
     117        8783 :     if (branch_safety != combined_safety) {
     118        3526 :       NodeProperties::ChangeOp(
     119        3526 :           branch, common()->MarkAsSafetyCheck(branch->op(), combined_safety));
     120             :     }
     121             : 
     122             :     // If we know the condition we can discard the branch.
     123        8783 :     if (condition_is_true == condition_value) {
     124             :       // We don't update the conditions here, because we're replacing {node}
     125             :       // with the {control} node that already contains the right information.
     126             :       ReplaceWithValue(node, dead(), effect, control);
     127             :     } else {
     128           0 :       control = graph()->NewNode(
     129             :           common()->Deoptimize(p.kind(), p.reason(), p.feedback()), frame_state,
     130             :           effect, control);
     131             :       // TODO(bmeurer): This should be on the AdvancedReducer somehow.
     132           0 :       NodeProperties::MergeControlToEnd(graph(), common(), control);
     133             :       Revisit(graph()->end());
     134             :     }
     135             :     return Replace(dead());
     136             :   }
     137      335774 :   return UpdateConditions(node, conditions, condition, node, condition_is_true);
     138             : }
     139             : 
     140     9464473 : Reduction BranchElimination::ReduceIf(Node* node, bool is_true_branch) {
     141             :   // Add the condition to the list arriving from the input branch.
     142     9464473 :   Node* branch = NodeProperties::GetControlInput(node, 0);
     143     9464560 :   ControlPathConditions from_branch = node_conditions_.Get(branch);
     144             :   // If we do not know anything about the predecessor, do not propagate just
     145             :   // yet because we will have to recompute anyway once we compute the
     146             :   // predecessor.
     147     9464560 :   if (!reduced_.Get(branch)) {
     148             :     return NoChange();
     149             :   }
     150             :   Node* condition = branch->InputAt(0);
     151     7615018 :   return UpdateConditions(node, from_branch, condition, branch, is_true_branch);
     152             : }
     153             : 
     154             : 
     155           0 : Reduction BranchElimination::ReduceLoop(Node* node) {
     156             :   // Here we rely on having only reducible loops:
     157             :   // The loop entry edge always dominates the header, so we can just use
     158             :   // the information from the loop entry edge.
     159      405860 :   return TakeConditionsFromFirstControl(node);
     160             : }
     161             : 
     162             : 
     163     3315929 : Reduction BranchElimination::ReduceMerge(Node* node) {
     164             :   // Shortcut for the case when we do not know anything about some
     165             :   // input.
     166             :   Node::Inputs inputs = node->inputs();
     167    12969755 :   for (Node* input : inputs) {
     168    10601483 :     if (!reduced_.Get(input)) {
     169             :       return NoChange();
     170             :     }
     171             :   }
     172             : 
     173             :   auto input_it = inputs.begin();
     174             : 
     175             :   DCHECK_GT(inputs.count(), 0);
     176             : 
     177     2368272 :   ControlPathConditions conditions = node_conditions_.Get(*input_it);
     178             :   ++input_it;
     179             :   // Merge the first input's conditions with the conditions from the other
     180             :   // inputs.
     181             :   auto input_end = inputs.end();
     182     6529797 :   for (; input_it != input_end; ++input_it) {
     183             :     // Change the current condition list to a longest common tail
     184             :     // of this condition list and the other list. (The common tail
     185             :     // should correspond to the list from the common dominator.)
     186     4161567 :     conditions.ResetToCommonAncestor(node_conditions_.Get(*input_it));
     187             :   }
     188     2368230 :   return UpdateConditions(node, conditions);
     189             : }
     190             : 
     191             : 
     192           0 : Reduction BranchElimination::ReduceStart(Node* node) {
     193     1923893 :   return UpdateConditions(node, {});
     194             : }
     195             : 
     196             : 
     197           0 : Reduction BranchElimination::ReduceOtherControl(Node* node) {
     198             :   DCHECK_EQ(1, node->op()->ControlInputCount());
     199    17642451 :   return TakeConditionsFromFirstControl(node);
     200             : }
     201             : 
     202             : 
     203    22867043 : 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    22867043 :   Node* input = NodeProperties::GetControlInput(node, 0);
     207    22867126 :   if (!reduced_.Get(input)) return NoChange();
     208    20404977 :   return UpdateConditions(node, node_conditions_.Get(input));
     209             : }
     210             : 
     211    32646909 : Reduction BranchElimination::UpdateConditions(
     212             :     Node* node, ControlPathConditions conditions) {
     213             :   // Only signal that the node has Changed if the condition information has
     214             :   // changed.
     215    32646909 :   if (reduced_.Set(node, true) | node_conditions_.Set(node, conditions)) {
     216             :     return Changed(node);
     217             :   }
     218             :   return NoChange();
     219             : }
     220             : 
     221     7950690 : Reduction BranchElimination::UpdateConditions(
     222             :     Node* node, ControlPathConditions prev_conditions, Node* current_condition,
     223             :     Node* current_branch, bool is_true_branch) {
     224             :   ControlPathConditions original = node_conditions_.Get(node);
     225             :   // The control path for the node is the path obtained by appending the
     226             :   // current_condition to the prev_conditions. Use the original control path as
     227             :   // a hint to avoid allocations.
     228     7950690 :   prev_conditions.AddCondition(zone_, current_condition, current_branch,
     229             :                                is_true_branch, original);
     230     7950631 :   return UpdateConditions(node, prev_conditions);
     231             : }
     232             : 
     233           0 : void BranchElimination::ControlPathConditions::AddCondition(
     234             :     Zone* zone, Node* condition, Node* branch, bool is_true,
     235             :     ControlPathConditions hint) {
     236             :   DCHECK_EQ(false, LookupCondition(condition, nullptr, nullptr));
     237     7950690 :   PushFront({condition, branch, is_true}, zone, hint);
     238           0 : }
     239             : 
     240           0 : bool BranchElimination::ControlPathConditions::LookupCondition(
     241             :     Node* condition, Node** branch, bool* is_true) const {
     242    29689876 :   for (BranchCondition element : *this) {
     243    24535222 :     if (element.condition == condition) {
     244       25909 :       *is_true = element.is_true;
     245           0 :       *branch = element.branch;
     246             :       return true;
     247             :     }
     248             :   }
     249           0 :   return false;
     250             : }
     251             : 
     252           0 : Graph* BranchElimination::graph() const { return jsgraph()->graph(); }
     253             : 
     254           0 : Isolate* BranchElimination::isolate() const { return jsgraph()->isolate(); }
     255             : 
     256           0 : CommonOperatorBuilder* BranchElimination::common() const {
     257           0 :   return jsgraph()->common();
     258             : }
     259             : 
     260             : }  // namespace compiler
     261             : }  // namespace internal
     262      122004 : }  // namespace v8

Generated by: LCOV version 1.10