blob: d78933e73408d7cbacc78af4b1544c6ddfead826 [file] [log] [blame]
// 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/base/compiler-specific.h"
#include "src/compiler/graph-reducer.h"
#include "src/globals.h"
namespace v8 {
namespace internal {
namespace compiler {
// Forward declarations.
class CommonOperatorBuilder;
class JSGraph;
class V8_EXPORT_PRIVATE BranchElimination final
: public NON_EXPORTED_BASE(AdvancedReducer) {
BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone);
~BranchElimination() final;
const char* reducer_name() const override { return "BranchElimination"; }
Reduction Reduce(Node* node) final;
struct BranchCondition {
Node* condition;
bool is_true;
BranchCondition* next;
BranchCondition(Node* condition, bool is_true, BranchCondition* next)
: condition(condition), is_true(is_true), next(next) {}
// Class for tracking information about branch conditions.
// At the moment it is a linked list of conditions and their values
// (true or false).
class ControlPathConditions {
Maybe<bool> LookupCondition(Node* condition) const;
const ControlPathConditions* AddCondition(Zone* zone, Node* condition,
bool is_true) const;
static const ControlPathConditions* Empty(Zone* zone);
void Merge(const ControlPathConditions& other);
bool IsSamePath(BranchCondition* first, BranchCondition* second) const;
bool EqualsAfterAddingCondition(const ControlPathConditions* other,
const Node* new_condition,
bool new_branch_condition) const;
bool operator==(const ControlPathConditions& other) const;
bool operator!=(const ControlPathConditions& other) const {
return !(*this == other);
ControlPathConditions(BranchCondition* head, size_t condition_count)
: head_(head), condition_count_(condition_count) {}
BranchCondition* head_;
// We keep track of the list length so that we can find the longest
// common tail easily.
size_t condition_count_;
// 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 {
PathConditionsForControlNodes(Zone* zone, size_t size_hint)
: info_for_node_(size_hint, nullptr, zone) {}
const ControlPathConditions* Get(Node* node) const;
void Set(Node* node, const ControlPathConditions* conditions);
ZoneVector<const ControlPathConditions*> info_for_node_;
Reduction ReduceBranch(Node* node);
Reduction ReduceDeoptimizeConditional(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);
Reduction UpdateConditions(Node* node,
const ControlPathConditions* prev_conditions,
Node* current_condition, bool is_true_branch);
Node* dead() const { return dead_; }
Graph* graph() const;
JSGraph* jsgraph() const { return jsgraph_; }
CommonOperatorBuilder* common() const;
JSGraph* const jsgraph_;
PathConditionsForControlNodes node_conditions_;
Zone* zone_;
Node* dead_;
} // namespace compiler
} // namespace internal
} // namespace v8