0.62/0.71 WORST_CASE(?,O(n^2)) 0.62/0.71 0.62/0.71 Preprocessing Cost Relations 0.62/0.71 ===================================== 0.62/0.71 0.62/0.71 #### Computed strongly connected components 0.62/0.71 0. recursive : [cut/7] 0.62/0.71 1. recursive : [cut_loop_cont/14,lbl71/13] 0.62/0.71 2. non_recursive : [exit_location/1] 0.62/0.71 3. non_recursive : [stop/7] 0.62/0.71 4. non_recursive : [lbl71_loop_cont/8] 0.62/0.71 5. non_recursive : [start/7] 0.62/0.71 6. non_recursive : [start0/7] 0.62/0.71 0.62/0.71 #### Obtained direct recursion through partial evaluation 0.62/0.71 0. SCC is partially evaluated into cut/7 0.62/0.71 1. SCC is partially evaluated into lbl71/13 0.62/0.71 2. SCC is completely evaluated into other SCCs 0.62/0.71 3. SCC is completely evaluated into other SCCs 0.62/0.71 4. SCC is partially evaluated into lbl71_loop_cont/8 0.62/0.71 5. SCC is partially evaluated into start/7 0.62/0.71 6. SCC is partially evaluated into start0/7 0.62/0.71 0.62/0.71 Control-Flow Refinement of Cost Relations 0.62/0.71 ===================================== 0.62/0.71 0.62/0.71 ### Specialization of cost equations cut/7 0.62/0.71 * CE 12 is refined into CE [13] 0.62/0.71 * CE 11 is refined into CE [14] 0.62/0.71 0.62/0.71 0.62/0.71 ### Cost equations --> "Loop" of cut/7 0.62/0.71 * CEs [13] --> Loop 13 0.62/0.71 * CEs [14] --> Loop 14 0.62/0.71 0.62/0.71 ### Ranking functions of CR cut(A,B,C,E,G,H,I) 0.62/0.71 0.62/0.71 #### Partial ranking functions of CR cut(A,B,C,E,G,H,I) 0.62/0.71 0.62/0.71 0.62/0.71 ### Specialization of cost equations lbl71/13 0.62/0.71 * CE 4 is refined into CE [15] 0.62/0.71 * CE 8 is refined into CE [16] 0.62/0.71 * CE 7 is refined into CE [17] 0.62/0.71 * CE 6 is refined into CE [18] 0.62/0.71 * CE 5 is refined into CE [19] 0.62/0.71 0.62/0.71 0.62/0.71 ### Cost equations --> "Loop" of lbl71/13 0.62/0.71 * CEs [18] --> Loop 15 0.62/0.71 * CEs [19] --> Loop 16 0.62/0.71 * CEs [15] --> Loop 17 0.62/0.71 * CEs [16] --> Loop 18 0.62/0.71 * CEs [17] --> Loop 19 0.62/0.71 0.62/0.71 ### Ranking functions of CR lbl71(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.62/0.71 0.62/0.71 #### Partial ranking functions of CR lbl71(A,B,C,D,E,F,G,H,I,J,K,L,M) 0.62/0.71 * Partial RF of phase [15,16]: 0.62/0.71 - RF of loop [15:1]: 0.62/0.71 A-C-1 depends on loops [16:1] 0.62/0.71 B-C-1 depends on loops [16:1] 0.62/0.71 - RF of loop [16:1]: 0.62/0.71 -A+C+2 depends on loops [15:1] 0.62/0.71 A-E-2 0.62/0.71 -B+C+2 depends on loops [15:1] 0.62/0.71 B-E-2 0.62/0.71 C-1 depends on loops [15:1] 0.62/0.71 C/2-E/2-1/2 depends on loops [15:1] 0.62/0.71 0.62/0.71 0.62/0.71 ### Specialization of cost equations lbl71_loop_cont/8 0.62/0.71 * CE 10 is refined into CE [20] 0.62/0.71 * CE 9 is refined into CE [21] 0.62/0.71 0.62/0.71 0.62/0.71 ### Cost equations --> "Loop" of lbl71_loop_cont/8 0.62/0.71 * CEs [20] --> Loop 20 0.62/0.71 * CEs [21] --> Loop 21 0.62/0.71 0.62/0.71 ### Ranking functions of CR lbl71_loop_cont(A,B,C,D,E,F,G,H) 0.62/0.71 0.62/0.71 #### Partial ranking functions of CR lbl71_loop_cont(A,B,C,D,E,F,G,H) 0.62/0.71 0.62/0.71 0.62/0.71 ### Specialization of cost equations start/7 0.62/0.71 * CE 3 is refined into CE [22,23,24,25,26] 0.62/0.71 * CE 2 is refined into CE [27] 0.62/0.71 0.62/0.71 0.62/0.71 ### Cost equations --> "Loop" of start/7 0.62/0.71 * CEs [23,25,26] --> Loop 22 0.62/0.71 * CEs [24] --> Loop 23 0.62/0.71 * CEs [27] --> Loop 24 0.62/0.71 * CEs [22] --> Loop 25 0.62/0.71 0.62/0.71 ### Ranking functions of CR start(A,B,C,D,E,F,G) 0.62/0.71 0.62/0.71 #### Partial ranking functions of CR start(A,B,C,D,E,F,G) 0.62/0.71 0.62/0.71 0.62/0.71 ### Specialization of cost equations start0/7 0.62/0.71 * CE 1 is refined into CE [28,29,30,31] 0.62/0.71 0.62/0.71 0.62/0.71 ### Cost equations --> "Loop" of start0/7 0.62/0.71 * CEs [31] --> Loop 26 0.62/0.71 * CEs [30] --> Loop 27 0.62/0.71 * CEs [29] --> Loop 28 0.62/0.71 * CEs [28] --> Loop 29 0.62/0.71 0.62/0.71 ### Ranking functions of CR start0(A,B,C,D,E,F,G) 0.62/0.71 0.62/0.71 #### Partial ranking functions of CR start0(A,B,C,D,E,F,G) 0.62/0.71 0.62/0.71 0.62/0.71 Computing Bounds 0.62/0.71 ===================================== 0.62/0.71 0.62/0.71 #### Cost of chains of cut(A,B,C,E,G,H,I): 0.62/0.71 * Chain [14]: 0 0.62/0.71 with precondition: [G=2,H=1,B=A,B=C+1,E=I,E>=1,B>=E+2] 0.62/0.71 0.62/0.71 * Chain [13]: 0 0.62/0.71 with precondition: [G=4,B=A,B=C+1,E>=1,B>=E+2] 0.62/0.71 0.62/0.71 0.62/0.71 #### Cost of chains of lbl71(A,B,C,D,E,F,G,H,I,J,K,L,M): 0.62/0.71 * Chain [[15,16],19]: 1*it(15)+1*it(16)+0 0.62/0.71 Such that:it(16) =< -E+J 0.62/0.71 aux(31) =< -E+2*J+2 0.62/0.71 aux(47) =< -C+J 0.62/0.71 aux(48) =< -C+J+1 0.62/0.71 aux(49) =< J+1 0.62/0.71 aux(31) =< aux(49) 0.62/0.71 aux(37) =< aux(49) 0.62/0.71 aux(31) =< aux(49) 0.62/0.71 aux(37) =< aux(31) 0.62/0.71 aux(38) =< it(16)*aux(37) 0.62/0.71 aux(1) =< it(16)*aux(37) 0.62/0.71 aux(32) =< it(16)*aux(31) 0.62/0.71 aux(3) =< it(16)*aux(31) 0.62/0.71 aux(22) =< it(16)*aux(49) 0.62/0.71 aux(1) =< it(16)*aux(49) 0.62/0.71 aux(3) =< it(16)*aux(49) 0.62/0.71 aux(5) =< aux(38) 0.62/0.71 aux(7) =< aux(32) 0.62/0.71 aux(5) =< aux(22) 0.62/0.71 aux(7) =< aux(22) 0.62/0.71 it(15) =< aux(3)+aux(48) 0.62/0.71 it(15) =< aux(1)+aux(48) 0.62/0.71 it(15) =< aux(7)+aux(47) 0.62/0.71 it(15) =< aux(5)+aux(47) 0.62/0.71 0.62/0.71 with precondition: [G=3,A=B,A=H,A=I,A=J+1,D=K,A=L+1,F=M,A>=3,C>=1,E>=0,A>=C+1,A>=E+2,2*A>=C+E+4] 0.62/0.71 0.62/0.71 * Chain [[15,16],18]: 1*it(15)+1*it(16)+0 0.62/0.71 Such that:it(16) =< A-E 0.62/0.71 aux(31) =< 2*A-E 0.62/0.71 aux(50) =< A 0.62/0.71 aux(51) =< A-C 0.62/0.71 aux(52) =< B-C 0.62/0.71 aux(6) =< aux(51) 0.62/0.71 aux(6) =< aux(52) 0.62/0.71 aux(31) =< aux(50) 0.62/0.71 aux(37) =< aux(50) 0.62/0.71 aux(31) =< aux(50) 0.62/0.71 aux(37) =< aux(31) 0.62/0.71 aux(38) =< it(16)*aux(37) 0.62/0.71 aux(1) =< it(16)*aux(37) 0.62/0.71 aux(32) =< it(16)*aux(31) 0.62/0.71 aux(3) =< it(16)*aux(31) 0.62/0.71 aux(22) =< it(16)*aux(50) 0.62/0.71 aux(1) =< it(16)*aux(50) 0.62/0.71 aux(3) =< it(16)*aux(50) 0.62/0.71 aux(5) =< aux(38) 0.62/0.71 aux(7) =< aux(32) 0.62/0.71 aux(5) =< aux(22) 0.62/0.71 aux(7) =< aux(22) 0.62/0.71 it(15) =< aux(3)+aux(51) 0.62/0.71 it(15) =< aux(1)+aux(51) 0.62/0.71 it(15) =< aux(7)+aux(6) 0.62/0.71 it(15) =< aux(5)+aux(6) 0.62/0.71 0.62/0.71 with precondition: [G=4,A=B,A>=3,C>=1,E>=0,A>=C+1,A>=E+2,2*A>=C+E+4] 0.62/0.71 0.62/0.71 * Chain [[15,16],17]: 1*it(15)+1*it(16)+0 0.62/0.71 Such that:it(16) =< A-E 0.62/0.71 aux(31) =< 2*A-E 0.62/0.71 aux(53) =< A 0.62/0.71 aux(54) =< A-C 0.62/0.71 aux(31) =< aux(53) 0.62/0.71 aux(37) =< aux(53) 0.62/0.71 aux(31) =< aux(53) 0.62/0.71 aux(37) =< aux(31) 0.62/0.71 aux(38) =< it(16)*aux(37) 0.62/0.71 aux(1) =< it(16)*aux(37) 0.62/0.71 aux(32) =< it(16)*aux(31) 0.62/0.71 aux(3) =< it(16)*aux(31) 0.62/0.71 aux(22) =< it(16)*aux(53) 0.62/0.71 aux(1) =< it(16)*aux(53) 0.62/0.71 aux(3) =< it(16)*aux(53) 0.62/0.71 aux(5) =< aux(38) 0.62/0.71 aux(7) =< aux(32) 0.62/0.71 aux(5) =< aux(22) 0.62/0.71 aux(7) =< aux(22) 0.62/0.71 it(15) =< aux(3)+aux(54) 0.62/0.71 it(15) =< aux(1)+aux(54) 0.62/0.71 it(15) =< aux(7)+aux(54) 0.62/0.71 it(15) =< aux(5)+aux(54) 0.62/0.71 0.62/0.71 with precondition: [G=4,A=B,C>=1,E>=0,A>=C+1,A>=E+3] 0.62/0.71 0.62/0.71 * Chain [19]: 0 0.62/0.71 with precondition: [G=3,B=A,B=C+1,K=D,B=E+2,M=F,B=H,B=I,B=J+1,B=L+1,B>=2] 0.62/0.71 0.62/0.71 * Chain [18]: 0 0.62/0.71 with precondition: [G=4,B=A,C>=1,E>=0,B>=C+1,B>=E+2] 0.62/0.71 0.62/0.71 0.62/0.71 #### Cost of chains of lbl71_loop_cont(A,B,C,D,E,F,G,H): 0.62/0.71 * Chain [21]: 0 0.62/0.71 with precondition: [A=3] 0.62/0.71 0.62/0.71 * Chain [20]: 0 0.62/0.71 with precondition: [A=4] 0.62/0.71 0.62/0.71 0.62/0.71 #### Cost of chains of start(A,B,C,D,E,F,G): 0.62/0.71 * Chain [25]: 0 0.62/0.71 with precondition: [A=2,B=2,D=C,F=E] 0.62/0.71 0.62/0.71 * Chain [24]: 0 0.62/0.71 with precondition: [B=A,D=C,F=E,1>=B] 0.62/0.71 0.62/0.71 * Chain [23]: 0 0.62/0.71 with precondition: [B=A,D=C,F=E,B>=2] 0.62/0.71 0.62/0.71 * Chain [22]: 3*s(1)+3*s(14)+0 0.62/0.71 Such that:aux(58) =< B 0.62/0.71 aux(59) =< 2*B 0.62/0.71 s(2) =< aux(59) 0.62/0.71 s(1) =< aux(58) 0.62/0.71 s(2) =< aux(58) 0.62/0.71 s(6) =< aux(58) 0.62/0.71 s(2) =< aux(58) 0.62/0.71 s(6) =< s(2) 0.62/0.71 s(7) =< s(1)*s(6) 0.62/0.71 s(8) =< s(1)*s(6) 0.62/0.71 s(9) =< s(1)*s(2) 0.62/0.71 s(10) =< s(1)*s(2) 0.62/0.71 s(11) =< s(1)*aux(58) 0.62/0.71 s(8) =< s(1)*aux(58) 0.62/0.71 s(10) =< s(1)*aux(58) 0.62/0.71 s(12) =< s(7) 0.62/0.71 s(13) =< s(9) 0.62/0.71 s(12) =< s(11) 0.62/0.71 s(13) =< s(11) 0.62/0.71 s(14) =< s(10)+aux(58) 0.62/0.71 s(14) =< s(8)+aux(58) 0.62/0.71 s(14) =< s(13)+aux(58) 0.62/0.71 s(14) =< s(12)+aux(58) 0.62/0.71 0.62/0.71 with precondition: [B=A,D=C,F=E,B>=3] 0.62/0.71 0.62/0.71 0.62/0.71 #### Cost of chains of start0(A,B,C,D,E,F,G): 0.62/0.71 * Chain [29]: 0 0.62/0.71 with precondition: [A=2] 0.62/0.71 0.62/0.71 * Chain [28]: 0 0.62/0.71 with precondition: [1>=A] 0.62/0.71 0.62/0.71 * Chain [27]: 0 0.62/0.71 with precondition: [A>=2] 0.62/0.71 0.62/0.71 * Chain [26]: 3*s(46)+3*s(55)+0 0.62/0.71 Such that:s(43) =< A 0.62/0.71 s(44) =< 2*A 0.62/0.71 s(45) =< s(44) 0.62/0.71 s(46) =< s(43) 0.62/0.71 s(45) =< s(43) 0.62/0.71 s(47) =< s(43) 0.62/0.71 s(45) =< s(43) 0.62/0.71 s(47) =< s(45) 0.62/0.71 s(48) =< s(46)*s(47) 0.62/0.71 s(49) =< s(46)*s(47) 0.62/0.71 s(50) =< s(46)*s(45) 0.62/0.71 s(51) =< s(46)*s(45) 0.62/0.71 s(52) =< s(46)*s(43) 0.62/0.71 s(49) =< s(46)*s(43) 0.62/0.71 s(51) =< s(46)*s(43) 0.62/0.71 s(53) =< s(48) 0.62/0.71 s(54) =< s(50) 0.62/0.71 s(53) =< s(52) 0.62/0.71 s(54) =< s(52) 0.62/0.71 s(55) =< s(51)+s(43) 0.62/0.71 s(55) =< s(49)+s(43) 0.62/0.71 s(55) =< s(54)+s(43) 0.62/0.71 s(55) =< s(53)+s(43) 0.62/0.71 0.62/0.71 with precondition: [A>=3] 0.62/0.71 0.62/0.71 0.62/0.71 Closed-form bounds of start0(A,B,C,D,E,F,G): 0.62/0.71 ------------------------------------- 0.62/0.71 * Chain [29] with precondition: [A=2] 0.62/0.71 - Upper bound: 0 0.62/0.71 - Complexity: constant 0.62/0.71 * Chain [28] with precondition: [1>=A] 0.62/0.71 - Upper bound: 0 0.62/0.71 - Complexity: constant 0.62/0.71 * Chain [27] with precondition: [A>=2] 0.62/0.71 - Upper bound: 0 0.62/0.71 - Complexity: constant 0.62/0.71 * Chain [26] with precondition: [A>=3] 0.62/0.71 - Upper bound: 3*A*(2*A)+6*A 0.62/0.71 - Complexity: n^2 0.62/0.71 0.62/0.71 ### Maximum cost of start0(A,B,C,D,E,F,G): nat(A)*3*nat(2*A)+nat(A)*6 0.62/0.71 Asymptotic class: n^2 0.62/0.71 * Total analysis performed in 593 ms. 0.62/0.71 0.71/0.81 EOF