0.03/0.46 WORST_CASE(?,O(n^2)) 0.03/0.46 0.03/0.46 Preprocessing Cost Relations 0.03/0.46 ===================================== 0.03/0.46 0.03/0.46 #### Computed strongly connected components 0.03/0.46 0. recursive : [evalperfectbb3in/4,evalperfectbb4in/4] 0.03/0.46 1. recursive : [evalperfectbb4in_loop_cont/10,evalperfectbb5in/9,evalperfectbb8in/9] 0.03/0.46 2. non_recursive : [evalperfectstop/5] 0.03/0.46 3. non_recursive : [evalperfectreturnin/5] 0.03/0.46 4. non_recursive : [evalperfectbb9in/5] 0.03/0.46 5. non_recursive : [exit_location/1] 0.03/0.46 6. non_recursive : [evalperfectbb8in_loop_cont/6] 0.03/0.46 7. non_recursive : [evalperfectbb1in/5] 0.03/0.46 8. non_recursive : [evalperfectentryin/5] 0.03/0.46 9. non_recursive : [evalperfectstart/5] 0.03/0.46 0.03/0.46 #### Obtained direct recursion through partial evaluation 0.03/0.46 0. SCC is partially evaluated into evalperfectbb4in/4 0.03/0.46 1. SCC is partially evaluated into evalperfectbb8in/9 0.03/0.46 2. SCC is completely evaluated into other SCCs 0.03/0.46 3. SCC is completely evaluated into other SCCs 0.03/0.46 4. SCC is partially evaluated into evalperfectbb9in/5 0.03/0.46 5. SCC is completely evaluated into other SCCs 0.03/0.46 6. SCC is partially evaluated into evalperfectbb8in_loop_cont/6 0.03/0.46 7. SCC is partially evaluated into evalperfectbb1in/5 0.03/0.46 8. SCC is partially evaluated into evalperfectentryin/5 0.03/0.46 9. SCC is partially evaluated into evalperfectstart/5 0.03/0.46 0.03/0.46 Control-Flow Refinement of Cost Relations 0.03/0.46 ===================================== 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectbb4in/4 0.03/0.46 * CE 15 is refined into CE [19] 0.03/0.46 * CE 14 is refined into CE [20] 0.03/0.46 * CE 13 is refined into CE [21] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectbb4in/4 0.03/0.46 * CEs [21] --> Loop 19 0.03/0.46 * CEs [19] --> Loop 20 0.03/0.46 * CEs [20] --> Loop 21 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectbb4in(C,D,E,F) 0.03/0.46 * RF of phase [19]: [-C+D+1,D] 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectbb4in(C,D,E,F) 0.03/0.46 * Partial RF of phase [19]: 0.03/0.46 - RF of loop [19:1]: 0.03/0.46 -C+D+1 0.03/0.46 D 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectbb8in/9 0.03/0.46 * CE 9 is refined into CE [22] 0.03/0.46 * CE 8 is refined into CE [23,24] 0.03/0.46 * CE 10 is refined into CE [25] 0.03/0.46 * CE 5 is refined into CE [26] 0.03/0.46 * CE 6 is discarded (unfeasible) 0.03/0.46 * CE 7 is refined into CE [27] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectbb8in/9 0.03/0.46 * CEs [26] --> Loop 22 0.03/0.46 * CEs [27] --> Loop 23 0.03/0.46 * CEs [22] --> Loop 24 0.03/0.46 * CEs [23,24] --> Loop 25 0.03/0.46 * CEs [25] --> Loop 26 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectbb8in(A,B,C,D,E,F,G,H,I) 0.03/0.46 * RF of phase [22,23]: [C] 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectbb8in(A,B,C,D,E,F,G,H,I) 0.03/0.46 * Partial RF of phase [22,23]: 0.03/0.46 - RF of loop [22:1]: 0.03/0.46 C-1 0.03/0.46 - RF of loop [23:1]: 0.03/0.46 C 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectbb9in/5 0.03/0.46 * CE 17 is refined into CE [28] 0.03/0.46 * CE 16 is refined into CE [29] 0.03/0.46 * CE 18 is refined into CE [30] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectbb9in/5 0.03/0.46 * CEs [28] --> Loop 27 0.03/0.46 * CEs [29] --> Loop 28 0.03/0.46 * CEs [30] --> Loop 29 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectbb9in(A,B,C,D,E) 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectbb9in(A,B,C,D,E) 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectbb8in_loop_cont/6 0.03/0.46 * CE 11 is refined into CE [31,32,33] 0.03/0.46 * CE 12 is refined into CE [34] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectbb8in_loop_cont/6 0.03/0.46 * CEs [33] --> Loop 30 0.03/0.46 * CEs [32] --> Loop 31 0.03/0.46 * CEs [31] --> Loop 32 0.03/0.46 * CEs [34] --> Loop 33 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectbb8in_loop_cont(A,B,C,D,E,F) 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectbb8in_loop_cont(A,B,C,D,E,F) 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectbb1in/5 0.03/0.46 * CE 4 is refined into CE [35,36,37,38,39,40] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectbb1in/5 0.03/0.46 * CEs [37] --> Loop 34 0.03/0.46 * CEs [35,36,38,39,40] --> Loop 35 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectbb1in(A,B,C,D,E) 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectbb1in(A,B,C,D,E) 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectentryin/5 0.03/0.46 * CE 3 is refined into CE [41,42] 0.03/0.46 * CE 2 is refined into CE [43] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectentryin/5 0.03/0.46 * CEs [42] --> Loop 36 0.03/0.46 * CEs [41] --> Loop 37 0.03/0.46 * CEs [43] --> Loop 38 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectentryin(A,B,C,D,E) 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectentryin(A,B,C,D,E) 0.03/0.46 0.03/0.46 0.03/0.46 ### Specialization of cost equations evalperfectstart/5 0.03/0.46 * CE 1 is refined into CE [44,45,46] 0.03/0.46 0.03/0.46 0.03/0.46 ### Cost equations --> "Loop" of evalperfectstart/5 0.03/0.46 * CEs [46] --> Loop 39 0.03/0.46 * CEs [45] --> Loop 40 0.03/0.46 * CEs [44] --> Loop 41 0.03/0.46 0.03/0.46 ### Ranking functions of CR evalperfectstart(A,B,C,D,E) 0.03/0.46 0.03/0.46 #### Partial ranking functions of CR evalperfectstart(A,B,C,D,E) 0.03/0.46 0.03/0.46 0.03/0.46 Computing Bounds 0.03/0.46 ===================================== 0.03/0.46 0.03/0.46 #### Cost of chains of evalperfectbb4in(C,D,E,F): 0.03/0.46 * Chain [[19],21]: 1*it(19)+0 0.03/0.46 Such that:it(19) =< -C+D+1 0.03/0.46 0.03/0.46 with precondition: [E=2,F>=0,C>=F+1,D>=C+F] 0.03/0.46 0.03/0.46 * Chain [[19],20]: 1*it(19)+0 0.03/0.46 Such that:it(19) =< -C+D+1 0.03/0.46 0.03/0.46 with precondition: [E=3,C>=1,D>=C] 0.03/0.46 0.03/0.46 * Chain [20]: 0 0.03/0.46 with precondition: [E=3,C>=1] 0.03/0.46 0.03/0.46 0.03/0.46 #### Cost of chains of evalperfectbb8in(A,B,C,D,E,F,G,H,I): 0.03/0.46 * Chain [[22,23],26]: 2*it(22)+1*s(5)+1*s(6)+0 0.03/0.46 Such that:aux(1) =< A 0.03/0.46 aux(5) =< C 0.03/0.46 it(22) =< aux(5) 0.03/0.46 aux(2) =< aux(1) 0.03/0.46 s(5) =< it(22)*aux(1) 0.03/0.46 s(6) =< it(22)*aux(2) 0.03/0.46 0.03/0.46 with precondition: [E=3,C>=1,A>=B,A>=C+1] 0.03/0.46 0.03/0.46 * Chain [[22,23],25]: 2*it(22)+1*s(5)+1*s(6)+1*s(7)+0 0.03/0.46 Such that:aux(6) =< A 0.03/0.46 aux(7) =< C 0.03/0.46 s(7) =< aux(6) 0.03/0.46 it(22) =< aux(7) 0.03/0.46 aux(2) =< aux(6) 0.03/0.46 s(5) =< it(22)*aux(6) 0.03/0.46 s(6) =< it(22)*aux(2) 0.03/0.46 0.03/0.46 with precondition: [E=3,C>=2,A>=B,A>=C+1] 0.03/0.46 0.03/0.46 * Chain [[22,23],24]: 2*it(22)+1*s(5)+1*s(6)+0 0.03/0.46 Such that:aux(1) =< A 0.03/0.46 aux(8) =< C 0.03/0.46 it(22) =< aux(8) 0.03/0.46 aux(2) =< aux(1) 0.03/0.46 s(5) =< it(22)*aux(1) 0.03/0.46 s(6) =< it(22)*aux(2) 0.03/0.46 0.03/0.46 with precondition: [E=4,H=0,I=0,F=G,C>=1,A>=B,A>=C+1,B>=F+1] 0.03/0.46 0.03/0.46 * Chain [26]: 0 0.03/0.46 with precondition: [E=3,A>=2,A>=B,A>=C+1,A+C>=B+1] 0.03/0.46 0.03/0.46 * Chain [25]: 1*s(7)+0 0.03/0.46 Such that:s(7) =< A-C+1 0.03/0.46 0.03/0.46 with precondition: [E=3,C>=1,A>=B,A>=C+1] 0.03/0.46 0.03/0.47 0.03/0.47 #### Cost of chains of evalperfectbb9in(A,B,C,D,E): 0.03/0.47 * Chain [29]: 0 0.03/0.47 with precondition: [A=0] 0.03/0.47 0.03/0.47 * Chain [28]: 0 0.03/0.47 with precondition: [0>=A+1] 0.03/0.47 0.03/0.47 * Chain [27]: 0 0.03/0.47 with precondition: [A>=1] 0.03/0.47 0.03/0.47 0.03/0.47 #### Cost of chains of evalperfectbb8in_loop_cont(A,B,C,D,E,F): 0.03/0.47 * Chain [33]: 0 0.03/0.47 with precondition: [A=3] 0.03/0.47 0.03/0.47 * Chain [32]: 0 0.03/0.47 with precondition: [A=4,B=0] 0.03/0.47 0.03/0.47 * Chain [31]: 0 0.03/0.47 with precondition: [A=4,0>=B+1] 0.03/0.47 0.03/0.47 * Chain [30]: 0 0.03/0.47 with precondition: [A=4,B>=1] 0.03/0.47 0.03/0.47 0.03/0.47 #### Cost of chains of evalperfectbb1in(A,B,C,D,E): 0.03/0.47 * Chain [35]: 1*s(16)+8*s(18)+4*s(20)+4*s(21)+0 0.03/0.47 Such that:s(16) =< 2 0.03/0.47 aux(13) =< A 0.03/0.47 s(18) =< aux(13) 0.03/0.47 s(19) =< aux(13) 0.03/0.47 s(20) =< s(18)*aux(13) 0.03/0.47 s(21) =< s(18)*s(19) 0.03/0.47 0.03/0.47 with precondition: [A>=2] 0.03/0.47 0.03/0.47 * Chain [34]: 3*s(42)+1*s(45)+1*s(46)+0 0.03/0.47 Such that:aux(14) =< A 0.03/0.47 s(42) =< aux(14) 0.03/0.47 s(44) =< aux(14) 0.03/0.47 s(45) =< s(42)*aux(14) 0.03/0.47 s(46) =< s(42)*s(44) 0.03/0.47 0.03/0.47 with precondition: [A>=3] 0.03/0.47 0.03/0.47 0.03/0.47 #### Cost of chains of evalperfectentryin(A,B,C,D,E): 0.03/0.47 * Chain [38]: 0 0.03/0.47 with precondition: [1>=A] 0.03/0.47 0.03/0.47 * Chain [37]: 1*s(47)+8*s(49)+4*s(51)+4*s(52)+0 0.03/0.47 Such that:s(47) =< 2 0.03/0.47 s(48) =< A 0.03/0.47 s(49) =< s(48) 0.03/0.47 s(50) =< s(48) 0.03/0.47 s(51) =< s(49)*s(48) 0.03/0.47 s(52) =< s(49)*s(50) 0.03/0.47 0.03/0.47 with precondition: [A>=2] 0.03/0.47 0.03/0.47 * Chain [36]: 3*s(54)+1*s(56)+1*s(57)+0 0.03/0.47 Such that:s(53) =< A 0.03/0.47 s(54) =< s(53) 0.03/0.47 s(55) =< s(53) 0.03/0.47 s(56) =< s(54)*s(53) 0.03/0.47 s(57) =< s(54)*s(55) 0.03/0.47 0.03/0.47 with precondition: [A>=3] 0.03/0.47 0.03/0.47 0.03/0.47 #### Cost of chains of evalperfectstart(A,B,C,D,E): 0.03/0.47 * Chain [41]: 0 0.03/0.47 with precondition: [1>=A] 0.03/0.47 0.03/0.47 * Chain [40]: 1*s(58)+8*s(60)+4*s(62)+4*s(63)+0 0.03/0.47 Such that:s(58) =< 2 0.03/0.47 s(59) =< A 0.03/0.47 s(60) =< s(59) 0.03/0.47 s(61) =< s(59) 0.03/0.47 s(62) =< s(60)*s(59) 0.03/0.47 s(63) =< s(60)*s(61) 0.03/0.47 0.03/0.47 with precondition: [A>=2] 0.03/0.47 0.03/0.47 * Chain [39]: 3*s(65)+1*s(67)+1*s(68)+0 0.03/0.47 Such that:s(64) =< A 0.03/0.47 s(65) =< s(64) 0.03/0.47 s(66) =< s(64) 0.03/0.47 s(67) =< s(65)*s(64) 0.03/0.47 s(68) =< s(65)*s(66) 0.03/0.47 0.03/0.47 with precondition: [A>=3] 0.03/0.47 0.03/0.47 0.03/0.47 Closed-form bounds of evalperfectstart(A,B,C,D,E): 0.03/0.47 ------------------------------------- 0.03/0.47 * Chain [41] with precondition: [1>=A] 0.03/0.47 - Upper bound: 0 0.03/0.47 - Complexity: constant 0.03/0.47 * Chain [40] with precondition: [A>=2] 0.03/0.47 - Upper bound: 8*A+2+8*A*A 0.03/0.47 - Complexity: n^2 0.03/0.47 * Chain [39] with precondition: [A>=3] 0.03/0.47 - Upper bound: 2*A*A+3*A 0.03/0.47 - Complexity: n^2 0.03/0.47 0.03/0.47 ### Maximum cost of evalperfectstart(A,B,C,D,E): nat(A)*5+2+nat(A)*6*nat(A)+(nat(A)*2*nat(A)+nat(A)*3) 0.03/0.47 Asymptotic class: n^2 0.03/0.47 * Total analysis performed in 382 ms. 0.03/0.47 0.47/0.57 EOF