Too Much Theory, Part 2

As I write this I am flying back on SwissAir having just spent a week in beautifully freezing downtown Stockholm (highs are below freezing all this week) speaking at JFokus.  My talks went well; the audience was engaged and I had lots of  questions and comments afterwards.  The speakers were treated to a marvolous dinner (thanks Mattias!) which included singing by some of the JFokus crew.  I attended a few talks and wish I had time for more; JFokus definitely was a fun conference to attend.

When not at JFokus, Shelley & I managed to see The Vasa, a 1600’s era warship that sank on her maiden voyage, barely out of dock.  She lay forgotten for 300 years and was finally raised in the 1960’s and preserved & restored in the 1970’s and 1980’s.  All the iron bolts had rusted out (the iron cannons were salvaged a mere 50 yrs after her sinking) but all else remained.  Apparently the salinity in the harbor prevented the usual shipworms from eating everything wooden; the ship is 95% original.  She remains by far the largest salvaged wooden structure in the world.  She’s an amazing sight to behold and well worth the museum trip.  We also managed to visit the Swedish historical museum and ride the local trams some.  Only the horrible hacking cough Shelley picked up kept us from doing more exploration (nothing like being sick in a foreign land).

Assuming the rest of our trip back remains easy (first flight out was 15min delayed, giving us a whopping 30min to change from Terminal A to Terminal E in Zurich, including 2 passport checks – but we made it with only a little running), I’m going to dive into Part Two of my Deep Dive into Too Much Theory.

