1.06/1.10 WORST_CASE(?,O(n^2)) 1.06/1.10 1.06/1.10 Preprocessing Cost Relations 1.06/1.10 ===================================== 1.06/1.10 1.06/1.10 #### Computed strongly connected components 1.06/1.10 0. recursive : [lbl141/9] 1.06/1.10 1. recursive : [lbl121/17,lbl141_loop_cont/18] 1.06/1.10 2. non_recursive : [stop/9] 1.06/1.10 3. non_recursive : [cut/9] 1.06/1.10 4. non_recursive : [exit_location/1] 1.06/1.10 5. non_recursive : [lbl121_loop_cont/10] 1.06/1.10 6. non_recursive : [lbl6/9] 1.06/1.10 7. non_recursive : [start/9] 1.06/1.10 8. non_recursive : [start0/9] 1.06/1.10 1.06/1.10 #### Obtained direct recursion through partial evaluation 1.06/1.10 0. SCC is partially evaluated into lbl141/9 1.06/1.10 1. SCC is partially evaluated into lbl121/17 1.06/1.10 2. SCC is completely evaluated into other SCCs 1.06/1.10 3. SCC is completely evaluated into other SCCs 1.06/1.10 4. SCC is completely evaluated into other SCCs 1.06/1.10 5. SCC is partially evaluated into lbl121_loop_cont/10 1.06/1.10 6. SCC is completely evaluated into other SCCs 1.06/1.10 7. SCC is partially evaluated into start/9 1.06/1.10 8. SCC is partially evaluated into start0/9 1.06/1.10 1.06/1.10 Control-Flow Refinement of Cost Relations 1.06/1.10 ===================================== 1.06/1.10 1.06/1.10 ### Specialization of cost equations lbl141/9 1.06/1.10 * CE 14 is refined into CE [15] 1.06/1.10 * CE 13 is refined into CE [16] 1.06/1.10 * CE 12 is refined into CE [17] 1.06/1.10 1.06/1.10 1.06/1.10 ### Cost equations --> "Loop" of lbl141/9 1.06/1.10 * CEs [15] --> Loop 15 1.06/1.10 * CEs [16] --> Loop 16 1.06/1.10 * CEs [17] --> Loop 17 1.06/1.10 1.06/1.10 ### Ranking functions of CR lbl141(A,B,C,D,E,G,I,J,K) 1.06/1.10 1.06/1.10 #### Partial ranking functions of CR lbl141(A,B,C,D,E,G,I,J,K) 1.06/1.10 1.06/1.10 1.06/1.10 ### Specialization of cost equations lbl121/17 1.06/1.10 * CE 5 is refined into CE [18] 1.06/1.10 * CE 9 is refined into CE [19] 1.06/1.10 * CE 7 is refined into CE [20] 1.06/1.10 * CE 8 is refined into CE [21] 1.06/1.10 * CE 6 is refined into CE [22] 1.06/1.10 1.06/1.10 1.06/1.10 ### Cost equations --> "Loop" of lbl121/17 1.06/1.10 * CEs [21] --> Loop 18 1.06/1.10 * CEs [22] --> Loop 19 1.06/1.10 * CEs [19] --> Loop 20 1.06/1.10 * CEs [18] --> Loop 21 1.06/1.10 * CEs [20] --> Loop 22 1.06/1.10 1.06/1.10 ### Ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q) 1.06/1.10 1.06/1.10 #### Partial ranking functions of CR lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q) 1.06/1.10 * Partial RF of phase [18,19]: 1.06/1.10 - RF of loop [18:1]: 1.06/1.10 A-E depends on loops [19:1] 1.06/1.10 B-E-1 depends on loops [19:1] 1.06/1.10 C-E-1 depends on loops [19:1] 1.06/1.10 D-E depends on loops [19:1] 1.06/1.10 - RF of loop [19:1]: 1.06/1.10 -A+E+1 depends on loops [18:1] 1.06/1.11 B-G-1 1.06/1.11 C-G-1 1.06/1.11 -D+E+1 depends on loops [18:1] 1.06/1.11 E-1 depends on loops [18:1] 1.06/1.11 1.06/1.11 1.06/1.11 ### Specialization of cost equations lbl121_loop_cont/10 1.06/1.11 * CE 10 is refined into CE [23] 1.06/1.11 * CE 11 is refined into CE [24] 1.06/1.11 1.06/1.11 1.06/1.11 ### Cost equations --> "Loop" of lbl121_loop_cont/10 1.06/1.11 * CEs [23] --> Loop 23 1.06/1.11 * CEs [24] --> Loop 24 1.06/1.11 1.06/1.11 ### Ranking functions of CR lbl121_loop_cont(A,B,C,D,E,F,G,H,I,J) 1.06/1.11 1.06/1.11 #### Partial ranking functions of CR lbl121_loop_cont(A,B,C,D,E,F,G,H,I,J) 1.06/1.11 1.06/1.11 1.06/1.11 ### Specialization of cost equations start/9 1.06/1.11 * CE 3 is refined into CE [25] 1.06/1.11 * CE 4 is refined into CE [26,27,28,29] 1.06/1.11 * CE 2 is refined into CE [30] 1.06/1.11 1.06/1.11 1.06/1.11 ### Cost equations --> "Loop" of start/9 1.06/1.11 * CEs [26,29] --> Loop 25 1.06/1.11 * CEs [25] --> Loop 26 1.06/1.11 * CEs [28] --> Loop 27 1.06/1.11 * CEs [30] --> Loop 28 1.06/1.11 * CEs [27] --> Loop 29 1.06/1.11 1.06/1.11 ### Ranking functions of CR start(A,B,C,D,E,F,G,H,I) 1.06/1.11 1.06/1.11 #### Partial ranking functions of CR start(A,B,C,D,E,F,G,H,I) 1.06/1.11 1.06/1.11 1.06/1.11 ### Specialization of cost equations start0/9 1.06/1.11 * CE 1 is refined into CE [31,32,33,34,35] 1.06/1.11 1.06/1.11 1.06/1.11 ### Cost equations --> "Loop" of start0/9 1.06/1.11 * CEs [35] --> Loop 30 1.06/1.11 * CEs [33] --> Loop 31 1.06/1.11 * CEs [34] --> Loop 32 1.06/1.11 * CEs [32] --> Loop 33 1.06/1.11 * CEs [31] --> Loop 34 1.06/1.11 1.06/1.11 ### Ranking functions of CR start0(A,B,C,D,E,F,G,H,I) 1.06/1.11 1.06/1.11 #### Partial ranking functions of CR start0(A,B,C,D,E,F,G,H,I) 1.06/1.11 1.06/1.11 1.06/1.11 Computing Bounds 1.06/1.11 ===================================== 1.06/1.11 1.06/1.11 #### Cost of chains of lbl141(A,B,C,D,E,G,I,J,K): 1.06/1.11 * Chain [17]: 0 1.06/1.11 with precondition: [E=0,I=2,J=0,D=A,C=B,C=G,C=K,D>=2,C>=D+1] 1.06/1.11 1.06/1.11 * Chain [16]: 0 1.06/1.11 with precondition: [E=0,I=3,J=1,D=A,C=B,G=K,D>=2,G>=1,C>=D+1,C>=G+1] 1.06/1.11 1.06/1.11 * Chain [15]: 0 1.06/1.11 with precondition: [E=0,I=4,D=A,C=B,D>=1,G>=1,C>=D+1,C>=G,C+D>=G+2] 1.06/1.11 1.06/1.11 1.06/1.11 #### Cost of chains of lbl121(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q): 1.06/1.11 * Chain [[18,19],22]: 1*it(18)+1*it(19)+0 1.06/1.11 Such that:it(19) =< C-G 1.06/1.11 aux(41) =< C-G+M 1.06/1.11 aux(57) =< C-E 1.06/1.11 aux(58) =< -E+M 1.06/1.11 aux(59) =< M 1.06/1.11 aux(41) =< aux(59) 1.06/1.11 aux(51) =< aux(59) 1.06/1.11 aux(41) =< aux(59) 1.06/1.11 aux(51) =< aux(41) 1.06/1.11 aux(52) =< it(19)*aux(51) 1.06/1.11 aux(1) =< it(19)*aux(51) 1.06/1.11 aux(3) =< it(19)*aux(41) 1.06/1.11 aux(7) =< it(19)*aux(59) 1.06/1.11 aux(1) =< it(19)*aux(59) 1.06/1.11 aux(9) =< aux(52) 1.06/1.11 aux(5) =< aux(3) 1.06/1.11 aux(5) =< aux(7) 1.06/1.11 aux(9) =< aux(7) 1.06/1.11 it(18) =< aux(7)+aux(58) 1.06/1.11 it(18) =< aux(3)+aux(57) 1.06/1.11 it(18) =< aux(1)+aux(58) 1.06/1.11 it(18) =< aux(5)+aux(58) 1.06/1.11 it(18) =< aux(9)+aux(58) 1.06/1.11 it(18) =< aux(5)+aux(57) 1.06/1.11 1.06/1.11 with precondition: [I=2,N=0,B=C,A=D,A=J,B=K,B=L,A=M,F=O,B=P,H=Q,A>=2,E>=1,G>=0,B>=A+1,A>=E,B>=G+1,A+B>=E+G+2] 1.06/1.11 1.06/1.11 * Chain [[18,19],21]: 1*it(18)+1*it(19)+0 1.06/1.11 Such that:aux(41) =< A+B-G 1.06/1.11 it(19) =< B-G 1.06/1.11 aux(60) =< A 1.06/1.11 aux(61) =< A-E 1.06/1.11 aux(62) =< B-E 1.06/1.11 aux(41) =< aux(60) 1.06/1.11 aux(51) =< aux(60) 1.06/1.11 aux(41) =< aux(60) 1.06/1.11 aux(51) =< aux(41) 1.06/1.11 aux(52) =< it(19)*aux(51) 1.06/1.11 aux(1) =< it(19)*aux(51) 1.06/1.11 aux(3) =< it(19)*aux(41) 1.06/1.11 aux(7) =< it(19)*aux(60) 1.06/1.11 aux(1) =< it(19)*aux(60) 1.06/1.11 aux(9) =< aux(52) 1.06/1.11 aux(5) =< aux(3) 1.06/1.11 aux(5) =< aux(7) 1.06/1.11 aux(9) =< aux(7) 1.06/1.11 it(18) =< aux(7)+aux(61) 1.06/1.11 it(18) =< aux(3)+aux(62) 1.06/1.11 it(18) =< aux(1)+aux(61) 1.06/1.11 it(18) =< aux(5)+aux(61) 1.06/1.11 it(18) =< aux(9)+aux(61) 1.06/1.11 it(18) =< aux(5)+aux(62) 1.06/1.11 1.06/1.11 with precondition: [I=4,B=C,A=D,A>=2,E>=1,G>=0,B>=A+1,A>=E,B>=G+1,A+B>=E+G+2] 1.06/1.11 1.06/1.11 * Chain [[18,19],20]: 1*it(18)+1*it(19)+0 1.06/1.11 Such that:aux(41) =< A+C-G 1.06/1.11 it(19) =< C-G 1.06/1.11 aux(63) =< A 1.06/1.11 aux(64) =< A-E 1.06/1.11 aux(65) =< C-E 1.06/1.11 aux(66) =< D-E 1.06/1.11 aux(10) =< aux(64) 1.06/1.11 aux(10) =< aux(66) 1.06/1.11 aux(41) =< aux(63) 1.06/1.11 aux(51) =< aux(63) 1.06/1.11 aux(41) =< aux(63) 1.06/1.11 aux(51) =< aux(41) 1.06/1.11 aux(52) =< it(19)*aux(51) 1.06/1.11 aux(1) =< it(19)*aux(51) 1.06/1.11 aux(3) =< it(19)*aux(41) 1.06/1.11 aux(7) =< it(19)*aux(63) 1.06/1.11 aux(1) =< it(19)*aux(63) 1.06/1.11 aux(9) =< aux(52) 1.06/1.11 aux(5) =< aux(3) 1.06/1.11 aux(5) =< aux(7) 1.06/1.11 aux(9) =< aux(7) 1.06/1.11 it(18) =< aux(7)+aux(64) 1.06/1.11 it(18) =< aux(3)+aux(65) 1.06/1.11 it(18) =< aux(1)+aux(64) 1.06/1.11 it(18) =< aux(5)+aux(10) 1.06/1.11 it(18) =< aux(9)+aux(10) 1.06/1.11 it(18) =< aux(5)+aux(65) 1.06/1.11 1.06/1.11 with precondition: [I=4,B=C,A=D,A>=2,E>=1,G>=0,B>=A+1,A>=E,B>=G+1,A+B>=E+G+2] 1.06/1.11 1.06/1.11 * Chain [21]: 0 1.06/1.11 with precondition: [I=4,D=A,C=B,D=E,D>=1,G>=0,C>=D+1,C>=G+1,C+D>=G+3] 1.06/1.11 1.06/1.11 * Chain [20]: 0 1.06/1.11 with precondition: [I=4,D=A,C=B,E>=1,G>=0,C>=D+1,D>=E] 1.06/1.11 1.06/1.11 1.06/1.11 #### Cost of chains of lbl121_loop_cont(A,B,C,D,E,F,G,H,I,J): 1.06/1.11 * Chain [24]: 0 1.06/1.11 with precondition: [A=2,F=0,C=D,B=E,C=H,B>=2,C>=B+1] 1.06/1.11 1.06/1.11 * Chain [23]: 0 1.06/1.11 with precondition: [A=4] 1.06/1.11 1.06/1.11 1.06/1.11 #### Cost of chains of start(A,B,C,D,E,F,G,H,I): 1.06/1.11 * Chain [29]: 0 1.06/1.11 with precondition: [A=1,D=1,C=B,F=E,H=G,C>=2] 1.06/1.11 1.06/1.11 * Chain [28]: 0 1.06/1.11 with precondition: [D=A,C=B,F=E,H=G,0>=D] 1.06/1.11 1.06/1.11 * Chain [27]: 0 1.06/1.11 with precondition: [D=A,C=B,F=E,H=G,D>=1,C>=D+1] 1.06/1.11 1.06/1.11 * Chain [26]: 0 1.06/1.11 with precondition: [D=A,C=B,F=E,H=G,D>=1,D>=C] 1.06/1.11 1.06/1.11 * Chain [25]: 3*s(29)+3*s(41)+0 1.06/1.11 Such that:aux(74) =< C 1.06/1.11 aux(75) =< C+D 1.06/1.11 aux(76) =< D 1.06/1.11 s(30) =< aux(75) 1.06/1.11 s(29) =< aux(74) 1.06/1.11 s(30) =< aux(76) 1.06/1.11 s(34) =< aux(76) 1.06/1.11 s(30) =< aux(76) 1.06/1.11 s(34) =< s(30) 1.06/1.11 s(35) =< s(29)*s(34) 1.06/1.11 s(36) =< s(29)*s(34) 1.06/1.11 s(37) =< s(29)*s(30) 1.06/1.11 s(38) =< s(29)*aux(76) 1.06/1.11 s(36) =< s(29)*aux(76) 1.06/1.11 s(39) =< s(35) 1.06/1.11 s(40) =< s(37) 1.06/1.11 s(40) =< s(38) 1.06/1.11 s(39) =< s(38) 1.06/1.11 s(41) =< s(38)+aux(76) 1.06/1.11 s(41) =< s(37)+aux(74) 1.06/1.11 s(41) =< s(36)+aux(76) 1.06/1.11 s(41) =< s(40)+aux(76) 1.06/1.11 s(41) =< s(39)+aux(76) 1.06/1.11 s(41) =< s(40)+aux(74) 1.06/1.11 1.06/1.11 with precondition: [D=A,C=B,F=E,H=G,D>=2,C>=D+1] 1.06/1.11 1.06/1.11 1.06/1.11 #### Cost of chains of start0(A,B,C,D,E,F,G,H,I): 1.06/1.11 * Chain [34]: 0 1.06/1.11 with precondition: [A=1,C>=2] 1.06/1.11 1.06/1.11 * Chain [33]: 0 1.06/1.11 with precondition: [0>=A] 1.06/1.11 1.06/1.11 * Chain [32]: 0 1.06/1.11 with precondition: [A>=1,C>=A+1] 1.06/1.11 1.06/1.11 * Chain [31]: 0 1.06/1.11 with precondition: [A>=1,A>=C] 1.06/1.11 1.06/1.11 * Chain [30]: 3*s(72)+3*s(80)+0 1.06/1.11 Such that:s(70) =< A 1.06/1.11 s(69) =< A+C 1.06/1.11 s(68) =< C 1.06/1.11 s(71) =< s(69) 1.06/1.11 s(72) =< s(68) 1.06/1.11 s(71) =< s(70) 1.06/1.11 s(73) =< s(70) 1.06/1.11 s(71) =< s(70) 1.06/1.11 s(73) =< s(71) 1.06/1.11 s(74) =< s(72)*s(73) 1.06/1.11 s(75) =< s(72)*s(73) 1.06/1.11 s(76) =< s(72)*s(71) 1.06/1.11 s(77) =< s(72)*s(70) 1.06/1.11 s(75) =< s(72)*s(70) 1.06/1.11 s(78) =< s(74) 1.06/1.11 s(79) =< s(76) 1.06/1.11 s(79) =< s(77) 1.06/1.11 s(78) =< s(77) 1.06/1.11 s(80) =< s(77)+s(70) 1.06/1.11 s(80) =< s(76)+s(68) 1.06/1.11 s(80) =< s(75)+s(70) 1.06/1.11 s(80) =< s(79)+s(70) 1.06/1.11 s(80) =< s(78)+s(70) 1.06/1.11 s(80) =< s(79)+s(68) 1.06/1.11 1.06/1.11 with precondition: [A>=2,C>=A+1] 1.06/1.11 1.06/1.11 1.06/1.11 Closed-form bounds of start0(A,B,C,D,E,F,G,H,I): 1.06/1.11 ------------------------------------- 1.06/1.11 * Chain [34] with precondition: [A=1,C>=2] 1.06/1.11 - Upper bound: 0 1.06/1.11 - Complexity: constant 1.06/1.11 * Chain [33] with precondition: [0>=A] 1.06/1.11 - Upper bound: 0 1.06/1.11 - Complexity: constant 1.06/1.11 * Chain [32] with precondition: [A>=1,C>=A+1] 1.06/1.11 - Upper bound: 0 1.06/1.11 - Complexity: constant 1.06/1.11 * Chain [31] with precondition: [A>=1,A>=C] 1.06/1.11 - Upper bound: 0 1.06/1.11 - Complexity: constant 1.06/1.11 * Chain [30] with precondition: [A>=2,C>=A+1] 1.06/1.11 - Upper bound: 3*A*C+3*A+3*C 1.06/1.11 - Complexity: n^2 1.06/1.11 1.06/1.11 ### Maximum cost of start0(A,B,C,D,E,F,G,H,I): nat(A)*3*nat(C)+nat(A)*3+nat(C)*3 1.06/1.11 Asymptotic class: n^2 1.06/1.11 * Total analysis performed in 972 ms. 1.06/1.11 1.10/1.21 EOF