[turbofan] Redundant branch elimination.

src/compiler/branch-condition-elimination.cc

+// Copyright 2015 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "src/compiler/branch-condition-elimination.h"
+
+#include "src/compiler/js-graph.h"
+#include "src/compiler/node-properties.h"
+#include "src/compiler/simplified-operator.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+BranchConditionElimination::BranchConditionElimination(Editor* editor,
+                                                       JSGraph* js_graph,
+                                                       Zone* zone)
+    : AdvancedReducer(editor),
+      node_conditions_(zone, js_graph->graph()->NodeCount()),
+      zone_(zone),
+      dead_(js_graph->graph()->NewNode(js_graph->common()->Dead())) {}
+
+
+BranchConditionElimination::~BranchConditionElimination() {}
+
+
+Reduction BranchConditionElimination::Reduce(Node* node) {
+  switch (node->opcode()) {
+    case IrOpcode::kDead:
+      return NoChange();
+    case IrOpcode::kMerge:
+      return ReduceMerge(node);
+    case IrOpcode::kLoop:
+      return ReduceLoop(node);
+    case IrOpcode::kBranch:
+      return ReduceBranch(node);
+    case IrOpcode::kIfFalse:
+      return ReduceIf(node, false);
+    case IrOpcode::kIfTrue:
+      return ReduceIf(node, true);
+    case IrOpcode::kStart:
+      return ReduceStart(node);
+    default:
+      if (node->op()->ControlOutputCount() > 0) {
+        return ReduceOtherControl(node);
+      }
+      break;
+  }
+  return NoChange();
+}
+
+
+Reduction BranchConditionElimination::ReduceBranch(Node* node) {
+  Node* condition = node->InputAt(0);
+  Node* control_input = NodeProperties::GetControlInput(node, 0);
+  const ControlPathConditions* from_input = node_conditions_.Get(control_input);
+  if (from_input != nullptr) {
+    Maybe<bool> condition_value = from_input->LookupCondition(condition);
+    // If we know the condition reduce the branch.
+    if (condition_value.IsJust()) {
+      bool known_value = condition_value.FromJust();
+      for (Node* const use : node->uses()) {
+        switch (use->opcode()) {
+          case IrOpcode::kIfTrue:
+            Replace(use, known_value ? control_input : dead());
+            break;
+          case IrOpcode::kIfFalse:
+            Replace(use, known_value ? dead() : control_input);
+            break;
+          default:
+            UNREACHABLE();
+        }
+      }
+      return Replace(dead());
+    }
+  }
+  return TakeConditionsFromFirstControl(node);
+}
+
+
+Reduction BranchConditionElimination::ReduceIf(Node* node,
+                                               bool is_true_branch) {
+  // Add the condition to the list arriving from the input branch.
+  Node* branch = NodeProperties::GetControlInput(node, 0);
+  const ControlPathConditions* from_branch = node_conditions_.Get(branch);
+  // If we do not know anything about the predecessor, do not propagate just
+  // yet because we will have to recompute anyway once we compute the
+  // predecessor.
+  if (from_branch == nullptr) {
+    DCHECK(node_conditions_.Get(node) == nullptr);
+    return NoChange();
+  }
+  Node* condition = branch->InputAt(0);
+  return UpdateConditions(
+      node, from_branch->AddCondition(zone_, condition, is_true_branch));
+}
+
+
+Reduction BranchConditionElimination::ReduceLoop(Node* node) {
+  // Here we rely on having only reducible loops:
+  // The loop entry edge always dominates the header, so we just use
+  // the information from the loop entry edge.
+  return TakeConditionsFromFirstControl(node);
+}
+
+
+Reduction BranchConditionElimination::ReduceMerge(Node* node) {
+  // Shortcut for the case when we do not know anything about some
+  // input.
+  for (int i = 0; i < node->InputCount(); i++) {
+    if (node_conditions_.Get(node->InputAt(i)) == nullptr) {
+      DCHECK(node_conditions_.Get(node) == nullptr);
+      return NoChange();
+    }
+  }
+
+  // Extract the information into the array.
+  ZoneVector<const ControlPathConditions*> input_conditions(zone_);
+  input_conditions.reserve(node->InputCount());
+  for (int i = 0; i < node->InputCount(); i++) {
+    input_conditions.push_back(node_conditions_.Get(node->InputAt(i)));
+  }
+
+  // Calculate the merged conditions.
+  const ControlPathConditions* conditions =
+      ControlPathConditions::Merge(zone_, input_conditions);
+
+  return UpdateConditions(node, conditions);
+}
+
+
+Reduction BranchConditionElimination::ReduceStart(Node* node) {
+  return UpdateConditions(node, ControlPathConditions::Empty(zone_));
+}
+
+
+const BranchConditionElimination::ControlPathConditions*
+BranchConditionElimination::PathConditionsForControlNodes::Get(Node* node) {
+  if (static_cast<size_t>(node->id()) < info_for_node_.size()) {
+    return info_for_node_[node->id()];
+  }
+  return nullptr;
+}
+
+
+void BranchConditionElimination::PathConditionsForControlNodes::Set(
+    Node* node, const ControlPathConditions* conditions) {
+  size_t index = static_cast<size_t>(node->id());
+  if (index >= info_for_node_.size()) {
+    info_for_node_.resize(index + 1, nullptr);
+  }
+  info_for_node_[index] = conditions;
+}
+
+
+Reduction BranchConditionElimination::ReduceOtherControl(Node* node) {
+  DCHECK_EQ(1, node->op()->ControlInputCount());
+  return TakeConditionsFromFirstControl(node);
+}
+
+
+Reduction BranchConditionElimination::TakeConditionsFromFirstControl(
+    Node* node) {
+  // We just propagate the information from the control input (ideally,
+  // we would only revisit control uses if there is change).
+  const ControlPathConditions* from_input =
+      node_conditions_.Get(NodeProperties::GetControlInput(node, 0));
+  return UpdateConditions(node, from_input);
+}
+
+
+Reduction BranchConditionElimination::UpdateConditions(
+    Node* node, const ControlPathConditions* conditions) {
+  const ControlPathConditions* original = node_conditions_.Get(node);
+  // Only signal that the node has Changed if the condition information has
+  // changed.
+  if (conditions != original) {
+    if (original == nullptr || *conditions != *original) {
+      node_conditions_.Set(node, conditions);
+      return Changed(node);
+    }
+  }
+  return NoChange();
+}
+
+
+bool BranchConditionElimination::BranchCondition::operator<(
+    const BranchCondition& other) const {
+  return condition_->id() < other.condition_->id();
+}
+
+
+bool BranchConditionElimination::BranchCondition::operator==(
+    const BranchCondition& other) const {
+  return condition_ == other.condition_ && is_true_ == other.is_true_;
+}
+
+
+// static
+const BranchConditionElimination::ControlPathConditions*
+BranchConditionElimination::ControlPathConditions::Empty(Zone* zone) {
+  return new (zone->New(sizeof(ControlPathConditions)))
+      ControlPathConditions(zone, 0);
+}
+
+
+// static
+const BranchConditionElimination::ControlPathConditions*
+BranchConditionElimination::ControlPathConditions::Merge(
+    Zone* zone, const ZoneVector<const ControlPathConditions*>& inputs) {
+  // The resulting list will not be longer than any of the input lists.
+  // We just take the size of the first list for capacity.
+  ControlPathConditions* conditions =
+      new (zone->New(sizeof(ControlPathConditions)))
+          ControlPathConditions(zone, inputs[0]->conditions_.size());
+  // We only take conditions that are known at each input. We use a naive
+  // to calculate that: take all the conditions from the first input that
+  // are present (and have the same value) in all the other inputs.
+  // Note: there are more efficient ways to do this (merge the lists or some
+  // such), but they are more complex.
+  for (auto branch_condition : inputs[0]->conditions_) {
+    bool all_same = true;
+    for (size_t j = 1; j < inputs.size(); j++) {
+      Maybe<bool> value =
+          inputs[j]->LookupCondition(branch_condition.condition_);
+      if (value.IsNothing() || value.FromJust() != branch_condition.is_true_) {
+        all_same = false;
+        break;
+      }
+    }
+    if (all_same) {
+      conditions->conditions_.push_back(branch_condition);
+    }
+  }
+  return conditions;
+}
+
+
+const BranchConditionElimination::ControlPathConditions*
+BranchConditionElimination::ControlPathConditions::AddCondition(
+    Zone* zone, Node* condition, bool is_true) const {
+  BranchCondition new_element(condition, is_true);
+  auto res =
+      std::lower_bound(conditions_.begin(), conditions_.end(), new_element);
+  if (res != conditions_.end() && res->condition_ == condition) {
+    // We found the same condition. We can just return the conditions. Note that
+    // it does not matter if the {is_true} value does not match - that just
+    // means that the current control path is not reachable.
+    return this;
+  }
+  // Build the new conditions.
+  ControlPathConditions* conditions =
+      new (zone->New(sizeof(ControlPathConditions)))
+          ControlPathConditions(zone, conditions_.size() + 1);
+  // Insert all the elements before the condition.
+  conditions->conditions_.insert(conditions->conditions_.end(),
+                                 conditions_.begin(), res);
+  // Insert the condition.
+  conditions->conditions_.push_back(new_element);
+  // Insert the rest.
+  conditions->conditions_.insert(conditions->conditions_.end(), res,
+                                 conditions_.end());
+  return conditions;
+}
+
+
+Maybe<bool> BranchConditionElimination::ControlPathConditions::LookupCondition(
+    Node* condition) const {
+  BranchCondition element(condition, false);
+  auto res = std::lower_bound(conditions_.begin(), conditions_.end(), element);
+  if (res != conditions_.end() && res->condition_ == condition) {
+    return Just<bool>(res->is_true_);
+  }
+  return Nothing<bool>();
+}
+
+
+bool BranchConditionElimination::ControlPathConditions::operator==(
+    const ControlPathConditions& other) const {
+  return conditions_ == other.conditions_;
+}
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8