0.05/0.46 WORST_CASE(?,O(n^2)) 0.05/0.46 0.05/0.46 Preprocessing Cost Relations 0.05/0.46 ===================================== 0.05/0.46 0.05/0.46 #### Computed strongly connected components 0.05/0.46 0. recursive : [eval_abc_bb2_in/4,eval_abc_bb3_in/4] 0.05/0.46 1. recursive : [eval_abc_11/10,eval_abc_12/10,eval_abc_bb1_in/10,eval_abc_bb2_in_loop_cont/11,eval_abc_bb4_in/10] 0.05/0.46 2. non_recursive : [eval_abc_stop/8] 0.05/0.46 3. non_recursive : [eval_abc_bb5_in/8] 0.05/0.46 4. non_recursive : [exit_location/1] 0.05/0.46 5. non_recursive : [eval_abc_bb1_in_loop_cont/9] 0.05/0.46 6. non_recursive : [eval_abc_7/8] 0.05/0.46 7. non_recursive : [eval_abc_6/8] 0.05/0.46 8. non_recursive : [eval_abc_5/8] 0.05/0.46 9. non_recursive : [eval_abc_4/8] 0.05/0.46 10. non_recursive : [eval_abc_3/8] 0.05/0.46 11. non_recursive : [eval_abc_2/8] 0.05/0.46 12. non_recursive : [eval_abc_1/8] 0.05/0.46 13. non_recursive : [eval_abc_0/8] 0.05/0.46 14. non_recursive : [eval_abc_bb0_in/8] 0.05/0.46 15. non_recursive : [eval_abc_start/8] 0.05/0.46 0.05/0.46 #### Obtained direct recursion through partial evaluation 0.05/0.46 0. SCC is partially evaluated into eval_abc_bb2_in/4 0.05/0.46 1. SCC is partially evaluated into eval_abc_bb1_in/10 0.05/0.46 2. SCC is completely evaluated into other SCCs 0.05/0.46 3. SCC is completely evaluated into other SCCs 0.05/0.46 4. SCC is completely evaluated into other SCCs 0.05/0.46 5. SCC is partially evaluated into eval_abc_bb1_in_loop_cont/9 0.05/0.46 6. SCC is partially evaluated into eval_abc_7/8 0.05/0.46 7. SCC is completely evaluated into other SCCs 0.05/0.46 8. SCC is completely evaluated into other SCCs 0.05/0.46 9. SCC is completely evaluated into other SCCs 0.05/0.46 10. SCC is completely evaluated into other SCCs 0.05/0.46 11. SCC is completely evaluated into other SCCs 0.05/0.46 12. SCC is completely evaluated into other SCCs 0.05/0.46 13. SCC is completely evaluated into other SCCs 0.05/0.46 14. SCC is completely evaluated into other SCCs 0.05/0.46 15. SCC is partially evaluated into eval_abc_start/8 0.05/0.46 0.05/0.46 Control-Flow Refinement of Cost Relations 0.05/0.46 ===================================== 0.05/0.46 0.05/0.46 ### Specialization of cost equations eval_abc_bb2_in/4 0.05/0.46 * CE 11 is refined into CE [12] 0.05/0.46 * CE 10 is refined into CE [13] 0.05/0.46 * CE 9 is refined into CE [14] 0.05/0.46 0.05/0.46 0.05/0.46 ### Cost equations --> "Loop" of eval_abc_bb2_in/4 0.05/0.46 * CEs [14] --> Loop 12 0.05/0.46 * CEs [12] --> Loop 13 0.05/0.46 * CEs [13] --> Loop 14 0.05/0.46 0.05/0.46 ### Ranking functions of CR eval_abc_bb2_in(V_d,V_j_0,B,C) 0.05/0.46 * RF of phase [12]: [V_d-V_j_0+1] 0.05/0.46 0.05/0.46 #### Partial ranking functions of CR eval_abc_bb2_in(V_d,V_j_0,B,C) 0.05/0.46 * Partial RF of phase [12]: 0.05/0.46 - RF of loop [12:1]: 0.05/0.46 V_d-V_j_0+1 0.05/0.46 0.05/0.46 0.05/0.46 ### Specialization of cost equations eval_abc_bb1_in/10 0.05/0.46 * CE 5 is refined into CE [15] 0.05/0.46 * CE 3 is refined into CE [16,17] 0.05/0.46 * CE 6 is refined into CE [18] 0.05/0.46 * CE 4 is refined into CE [19,20] 0.05/0.46 0.05/0.46 0.05/0.46 ### Cost equations --> "Loop" of eval_abc_bb1_in/10 0.05/0.46 * CEs [20] --> Loop 15 0.05/0.46 * CEs [19] --> Loop 16 0.05/0.46 * CEs [15] --> Loop 17 0.05/0.46 * CEs [16] --> Loop 18 0.05/0.46 * CEs [17] --> Loop 19 0.05/0.46 * CEs [18] --> Loop 20 0.05/0.46 0.05/0.46 ### Ranking functions of CR eval_abc_bb1_in(V_3,V_b,V_c,V_d,V_i_0,V_j_0,B,C,D,E) 0.05/0.46 * RF of phase [15]: [V_b-V_i_0+1] 0.05/0.46 * RF of phase [16]: [V_b-V_i_0+1] 0.05/0.46 0.05/0.46 #### Partial ranking functions of CR eval_abc_bb1_in(V_3,V_b,V_c,V_d,V_i_0,V_j_0,B,C,D,E) 0.05/0.46 * Partial RF of phase [15]: 0.05/0.46 - RF of loop [15:1]: 0.05/0.46 V_b-V_i_0+1 0.05/0.46 * Partial RF of phase [16]: 0.05/0.46 - RF of loop [16:1]: 0.05/0.46 V_b-V_i_0+1 0.05/0.46 0.05/0.46 0.05/0.46 ### Specialization of cost equations eval_abc_bb1_in_loop_cont/9 0.05/0.46 * CE 7 is refined into CE [21] 0.05/0.46 * CE 8 is refined into CE [22] 0.05/0.46 0.05/0.46 0.05/0.46 ### Cost equations --> "Loop" of eval_abc_bb1_in_loop_cont/9 0.05/0.46 * CEs [21] --> Loop 21 0.05/0.46 * CEs [22] --> Loop 22 0.05/0.46 0.05/0.46 ### Ranking functions of CR eval_abc_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.05/0.46 0.05/0.46 #### Partial ranking functions of CR eval_abc_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.05/0.46 0.05/0.46 0.05/0.46 ### Specialization of cost equations eval_abc_7/8 0.05/0.46 * CE 2 is refined into CE [23,24,25,26,27,28,29,30,31] 0.05/0.46 0.05/0.46 0.05/0.46 ### Cost equations --> "Loop" of eval_abc_7/8 0.05/0.46 * CEs [29] --> Loop 23 0.05/0.46 * CEs [27] --> Loop 24 0.05/0.46 * CEs [25] --> Loop 25 0.05/0.46 * CEs [26,30] --> Loop 26 0.05/0.46 * CEs [24,31] --> Loop 27 0.05/0.46 * CEs [28] --> Loop 28 0.05/0.46 * CEs [23] --> Loop 29 0.05/0.46 0.05/0.46 ### Ranking functions of CR eval_abc_7(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B) 0.05/0.46 0.05/0.46 #### Partial ranking functions of CR eval_abc_7(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B) 0.05/0.46 0.05/0.46 0.05/0.46 ### Specialization of cost equations eval_abc_start/8 0.05/0.46 * CE 1 is refined into CE [32,33,34,35,36,37,38] 0.05/0.46 0.05/0.46 0.05/0.46 ### Cost equations --> "Loop" of eval_abc_start/8 0.05/0.46 * CEs [38] --> Loop 30 0.05/0.46 * CEs [37] --> Loop 31 0.05/0.46 * CEs [36] --> Loop 32 0.05/0.46 * CEs [35] --> Loop 33 0.05/0.46 * CEs [34] --> Loop 34 0.05/0.46 * CEs [33] --> Loop 35 0.05/0.46 * CEs [32] --> Loop 36 0.05/0.46 0.05/0.46 ### Ranking functions of CR eval_abc_start(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B) 0.05/0.46 0.05/0.46 #### Partial ranking functions of CR eval_abc_start(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B) 0.05/0.46 0.05/0.46 0.05/0.46 Computing Bounds 0.05/0.46 ===================================== 0.05/0.46 0.05/0.46 #### Cost of chains of eval_abc_bb2_in(V_d,V_j_0,B,C): 0.05/0.46 * Chain [[12],14]: 1*it(12)+0 0.05/0.46 Such that:it(12) =< V_d-V_j_0+1 0.05/0.46 0.05/0.46 with precondition: [B=2,V_d+1=C,V_d>=V_j_0] 0.05/0.46 0.05/0.46 * Chain [[12],13]: 1*it(12)+0 0.05/0.46 Such that:it(12) =< V_d-V_j_0+1 0.05/0.46 0.05/0.46 with precondition: [B=3,V_d>=V_j_0] 0.05/0.46 0.05/0.46 * Chain [14]: 0 0.05/0.46 with precondition: [B=2,V_j_0=C,V_j_0>=V_d+1] 0.05/0.46 0.05/0.46 * Chain [13]: 0 0.05/0.46 with precondition: [B=3] 0.05/0.46 0.05/0.46 0.05/0.46 #### Cost of chains of eval_abc_bb1_in(V_3,V_b,V_c,V_d,V_i_0,V_j_0,B,C,D,E): 0.05/0.46 * Chain [[16],20]: 1*it(16)+1*s(3)+0 0.05/0.46 Such that:it(16) =< V_b-V_i_0+1 0.05/0.46 aux(1) =< -V_c+V_d+1 0.05/0.46 s(3) =< it(16)*aux(1) 0.05/0.46 0.05/0.46 with precondition: [B=3,V_d>=V_c,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [[16],19]: 1*it(16)+1*s(3)+1*s(4)+0 0.05/0.46 Such that:it(16) =< V_b-V_i_0 0.05/0.46 aux(2) =< -V_c+V_d+1 0.05/0.46 s(4) =< aux(2) 0.05/0.46 s(3) =< it(16)*aux(2) 0.05/0.46 0.05/0.46 with precondition: [B=3,V_d>=V_c,V_b>=V_i_0+1] 0.05/0.46 0.05/0.46 * Chain [[16],18]: 1*it(16)+1*s(3)+0 0.05/0.46 Such that:it(16) =< V_b-V_i_0 0.05/0.46 aux(1) =< -V_c+V_d+1 0.05/0.46 s(3) =< it(16)*aux(1) 0.05/0.46 0.05/0.46 with precondition: [B=3,V_d>=V_c,V_b>=V_i_0+1] 0.05/0.46 0.05/0.46 * Chain [[16],17]: 1*it(16)+1*s(3)+0 0.05/0.46 Such that:it(16) =< V_b-V_i_0+1 0.05/0.46 aux(1) =< -V_c+E 0.05/0.46 s(3) =< it(16)*aux(1) 0.05/0.46 0.05/0.46 with precondition: [B=4,V_b+1=C,V_b+1=D,V_d+1=E,V_d>=V_c,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [[15],20]: 1*it(15)+0 0.05/0.46 Such that:it(15) =< V_b-V_i_0+1 0.05/0.46 0.05/0.46 with precondition: [B=3,V_c>=V_d+1,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [[15],18]: 1*it(15)+0 0.05/0.46 Such that:it(15) =< V_b-V_i_0 0.05/0.46 0.05/0.46 with precondition: [B=3,V_c>=V_d+1,V_b>=V_i_0+1] 0.05/0.46 0.05/0.46 * Chain [[15],17]: 1*it(15)+0 0.05/0.46 Such that:it(15) =< V_b-V_i_0+1 0.05/0.46 0.05/0.46 with precondition: [B=4,V_b+1=C,V_b+1=D,V_c=E,V_c>=V_d+1,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [20]: 0 0.05/0.46 with precondition: [B=3] 0.05/0.46 0.05/0.46 * Chain [19]: 1*s(4)+0 0.05/0.46 Such that:s(4) =< -V_c+V_d+1 0.05/0.46 0.05/0.46 with precondition: [B=3,V_d>=V_c,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [18]: 0 0.05/0.46 with precondition: [B=3,V_b>=V_i_0] 0.05/0.46 0.05/0.46 * Chain [17]: 0 0.05/0.46 with precondition: [B=4,C=V_3,E=V_j_0,V_i_0=D,V_i_0>=V_b+1] 0.05/0.46 0.05/0.46 0.05/0.46 #### Cost of chains of eval_abc_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I): 0.05/0.46 * Chain [22]: 0 0.05/0.46 with precondition: [A=3] 0.05/0.46 0.05/0.46 * Chain [21]: 0 0.05/0.46 with precondition: [A=4] 0.05/0.46 0.05/0.46 0.05/0.46 #### Cost of chains of eval_abc_7(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B): 0.05/0.46 * Chain [29]: 0 0.05/0.46 with precondition: [] 0.05/0.46 0.05/0.46 * Chain [28]: 0 0.05/0.46 with precondition: [V_b>=V_a] 0.05/0.46 0.05/0.46 * Chain [27]: 2*s(16)+1*s(18)+2*s(19)+0 0.05/0.46 Such that:aux(6) =< -V_a+V_b+1 0.05/0.46 aux(7) =< -V_c+V_d+1 0.05/0.46 s(16) =< aux(6) 0.05/0.46 s(18) =< aux(7) 0.05/0.46 s(19) =< s(16)*aux(7) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a,V_d>=V_c] 0.05/0.46 0.05/0.46 * Chain [26]: 2*s(23)+0 0.05/0.46 Such that:aux(8) =< -V_a+V_b+1 0.05/0.46 s(23) =< aux(8) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.46 0.05/0.46 * Chain [25]: 2*s(27)+2*s(28)+1*s(29)+0 0.05/0.46 Such that:s(25) =< -V_a+V_b 0.05/0.46 s(26) =< -V_c+V_d+1 0.05/0.46 s(27) =< s(25) 0.05/0.46 s(28) =< s(27)*s(26) 0.05/0.46 s(29) =< s(26) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a+1,V_d>=V_c] 0.05/0.46 0.05/0.46 * Chain [24]: 1*s(30)+0 0.05/0.46 Such that:s(30) =< -V_a+V_b 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a+1,V_c>=V_d+1] 0.05/0.46 0.05/0.46 * Chain [23]: 0 0.05/0.46 with precondition: [V_a>=V_b+1] 0.05/0.46 0.05/0.46 0.05/0.46 #### Cost of chains of eval_abc_start(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B): 0.05/0.46 * Chain [36]: 0 0.05/0.46 with precondition: [] 0.05/0.46 0.05/0.46 * Chain [35]: 0 0.05/0.46 with precondition: [V_b>=V_a] 0.05/0.46 0.05/0.46 * Chain [34]: 2*s(33)+1*s(34)+2*s(35)+0 0.05/0.46 Such that:s(31) =< -V_a+V_b+1 0.05/0.46 s(32) =< -V_c+V_d+1 0.05/0.46 s(33) =< s(31) 0.05/0.46 s(34) =< s(32) 0.05/0.46 s(35) =< s(33)*s(32) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a,V_d>=V_c] 0.05/0.46 0.05/0.46 * Chain [33]: 2*s(37)+0 0.05/0.46 Such that:s(36) =< -V_a+V_b+1 0.05/0.46 s(37) =< s(36) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.46 0.05/0.46 * Chain [32]: 2*s(40)+2*s(41)+1*s(42)+0 0.05/0.46 Such that:s(38) =< -V_a+V_b 0.05/0.46 s(39) =< -V_c+V_d+1 0.05/0.46 s(40) =< s(38) 0.05/0.46 s(41) =< s(40)*s(39) 0.05/0.46 s(42) =< s(39) 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a+1,V_d>=V_c] 0.05/0.46 0.05/0.46 * Chain [31]: 1*s(43)+0 0.05/0.46 Such that:s(43) =< -V_a+V_b 0.05/0.46 0.05/0.46 with precondition: [V_b>=V_a+1,V_c>=V_d+1] 0.05/0.46 0.05/0.46 * Chain [30]: 0 0.05/0.46 with precondition: [V_a>=V_b+1] 0.05/0.46 0.05/0.46 0.05/0.46 Closed-form bounds of eval_abc_start(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B): 0.05/0.46 ------------------------------------- 0.05/0.46 * Chain [36] with precondition: [] 0.05/0.46 - Upper bound: 0 0.05/0.46 - Complexity: constant 0.05/0.46 * Chain [35] with precondition: [V_b>=V_a] 0.05/0.46 - Upper bound: 0 0.05/0.46 - Complexity: constant 0.05/0.46 * Chain [34] with precondition: [V_b>=V_a,V_d>=V_c] 0.05/0.46 - Upper bound: -2*V_a+2*V_b+2+(-2*V_a+2*V_b+2)*(-V_c+V_d+1)+(-V_c+V_d+1) 0.05/0.46 - Complexity: n^2 0.05/0.46 * Chain [33] with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.46 - Upper bound: -2*V_a+2*V_b+2 0.05/0.46 - Complexity: n 0.05/0.46 * Chain [32] with precondition: [V_b>=V_a+1,V_d>=V_c] 0.05/0.46 - Upper bound: -2*V_a+2*V_b+(-V_c+V_d+1)*(-2*V_a+2*V_b)+(-V_c+V_d+1) 0.05/0.46 - Complexity: n^2 0.05/0.46 * Chain [31] with precondition: [V_b>=V_a+1,V_c>=V_d+1] 0.05/0.46 - Upper bound: -V_a+V_b 0.05/0.46 - Complexity: n 0.05/0.46 * Chain [30] with precondition: [V_a>=V_b+1] 0.05/0.46 - Upper bound: 0 0.05/0.46 - Complexity: constant 0.05/0.46 0.05/0.46 ### Maximum cost of eval_abc_start(V_3,V_a,V_b,V_c,V_d,V_i_0,V_j_0,B): max([nat(-V_a+V_b+1)*2*nat(-V_c+V_d+1)+nat(-V_c+V_d+1)+nat(-V_a+V_b+1)*2,nat(-V_a+V_b)*2*nat(-V_c+V_d+1)+nat(-V_a+V_b)+nat(-V_c+V_d+1)+nat(-V_a+V_b)]) 0.05/0.46 Asymptotic class: n^2 0.05/0.46 * Total analysis performed in 374 ms. 0.05/0.46 0.05/0.56 EOF