1014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Copyright 2015 the V8 project authors. All rights reserved. 2014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch// found in the LICENSE file. 4014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 5014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#ifndef V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_ 6014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#define V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_ 7014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 8c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/base/compiler-specific.h" 9014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/compiler/graph-reducer.h" 10c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch#include "src/globals.h" 11014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 12014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace v8 { 13014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace internal { 14014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochnamespace compiler { 15014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 163b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch// Forward declarations. 173b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdochclass CommonOperatorBuilder; 18014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdochclass JSGraph; 19014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 20c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdochclass V8_EXPORT_PRIVATE BranchElimination final 21c8c1d9e03f4babd16833b0f8ccf6aab5fa6e8c7aBen Murdoch : public NON_EXPORTED_BASE(AdvancedReducer) { 22014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 23014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BranchElimination(Editor* editor, JSGraph* js_graph, Zone* zone); 24014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ~BranchElimination() final; 25014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 26014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction Reduce(Node* node) final; 27014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 28014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 29014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch struct BranchCondition { 30014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* condition; 31014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_true; 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BranchCondition* next; 33014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 34014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BranchCondition(Node* condition, bool is_true, BranchCondition* next) 35014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : condition(condition), is_true(is_true), next(next) {} 36014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 37014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 38014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Class for tracking information about branch conditions. 39014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // At the moment it is a linked list of conditions and their values 40014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // (true or false). 41014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class ControlPathConditions { 42014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 43014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Maybe<bool> LookupCondition(Node* condition) const; 44014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 45014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ControlPathConditions* AddCondition(Zone* zone, Node* condition, 46014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool is_true) const; 47014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch static const ControlPathConditions* Empty(Zone* zone); 48014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Merge(const ControlPathConditions& other); 49014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 50014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator==(const ControlPathConditions& other) const; 51014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch bool operator!=(const ControlPathConditions& other) const { 52014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch return !(*this == other); 53014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch } 54014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 55014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 56014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ControlPathConditions(BranchCondition* head, size_t condition_count) 57014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : head_(head), condition_count_(condition_count) {} 58014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 59014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch BranchCondition* head_; 60014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // We keep track of the list length so that we can find the longest 61014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // common tail easily. 62014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch size_t condition_count_; 63014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 64014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 65014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // Maps each control node to the condition information known about the node. 66014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // If the information is nullptr, then we have not calculated the information 67014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch // yet. 68014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch class PathConditionsForControlNodes { 69014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch public: 70014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PathConditionsForControlNodes(Zone* zone, size_t size_hint) 71014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch : info_for_node_(size_hint, nullptr, zone) {} 72014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ControlPathConditions* Get(Node* node); 73014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch void Set(Node* node, const ControlPathConditions* conditions); 74014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 75014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch private: 76014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch ZoneVector<const ControlPathConditions*> info_for_node_; 77014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch }; 78014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 79014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceBranch(Node* node); 803b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch Reduction ReduceDeoptimizeConditional(Node* node); 81014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceIf(Node* node, bool is_true_branch); 82014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceLoop(Node* node); 83014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceMerge(Node* node); 84014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceStart(Node* node); 85014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction ReduceOtherControl(Node* node); 86014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 87014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction TakeConditionsFromFirstControl(Node* node); 88014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Reduction UpdateConditions(Node* node, 89014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch const ControlPathConditions* conditions); 90014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 91014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* dead() const { return dead_; } 923b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch Graph* graph() const; 933b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch JSGraph* jsgraph() const { return jsgraph_; } 943b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch CommonOperatorBuilder* common() const; 95014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 963b9bc31999c9787eb726ecdbfd5796bfdec32a18Ben Murdoch JSGraph* const jsgraph_; 97014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch PathConditionsForControlNodes node_conditions_; 98014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone* zone_; 99014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Node* dead_; 100014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch}; 101014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 102014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace compiler 103014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace internal 104014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch} // namespace v8 105014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch 106014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#endif // V8_COMPILER_BRANCH_CONDITION_ELIMINATION_H_ 107