Escape Analysis for JavaPoints-to vs. Escape AnalysisReasons for Escape AnalysisEscape Analysis Definitions and PropositionsEscape LatticeConnection GraphSlide 7Intraprocedural AnalysisIntra (cont’d)Interprocedural AnalysisMethod EntryMethod ExitPowerPoint PresentationImmediately Before a MethodImmediately After a MethodUpdating Caller NodesSlide 17ResultsResults (cont’d)Slide 20Slide 21Slide 22Slide 23Results FinalWe’re done!Slide 26Slide 27Escape Analysis for JavaEscape Analysis for JavaWill von Rosenberg Will von Rosenberg Noah WallaceNoah WallacePoints-to vs. Escape AnalysisPoints-to vs. Escape AnalysisPoints-toPoints-to–Memory disambiguationMemory disambiguation–To determine if two pointers can be resolved to point at the same To determine if two pointers can be resolved to point at the same locationlocation–Points-to graph should lead to the same location for correctness, Points-to graph should lead to the same location for correctness, i.e. they may resolve to the same memory locationi.e. they may resolve to the same memory locationEscape AnalysisEscape Analysis–Identify objects that might escape a (dynamic) scope such as a Identify objects that might escape a (dynamic) scope such as a method invocation or a thread object.method invocation or a thread object.–Connection graph may lead to different nodes, but could still be Connection graph may lead to different nodes, but could still be correctcorrect–Can safely ignore the calling context for escape analysis.Can safely ignore the calling context for escape analysis.Reasons for Escape AnalysisReasons for Escape AnalysisIf an object does not escape the method it was If an object does not escape the method it was created in, then that object can be allocated onto created in, then that object can be allocated onto the stack instead of the heap, since heap the stack instead of the heap, since heap allocation is (supposedly) time expensive.allocation is (supposedly) time expensive.If an object does not escape the thread it was If an object does not escape the thread it was created in, then that object does not need to be created in, then that object does not need to be synchronized. That means that lock() and unlock() synchronized. That means that lock() and unlock() do not need to be used on it. These do not need to be used on it. These synchronization methods are inherently time synchronization methods are inherently time expensive.expensive.Escape Analysis Definitions and Escape Analysis Definitions and PropositionsPropositionsAn object is said to escape a Method if the lifetime of the An object is said to escape a Method if the lifetime of the object is larger than the lifetime of the Method. That is to object is larger than the lifetime of the Method. That is to say that the scope of the object is greater than the scope of say that the scope of the object is greater than the scope of the Method it was created in. the Method it was created in. An object is said to escape a Thread if another thread, not An object is said to escape a Thread if another thread, not equal to the first, uses (locks) that object.equal to the first, uses (locks) that object.If an object does not escape the method, !Escapes(O, M), If an object does not escape the method, !Escapes(O, M), and that method was invoked in thread T, then it can be and that method was invoked in thread T, then it can be said that the object does not escape the thread, !said that the object does not escape the thread, !Escapes(O, T).Escapes(O, T).(Proposition 2.3)(Proposition 2.3)Escape LatticeEscape LatticeGlobalEscapeGlobalEscape–Escapes all Methods and ThreadsEscapes all Methods and ThreadsArgEscapeArgEscape–Escapes the Methods in which it was created, Escapes the Methods in which it was created, but not the thread invocationbut not the thread invocationNoEscapeNoEscape–Does not escape either the Method and the Does not escape either the Method and the ThreadThreadConnection GraphConnection GraphCapture the connectivity relationship among Capture the connectivity relationship among objectsobjectsConnection GraphConnection GraphFid()Fid()–A unique number that identifies a field within a class, A unique number that identifies a field within a class, this field identifier or offset, is unique within the class, this field identifier or offset, is unique within the class, and can be compared to instances of the same class.and can be compared to instances of the same class.The notation refers to a reference node The notation refers to a reference node --------------- that contains an arbitrary number of --------------- that contains an arbitrary number of deferred edges, that lead to a points-to edge.deferred edges, that lead to a points-to edge.The PointsTo() function refers to all nodes, such The PointsTo() function refers to all nodes, such as the above, where m, through a sequence of as the above, where m, through a sequence of deferred edges, points-to n. The function returns deferred edges, points-to n. The function returns the set of all n’s that m points-to.the set of all n’s that m points-to.Intraprocedural AnalysisIntraprocedural AnalysisFlow-sensitive and Flow-insensitiveFlow-sensitive and Flow-insensitiveSimplify presentation by Simplify presentation by –splitting a multiple level reference expression splitting a multiple level reference expression into a two level reference. ()into a two level reference. ()–Bypass() functionBypass() functionEliminates all edges to a node, either incoming, or Eliminates all edges to a node, either incoming, or outgoing.outgoing.Redirects them to a more precise location for the Redirects them to a more precise location for the purpose of flow-sensitive analysispurpose of flow-sensitive analysisIntra (cont’d)Intra (cont’d)P=new r()P=new r()–FS (Flow Sensitive) new object node is created and ByPass(p). FS (Flow Sensitive) new object node is created and ByPass(p). –FI new object node created with a points to edge from p to new node. FI new object node created with a points to edge from p to new node. ByPass(p) is not called.ByPass(p) is not called.P=qP=q–FS apply ByPass(p) and add the deferred edge to q.FS apply ByPass(p) and add the deferred edge to q.–FI ignore ByPass(p) and add the deferred edge to q.FI ignore ByPass(p) and add the deferred edge to q.P.f=q P.f=q –FS and FI are treated