long_by_long_mulhi() rewritten and commented

[Christian Thalinger]

Hi!

While looking at 6795362, I tried to understand what the code in
long_by_long_mulhi() does and I rewrote it with a lot more comments
(plus original code from Hacker's Delight).

I'd like to commit this one but I'm not sure if there might be a
copyright problem.

Would it be okay to open a new CR and commit it?

-- Christian


--- 6795362.3b5ac9e7e6ea/src/share/vm/opto/divnode.cpp	2009-02-02 11:56:15.694744045 +0100
+++ /export/home/twisti/hotspot-comp/6795362/src/share/vm/opto/divnode.cpp	2009-02-02 11:55:20.837538078 +0100
@@ -252,34 +252,62 @@ static Node *long_by_long_mulhi( PhaseGV
     return new (phase->C, 3) MulHiLNode(dividend, v);
   }
 
-  const int N = 64;
-
-  Node *u_hi = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N / 2)));
-  Node *u_lo = phase->transform(new (phase->C, 3) AndLNode(dividend, phase->longcon(0xFFFFFFFF)));
+  // Taken from Hacker's Delight, Fig. 8-2. Multiply high signed.
+  // (http://www.hackersdelight.org/HDcode/mulhs.c)
+  //
+  // int mulhs(int u, int v) {
+  //    unsigned u0, v0, w0;
+  //    int u1, v1, w1, w2, t;
+  //
+  //    u0 = u & 0xFFFF;  u1 = u >> 16;
+  //    v0 = v & 0xFFFF;  v1 = v >> 16;
+  //    w0 = u0*v0;
+  //    t  = u1*v0 + (w0 >> 16);
+  //    w1 = t & 0xFFFF;
+  //    w2 = t >> 16;
+  //    w1 = u0*v1 + w1;
+  //    return u1*v1 + w2 + (w1 >> 16);
+  // }
 
-  Node *v_hi = phase->longcon(magic_const >> N/2);
-  Node *v_lo = phase->longcon(magic_const & 0XFFFFFFFF);
+  const int N = 64;
 
-  Node *hihi_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_hi));
-  Node *hilo_product = phase->transform(new (phase->C, 3) MulLNode(u_hi, v_lo));
-  Node *lohi_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_hi));
-  Node *lolo_product = phase->transform(new (phase->C, 3) MulLNode(u_lo, v_lo));
-
-  Node *t1 = phase->transform(new (phase->C, 3) URShiftLNode(lolo_product, phase->intcon(N / 2)));
-  Node *t2 = phase->transform(new (phase->C, 3) AddLNode(hilo_product, t1));
-
-  // Construct both t3 and t4 before transforming so t2 doesn't go dead
-  // prematurely.
-  Node *t3 = new (phase->C, 3) RShiftLNode(t2, phase->intcon(N / 2));
-  Node *t4 = new (phase->C, 3) AndLNode(t2, phase->longcon(0xFFFFFFFF));
-  t3 = phase->transform(t3);
-  t4 = phase->transform(t4);
-
-  Node *t5 = phase->transform(new (phase->C, 3) AddLNode(t4, lohi_product));
-  Node *t6 = phase->transform(new (phase->C, 3) RShiftLNode(t5, phase->intcon(N / 2)));
-  Node *t7 = phase->transform(new (phase->C, 3) AddLNode(t3, hihi_product));
+  // u0 = u & 0xFFFF;  u1 = u >> 16;
+  Node *u0 = phase->transform(new (phase->C, 3) AndLNode(dividend, phase->longcon(0xFFFFFFFF)));
+  Node *u1 = phase->transform(new (phase->C, 3) RShiftLNode(dividend, phase->intcon(N / 2)));
+
+  // v0 = v & 0xFFFF;  v1 = v >> 16;
+  Node *v0 = phase->longcon(magic_const & 0xFFFFFFFF);
+  Node *v1 = phase->longcon(magic_const >> N / 2);
+
+  // w0 = u0*v0;
+  Node *w0 = phase->transform(new (phase->C, 3) MulLNode(u0, v0));
+
+  // t  = u1*v0 + (w0 >> 16);
+  Node *u1v0 = phase->transform(new (phase->C, 3) MulLNode(u1, v0));
+  Node *temp = phase->transform(new (phase->C, 3) URShiftLNode(w0, phase->intcon(N / 2)));
+  Node *t    = phase->transform(new (phase->C, 3) AddLNode(u1v0, temp));
+
+  // w1 = t & 0xFFFF;
+  Node *w1 = new (phase->C, 3) AndLNode(t, phase->longcon(0xFFFFFFFF));
+
+  // w2 = t >> 16;
+  Node *w2 = new (phase->C, 3) RShiftLNode(t, phase->intcon(N / 2));
+
+  // 6732154: Construct both w1 and w2 before transforming, so t
+  // doesn't go dead prematurely.
+  w1 = phase->transform(w1);
+  w2 = phase->transform(w2);
+
+  // w1 = u0*v1 + w1;
+  Node *u0v1 = phase->transform(new (phase->C, 3) MulLNode(u0, v1));
+  w1         = phase->transform(new (phase->C, 3) AddLNode(u0v1, w1));
+
+  // return u1*v1 + w2 + (w1 >> 16);
+  Node *u1v1  = phase->transform(new (phase->C, 3) MulLNode(u1, v1));
+  Node *temp1 = phase->transform(new (phase->C, 3) AddLNode(u1v1, w2));
+  Node *temp2 = phase->transform(new (phase->C, 3) RShiftLNode(w1, phase->intcon(N / 2)));
 
-  return new (phase->C, 3) AddLNode(t7, t6);
+  return new (phase->C, 3) AddLNode(temp1, temp2);
 }