[webkit-reviews] review denied: [Bug 125026] Implement a one-pass CSE using a hash table : [Attachment 218108] Patch

[bugzilla-daemon at webkit.org]

Filip Pizlo <fpizlo at apple.com> has denied Nadav Rotem <nrotem at apple.com>'s
request for review:
Bug 125026: Implement a one-pass CSE using a hash table
https://bugs.webkit.org/show_bug.cgi?id=125026

Attachment 218108: Patch
https://bugs.webkit.org/attachment.cgi?id=218108&action=review

------- Additional Comments from Filip Pizlo <fpizlo at apple.com>
View in context: https://bugs.webkit.org/attachment.cgi?id=218108&action=review


> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:98
> +    unsigned hashNode(Node *node)
> +    {
> +	   if (node->op() == JSConstant)
> +	       return (node->constantNumber() << 2) ^ 17;
> +
> +	   unsigned h = node->op() ^ node->arithNodeFlags();
> +	   for (unsigned i = 0; i < 3; i++) {
> +	       Edge edge = node->child(i);
> +	       if (!edge)
> +		   break;
> +
> +	       h <<= 8;
> +	       h ^= edge.node()->op() ^ edge.node()->arithNodeFlags();
> +	       if (edge.node()->op() == JSConstant)
> +		   h = (h << 8) ^ edge.node()->constantNumber();
> +	   }
> +	   return h;
> +    }

We like to put hash function fanciness into WTF/wtf/HashFunctions.h.  Also,
hashing a node seems like something that we might want to do from more than
just this phase.  I would recommend adding a "unsigned Node::hash()" const
method rather than having the hashNode() method here.  If you can see a nice
way of composing this out of HashFunctions.h, or putting some of the hash
tricks into HashFunctions.h (like blah << 2) ^ 17, which seems like a fairly
reusable cheap int hash), then you should do it - but that doesn't matter to me
as much.

> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:130
> +    bool nodeEquivalent(Node *a, Node *b)
> +    {
> +	   // Same opcode.
> +	   if (a->op() != b->op())
> +	       return false;
> +
> +	   // Handle Constants.
> +	   if (a->op() == JSConstant)
> +	       return a->constantNumber() == b->constantNumber();
> +
> +	   // Handle Weak Constants.
> +	   if (a->op() == WeakJSConstant)
> +	       return a->weakConstant() == b->weakConstant();
> +
> +	   // Same flags.
> +	   if (a->arithNodeFlags() != b->arithNodeFlags())
> +	       return false;
> +
> +	   // Same operands.
> +	   for (unsigned i = 0; i < 3; i++) {
> +	       Edge edge = b->child(i);
> +	       if (!edge)
> +		   break;
> +
> +	       if (a->child(i) != edge)
> +		   return false;
> +	   }
> +
> +	   // Nodes are identical.
> +	   return true;
> +    }

How about implementing this as "Node::operator==(const Node&) const"?

Well, to do that you'll probably want to also compare m_opInfo's.  Or, you can
call it something other than operator==.  But for sure, I'd rather have this be
a method in Node (with some appropriate name).

> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:224
> +    bool isPure(Node *node)
> +    {
> +	   switch (node->op()) {
> +	   case Identity:
> +	       return false;
> +	   case BitAnd:
> +	   case BitOr:
> +	   case BitXor:
> +	   case BitRShift:
> +	   case BitLShift:
> +	   case BitURShift:
> +	   case ArithAdd:
> +	   case ArithSub:
> +	   case ArithNegate:
> +	   case ArithMul:
> +	   case ArithIMul:
> +	   case ArithMod:
> +	   case ArithDiv:
> +	   case ArithAbs:
> +	   case ArithMin:
> +	   case ArithMax:
> +	   case ArithSqrt:
> +	   case ArithSin:
> +	   case ArithCos:
> +	   case StringCharAt:
> +	   case StringCharCodeAt:
> +	   case IsUndefined:
> +	   case IsBoolean:
> +	   case IsNumber:
> +	   case IsString:
> +	   case IsObject:
> +	   case IsFunction:
> +	   case DoubleAsInt32:
> +	   case LogicalNot:
> +	   case SkipTopScope:
> +	   case SkipScope:
> +	   case GetClosureRegisters:
> +	   case GetScope:
> +	   case TypeOf:
> +	   case CompareEqConstant:
> +	   case ValueToInt32:
> +	   case MakeRope:
> +	   case Int52ToDouble:
> +	   case Int52ToValue:
> +	       return true;
> +	   case Int32ToDouble:
> +	   case GetCallee:
> +	   case GetLocal:
> +	   case GetLocalUnlinked:
> +	   case Flush:
> +	       return false;
> +	   case JSConstant:
> +	       return true;
> +	   case WeakJSConstant:
> +	       return false;
> +	   case GetArrayLength:
> +	   case GetMyScope:
> +	       return false;
> +
> +	   // These nodes are only conditionally pure. Ignore them for now.
> +	   case ValueAdd:
> +	   case CompareLess:
> +	   case CompareLessEq:
> +	   case CompareGreater:
> +	   case CompareGreaterEq:
> +	   case CompareEq:
> +	       return false;
> +	   case GetGlobalVar:
> +	   case GetClosureVar:
> +	       return false;
> +	   case VarInjectionWatchpoint:
> +	   case PutGlobalVar:
> +	   case PutClosureVar:
> +	   case GetByVal:
> +	   case PutByValDirect:
> +	   case PutByVal:
> +	   case CheckStructure:
> +	   case StructureTransitionWatchpoint:
> +	   case PutStructure:
> +	   case CheckFunction:
> +	   case CheckExecutable:
> +	   case CheckArray:
> +	   case GetIndexedPropertyStorage:
> +	   case GetTypedArrayByteOffset:
> +	   case GetButterfly:
> +	   case GetByOffset:
> +	   case PutByOffset:
> +	   case Phantom:
> +	       return false;
> +	   default:
> +	       return false;
> +	   }
> +    }

See DFGClobberize.h.  There is a function like this:

bool doesWrites(Graph&, Node*);

Note that this function will think that certain special forward-exiting nodes
"do writes"; this is a hack to prevent hoisting them.  But that's probably OK
for now.  OTOH, doesWrites() will precisely handle things like ValueAdd. 
Probably for pure CSE, you'll actually want something like
"doesReadsOrWrites()" or you can call it "accessesHeap()".  You can implement
that function using the same pattern as doesWrites() - it's very simple.

Basically, for a while the DFG did have a bunch of different "isPure"-like
functions, and they got to be a huge pain to maintain.	So I'm trying to make
DFGClobberize.h be the oracle for all "is pure" type queries.