Last week, if you recall (I’ve wanted to use that phrase in a sentence for a long time now!  🙂 we were looking at the link between lattices and constant propragationConstant propagation is a means to discover constants in programs which in turn can enable more optimizations (e.g. replacing the obvious math producing the constant with just the constant directly).  Lattices are how we describe the kinds of “constants” we can discover.  As already discussed, we’re not just finding simple integer constants like “3”, but possibly things like the null pointer, or that a pointer is not_null (some unknown value… just never null), or ranges of integers (useful to remove some kinds of array range checks).  So when I say “Constant” what I really mean is “Some interesting values” – or properties about values – not necessarily limited to true constant values.

Before we dive into extending our lattice into even more exciting forms, I want to talk about properties of the lattice directly.  We need some properties or we’re doomed – but there are some properties that we want that are less obvious.

 

A Commutative, Associative, and Symmetric Lattice

  • A lattice is a collection of elements (e.g. top, bottom, 0, 1, 2, 3, …)
  • With an operator for mixing the elements called meet, which defines a partial order over the elements

We used meet when mixing different values for the same variable because of control-flow; (for you SSA wonks it is the operation given to Phi functions) meet produces another element in the lattice.  Thus lattices are closed under the meet operation.  Lattices also need:

  • A distinguished top-most and bottom-most values.  We call these values top and bottom respectively.  They represent the start and endpoints of Constant Propagation.
  • Our lattices need to be bounded height: meaning we cannot apply the meet operator an infinite number of times before we hit bottom.  The height of the lattice dictates our running time.  Especially for a JIT short running time is key; in practice lattices used in compilers tend to have a very small height.  For HotSpot it is something like 5 or 6.
  • We want our meet operator to be commutative, associative and symmetric.  The HotSpot C2 lattice has all these properties, and is defined using the above meet operator and a dual operator: reflection across a centerline.  The Wikipedia article uses meet and join to define a lattice, but HotSpot uses meet and dual because its easier to implement in C++.

The reason for these properties is a little subtle: if the meet operator lacks these then the lattice isn’t such a simple structure – and the order of application of meet will matter.  i.e., the order we visit our program and apply our constant propagation will matter.  Some visitation orders will give better answers than others.  Example: Suppose meet is not commutative and ‘b=3’ on entry to a loop and ‘b=TOP‘ on the backedge.  If (3 meet TOP) is (3) but (TOP meet 3) is (BOTTOM) then we lose a constant – and it matters how (& when) we flow information around.  By requiring a commutative, associative and symmetric lattice we get a “Church-Rosser” style property, and this in turns means we can use an un-ordered worklist style technique and get the same best answer no matter how things come off the worklist – which is exactly how HotSpot implements Constant Propagation.

  • We want our lattice to be reflective around some centerline (which we choose as the line of simple constants); this is implied from the symmetry on the meet operator above.

The prior integer lattice was commutative, associative & symmetric:

                        <em><strong>top</strong></em>
    ...   -2      -1     0     1     2     3  ...
                       <em><strong>bottom</strong></em>
But the lattice with ranges from the prior blog (in additional to having a ridiculous bound) was not symmetric.  Lets try the lattice of ranges again – but limited to 2 values and then we’ll add symmetry.  As before if we try to merge (meet) a lattice element of X with X+1 we’ll make a short range, but if we meet a range of 2 values with a third – instead of expanding the range we will fall to bottom.  Here’s our lattice:
                        <em><strong>top</strong></em>
    ...   -2      -1     0     1     2     3  ...
    ...  (-2,-1) (-1,0) (0,1) (1,2) (2,3) (3,4) ....
                       <em><strong>bottom</strong></em>

Is this lattice commutative?  i.e., is (a meet b) == (b meet a)?  Lets look at some examples.  What happens when we meet top and -1?  (top meet -1) == -1 == (-1 meet top), so this example works.  So does: (1 meet 2,3) == bottom == (2,3 meet 1).  So does: (0 meet 0,1) == 0,1 == (0,1 meet 0). I claim the “obvious interpretation” of this lattice is commutative.

Is this lattice associative?  i.e., is ((a meet b) meet c) == (a meet (b meet c))?  Again, running a few examples can convince us the lattice is indeed associative.

Is this lattice symmetric?  Well, in a word: No.  The opposite of top is bottom.  Things on the centerline are symmetric with themselves (e.g. in the lattice world, 3 is the opposite of 3).  How about a range like (1,2)?  It represents “1 or 2 but we don’t know which, and no other number”.  What is opposite the centerline from the range (1,2)?  Well, it’s a little weird: it is both the constant 1 AND the constant 2 at the same time.  NOT the more obvious “1 OR 2 and we don’t know which one it is”.  Whoa… lets digest that for a second.  Like top, it is an unnatural state of affairs (except in mathematics) whose concept is a little slippery.  Like top, we want to embrace a concept of allowing as much flexibility in number choices as we can… while still being a *little bit more* constrained than top.  Remember: top is ALL constants ALL the time; we’ll settle here for just 2 constants, but BOTH AT ONCE.

Having discussed the concept to death, lets settle on some nomenclature and then run some examples.  Lets write the opposite of the range (1,2) as the inverted range (2,1) (the high and low values are inverted).  Another syntax might be pre-pending a ‘~’ as in: ~(1,2).

                         <em><strong>top</strong></em>
     ..(-1,-2)  (0,-1) (1,0) (2,1) (3,2) (4,3) ....
     ...   -2      -1     0     1     2     3  ...
     ...  (-2,-1) (-1,0) (0,1) (1,2) (2,3) (3,4) ....
                        <em><strong>bottom</strong></em>
Notice how our lattice looks symmetric across the centerline now?  Here’s the same example from the last blog using top:
  b = 1;       // b is the constant '1' here.
  while( P ) { // b is <em><strong>top</strong></em> around the backedge -
               //   which matches the constant '1'
    S1;        // b is a '1' here
    b = 2-b;   // b is STILL a '1' here!
  }            // we bring a '1' value around for 'b' here
Again using the inverted range (2,1):
  b = 1;       // b is the constant '1' here.
  while( P ) { // b is (2,1) around the backedge -
               //   which matches the constant '1'
    S1;        // b is a '1' here
    b = 2-b;   // b is STILL a '1' here!
  }            // we bring a '1' value around for 'b' here
Ok, why bother with inverted ranges when top covers everything?  Because we use them whenever we can assert a property is true, such as just after the property is tested with an IF:
  b = ...; // b is BOTTOM
  if( b &gt;= 1 &amp;&amp; b &lt;= 2 ) {
    // here we can <strong>assert</strong> that b is the <strong>join</strong>
    //      of whatever it was before, and (1,2)
    b;     // b is range (1,2)
  }
New jargon word: join, an operation which produces the intersection of properties (both the state of ‘b’ before the IF must be true, but also inside the if() the test must be true – so both properties are true at once).  Contrast this to the meet operator which yields the union of unknown properties.  The join of A and B can also be defined as: ~(~A meet ~B), and indeed this is exactly how HotSpot’s C2 compiler computes it from src/share/vm/opto/type.cpp:
<span style="color: #000080;">// JOIN operation; higher in lattice.</span>
<span style="color: #000080;">// Done by finding the dual of the</span>
<span style="color: #000080;">// meet of the dual of the 2 inputs.</span>
<span style="color: #000080;">const Type *join( const Type *t ) const {</span>
<span style="color: #000080;"> return dual()-&gt;meet(t-&gt;dual())-&gt;dual(); }</span>
Back to our example of using join in a sentence:
  b = ...; // b is <em><strong>bottom</strong></em>
  if( b &gt;= 1 &amp;&amp; b &lt;= 2 ) {     // b is the join of <em><strong>bottom</strong></em> and (1,2)
    // b is ~(~<em><strong>bottom</strong></em> <strong>meet</strong> ~(1,2))
    // b is ~(<em><strong>top</strong> </em><strong>meet</strong> (2,1))
    // b is ~(2,1)
    // b is (1,2)
  }
The symmetry property implies that:
if  M == (A meet B), then:~A == ~A meet ~M     AND~B == ~B meet ~M

Our range lattice is now symmetric, so lets test that on some A,B pairs.
Example 1:  top & (1,2)
M == (top meet(1,2)) == (1,2)~top =? ~top meet ~(1,2) bottom =? bottom meet (2,1)

bottom == bottom

~(1,2) =? ~(1,2) meet ~(1,2)

(2,1) =? (2,1) meet (2,1)

(2,1) == (2,1)

Example 2: 1 & (0,1)
M == (1 meet(0,1)) == (0,1)~1 =? ~1 meet ~(0,1) 1 =? 1 meet (1,0)

1 == 1

~(0,1) =? ~(0,1) meet ~(0,1)

(1,0) =? (1,0) meet (1,0)

(1,0) == (1,0)

Summary:

We have a lattice, with a distinguished top and bottom elements.  It has a meet operator which defines the lattice structure; meet is commutative, and associative.  The lattice is also symmetric about the centerline and we use the dual operator “~” to refer to elements across the centerline.  Constants exist on the centerline.  The elements above the centerline are used after IF statements to assert properties, or for unknown loop backedge values – and represent ‘impossible’ situations like some expression producing multiple constants being true at the same time.

We (almost) have enough knowledge now to be dangerous!  Lets build a more realistic Java lattice now.

A Class Hierarchy

Our pointers have more structure than just null or not_null; they have types!  We have a Class Hierarchy.  Can we do something with it?  Somewhat similar to adding ranges to plain integer constants, the base case is simple but we need to be careful as we get clever.  The payoff is also very high: if we can deduce a constant class for a pointer, and the pointer is used to make a virtual call then we can simplify the virtual call to a static call … and maybe even inline.  That’s a big payoff, so it’s worth some effort here.

Lets go with a simple starter lattice; similar to the integers we’ll look JUST for things are known to be a specific constant class… and NOT any subclass.  Weird, I know, but bear with me:

            <em><strong>top</strong></em> - <strong>any</strong> single class the compiler desires
String   Object(no subclass!)   XMLNode   Fred
           <em><strong>bottom</strong></em> - multiple choices,
           e.g. String or XMLNode or a subclass

A common source of known-class-thingies is the ‘this‘ pointer in calls (and usually any other arguments), so my examples start that way:

boolean String.weird_equal( Object that ) {
  // 'this' has the constant Class String, no subclasses!
  // 'that' has the Class <em><strong>bottom</strong></em>
  //        since it might be a subclass of Object
  int hash1 = this.hashCode();
  int hash2 = that.hashCode();
  if( hash1 != hash2 ) return false;
  if( !(that instanceOf String) ) return false;
  return equals((String)that);
}

What does CP tell us here?  Lets roll it forward one line at a time:

        int hash1 = this.hashCode();  // '<strong>this</strong>' has Class String
                                      //  and is <strong>not_null</strong>

this has the class String, so this is really a call to String.hashCode() and we can (now) happily inline it.

        if( that == null ) throw NPE; // hidden built-in NPE check...
        int hash2 = that.hashCode();  // 'that' has Class <strong><em>bottom</em></strong>
                                      // and is <strong>not_null </strong>

No constant Class here, so this becomes a not-inlinable virtual-call, i.e. expensive.

        if( hash1 != hash2 ) return false;
        if( !(that instanceOf String) ) return false;

Hey!  After the ‘if’ test we know that ‘that‘ has Class String!  We already know that ‘that‘ is not_null – this gives us 2 orthogonal lattices we can track: pointers might be null or not, and they might be a constant Class or not.

        return equals((String)that); // the cast can be optimized away!

And since ‘that‘ is known to be the class String, the JIT can remove the cast.

A quick summary of what we have so far:
  pointers can be <strong>null</strong> or <strong>not_null</strong> (or <em><strong>top</strong></em> or <em><strong>bottom</strong></em>)
    and this info is used to remove <em>null checks</em>
  pointers can be constant Classes (or <em><strong>top</strong></em> or <em><strong>bottom</strong></em>)
    and this info is used to <em>de-virtualize</em> calls
    and remove extra type checks
  We know both kinds of lattice info about pointers, at the same time.

Similar to integer constants, our pointer Constant Propagation can be optimistic or pessimistic.  Here’s some code where being optimistic might help:

  <strong>final class</strong> LinkedListThing {
    LinkedListThing _next; // instance field
    int hashCode() {
      int hash = 0;
      Object x = <strong>this</strong>;
      while( PRED ) {
        hash += x.hashCode();
        if( x <strong>instanceof</strong> LinkedListThing )
           x = ((LinkedListThing)x)._next;
        else
           x = "fail";
      }
      return hash;
    }

Deep breathe – okay, this example is getting large for a blog.  Let’s break it down.  What happens if we are pessimistic?

  int hashCode() {    // this is Class LinkedListThing
    int hash = 0;
    Object x = <strong>this</strong>;  // x also is Class LinkedListThing
    while( PRED ) {  
      // x is <em><strong>bottom</strong></em> around the backedge

      hash += x.hashCode(); // unknown v-call

      if( x <strong>instanceof</strong> LinkedListThing )
      // <em><strong>bottom</strong></em> so needs the full type-check

           x = ((LinkedListThing)x)._next;
           // x is Class LinkedListThing

      else x = "fail";
      // Else x is Class String if the full type-check fails

    } // Here x is either String or LLT... so <em><strong>bottom</strong></em>
    return hash;
  }

In one pass of CP we “discover” that ‘x’ is Class bottom – not much help here!  Let’s go again with the optimistic approach:

  int hashCode() {    // this is Class LinkedListThing
    int hash = 0;
    Object x = <strong>this</strong>;  // x also is Class LinkedListThing
    while( PRED ) {   // x is <em><strong>top</strong></em> around the backedge;
                      //   assume it is LLT
      hash += x.hashCode(); // known call to LLT.hashCode()
      if( x <strong>instanceof</strong> LinkedListThing )
           // type-check not needed!

           x = ((LinkedListThing)x)._next;
           // x is Class LinkedListThing

      else ... // Not reachable; x is the correct Class already
    } // Here x is LinkedListThing!
    return hash;
  }

Hey presto!  We figure out what the programmer shoulda wrote already: that ‘x’ is of type LinkedListThing, and the instanceof test is useless.  Of course, we might have gotten here from some prior rounds of inlining, where ‘x’ could only be typed as an Object so lets not blame our strawman programmer (who’s really just me trying to make some not-too-contrived examples).

 

All right, time to wrap up this blog.  Next time we’ll add subclasses (and maybe arrays and/or interfaces) and see what happens.  But for now this blog is big enough.  Besides, me & my daughter hiked up to Upper Yosemite Falls and then hiked down at night, strictly by starlight… but that’s a exciting story for the next blog.

 

Cliff

Too Much Theory

Today I am in beautiful downtown Stockholm, having left sunny San Jose (highs hitting 70 in mid-Feb) for a balmy 28F (yes that’s the HIGH) for JFokus.  If I don’t freeze to death (or die from the cold I’m suffering or lose my voice) I might actually give some talks.  Wish me luck.

 

To make up for last month’s non-techy blog, this one will be over-the-top in techy theory AND be a multi-part’er.  I’ve been wrestling with some tricky bugs and I’d thought I’d share the pain.  For fun, I’m going to toss in evidence that All Your Existing Optimizing Compilers Are Broken, and least they are if they attempt a data-flow style Constant Propagation on a language with a class hierarchy and a distinguished NULL pointer (e.g. Java, C++).  This includes the HotSpot server compiler (although I doubt anyone’s hit the problem in practice), and many many compilers I suspect. However, this blog is going to be at least a 2-parter, so you’ll have to wait until you’ve waded through 2 techy blogs before we get to the juicy (theoretical) bug.  To start down this discussion we first need to talk about Constant Propagation and the notion of a “lattice”.

 

CONSTANT PROPAGATION

First up: Constant Propagation.  Basic stuff only, and we’re skipping over the practical concerns of how to do this fast & accurate (which is what is in HotSpot), and what kind of realistic performance you get from the code if you do (or do not) do it (trust me, it’s worth doing if you’re looking for the right kind of “constants”).  Instead, lets just look at what CP is trying to accomplish, and we’re going to stick with ‘int’ types for awhile to get the basic ideas across.

  a = 1;
  b = a+2;
  System.out.println(b);

Rather obviously we can propagate the constant 1 for a into the expression for b:

  b = 1+2;

and fold the constant:

  b = 3;

and propagate this constant forward:

  System.out.println(3);

Easy, right?  We now don’t need a or b so hopefully this program runs faster.  Lets try a (slightly) harder example:

  if( P ) {
    b = 3;
  } else {
    a = 1;
    b = a+2;
  }
  System.out.println(b);

Here P is some unknown predicate; we assume it’s beyond the ability of the compiler to deduce in advance (at compile-time) what values P will take on. Let us suppose P is something like read() where you can type a 0 or 1 at a prompt.  Back to CP: since we don’t know what P might be, we have to assume it could be either true or false – and both sides of the if() expression might be taken.  So we need to evaluate both; this whole style of evaluation is sometimes called Partial Evaluation.  First arm of the if() is easy:

  if( P ) {
    b = 3;  // the obvious constant 3
  } else ...

Now we can do the other arm – and we NEED to do it before the following println or else we miss a possible constant:

  } else {
    a = 1;
    b = 3;
  }

And at this point we can see b is 3 no matter what value P takes on (and for those “in the know” please notice I’m not going to explain SSA theory and Phi functions in this blog; it’s got too much in it already):

  if( P ) { b = 3; } else { ... b = 3; }
  System.out.println(3);

What happens if b takes on different values on both arms of the if()?  Well that depends on how clever a ‘constant’ we are willing to work with.

  if( P ) {
    b = 3;
  } else {
    b = 4;
  }
  X;

What can we say at statement Xb is not known to be either 3 or 4, but we can say that b is definitely positive (and that it is either 3 or 4).  This is useful if X is e.g. part of an array range check like so:  if( b >= 0 ) …  because now we can fold the control flow.  OK, lets try something more tricky yet: a loop.  First a loop for which “we got nuthin”: no constants.

  a = 1;
  b = 1;
  while( P ) {
    tmp = a+b;
    a = b;
    b = tmp;
  }

Here we’re computing Fibonacci while predicate P holds true, at least until Java integers start overflowing.  Pretty quickly a & b become big unknown integers (and then overflow).  Here’s a loop where we CAN find an obvious constant:

  b = 3;
  while( P ) {
   ...
   b = 3;
   ...
 }

Even though b is set in the loop, it’s set to the same constant we get on loop entry so b must be 3.  Here’s a loop where b is not a constant (but IS known positive):

  b = 1;
  while( P ) {
    S1;        // b is NOT the constant 1 here!!!
    b = 2;
    S2;
  }

Knowing b is positive might be useful if b is used as an array index in the loop.  OK, now lets try our first really tricky case:

  b = 1;
  while( P ) {
    S1;        // b IS constant 1 here!!!
    b = 2-b;
    S2;
  }
  System.out.println(b);

Is b a constant on loop exit?  And if so, what value?  (yes & 1)

Why is it that in this example I can say b is a constant 1 on statement S1 and yet it is not a constant in the prior example?  BOTH code snippets start out with:

  b = 1;
  while( P ) {
    S1;        // b is ????

The cases are different obviously because the rest of the loop matters!  But lets be explicit about it: at the loop head while( P )  – we can see that b is 1 on entry… but we just don’t know what b will be around the loop backedge.  It might be the desired constant 1 – which meshes with the entry value for b, or it might be some unrelated constant, or not a constant at all.  We have to inspect the whole loop to discover if b is a constant.

Furthermore, how we inspect the loop will let us find more (or less) constants – for the same loop!  Suppose we inspect code instructions one at a time, in order – “propagating” the constants like I did with a and b above.  What do we do with loops?  We can’t do the loop instructions “in order” because we haven’t done them yet when we want to know what constant comes around the loop backedge.  The simple (pessimistic) approach is to say “we don’t know” at the loop entry about what b will be around the backedge.  In this case we say “b is not a constant” as we enter the loop.  Lets call “b is not a constant” by saying b has value bottom (which means “we don’t know what values b might take on“).

  b = 1;       // b is the constant '1' here!
  while( P ) { // unknown backedge value, so b is <em><strong>bottom</strong></em> here!
    S1;        // b is <strong><em>bottom</em></strong>
    b = 2-b;   // 2 minus <em><strong>bottom</strong></em> is also <em><strong>bottom</strong></em>, so <strong>b</strong> is <em><strong>bottom</strong></em> here also
  }            // we bring a <em><strong>bottom</strong></em> value around for <strong>b</strong> here

Our end result of bottom for b matches what we assumed it would be around the loop backedge and pretty quickly decide that we don’t know anything about b.

Lets try this loop again with an optimistic approach.  When we hit the loop and we don’t know (yet) what b will be, we optimistically assume b will be exactly what we want it to be – and then we’ll confirm that.  We use the special value top to say “b is any constant I want it to be – b is ALL CONSTANTS AT THE SAME TIME” – an obviously unrealistic situation that we’ll have to rectify later:

  b = 1;       // b is the constant '1' here.
  while( P ) { // b is <em><strong>top</strong></em> around the backedge - which matches the constant '1'
    S1;        // b is a '1' here
    b = 2-1;   // b is STILL a '1' here!
  }            // we bring a '1' value around for b here

HEY – we found a constant!  (and we brought around the backedge b‘s value as both top when we started, but as a 1 as we finished).  This is the trick about optimistic-vs-pessimistic approaches: optimistic approaches can find strictly more constants than pessimistic approaches (if any are to be found) BUT the analysis is in this unrealistic state for awhile – we have to confirm all our optimistic assumptions… and sometimes they don’t work out – and then we’ll have to re-compute over the code where we assumed wrongly.  Pessimistic approaches always have a conservative but correct solution:

  b = 1;       // b is the constant '1' here.
  while( P ) { // b is <em><strong>top</strong></em> around the backedge - which matches the const '1'
    S1;        // b is a '1' here
    b = 2;     // b is now a '2'
  }            // we bring a '2' value around for b here

Oops – 2 around the backedge meets 1 on entry – b is NOT a constant.  So we need to continue the analysis with our new more realistic result:

  ...
  while( P ) { // b is 2 around the backedge and 1 on entry, so we set <strong></strong>b to <em><strong>bottom</strong></em>
    S1;        // b is a <em><strong>bottom</strong></em> here
    b = 2;     // b is now a '2'
  }            // we bring a '2' value around for b here

This 2nd solution is the correct one.

In general, when running an optimistic solution you start with all values at top until computations force them “down” towards bottom (or constants we hope)… but every time a value “falls down” you have to recompute all dependent calculations to see if they also “fall”.  The number of times you might need to recompute depends on the number of times you can “fall”.  There are efficient techniques for doing this analysis in time linear in the size of the program… times the number of times you might “fall”.

 

LATTICES

If we look at our choices of values for b graphically we get this:

         <em><strong>top</strong></em>
... -2 -1 0 1 2 3 4 .....
       <em><strong>bottom</strong></em>

This structure is called a lattice.  In this lattice we can see the distinguished top and bottom values along with all possible constants in the middle.  We’ll start our optimistic Constant Propagation by setting all values to top.  Statements like b=3 will cause b to “fall” from top to the constant 3 in the middle row.  If we have to merge two different constants for b then we fall again to bottom.  Mixing bottom with anything else will always “fall” to bottom.  We can only fall twice, so a good algorithm for CP will run in 2*size_of(program).

Lets look at another choice of lattice that sounds good but fails in practice.  Suppose we’d like a lattice that allows b to take on any range of values, such as 1-10 or 7-23 or -99 to +99, or MININT to MAXINT – suppose we’re trying to get clever about finding better array index values (perhaps to remove more range checks).  We can merge different values in the lattice by widening the ranges.  Here’s a simple example:

  if( P1 ) { b = P2 ? 0 : 4; } // b has range 0-4
  else     { b = P3 ? 1 : 5; } // b has range 1-5
  // here b has range 0-5 - the widened version of 0-4 and 1-5

Looks good, right?  Here’s the poster-child case:

  for( int i=0; i&lt;A.length; i++ ) {
    A[i]...
  }

Lets break that down a little more, removing syntactic sugar and exposing the tender bare insides of this little problem:

  i = 0;                   // i is the constant '0', duh!
  while( i &lt; A.length ) {  // Assume 'i' is <em><strong>top</strong></em> on the backedge!  Matches our 0 on entry
    ...
    if( i&lt;A.length ) ...   //... happy happy, i is 0
    i = i + 1;             // i is now: 0+1 == 1
 } // bring '1' around the backedge.

Ok, on the 1st CP pass we assumed i was top on the backedge on entry and found a 1 instead – so let us “fall” i to the range 0-1 (instead of bottom) and try again:

  i = 0;                   // i is the constant '0', duh!
  while( i &lt; A.length ) {  // Assume 'i' is 0 or 1 on the backedge!
   ...
   if( i&lt;A.length ) ...    //... still happy, i is 0-1
   i = i + 1;              // i is now: "0-1"+1 which gives us the range 1-2
 } // bring '1-2' around the backedge.

Ok, 2nd CP pass and we assumed i was 0-1 on the backedge on entry and found a 1-2 instead – so lets “fall” to the range 0-2 and try again:

  i = 0;                    // i is the constant '0', duh!
  while( i &lt; A.length ) {   // Assume 'i' is the range 0-2 on the backedge!
    ...
    if( i&lt;A.length ) ...    //... still happy?: i is 0-2
    i = i + 1;              // i is now 1-3
 } // bring '1-3' around the backedge.

Hey… there’s a pattern here!  And we’re never gonna converge… what’s going on?  What IS the lattice for ranges?

                   TOP
 ...  -1    0    1    2    3  ...   // ranges with 1 value (i.e. constants)
 ... -1-0  0-1  1-2  2-3  3-4 ...   // ranges with 2 values
 ... -1-1  0-2  1-3  2-4  3-5 ...   // ranges with 3 values
 ....
 ...    -1-99  0-100  1-101   ...   // ranges with 100 values
 ....                               // ...many lattice layers later...
                                    // ranges with 1000 values, etc...
 ....                               // ...many MANY lattice layers later...
        MININT - MAXINT (<em><strong>bottom</strong></em>)    // ranges with 4 billion values

Blah!  That’s a heckava huge lattice!  You might be “falling” for a long long time – 4 billion times roughly. Worst-case compile-time scenario: 4 billion times sizeof(program).  OK – so THIS lattice doesn’t work (but actually there’s another one nearby that does which HotSpot DOES do but I’ll leave that one for serious compiler junkies to read from the OpenJDK code ).

 

Brow sweating, but still with me?  Congratulations!  I first saw this stuff as a PhD grad student.  It would be time to move on to the next more interesting lattice – but I’m out of space.   Next blog we will attempt to cover the fearsome ‘null‘ pointer!  Sounds easy?  Piece-o-cake?  Trust me, it only ramps up from here!    🙂

Till next time,

Cliff