147:8 Tian Tan,Yue Li,Xiaoxing Ma,Chang Xu,and Yannis Smaragdakis 4 ,3ob1 300 2obj: 2obl:1type Relay-01 2type Precision of 2obf Precision of Pass 1(P1) 2type Pass 2(P2) 2 CI ci CI Pass 1 Pass 2 Pass 3 3obj 2obj 1type Relay-02 Precision of Precision of Pass 1(P1) 2type Pass 2(P2) CI CI Pass 1 Pass 2 Pass 3 Fig.3.Examples for illustrating the idea of Relay with the same input approaches setting as in Figure 2.Relay has two options,Relay-o1 and Relay-02 and the former is more precise but less scalable than the latter.In each pass of both options,only the methods enclosed in the solid circles,say M.are analyzed context-sensitively (the dotted lines in Relay-o1 are to facilitate understanding).Both options adopt the same precision filtering mechanism,and their difference only lies in what context-sensitivity variants are assigned to M. with a more precise context.Therefore,the probability to select scalability-threat methods is low, making Relay more likely to scale compared to Unity. After running the first pass,its precision,which is reflected in the points-to set for every variable, will be transmitted to the next pass(pass 2).Then,in pass 2,we can use the precision of pass 1, i.e.,the points-to information,to help soundly filtering the points-to sets for all variables when performing the analysis in pass 2.For example,assume a variable v points to three objects under CI with its points-to set,say pt(v),being {o1,02,03).After pass 1,pt(v)becomes {o1,03)where o2 is identified as a spurious object by analyzing M1 context-sensitively.However,in pass 2,purely analyzing M2 under the contexts shown in Figure 3 cannot recognize that v should not point to o2. However,this imprecision does not matter,as the pt(v)transmitted from pass 1 can be used to filter pt(v)during the analysis in pass 2,i.e.,preventing o2 from being propagated to pt(v).Such filtering is safe as the pointer analysis in pass 1 is sound,so no true objects will be filtered away in Relay(this will be formally proven in Section 4). Finally,although uncommon,what if Relay-o1 is not scalable?After all,given a program,we hope to confidently rely on Unity-Relay for yielding precise pointer analysis results all the time. Under this context,we design Relay-02 as the last line of defense of Unity-Relay.Relay-o2 employs the same principle as Relay-o1 with the exception that context-sensitivity variants (selected by input approach Si)are not reassigned any more in each pass,say Passi(see Relay-o2 in Figure 3).In other words,Pass;and the analysis guided by Si,say Ai,adopt the same selective context sensitivity.The only difference between running the selective approaches independently is that precision accumulates,using the same filtering mechanism as in Relay-01.Thus,in Passi,the points-to set for each variable is never larger than the one in Ai,resulting in less data propagation and faster analysis convergence.The only extra cost introduced in Relay-02 is the process of filtering,which is small compared to the overhead of a context-sensitive pointer analysis,and easily offset by the aforementioned efficiency benefit.Thus,we can expect Relay-02 to scale as long Proc.ACM Program.Lang.,Vol.5.No.OOPSLA,Article 147.Publication date:October 2021.147:8 Tian Tan, Yue Li, Xiaoxing Ma, Chang Xu, and Yannis Smaragdakis 2obj CI 3obj 1type 2obj 3obj CI 2obj 2type CI 2type 2obj Pass 1 Pass 2 Pass 3 Precision of Pass 1 (P1) Precision of Pass 2 (P2) P1 P2 2obj CI 1type 2obj 3obj CI CI Pass 1 Pass 2 Pass 3 Precision of Pass 1 (P1) Precision of Pass 2 (P2) P1 P2 Relay-o2 Relay-o1 2type Fig. 3. Examples for illustrating the idea of Relay with the same input approaches setting as in Figure 2. Relay has two options, Relay-o1 and Relay-o2 and the former is more precise but less scalable than the latter. In each pass of both options, only the methods enclosed in the solid circles, say M, are analyzed context-sensitively (the dotted lines in Relay-o1 are to facilitate understanding). Both options adopt the same precision filtering mechanism, and their difference only lies in what context-sensitivity variants are assigned to M. with a more precise context. Therefore, the probability to select scalability-threat methods is low, making Relay more likely to scale compared to Unity. After running the first pass, its precision, which is reflected in the points-to set for every variable, will be transmitted to the next pass (pass 2). Then, in pass 2, we can use the precision of pass 1, i.e., the points-to information, to help soundly filtering the points-to sets for all variables when performing the analysis in pass 2. For example, assume a variable v points to three objects under CI with its points-to set, say pt(v), being {o1,o2,o3}. After pass 1, pt(v) becomes {o1,o3} where o2 is identified as a spurious object by analyzing M1 context-sensitively. However, in pass 2, purely analyzing M2 under the contexts shown in Figure 3 cannot recognize that v should not point to o2. However, this imprecision does not matter, as the pt(v) transmitted from pass 1 can be used to filter pt(v) during the analysis in pass 2, i.e., preventing o2 from being propagated to pt(v). Such filtering is safe as the pointer analysis in pass 1 is sound, so no true objects will be filtered away in Relay (this will be formally proven in Section 4). Finally, although uncommon, what if Relay-o1 is not scalable? After all, given a program, we hope to confidently rely on Unity-Relay for yielding precise pointer analysis results all the time. Under this context, we design Relay-o2 as the last line of defense of Unity-Relay. Relay-o2 employs the same principle as Relay-o1 with the exception that context-sensitivity variants (selected by input approach S𝑖 ) are not reassigned any more in each pass, say Pass𝑖 (see Relay-o2 in Figure 3). In other words, Pass𝑖 and the analysis guided by S𝑖 , say A𝑖 , adopt the same selective context sensitivity. The only difference between running the selective approaches independently is that precision accumulates, using the same filtering mechanism as in Relay-o1. Thus, in Pass𝑖 , the points-to set for each variable is never larger than the one in A𝑖 , resulting in less data propagation and faster analysis convergence. The only extra cost introduced in Relay-o2 is the process of filtering, which is small compared to the overhead of a context-sensitive pointer analysis, and easily offset by the aforementioned efficiency benefit. Thus, we can expect Relay-o2 to scale as long Proc. ACM Program. Lang., Vol. 5, No. OOPSLA, Article 147. Publication date: October 2021