0.68/0.68 WORST_CASE(?,O(n^2)) 0.68/0.68 0.68/0.68 Preprocessing Cost Relations 0.68/0.68 ===================================== 0.68/0.68 0.68/0.68 #### Computed strongly connected components 0.68/0.68 0. recursive : [lbl43/8] 0.68/0.68 1. recursive : [lbl13/11,lbl31/11,lbl43_loop_cont/12] 0.68/0.68 2. non_recursive : [exit_location/1] 0.68/0.68 3. non_recursive : [stop/11] 0.68/0.68 4. non_recursive : [lbl31_loop_cont/12] 0.68/0.68 5. non_recursive : [start/11] 0.68/0.68 6. non_recursive : [start0/11] 0.68/0.68 0.68/0.68 #### Obtained direct recursion through partial evaluation 0.68/0.68 0. SCC is partially evaluated into lbl43/8 0.68/0.68 1. SCC is partially evaluated into lbl31/11 0.68/0.68 2. SCC is completely evaluated into other SCCs 0.68/0.68 3. SCC is completely evaluated into other SCCs 0.68/0.68 4. SCC is partially evaluated into lbl31_loop_cont/12 0.68/0.68 5. SCC is partially evaluated into start/11 0.68/0.68 6. SCC is partially evaluated into start0/11 0.68/0.68 0.68/0.68 Control-Flow Refinement of Cost Relations 0.68/0.68 ===================================== 0.68/0.68 0.68/0.68 ### Specialization of cost equations lbl43/8 0.68/0.68 * CE 14 is refined into CE [15] 0.68/0.68 * CE 13 is refined into CE [16] 0.68/0.68 * CE 12 is refined into CE [17] 0.68/0.68 0.68/0.68 0.68/0.68 ### Cost equations --> "Loop" of lbl43/8 0.68/0.68 * CEs [17] --> Loop 15 0.68/0.68 * CEs [15] --> Loop 16 0.68/0.68 * CEs [16] --> Loop 17 0.68/0.68 0.68/0.68 ### Ranking functions of CR lbl43(A,D,F,G,I,L,M,N) 0.68/0.68 * RF of phase [15]: [G+1] 0.68/0.68 0.68/0.68 #### Partial ranking functions of CR lbl43(A,D,F,G,I,L,M,N) 0.68/0.68 * Partial RF of phase [15]: 0.68/0.68 - RF of loop [15:1]: 0.68/0.68 G+1 0.68/0.68 0.68/0.68 0.68/0.68 ### Specialization of cost equations lbl31/11 0.68/0.68 * CE 7 is refined into CE [18] 0.68/0.68 * CE 6 is refined into CE [19,20] 0.68/0.68 * CE 8 is refined into CE [21,22] 0.68/0.68 * CE 9 is refined into CE [23] 0.68/0.68 * CE 4 is refined into CE [24,25] 0.68/0.68 * CE 5 is refined into CE [26] 0.68/0.68 0.68/0.68 0.68/0.68 ### Cost equations --> "Loop" of lbl31/11 0.68/0.68 * CEs [26] --> Loop 18 0.68/0.68 * CEs [25] --> Loop 19 0.68/0.68 * CEs [24] --> Loop 20 0.68/0.68 * CEs [20] --> Loop 21 0.68/0.68 * CEs [19] --> Loop 22 0.68/0.68 * CEs [18] --> Loop 23 0.68/0.68 * CEs [22] --> Loop 24 0.68/0.68 * CEs [21,23] --> Loop 25 0.68/0.68 0.68/0.68 ### Ranking functions of CR lbl31(A,B,D,F,G,I,L,M,N,O,P) 0.68/0.68 * RF of phase [18,19,20]: [A-I-1,F-I-1] 0.68/0.68 0.68/0.68 #### Partial ranking functions of CR lbl31(A,B,D,F,G,I,L,M,N,O,P) 0.68/0.68 * Partial RF of phase [18,19,20]: 0.68/0.68 - RF of loop [18:1,19:1,20:1]: 0.68/0.68 A-I-1 0.68/0.68 F-I-1 0.68/0.68 0.68/0.68 0.68/0.68 ### Specialization of cost equations lbl31_loop_cont/12 0.68/0.68 * CE 10 is refined into CE [27] 0.68/0.68 * CE 11 is refined into CE [28] 0.68/0.68 0.68/0.68 0.68/0.68 ### Cost equations --> "Loop" of lbl31_loop_cont/12 0.68/0.68 * CEs [27] --> Loop 26 0.68/0.68 * CEs [28] --> Loop 27 0.68/0.68 0.68/0.68 ### Ranking functions of CR lbl31_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 0.68/0.68 0.68/0.68 #### Partial ranking functions of CR lbl31_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 0.68/0.68 0.68/0.68 0.68/0.68 ### Specialization of cost equations start/11 0.68/0.68 * CE 3 is refined into CE [29,30,31,32,33,34] 0.68/0.68 * CE 2 is refined into CE [35] 0.68/0.68 0.68/0.68 0.68/0.68 ### Cost equations --> "Loop" of start/11 0.68/0.68 * CEs [30,32,33,34] --> Loop 28 0.68/0.68 * CEs [29] --> Loop 29 0.68/0.68 * CEs [35] --> Loop 30 0.68/0.68 * CEs [31] --> Loop 31 0.68/0.68 0.68/0.68 ### Ranking functions of CR start(A,B,C,D,E,F,G,H,I,J,L) 0.68/0.68 0.68/0.68 #### Partial ranking functions of CR start(A,B,C,D,E,F,G,H,I,J,L) 0.68/0.68 0.68/0.68 0.68/0.68 ### Specialization of cost equations start0/11 0.68/0.68 * CE 1 is refined into CE [36,37,38,39] 0.68/0.68 0.68/0.68 0.68/0.68 ### Cost equations --> "Loop" of start0/11 0.68/0.68 * CEs [39] --> Loop 32 0.68/0.68 * CEs [38] --> Loop 33 0.68/0.68 * CEs [37] --> Loop 34 0.68/0.68 * CEs [36] --> Loop 35 0.68/0.68 0.68/0.68 ### Ranking functions of CR start0(A,B,C,D,E,F,G,H,I,J,L) 0.68/0.68 0.68/0.68 #### Partial ranking functions of CR start0(A,B,C,D,E,F,G,H,I,J,L) 0.68/0.68 0.68/0.68 0.68/0.68 Computing Bounds 0.68/0.68 ===================================== 0.68/0.68 0.68/0.68 #### Cost of chains of lbl43(A,D,F,G,I,L,M,N): 0.68/0.68 * Chain [[15],17]: 1*it(15)+0 0.68/0.68 Such that:it(15) =< G-M 0.68/0.68 0.68/0.68 with precondition: [L=2,A=F,I+1=N,M+1>=0,I>=G+2,A>=I+1,G>=M+1] 0.68/0.68 0.68/0.68 * Chain [[15],16]: 1*it(15)+0 0.68/0.68 Such that:it(15) =< G+1 0.68/0.68 0.68/0.68 with precondition: [L=3,A=F,G>=0,I>=G+2,A>=I+1] 0.68/0.68 0.68/0.68 * Chain [17]: 0 0.68/0.68 with precondition: [L=2,F=A,G=M,I+1=N,G+1>=0,I>=G+2,F>=I+1] 0.68/0.68 0.68/0.68 * Chain [16]: 0 0.68/0.68 with precondition: [L=3,F=A,G+1>=0,I>=G+2,F>=I+1] 0.68/0.68 0.68/0.68 0.68/0.68 #### Cost of chains of lbl31(A,B,D,F,G,I,L,M,N,O,P): 0.68/0.68 * Chain [[18,19,20],25]: 3*it(18)+1*s(3)+0 0.68/0.68 Such that:aux(1) =< F 0.68/0.68 aux(6) =< F-I 0.68/0.68 it(18) =< aux(6) 0.68/0.68 s(3) =< it(18)*aux(1) 0.68/0.68 0.68/0.68 with precondition: [L=3,A=F,I>=1,A>=I+2] 0.68/0.68 0.68/0.68 * Chain [[18,19,20],24]: 3*it(18)+1*s(3)+1*s(4)+0 0.68/0.68 Such that:aux(7) =< F 0.68/0.68 aux(8) =< F-I 0.68/0.68 s(4) =< aux(7) 0.68/0.68 it(18) =< aux(8) 0.68/0.68 s(3) =< it(18)*aux(7) 0.68/0.68 0.68/0.68 with precondition: [L=3,A=F,I>=1,A>=I+2] 0.68/0.68 0.68/0.68 * Chain [[18,19,20],23]: 3*it(18)+1*s(3)+0 0.68/0.68 Such that:aux(1) =< P 0.68/0.68 aux(9) =< -I+P 0.68/0.68 it(18) =< aux(9) 0.68/0.68 s(3) =< it(18)*aux(1) 0.68/0.68 0.68/0.68 with precondition: [L=4,A=F,A=N+1,A=O+2,A=P,I>=1,A>=I+2] 0.68/0.68 0.68/0.68 * Chain [[18,19,20],22]: 3*it(18)+1*s(3)+0 0.68/0.68 Such that:aux(1) =< P 0.68/0.68 aux(10) =< -I+P 0.68/0.68 it(18) =< aux(10) 0.68/0.68 s(3) =< it(18)*aux(1) 0.68/0.68 0.68/0.68 with precondition: [L=4,A=F,A=N+1,A=O+3,A=P,I>=1,A>=I+2] 0.68/0.68 0.68/0.68 * Chain [[18,19,20],21]: 3*it(18)+1*s(3)+1*s(5)+0 0.68/0.68 Such that:aux(11) =< A 0.68/0.68 aux(12) =< A-I 0.68/0.68 s(5) =< aux(11) 0.68/0.68 it(18) =< aux(12) 0.68/0.68 s(3) =< it(18)*aux(11) 0.68/0.68 0.68/0.68 with precondition: [L=4,A=F,A=N+1,A=P,I>=1,O+1>=0,A>=I+2,A>=O+4] 0.68/0.68 0.68/0.68 * Chain [25]: 0 0.68/0.68 with precondition: [L=3,F=A,I>=1,F>=I+1] 0.68/0.68 0.68/0.68 * Chain [23]: 0 0.68/0.68 with precondition: [L=4,F=A,M=B,F=I+1,F=N+1,F=O+2,F=P,F>=2] 0.68/0.68 0.68/0.68 0.68/0.68 #### Cost of chains of lbl31_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): 0.68/0.68 * Chain [27]: 0 0.68/0.68 with precondition: [A=3,G=B,G>=2] 0.68/0.68 0.68/0.68 * Chain [26]: 0 0.68/0.68 with precondition: [A=4,G=B,G>=2] 0.68/0.68 0.68/0.68 0.68/0.68 #### Cost of chains of start(A,B,C,D,E,F,G,H,I,J,L): 0.68/0.68 * Chain [31]: 0 0.68/0.68 with precondition: [A=2,F=2,C=B,E=D,H=G,J=I] 0.68/0.68 0.68/0.68 * Chain [30]: 0 0.68/0.69 with precondition: [F=A,C=B,E=D,H=G,J=I,1>=F] 0.68/0.69 0.68/0.69 * Chain [29]: 0 0.68/0.69 with precondition: [F=A,C=B,E=D,H=G,J=I,F>=2] 0.68/0.69 0.68/0.69 * Chain [28]: 17*s(17)+5*s(19)+0 0.68/0.69 Such that:aux(19) =< F 0.68/0.69 s(17) =< aux(19) 0.68/0.69 s(19) =< s(17)*aux(19) 0.68/0.69 0.68/0.69 with precondition: [F=A,C=B,E=D,H=G,J=I,F>=3] 0.68/0.69 0.68/0.69 0.68/0.69 #### Cost of chains of start0(A,B,C,D,E,F,G,H,I,J,L): 0.68/0.69 * Chain [35]: 0 0.68/0.69 with precondition: [A=2] 0.68/0.69 0.68/0.69 * Chain [34]: 0 0.68/0.69 with precondition: [1>=A] 0.68/0.69 0.68/0.69 * Chain [33]: 0 0.68/0.69 with precondition: [A>=2] 0.68/0.69 0.68/0.69 * Chain [32]: 17*s(34)+5*s(35)+0 0.68/0.69 Such that:s(33) =< A 0.68/0.69 s(34) =< s(33) 0.68/0.69 s(35) =< s(34)*s(33) 0.68/0.69 0.68/0.69 with precondition: [A>=3] 0.68/0.69 0.68/0.69 0.68/0.69 Closed-form bounds of start0(A,B,C,D,E,F,G,H,I,J,L): 0.68/0.69 ------------------------------------- 0.68/0.69 * Chain [35] with precondition: [A=2] 0.68/0.69 - Upper bound: 0 0.68/0.69 - Complexity: constant 0.68/0.69 * Chain [34] with precondition: [1>=A] 0.68/0.69 - Upper bound: 0 0.68/0.69 - Complexity: constant 0.68/0.69 * Chain [33] with precondition: [A>=2] 0.68/0.69 - Upper bound: 0 0.68/0.69 - Complexity: constant 0.68/0.69 * Chain [32] with precondition: [A>=3] 0.68/0.69 - Upper bound: 5*A*A+17*A 0.68/0.69 - Complexity: n^2 0.68/0.69 0.68/0.69 ### Maximum cost of start0(A,B,C,D,E,F,G,H,I,J,L): nat(A)*5*nat(A)+nat(A)*17 0.68/0.69 Asymptotic class: n^2 0.68/0.69 * Total analysis performed in 588 ms. 0.68/0.69 0.69/0.79 EOF