[turbofan] Redundant branch elimination.

src/compiler/branch-condition-elimination.h

Index: src/compiler/branch-condition-elimination.h
diff --git a/src/compiler/branch-condition-elimination.h b/src/compiler/branch-condition-elimination.h
new file mode 100644
index 0000000000000000000000000000000000000000..299a445d69566032985648d71ea2bdc4cef787c8
--- /dev/null
+++ b/src/compiler/branch-condition-elimination.h
@@ -0,0 +1,107 @@
+// 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.
+
+#ifndef V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_
+#define V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_
+
+#include "src/compiler/graph-reducer.h"
+
+namespace v8 {
+namespace internal {
+namespace compiler {
+
+class JSGraph;
+
+
+class BranchConditionElimination final : public AdvancedReducer {
+ public:
+  BranchConditionElimination(Editor* editor, JSGraph* js_graph, Zone* zone);
+  ~BranchConditionElimination() final;
+
+  Reduction Reduce(Node* node) final;
+
+ private:
+  struct BranchCondition {
+    Node* condition_;
+    bool is_true_;
+
+    // Inequality compares only the condition identity.
+    // This is sufficient for our search because we cannot have
+    // conflicting conditions on a path.
+    bool operator<(const BranchCondition& other) const;
+
+    // Equality is field-wise.
+    bool operator==(const BranchCondition& other) const;
+    bool operator!=(const BranchCondition& other) const {
+      return !(*this == other);
+    }
+
+    BranchCondition(Node* condition, bool is_true)
+        : condition_(condition), is_true_(is_true) {}
+  };
+
+  // Class for tracking information about branch conditions.
+  // At the moment it is a simple list of conditions and their values
+  // (true or false). The list is sorted by the node conditions' ids.
+  class ControlPathConditions {

[titzer, 2015/10/08 18:01:07]

The number of control path conditions is proportional to the dominator tree
height, so O(small). What about just using a simple unsorted list? That can be
immutable and therefore appended to by just cons'ing, allowing sharing
underneath. Merging can be a simple as finding the common prefix.

[Jarin, 2015/10/09 05:28:08]

Yeah, that's a good idea. The code might be even simpler. I was a bit worried
about the quadratic merge, but if we just do common prefix, it will stay linear.
However, we will lose a bit of precision, if we have the same conditions on all
paths but not on a dominator. Example:

while (true) { if (x) break; ... if (y) { if (x) break; } }
if (x) {...} // Redundant if.

The if statement should be eliminated by the current version, but not if we just
do common prefix for merges. I agree that this is rare, so it should be fine.

[Jarin, 2015/10/17 14:18:21]

Changed now, and it is indeed a bit faster (~10%) with unsorted lists.

+   public:
+    const ControlPathConditions* AddCondition(Zone* zone, Node* condition,
+                                              bool is_true) const;
+    Maybe<bool> LookupCondition(Node* condition) const;
+
+    static const ControlPathConditions* Empty(Zone* zone);
+    static const ControlPathConditions* Merge(
+        Zone* zone, const ZoneVector<const ControlPathConditions*>& inputs);
+
+    bool operator==(const ControlPathConditions& other) const;
+    bool operator!=(const ControlPathConditions& other) const {
+      return !(*this == other);
+    }
+
+   private:
+    ControlPathConditions(Zone* zone, size_t reserved_count)
+        : conditions_(zone) {
+      conditions_.reserve(reserved_count);
+    }
+
+    ZoneVector<BranchCondition> conditions_;
+  };
+
+  // Maps each control node to the condition information known about the node.
+  // If the information is nullptr, then we have not calculated the information
+  // yet.
+  class PathConditionsForControlNodes {
+   public:
+    PathConditionsForControlNodes(Zone* zone, size_t size_hint)
+        : info_for_node_(size_hint, nullptr, zone) {}
+    const ControlPathConditions* Get(Node* node);
+    void Set(Node* node, const ControlPathConditions* conditions);
+
+   private:
+    ZoneVector<const ControlPathConditions*> info_for_node_;
+  };
+
+  Reduction ReduceBranch(Node* node);
+  Reduction ReduceIf(Node* node, bool is_true_branch);
+  Reduction ReduceLoop(Node* node);
+  Reduction ReduceMerge(Node* node);
+  Reduction ReduceStart(Node* node);
+  Reduction ReduceOtherControl(Node* node);
+
+  Reduction TakeConditionsFromFirstControl(Node* node);
+  Reduction UpdateConditions(Node* node,
+                             const ControlPathConditions* conditions);
+
+  Node* dead() const { return dead_; }
+
+  PathConditionsForControlNodes node_conditions_;
+  Zone* zone_;
+  Node* dead_;
+};
+
+}  // namespace compiler
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_