long_by_long_mulhi() rewritten and commented

[Chuck Rasbold]

Christian -

I think your suggested change with attribution to Hacker's Delight is
a good idea. C2 already references that source elsewhere.

I would change the constants in the comments to match those used in
the building the ideal graph. Then note in a single place that you
adjusted Warren's algorithm to 64 bits.

 -- Chuck

On Mon, Feb 2, 2009 at 3:01 AM, Christian Thalinger
<Christian.Thalinger at sun.com> wrote:
> 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);
>  }
>
>
>
>
>