src/compiler/node-matchers.h - experimental/external/v8 - Git at Google

 // Copyright 2014 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_NODE_MATCHERS_H_
 #define V8_COMPILER_NODE_MATCHERS_H_

 #include "src/compiler/generic-node.h"
 #include "src/compiler/generic-node-inl.h"
 #include "src/compiler/node.h"
 #include "src/compiler/operator.h"
 #include "src/unique.h"

 namespace v8 {
 namespace internal {
 namespace compiler {

 // A pattern matcher for nodes.
 struct NodeMatcher {
   explicit NodeMatcher(Node* node) : node_(node) {}

   Node* node() const { return node_; }
   const Operator* op() const { return node()->op(); }
   IrOpcode::Value opcode() const { return node()->opcode(); }

   bool HasProperty(Operator::Property property) const {
     return op()->HasProperty(property);
   }
   Node* InputAt(int index) const { return node()->InputAt(index); }

 #define DEFINE_IS_OPCODE(Opcode) \
   bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
   ALL_OP_LIST(DEFINE_IS_OPCODE)
 #undef DEFINE_IS_OPCODE

  private:
   Node* node_;
 };


 // A pattern matcher for abitrary value constants.
 template <typename T, IrOpcode::Value kOpcode>
 struct ValueMatcher : public NodeMatcher {
   explicit ValueMatcher(Node* node)
       : NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
     if (has_value_) {
       value_ = OpParameter<T>(node);
     }
   }

   bool HasValue() const { return has_value_; }
   const T& Value() const {
     DCHECK(HasValue());
     return value_;
   }

   bool Is(const T& value) const {
     return this->HasValue() && this->Value() == value;
   }

   bool IsInRange(const T& low, const T& high) const {
     return this->HasValue() && low <= this->Value() && this->Value() <= high;
   }

  private:
   T value_;
   bool has_value_;
 };


 // A pattern matcher for integer constants.
 template <typename T, IrOpcode::Value kOpcode>
 struct IntMatcher FINAL : public ValueMatcher<T, kOpcode> {
   explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}

   bool IsPowerOf2() const {
     return this->HasValue() && this->Value() > 0 &&
            (this->Value() & (this->Value() - 1)) == 0;
   }
 };

 typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
 typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
 typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
 typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
 #if V8_HOST_ARCH_32_BIT
 typedef Int32Matcher IntPtrMatcher;
 typedef Uint32Matcher UintPtrMatcher;
 #else
 typedef Int64Matcher IntPtrMatcher;
 typedef Uint64Matcher UintPtrMatcher;
 #endif


 // A pattern matcher for floating point constants.
 template <typename T, IrOpcode::Value kOpcode>
 struct FloatMatcher FINAL : public ValueMatcher<T, kOpcode> {
   explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}

   bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
 };

 typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
 typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
 typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;


 // A pattern matcher for heap object constants.
 template <typename T>
 struct HeapObjectMatcher FINAL
     : public ValueMatcher<Unique<T>, IrOpcode::kHeapConstant> {
   explicit HeapObjectMatcher(Node* node)
       : ValueMatcher<Unique<T>, IrOpcode::kHeapConstant>(node) {}
 };


 // For shorter pattern matching code, this struct matches both the left and
 // right hand sides of a binary operation and can put constants on the right
 // if they appear on the left hand side of a commutative operation.
 template <typename Left, typename Right>
 struct BinopMatcher : public NodeMatcher {
   explicit BinopMatcher(Node* node)
       : NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
     if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
   }

   const Left& left() const { return left_; }
   const Right& right() const { return right_; }

   bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
   bool LeftEqualsRight() const { return left().node() == right().node(); }

  protected:
   void SwapInputs() {
     std::swap(left_, right_);
     node()->ReplaceInput(0, left().node());
     node()->ReplaceInput(1, right().node());
   }

  private:
   void PutConstantOnRight() {
     if (left().HasValue() && !right().HasValue()) {
       SwapInputs();
     }
   }

   Left left_;
   Right right_;
 };

 typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
 typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
 typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
 typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
 typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
 typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
 typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
 typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;

 struct Int32AddMatcher : public Int32BinopMatcher {
   explicit Int32AddMatcher(Node* node)
       : Int32BinopMatcher(node), scale_exponent_(-1) {
     PutScaledInputOnLeft();
   }

   bool HasScaledInput() const { return scale_exponent_ != -1; }
   Node* ScaledInput() const {
     DCHECK(HasScaledInput());
     return left().node()->InputAt(0);
   }
   int ScaleExponent() const {
     DCHECK(HasScaledInput());
     return scale_exponent_;
   }

  private:
   int GetInputScaleExponent(Node* node) const {
     if (node->opcode() == IrOpcode::kWord32Shl) {
       Int32BinopMatcher m(node);
       if (m.right().HasValue()) {
         int32_t value = m.right().Value();
         if (value >= 0 && value <= 3) {
           return value;
         }
       }
     } else if (node->opcode() == IrOpcode::kInt32Mul) {
       Int32BinopMatcher m(node);
       if (m.right().HasValue()) {
         int32_t value = m.right().Value();
         if (value == 1) {
           return 0;
         } else if (value == 2) {
           return 1;
         } else if (value == 4) {
           return 2;
         } else if (value == 8) {
           return 3;
         }
       }
     }
     return -1;
   }

   void PutScaledInputOnLeft() {
     scale_exponent_ = GetInputScaleExponent(right().node());
     if (scale_exponent_ >= 0) {
       int left_scale_exponent = GetInputScaleExponent(left().node());
       if (left_scale_exponent == -1) {
         SwapInputs();
       } else {
         scale_exponent_ = left_scale_exponent;
       }
     } else {
       scale_exponent_ = GetInputScaleExponent(left().node());
       if (scale_exponent_ == -1) {
         if (right().opcode() == IrOpcode::kInt32Add &&
             left().opcode() != IrOpcode::kInt32Add) {
           SwapInputs();
         }
       }
     }
   }

   int scale_exponent_;
 };

 struct ScaledWithOffsetMatcher {
   explicit ScaledWithOffsetMatcher(Node* node)
       : matches_(false),
         scaled_(NULL),
         scale_exponent_(0),
         offset_(NULL),
         constant_(NULL) {
     if (node->opcode() != IrOpcode::kInt32Add) return;

     // The Int32AddMatcher canonicalizes the order of constants and scale
     // factors that are used as inputs, so instead of enumerating all possible
     // patterns by brute force, checking for node clusters using the following
     // templates in the following order suffices to find all of the interesting
     // cases (S = scaled input, O = offset input, C = constant input):
     // (S + (O + C))
     // (S + (O + O))
     // (S + C)
     // (S + O)
     // ((S + C) + O)
     // ((S + O) + C)
     // ((O + C) + O)
     // ((O + O) + C)
     // (O + C)
     // (O + O)
     Int32AddMatcher base_matcher(node);
     Node* left = base_matcher.left().node();
     Node* right = base_matcher.right().node();
     if (base_matcher.HasScaledInput() && left->OwnedBy(node)) {
       scaled_ = base_matcher.ScaledInput();
       scale_exponent_ = base_matcher.ScaleExponent();
       if (right->opcode() == IrOpcode::kInt32Add && right->OwnedBy(node)) {
         Int32AddMatcher right_matcher(right);
         if (right_matcher.right().HasValue()) {
           // (S + (O + C))
           offset_ = right_matcher.left().node();
           constant_ = right_matcher.right().node();
         } else {
           // (S + (O + O))
           offset_ = right;
         }
       } else if (base_matcher.right().HasValue()) {
         // (S + C)
         constant_ = right;
       } else {
         // (S + O)
         offset_ = right;
       }
     } else {
       if (left->opcode() == IrOpcode::kInt32Add && left->OwnedBy(node)) {
         Int32AddMatcher left_matcher(left);
         Node* left_left = left_matcher.left().node();
         Node* left_right = left_matcher.right().node();
         if (left_matcher.HasScaledInput() && left_left->OwnedBy(left)) {
           scaled_ = left_matcher.ScaledInput();
           scale_exponent_ = left_matcher.ScaleExponent();
           if (left_matcher.right().HasValue()) {
             // ((S + C) + O)
             constant_ = left_right;
             offset_ = right;
           } else if (base_matcher.right().HasValue()) {
             // ((S + O) + C)
             offset_ = left_right;
             constant_ = right;
           } else {
             // (O + O)
             scaled_ = left;
             offset_ = right;
           }
         } else {
           if (left_matcher.right().HasValue()) {
             // ((O + C) + O)
             scaled_ = left_left;
             constant_ = left_right;
             offset_ = right;
           } else if (base_matcher.right().HasValue()) {
             // ((O + O) + C)
             scaled_ = left_left;
             offset_ = left_right;
             constant_ = right;
           } else {
             // (O + O)
             scaled_ = left;
             offset_ = right;
           }
         }
       } else {
         if (base_matcher.right().HasValue()) {
           // (O + C)
           offset_ = left;
           constant_ = right;
         } else {
           // (O + O)
           offset_ = left;
           scaled_ = right;
         }
       }
     }
     matches_ = true;
   }

   bool matches() const { return matches_; }
   Node* scaled() const { return scaled_; }
   int scale_exponent() const { return scale_exponent_; }
   Node* offset() const { return offset_; }
   Node* constant() const { return constant_; }

  private:
   bool matches_;

  protected:
   Node* scaled_;
   int scale_exponent_;
   Node* offset_;
   Node* constant_;
 };

 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8

 #endif  // V8_COMPILER_NODE_MATCHERS_H_
	// Copyright 2014 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_NODE_MATCHERS_H_
	#define V8_COMPILER_NODE_MATCHERS_H_

	#include "src/compiler/generic-node.h"
	#include "src/compiler/generic-node-inl.h"
	#include "src/compiler/node.h"
	#include "src/compiler/operator.h"
	#include "src/unique.h"

	namespace v8 {
	namespace internal {
	namespace compiler {

	// A pattern matcher for nodes.
	struct NodeMatcher {
	explicit NodeMatcher(Node* node) : node_(node) {}

	Node* node() const { return node_; }
	const Operator* op() const { return node()->op(); }
	IrOpcode::Value opcode() const { return node()->opcode(); }

	bool HasProperty(Operator::Property property) const {
	return op()->HasProperty(property);
	}
	Node* InputAt(int index) const { return node()->InputAt(index); }

	#define DEFINE_IS_OPCODE(Opcode) \
	bool Is##Opcode() const { return opcode() == IrOpcode::k##Opcode; }
	ALL_OP_LIST(DEFINE_IS_OPCODE)
	#undef DEFINE_IS_OPCODE

	private:
	Node* node_;
	};


	// A pattern matcher for abitrary value constants.
	template <typename T, IrOpcode::Value kOpcode>
	struct ValueMatcher : public NodeMatcher {
	explicit ValueMatcher(Node* node)
	: NodeMatcher(node), value_(), has_value_(opcode() == kOpcode) {
	if (has_value_) {
	value_ = OpParameter<T>(node);
	}
	}

	bool HasValue() const { return has_value_; }
	const T& Value() const {
	DCHECK(HasValue());
	return value_;
	}

	bool Is(const T& value) const {
	return this->HasValue() && this->Value() == value;
	}

	bool IsInRange(const T& low, const T& high) const {
	return this->HasValue() && low <= this->Value() && this->Value() <= high;
	}

	private:
	T value_;
	bool has_value_;
	};


	// A pattern matcher for integer constants.
	template <typename T, IrOpcode::Value kOpcode>
	struct IntMatcher FINAL : public ValueMatcher<T, kOpcode> {
	explicit IntMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}

	bool IsPowerOf2() const {
	return this->HasValue() && this->Value() > 0 &&
	(this->Value() & (this->Value() - 1)) == 0;
	}
	};

	typedef IntMatcher<int32_t, IrOpcode::kInt32Constant> Int32Matcher;
	typedef IntMatcher<uint32_t, IrOpcode::kInt32Constant> Uint32Matcher;
	typedef IntMatcher<int64_t, IrOpcode::kInt64Constant> Int64Matcher;
	typedef IntMatcher<uint64_t, IrOpcode::kInt64Constant> Uint64Matcher;
	#if V8_HOST_ARCH_32_BIT
	typedef Int32Matcher IntPtrMatcher;
	typedef Uint32Matcher UintPtrMatcher;
	#else
	typedef Int64Matcher IntPtrMatcher;
	typedef Uint64Matcher UintPtrMatcher;
	#endif


	// A pattern matcher for floating point constants.
	template <typename T, IrOpcode::Value kOpcode>
	struct FloatMatcher FINAL : public ValueMatcher<T, kOpcode> {
	explicit FloatMatcher(Node* node) : ValueMatcher<T, kOpcode>(node) {}

	bool IsNaN() const { return this->HasValue() && std::isnan(this->Value()); }
	};

	typedef FloatMatcher<float, IrOpcode::kFloat32Constant> Float32Matcher;
	typedef FloatMatcher<double, IrOpcode::kFloat64Constant> Float64Matcher;
	typedef FloatMatcher<double, IrOpcode::kNumberConstant> NumberMatcher;


	// A pattern matcher for heap object constants.
	template <typename T>
	struct HeapObjectMatcher FINAL
	: public ValueMatcher<Unique<T>, IrOpcode::kHeapConstant> {
	explicit HeapObjectMatcher(Node* node)
	: ValueMatcher<Unique<T>, IrOpcode::kHeapConstant>(node) {}
	};


	// For shorter pattern matching code, this struct matches both the left and
	// right hand sides of a binary operation and can put constants on the right
	// if they appear on the left hand side of a commutative operation.
	template <typename Left, typename Right>
	struct BinopMatcher : public NodeMatcher {
	explicit BinopMatcher(Node* node)
	: NodeMatcher(node), left_(InputAt(0)), right_(InputAt(1)) {
	if (HasProperty(Operator::kCommutative)) PutConstantOnRight();
	}

	const Left& left() const { return left_; }
	const Right& right() const { return right_; }

	bool IsFoldable() const { return left().HasValue() && right().HasValue(); }
	bool LeftEqualsRight() const { return left().node() == right().node(); }

	protected:
	void SwapInputs() {
	std::swap(left_, right_);
	node()->ReplaceInput(0, left().node());
	node()->ReplaceInput(1, right().node());
	}

	private:
	void PutConstantOnRight() {
	if (left().HasValue() && !right().HasValue()) {
	SwapInputs();
	}
	}

	Left left_;
	Right right_;
	};

	typedef BinopMatcher<Int32Matcher, Int32Matcher> Int32BinopMatcher;
	typedef BinopMatcher<Uint32Matcher, Uint32Matcher> Uint32BinopMatcher;
	typedef BinopMatcher<Int64Matcher, Int64Matcher> Int64BinopMatcher;
	typedef BinopMatcher<Uint64Matcher, Uint64Matcher> Uint64BinopMatcher;
	typedef BinopMatcher<IntPtrMatcher, IntPtrMatcher> IntPtrBinopMatcher;
	typedef BinopMatcher<UintPtrMatcher, UintPtrMatcher> UintPtrBinopMatcher;
	typedef BinopMatcher<Float64Matcher, Float64Matcher> Float64BinopMatcher;
	typedef BinopMatcher<NumberMatcher, NumberMatcher> NumberBinopMatcher;

	struct Int32AddMatcher : public Int32BinopMatcher {
	explicit Int32AddMatcher(Node* node)
	: Int32BinopMatcher(node), scale_exponent_(-1) {
	PutScaledInputOnLeft();
	}

	bool HasScaledInput() const { return scale_exponent_ != -1; }
	Node* ScaledInput() const {
	DCHECK(HasScaledInput());
	return left().node()->InputAt(0);
	}
	int ScaleExponent() const {
	DCHECK(HasScaledInput());
	return scale_exponent_;
	}

	private:
	int GetInputScaleExponent(Node* node) const {
	if (node->opcode() == IrOpcode::kWord32Shl) {
	Int32BinopMatcher m(node);
	if (m.right().HasValue()) {
	int32_t value = m.right().Value();
	if (value >= 0 && value <= 3) {
	return value;
	}
	}
	} else if (node->opcode() == IrOpcode::kInt32Mul) {
	Int32BinopMatcher m(node);
	if (m.right().HasValue()) {
	int32_t value = m.right().Value();
	if (value == 1) {
	return 0;
	} else if (value == 2) {
	return 1;
	} else if (value == 4) {
	return 2;
	} else if (value == 8) {
	return 3;
	}
	}
	}
	return -1;
	}

	void PutScaledInputOnLeft() {
	scale_exponent_ = GetInputScaleExponent(right().node());
	if (scale_exponent_ >= 0) {
	int left_scale_exponent = GetInputScaleExponent(left().node());
	if (left_scale_exponent == -1) {
	SwapInputs();
	} else {
	scale_exponent_ = left_scale_exponent;
	}
	} else {
	scale_exponent_ = GetInputScaleExponent(left().node());
	if (scale_exponent_ == -1) {
	if (right().opcode() == IrOpcode::kInt32Add &&
	left().opcode() != IrOpcode::kInt32Add) {
	SwapInputs();
	}
	}
	}
	}

	int scale_exponent_;
	};

	struct ScaledWithOffsetMatcher {
	explicit ScaledWithOffsetMatcher(Node* node)
	: matches_(false),
	scaled_(NULL),
	scale_exponent_(0),
	offset_(NULL),
	constant_(NULL) {
	if (node->opcode() != IrOpcode::kInt32Add) return;

	// The Int32AddMatcher canonicalizes the order of constants and scale
	// factors that are used as inputs, so instead of enumerating all possible
	// patterns by brute force, checking for node clusters using the following
	// templates in the following order suffices to find all of the interesting
	// cases (S = scaled input, O = offset input, C = constant input):
	// (S + (O + C))
	// (S + (O + O))
	// (S + C)
	// (S + O)
	// ((S + C) + O)
	// ((S + O) + C)
	// ((O + C) + O)
	// ((O + O) + C)
	// (O + C)
	// (O + O)
	Int32AddMatcher base_matcher(node);
	Node* left = base_matcher.left().node();
	Node* right = base_matcher.right().node();
	if (base_matcher.HasScaledInput() && left->OwnedBy(node)) {
	scaled_ = base_matcher.ScaledInput();
	scale_exponent_ = base_matcher.ScaleExponent();
	if (right->opcode() == IrOpcode::kInt32Add && right->OwnedBy(node)) {
	Int32AddMatcher right_matcher(right);
	if (right_matcher.right().HasValue()) {
	// (S + (O + C))
	offset_ = right_matcher.left().node();
	constant_ = right_matcher.right().node();
	} else {
	// (S + (O + O))
	offset_ = right;
	}
	} else if (base_matcher.right().HasValue()) {
	// (S + C)
	constant_ = right;
	} else {
	// (S + O)
	offset_ = right;
	}
	} else {
	if (left->opcode() == IrOpcode::kInt32Add && left->OwnedBy(node)) {
	Int32AddMatcher left_matcher(left);
	Node* left_left = left_matcher.left().node();
	Node* left_right = left_matcher.right().node();
	if (left_matcher.HasScaledInput() && left_left->OwnedBy(left)) {
	scaled_ = left_matcher.ScaledInput();
	scale_exponent_ = left_matcher.ScaleExponent();
	if (left_matcher.right().HasValue()) {
	// ((S + C) + O)
	constant_ = left_right;
	offset_ = right;
	} else if (base_matcher.right().HasValue()) {
	// ((S + O) + C)
	offset_ = left_right;
	constant_ = right;
	} else {
	// (O + O)
	scaled_ = left;
	offset_ = right;
	}
	} else {
	if (left_matcher.right().HasValue()) {
	// ((O + C) + O)
	scaled_ = left_left;
	constant_ = left_right;
	offset_ = right;
	} else if (base_matcher.right().HasValue()) {
	// ((O + O) + C)
	scaled_ = left_left;
	offset_ = left_right;
	constant_ = right;
	} else {
	// (O + O)
	scaled_ = left;
	offset_ = right;
	}
	}
	} else {
	if (base_matcher.right().HasValue()) {
	// (O + C)
	offset_ = left;
	constant_ = right;
	} else {
	// (O + O)
	offset_ = left;
	scaled_ = right;
	}
	}
	}
	matches_ = true;
	}

	bool matches() const { return matches_; }
	Node* scaled() const { return scaled_; }
	int scale_exponent() const { return scale_exponent_; }
	Node* offset() const { return offset_; }
	Node* constant() const { return constant_; }

	private:
	bool matches_;

	protected:
	Node* scaled_;
	int scale_exponent_;
	Node* offset_;
	Node* constant_;
	};

	} // namespace compiler
	} // namespace internal
	} // namespace v8

	#endif // V8_COMPILER_NODE_MATCHERS_H_