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