1.69/1.75 MAYBE 1.69/1.75 1.69/1.75 Preprocessing Cost Relations 1.69/1.75 ===================================== 1.69/1.75 1.69/1.75 #### Computed strongly connected components 1.69/1.75 0. recursive : [f1/31] 1.69/1.75 1. non_recursive : [f10/39] 1.69/1.75 2. non_recursive : [exit_location/1] 1.69/1.75 3. recursive : [f16/34] 1.69/1.75 4. recursive : [f8/27] 1.69/1.75 5. non_recursive : [f8_loop_cont/40] 1.69/1.75 6. non_recursive : [f16_loop_cont/40] 1.69/1.75 7. non_recursive : [f1_loop_cont/40] 1.69/1.75 8. non_recursive : [f9/39] 1.69/1.75 1.69/1.75 #### Obtained direct recursion through partial evaluation 1.69/1.75 0. SCC is partially evaluated into f1/31 1.69/1.75 1. SCC is completely evaluated into other SCCs 1.69/1.75 2. SCC is completely evaluated into other SCCs 1.69/1.75 3. SCC is partially evaluated into f16/34 1.69/1.75 4. SCC is partially evaluated into f8/27 1.69/1.75 5. SCC is partially evaluated into f8_loop_cont/40 1.69/1.75 6. SCC is partially evaluated into f16_loop_cont/40 1.69/1.75 7. SCC is partially evaluated into f1_loop_cont/40 1.69/1.75 8. SCC is partially evaluated into f9/39 1.69/1.75 1.69/1.75 Control-Flow Refinement of Cost Relations 1.69/1.75 ===================================== 1.69/1.75 1.69/1.75 ### Specialization of cost equations f1/31 1.69/1.75 * CE 5 is refined into CE [18] 1.69/1.75 * CE 4 is refined into CE [19] 1.69/1.75 * CE 3 is refined into CE [20] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f1/31 1.69/1.75 * CEs [20] --> Loop 17 1.69/1.75 * CEs [18] --> Loop 18 1.69/1.75 * CEs [19] --> Loop 19 1.69/1.75 1.69/1.75 ### Ranking functions of CR f1(A,B,C,D,G,M,Q,R,S,T,U,V,W,X,Y,Z,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2) 1.69/1.75 * RF of phase [17]: [-A+C,-A+Q] 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f1(A,B,C,D,G,M,Q,R,S,T,U,V,W,X,Y,Z,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2) 1.69/1.75 * Partial RF of phase [17]: 1.69/1.75 - RF of loop [17:1]: 1.69/1.75 -A+C 1.69/1.75 -A+Q 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f16/34 1.69/1.75 * CE 10 is refined into CE [21] 1.69/1.75 * CE 9 is refined into CE [22] 1.69/1.75 * CE 8 is refined into CE [23] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f16/34 1.69/1.75 * CEs [23] --> Loop 20 1.69/1.75 * CEs [21] --> Loop 21 1.69/1.75 * CEs [22] --> Loop 22 1.69/1.75 1.69/1.75 ### Ranking functions of CR f16(B,C,D,E,G,L,M,N,O,P,A1,B1,C1,D1,E1,F1,G1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2,U2,V2) 1.69/1.75 * RF of phase [20]: [G+1] 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f16(B,C,D,E,G,L,M,N,O,P,A1,B1,C1,D1,E1,F1,G1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2,U2,V2) 1.69/1.75 * Partial RF of phase [20]: 1.69/1.75 - RF of loop [20:1]: 1.69/1.75 G+1 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f8/27 1.69/1.75 * CE 15 is refined into CE [24] 1.69/1.75 * CE 14 is refined into CE [25] 1.69/1.75 * CE 13 is refined into CE [26] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f8/27 1.69/1.75 * CEs [26] --> Loop 23 1.69/1.75 * CEs [24] --> Loop 24 1.69/1.75 * CEs [25] --> Loop 25 1.69/1.75 1.69/1.75 ### Ranking functions of CR f8(C,D,E,M,Y,B1,C1,D1,E1,F1,G1,H1,I1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2) 1.69/1.75 * RF of phase [23]: [H1+1] 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f8(C,D,E,M,Y,B1,C1,D1,E1,F1,G1,H1,I1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2) 1.69/1.75 * Partial RF of phase [23]: 1.69/1.75 - RF of loop [23:1]: 1.69/1.75 H1+1 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f8_loop_cont/40 1.69/1.75 * CE 17 is refined into CE [27] 1.69/1.75 * CE 16 is refined into CE [28] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f8_loop_cont/40 1.69/1.75 * CEs [27] --> Loop 26 1.69/1.75 * CEs [28] --> Loop 27 1.69/1.75 1.69/1.75 ### Ranking functions of CR f8_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f8_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f16_loop_cont/40 1.69/1.75 * CE 12 is refined into CE [29,30,31,32] 1.69/1.75 * CE 11 is refined into CE [33] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f16_loop_cont/40 1.69/1.75 * CEs [32] --> Loop 28 1.69/1.75 * CEs [31] --> Loop 29 1.69/1.75 * CEs [30] --> Loop 30 1.69/1.75 * CEs [29] --> Loop 31 1.69/1.75 * CEs [33] --> Loop 32 1.69/1.75 1.69/1.75 ### Ranking functions of CR f16_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f16_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f1_loop_cont/40 1.69/1.75 * CE 7 is refined into CE [34,35,36,37,38,39,40,41,42,43] 1.69/1.75 * CE 6 is refined into CE [44] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f1_loop_cont/40 1.69/1.75 * CEs [43] --> Loop 33 1.69/1.75 * CEs [42] --> Loop 34 1.69/1.75 * CEs [34] --> Loop 35 1.69/1.75 * CEs [35,37] --> Loop 36 1.69/1.75 * CEs [36] --> Loop 37 1.69/1.75 * CEs [39] --> Loop 38 1.69/1.75 * CEs [40] --> Loop 39 1.69/1.75 * CEs [38] --> Loop 40 1.69/1.75 * CEs [41] --> Loop 41 1.69/1.75 * CEs [44] --> Loop 42 1.69/1.75 1.69/1.75 ### Ranking functions of CR f1_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f1_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1) 1.69/1.75 1.69/1.75 1.69/1.75 ### Specialization of cost equations f9/39 1.69/1.75 * CE 1 is refined into CE [45] 1.69/1.75 * CE 2 is refined into CE [46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65] 1.69/1.75 1.69/1.75 1.69/1.75 ### Cost equations --> "Loop" of f9/39 1.69/1.75 * CEs [47,52,56,61] --> Loop 43 1.69/1.75 * CEs [46,49,51,55,58,60] --> Loop 44 1.69/1.75 * CEs [48,50,53,54,57,59,62,63] --> Loop 45 1.69/1.75 * CEs [45,64,65] --> Loop 46 1.69/1.75 1.69/1.75 ### Ranking functions of CR f9(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,F2) 1.69/1.75 1.69/1.75 #### Partial ranking functions of CR f9(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,F2) 1.69/1.75 1.69/1.75 1.69/1.75 Computing Bounds 1.69/1.75 ===================================== 1.69/1.75 1.69/1.75 #### Cost of chains of f1(A,B,C,D,G,M,Q,R,S,T,U,V,W,X,Y,Z,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2): 1.69/1.75 * Chain [[17],19]: 1*it(17)+0 1.69/1.75 Such that:it(17) =< -A+C 1.69/1.75 1.69/1.75 with precondition: [B=0,F2=5,G2=0,C=Q,R=T,I2=J2,C=P2+1,A>=2,H2>=2,C>=A+1,G>=H2,T2>=H2] 1.69/1.75 1.69/1.75 * Chain [[17],18]: 1*it(17)+0 1.69/1.75 Such that:it(17) =< -A+C 1.69/1.75 1.69/1.75 with precondition: [F2=3,C=Q,R=T,A>=2,C>=A+1] 1.69/1.75 1.69/1.75 * Chain [19]: 0 1.69/1.75 with precondition: [B=0,F2=5,G2=0,C=A,C=Q,T=R,O2=U,P2=V,T=I2,T=J2,C>=2,H2>=2,G>=H2,T2>=H2] 1.69/1.75 1.69/1.75 * Chain [18]: 0 1.69/1.75 with precondition: [F2=3,Q=C,T=R,A>=2,Q>=A] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f16(B,C,D,E,G,L,M,N,O,P,A1,B1,C1,D1,E1,F1,G1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2,T2,U2,V2): 1.69/1.75 * Chain [[20],22]: 1*it(20)+0 1.69/1.75 Such that:it(20) =< -B+O2 1.69/1.75 1.69/1.75 with precondition: [M=0,F2=4,L2=0,M2=0,Q2=0,S2=0,K2=P2,I2=R2,I2=T2,I2=U2,I2=V2,K2+O2=B+G,B>=0,H2>=2,K2>=0,G>=K2+1] 1.69/1.75 1.69/1.75 * Chain [[20],21]: 1*it(20)+0 1.69/1.75 Such that:it(20) =< G+1 1.69/1.75 1.69/1.75 with precondition: [F2=3,B>=0,G>=0] 1.69/1.75 1.69/1.75 * Chain [22]: 0 1.69/1.75 with precondition: [M=0,F2=4,M2=0,Q2=0,S2=0,J2=E,L2=L,N2=N,O2=O,P2=P,D=I2,G=K2,D=R2,D=T2,D=U2,D=V2,B>=0,G>=0,H2>=2] 1.69/1.75 1.69/1.75 * Chain [21]: 0 1.69/1.75 with precondition: [F2=3] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f8(C,D,E,M,Y,B1,C1,D1,E1,F1,G1,H1,I1,F2,G2,H2,I2,J2,K2,L2,M2,N2,O2,P2,Q2,R2,S2): 1.69/1.75 * Chain [[23],25]: 1*it(23)+0 1.69/1.75 Such that:it(23) =< H1-S2 1.69/1.75 1.69/1.75 with precondition: [B1=0,G1=0,F2=2,J2=0,R2=S2,G2>=2,R2>=0,H1>=R2+1] 1.69/1.75 1.69/1.75 * Chain [[23],24]: 1*it(23)+0 1.69/1.75 Such that:it(23) =< H1+1 1.69/1.75 1.69/1.75 with precondition: [B1=0,F2=3,H1>=0] 1.69/1.75 1.69/1.75 * Chain [25]: 0 1.69/1.75 with precondition: [F2=2,H2=D,I2=E,J2=M,G1=B1,S2=I1,H1=R2,H1>=0,G2>=2] 1.69/1.75 1.69/1.75 * Chain [24]: 0 1.69/1.75 with precondition: [F2=3] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f8_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1): 1.69/1.75 * Chain [27]: 0 1.69/1.75 with precondition: [A=2,M1=2] 1.69/1.75 1.69/1.75 * Chain [26]: 0 1.69/1.75 with precondition: [A=3,M1=2] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f16_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1): 1.69/1.75 * Chain [32]: 0 1.69/1.75 with precondition: [A=3,M1=2,I1=B1] 1.69/1.75 1.69/1.75 * Chain [31]: 1*s(1)+0 1.69/1.75 Such that:s(1) =< I1 1.69/1.75 1.69/1.75 with precondition: [A=4,C1=0,H1=0,M1=2,I1=B1,I1>=1] 1.69/1.75 1.69/1.75 * Chain [30]: 1*s(2)+0 1.69/1.75 Such that:s(2) =< I1+1 1.69/1.75 1.69/1.75 with precondition: [A=4,C1=0,M1=2,I1=B1,I1>=0] 1.69/1.75 1.69/1.75 * Chain [29]: 0 1.69/1.75 with precondition: [A=4,M1=2,I1=B1,H1=C1,I1>=0] 1.69/1.75 1.69/1.75 * Chain [28]: 0 1.69/1.75 with precondition: [A=4,M1=2,I1=B1] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f1_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,M1,N1): 1.69/1.75 * Chain [42]: 0 1.69/1.75 with precondition: [A=3,M1=2,H=B] 1.69/1.75 1.69/1.75 * Chain [41]: 0 1.69/1.75 with precondition: [A=5,E=0,N=0,M1=2,H=B,C>=0,H>=0,I1>=0] 1.69/1.75 1.69/1.75 * Chain [40]: 1*s(3)+0 1.69/1.75 Such that:s(3) =< I1 1.69/1.75 1.69/1.75 with precondition: [A=5,E=0,N=0,M1=2,H=B,C>=0,H>=0,I1>=1] 1.69/1.75 1.69/1.75 * Chain [39]: 0 1.69/1.75 with precondition: [A=5,N=0,M1=2,H=B,C>=0,H>=0] 1.69/1.75 1.69/1.75 * Chain [38]: 1*s(4)+0 1.69/1.75 Such that:s(4) =< I1+1 1.69/1.75 1.69/1.75 with precondition: [A=5,N=0,M1=2,H=B,C>=0,H>=0,I1>=0] 1.69/1.75 1.69/1.75 * Chain [37]: 1*s(5)+0 1.69/1.75 Such that:s(5) =< B 1.69/1.75 1.69/1.75 with precondition: [A=5,N=0,M1=2,H=B,C>=0,H>=1] 1.69/1.75 1.69/1.75 * Chain [36]: 2*s(6)+1*s(7)+0 1.69/1.75 Such that:s(7) =< I1+1 1.69/1.75 aux(1) =< B 1.69/1.75 s(6) =< aux(1) 1.69/1.75 1.69/1.75 with precondition: [A=5,N=0,M1=2,H=B,C>=0,H>=1,I1>=0] 1.69/1.75 1.69/1.75 * Chain [35]: 1*s(9)+1*s(10)+0 1.69/1.75 Such that:s(9) =< B 1.69/1.75 s(10) =< I1 1.69/1.75 1.69/1.75 with precondition: [A=5,N=0,M1=2,H=B,C>=0,H>=1,I1>=1] 1.69/1.75 1.69/1.75 * Chain [34]: 0 1.69/1.75 with precondition: [A=5,M1=2,H=B] 1.69/1.75 1.69/1.75 * Chain [33]: 1*s(11)+0 1.69/1.75 Such that:s(11) =< B+1 1.69/1.75 1.69/1.75 with precondition: [A=5,M1=2,H=B,C>=0,H>=0] 1.69/1.75 1.69/1.75 1.69/1.75 #### Cost of chains of f9(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,F2): 1.69/1.75 * Chain [46]: 1*aux(2)+0 1.69/1.75 with precondition: [] 1.69/1.75 1.69/1.75 * Chain [45]: 2*s(13)+2*s(14)+4*s(15)+0 1.69/1.75 Such that:aux(3) =< G 1.69/1.75 aux(4) =< G+1 1.69/1.75 s(13) =< aux(3) 1.69/1.75 s(14) =< aux(4) 1.69/1.75 1.69/1.75 with precondition: [B=0,G>=2] 1.69/1.75 1.69/1.75 * Chain [44]: 4*s(21)+4*s(24)+3*s(25)+0 1.69/1.75 Such that:aux(5) =< G 1.69/1.75 aux(6) =< H1+1 1.69/1.75 s(21) =< aux(6) 1.69/1.75 s(24) =< aux(5) 1.69/1.75 1.69/1.75 with precondition: [B=0,G>=2,H1>=0] 1.69/1.75 1.69/1.75 * Chain [43]: 4*s(32)+2*s(33)+2*s(35)+0 1.69/1.75 Such that:aux(7) =< G 1.69/1.75 aux(8) =< H1 1.69/1.75 s(33) =< aux(7) 1.69/1.75 s(32) =< aux(8) 1.69/1.75 1.69/1.75 with precondition: [B=0,G>=2,H1>=1] 1.69/1.75 1.69/1.75 1.69/1.75 Closed-form bounds of f9(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,F2): 1.69/1.75 ------------------------------------- 1.69/1.75 * Chain [46] with precondition: [] 1.69/1.75 - Upper bound: inf 1.69/1.75 - Complexity: infinity 1.69/1.75 * Chain [45] with precondition: [B=0,G>=2] 1.69/1.75 - Upper bound: inf 1.69/1.75 - Complexity: infinity 1.69/1.75 * Chain [44] with precondition: [B=0,G>=2,H1>=0] 1.69/1.75 - Upper bound: inf 1.69/1.75 - Complexity: infinity 1.69/1.75 * Chain [43] with precondition: [B=0,G>=2,H1>=1] 1.69/1.75 - Upper bound: inf 1.69/1.75 - Complexity: infinity 1.69/1.75 1.69/1.75 ### Maximum cost of f9(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1,G1,H1,I1,J1,K1,L1,F2): inf 1.69/1.75 Asymptotic class: infinity 1.69/1.75 * Total analysis performed in 1585 ms. 1.69/1.75 1.75/1.85 EOF