CIS 570 Lecture 17 Field Analysis 2Field Analysis Last time− Exploit encapsulation to improve memory system performance This time− Exploit encapsulation to simplify analysis− Two uses of field analysis− Escape analysis− Object inlining− Lesson: You don’t always have to solve the general problem!CIS 570 Lecture 17 Field Analysis 3Motivation “Problems” with Modern High Level Languages− Bounds checks for type safety− Virtual method calls to support object-oriented semantics− Heap allocation to provide uniform view of objects Solutions− Prove facts about array bounds and about types to tighten assumptions e.g. To devirtualize a call, prove that the call has exactly one target class− Such analysis typically requires interprocedural analysis− Costly− Sometimes impossible: dynamic class loading, unavailable source codeCIS 570 Lecture 17 Field Analysis 4Field Analysis A Cheap Form of Interprocedural Analysis− Exploits encapsulation to limit the scope of analysis e.g., If an array is indexed by a private variable that is only set by onemethod, then only that one method needs to be analyzed to determine theindex’s value− Deduce properties about fields based on the properties of all accesses tothat field Benefits− Efficient− Does not require access to the entire program− Works well with dynamic class loading− Can be applied to any language that supports encapsulation− Java, C++, Modula-3, etc.CIS 570 Lecture 17 Field Analysis 5Field Analysis for JavaToday: A specific solution [Ghemawat, Randall, & Scales, PLDI’00]− Implemented in the context of Compaq’s Swift optimizing Java compiler− Swift translates bytecode to native Alpha code− Swift performs a number of aggressive optimizations− This implementation focuses on reference types− Ignores scalar fieldsCIS 570 Lecture 17 Field Analysis 6Field Modifiers Dictate Scope of Analysis Java field modifiersClass Field modifier Where can the field be assigned?publicpublicpublicnon-publicnon-publicprivatepackageprotectedprivatenon-privatecontaining classcontaining packagecontaining package and subclassescontaining classcontaining packagepublicpublicentire programCIS 570 Lecture 17 Field Analysis 7Examplepublic class Plane { private Point[] points; public Plane() { points = new Point[3]; } public int GetAverageColor() { return (points[0].GetColor() + points[1].GetColor() + points[2].GetColor())/3; }} Since points is private− Its properties can be determined by analyzing only the Plane class− We can determine the exact type of points− So we can inline the GetColor() methodCIS 570 Lecture 17 Field Analysis 8Idea: Create an Enhanced Type System Introduce special types− A value is an object of exactly class T, and not a subclass of T− A value is an array of some constant size− The value is known to be non-null− . . . Type analysis begins by determining types of− Method arguments− Loads of fields of objects− Loads of global variables− Non-null exact types assigned to newly allocated objects Use type propagation to determine types of other nodes in the SSA graphCIS 570 Lecture 17 Field Analysis 9Basic Approach 1. Initialize− Build SSA graph and gather type information SSA provides flow-sensitivity 2. Incrementally update properties− Consider all loads and stores and update properties associated with eachfield Load of a field: Analyze all uses of the loadx = y.f;. . .x.z(); Store of a field: Analyze the value stored into the fieldand all other uses of the valuex = new T;. . .y.f = x;CIS 570 Lecture 17 Field Analysis 10Example of Useful Propertiesexact_type(field)− The field is always assigned a value of the specified typealways_init(field)− The field is always initializedonly_init(field)− The field is only modified by constructorsCIS 570 Lecture 17 Field Analysis 11only_init(points)is trueExample Analysispublic class Plane { private Point[] points; public Plane() { points = new Point[3]; } public void SetPoint(Point p, int i) { points[i] = p; } public Point GetPoint(int i) { return points[i]; }} points is private, so itsproperties can bedetermined by onlyscanning the Plane classexact_types(points)indicates a non-null arraywith base type Point anda constant size of 3always_init(points)is trueCIS 570 Lecture 17 Field Analysis 12Example Optimizationsexact_type(field)− If the type is precisely known, we can convert a virtual method call to astatic method call− Precise type information can be used to statically evaluate type-inclusiontests such as instanceof or array store checks− If the type is an array of constant size, some bounds checks can beeliminated and expressions that use the array length (e.g., a.length())can be statically evaluatedCIS 570 Lecture 17 Field Analysis 13Example Optimizations (cont)public class Plane { private Point[] points; public Plane() { points = new Point[3]; } public void SetPoint(Point p, int i) { points[i] = p; } public Point GetPoint(int i) { return points[i]; }} Can eliminate null checkson pointsCan use the constant 3 inbounds checks on pointsCan eliminate the arraystore check for pointsWhat optimizations arepossible in this example?CIS 570 Lecture 17 Field Analysis 14Example Optimizations (cont)These properties can enhance other optimizations x = y.f; x.foo(); z = y.f; x = y.f; x.foo(); z = x;CSE is possible if x.foo does not modify y.f.We know that y.f is only modified by a constructor ifonly_init(f) = trueCSE?CIS 570 Lecture 17 Field Analysis 15Escape Analysis Idea− Does an object escape the method in which it is allocated?− E.g., return, assign to global/heap, pass to another method f() { Point p = new Point(); Stack s = new Stack(100); s.push(p); /* p escapes */ . . . return p; /* p escapes */ }CIS 570 Lecture 17 Field Analysis 16Escape Analysis Uses− Objects that do not escape can be allocated on the stack f() { Point p = new Point(); return; /* Allocate p on the stack */ }− Why is this desirable?− Less overhead than heap allocation− Less work for garbage collector− Usually has better cache behavior− Synchronization elimination− Escape from a thread: Can another thread access the object?− If an object cannot escape a thread, it need not be synchronizedCIS 570 Lecture 17 Field Analysis 17Escape Analysis (cont) Heavyweight escape analysis− Many proposed variations [Aldrich’99, Blanchet’99,