0.67/0.68 WORST_CASE(?,O(n^1)) 0.67/0.68 0.67/0.68 Preprocessing Cost Relations 0.67/0.68 ===================================== 0.67/0.68 0.67/0.68 #### Computed strongly connected components 0.67/0.68 0. recursive : [eval_rank2_10/6,eval_rank2_11/6,eval_rank2_bb3_in/6,eval_rank2_bb4_in/6,eval_rank2_bb5_in/6] 0.67/0.68 1. recursive : [eval_rank2_15/15,eval_rank2_16/15,eval_rank2_17/15,eval_rank2_18/15,eval_rank2__critedge_in/15,eval_rank2_bb1_in/15,eval_rank2_bb2_in/15,eval_rank2_bb3_in_loop_cont/16] 0.67/0.68 2. non_recursive : [eval_rank2_stop/9] 0.67/0.68 3. non_recursive : [eval_rank2_bb6_in/9] 0.67/0.68 4. non_recursive : [exit_location/1] 0.67/0.68 5. non_recursive : [eval_rank2_bb1_in_loop_cont/10] 0.67/0.68 6. non_recursive : [eval_rank2_6/9] 0.67/0.68 7. non_recursive : [eval_rank2_5/9] 0.67/0.68 8. non_recursive : [eval_rank2_4/9] 0.67/0.68 9. non_recursive : [eval_rank2_3/9] 0.67/0.68 10. non_recursive : [eval_rank2_2/9] 0.67/0.68 11. non_recursive : [eval_rank2_1/9] 0.67/0.68 12. non_recursive : [eval_rank2_0/9] 0.67/0.68 13. non_recursive : [eval_rank2_bb0_in/9] 0.67/0.68 14. non_recursive : [eval_rank2_start/9] 0.67/0.68 0.67/0.68 #### Obtained direct recursion through partial evaluation 0.67/0.68 0. SCC is partially evaluated into eval_rank2_bb3_in/6 0.67/0.68 1. SCC is partially evaluated into eval_rank2_bb1_in/15 0.67/0.68 2. SCC is completely evaluated into other SCCs 0.67/0.68 3. SCC is completely evaluated into other SCCs 0.67/0.68 4. SCC is completely evaluated into other SCCs 0.67/0.68 5. SCC is partially evaluated into eval_rank2_bb1_in_loop_cont/10 0.67/0.68 6. SCC is partially evaluated into eval_rank2_6/9 0.67/0.68 7. SCC is completely evaluated into other SCCs 0.67/0.68 8. SCC is completely evaluated into other SCCs 0.67/0.68 9. SCC is completely evaluated into other SCCs 0.67/0.68 10. SCC is completely evaluated into other SCCs 0.67/0.68 11. SCC is completely evaluated into other SCCs 0.67/0.68 12. SCC is completely evaluated into other SCCs 0.67/0.68 13. SCC is completely evaluated into other SCCs 0.67/0.68 14. SCC is partially evaluated into eval_rank2_start/9 0.67/0.68 0.67/0.68 Control-Flow Refinement of Cost Relations 0.67/0.68 ===================================== 0.67/0.68 0.67/0.68 ### Specialization of cost equations eval_rank2_bb3_in/6 0.67/0.68 * CE 12 is refined into CE [13] 0.67/0.68 * CE 9 is refined into CE [14] 0.67/0.68 * CE 11 is refined into CE [15] 0.67/0.68 * CE 10 is refined into CE [16] 0.67/0.68 0.67/0.68 0.67/0.68 ### Cost equations --> "Loop" of eval_rank2_bb3_in/6 0.67/0.68 * CEs [16] --> Loop 13 0.67/0.68 * CEs [13] --> Loop 14 0.67/0.68 * CEs [14] --> Loop 15 0.67/0.68 * CEs [15] --> Loop 16 0.67/0.68 0.67/0.68 ### Ranking functions of CR eval_rank2_bb3_in(V_1,V_4,V_y_1,B,C,D) 0.67/0.68 * RF of phase [13]: [-V_1+V_y_1+1,V_y_1] 0.67/0.68 0.67/0.68 #### Partial ranking functions of CR eval_rank2_bb3_in(V_1,V_4,V_y_1,B,C,D) 0.67/0.68 * Partial RF of phase [13]: 0.67/0.68 - RF of loop [13:1]: 0.67/0.68 -V_1+V_y_1+1 0.67/0.68 V_y_1 0.67/0.68 0.67/0.68 0.67/0.68 ### Specialization of cost equations eval_rank2_bb1_in/15 0.67/0.68 * CE 5 is refined into CE [17] 0.67/0.68 * CE 3 is refined into CE [18,19] 0.67/0.68 * CE 6 is refined into CE [20] 0.67/0.68 * CE 4 is refined into CE [21,22,23,24] 0.67/0.68 0.67/0.68 0.67/0.68 ### Cost equations --> "Loop" of eval_rank2_bb1_in/15 0.67/0.68 * CEs [24] --> Loop 17 0.67/0.68 * CEs [23] --> Loop 18 0.67/0.68 * CEs [21] --> Loop 19 0.67/0.68 * CEs [22] --> Loop 20 0.67/0.68 * CEs [17] --> Loop 21 0.67/0.68 * CEs [19] --> Loop 22 0.67/0.68 * CEs [18] --> Loop 23 0.67/0.68 * CEs [20] --> Loop 24 0.67/0.68 0.67/0.68 ### Ranking functions of CR eval_rank2_bb1_in(V_1,V_4,V_7,V_8,V_x_0,V_y_0,V_y_1,B,C,D,E,F,G,H,I) 0.67/0.68 * RF of phase [17,18,20]: [V_x_0/2-1/2] 0.67/0.68 0.67/0.68 #### Partial ranking functions of CR eval_rank2_bb1_in(V_1,V_4,V_7,V_8,V_x_0,V_y_0,V_y_1,B,C,D,E,F,G,H,I) 0.67/0.68 * Partial RF of phase [17,18,20]: 0.67/0.68 - RF of loop [17:1,18:1,20:1]: 0.67/0.68 V_x_0/2-1/2 0.67/0.68 0.67/0.68 0.67/0.68 ### Specialization of cost equations eval_rank2_bb1_in_loop_cont/10 0.67/0.68 * CE 7 is refined into CE [25] 0.67/0.68 * CE 8 is refined into CE [26] 0.67/0.68 0.67/0.68 0.67/0.68 ### Cost equations --> "Loop" of eval_rank2_bb1_in_loop_cont/10 0.67/0.68 * CEs [25] --> Loop 25 0.67/0.68 * CEs [26] --> Loop 26 0.67/0.68 0.67/0.68 ### Ranking functions of CR eval_rank2_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J) 0.67/0.68 0.67/0.68 #### Partial ranking functions of CR eval_rank2_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J) 0.67/0.68 0.67/0.68 0.67/0.68 ### Specialization of cost equations eval_rank2_6/9 0.67/0.68 * CE 2 is refined into CE [27,28,29,30,31,32] 0.67/0.68 0.67/0.68 0.67/0.68 ### Cost equations --> "Loop" of eval_rank2_6/9 0.67/0.68 * CEs [30] --> Loop 27 0.67/0.68 * CEs [28,29,32] --> Loop 28 0.67/0.68 * CEs [31] --> Loop 29 0.67/0.68 * CEs [27] --> Loop 30 0.67/0.68 0.67/0.68 ### Ranking functions of CR eval_rank2_6(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B) 0.67/0.68 0.67/0.68 #### Partial ranking functions of CR eval_rank2_6(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B) 0.67/0.68 0.67/0.68 0.67/0.68 ### Specialization of cost equations eval_rank2_start/9 0.67/0.68 * CE 1 is refined into CE [33,34,35,36] 0.67/0.68 0.67/0.68 0.67/0.68 ### Cost equations --> "Loop" of eval_rank2_start/9 0.67/0.68 * CEs [36] --> Loop 31 0.67/0.68 * CEs [35] --> Loop 32 0.67/0.68 * CEs [34] --> Loop 33 0.67/0.68 * CEs [33] --> Loop 34 0.67/0.68 0.67/0.68 ### Ranking functions of CR eval_rank2_start(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B) 0.67/0.68 0.67/0.68 #### Partial ranking functions of CR eval_rank2_start(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B) 0.67/0.68 0.67/0.68 0.67/0.68 Computing Bounds 0.67/0.68 ===================================== 0.67/0.68 0.67/0.68 #### Cost of chains of eval_rank2_bb3_in(V_1,V_4,V_y_1,B,C,D): 0.67/0.68 * Chain [[13],16]: 1*it(13)+0 0.67/0.68 Such that:it(13) =< -V_1+V_y_1+1 0.67/0.68 0.67/0.68 with precondition: [B=2,V_1=D+1,V_1>=1,C>=1,V_y_1>=V_1] 0.67/0.68 0.67/0.68 * Chain [[13],15]: 1*it(13)+0 0.67/0.68 Such that:it(13) =< V_y_1-D 0.67/0.68 0.67/0.68 with precondition: [B=2,0>=C,V_1>=1,D>=V_1,V_y_1>=D+1] 0.67/0.68 0.67/0.68 * Chain [[13],14]: 1*it(13)+0 0.67/0.68 Such that:it(13) =< -V_1+V_y_1+1 0.67/0.68 0.67/0.68 with precondition: [B=3,V_1>=1,V_y_1>=V_1] 0.67/0.68 0.67/0.68 * Chain [16]: 0 0.67/0.68 with precondition: [B=2,C=V_4,V_y_1=D,V_1>=1,V_1>=V_y_1+1] 0.67/0.68 0.67/0.68 * Chain [15]: 0 0.67/0.68 with precondition: [B=2,V_y_1=D,0>=C,V_1>=1,V_y_1>=V_1] 0.67/0.68 0.67/0.68 * Chain [14]: 0 0.67/0.68 with precondition: [B=3,V_1>=1] 0.67/0.68 0.67/0.68 0.67/0.68 #### Cost of chains of eval_rank2_bb1_in(V_1,V_4,V_7,V_8,V_x_0,V_y_0,V_y_1,B,C,D,E,F,G,H,I): 0.67/0.68 * Chain [[17,18,20],24]: 2*it(17)+1*it(20)+2*s(5)+0 0.67/0.68 Such that:aux(5) =< V_x_0/2 0.67/0.68 aux(6) =< V_x_0/2+V_y_0 0.67/0.68 it(17) =< aux(5) 0.67/0.68 it(20) =< aux(5) 0.67/0.68 s(5) =< aux(6) 0.67/0.68 it(20) =< aux(6) 0.67/0.68 0.67/0.68 with precondition: [B=3,V_x_0>=2,V_y_0>=0] 0.67/0.68 0.67/0.68 * Chain [[17,18,20],23]: 2*it(17)+1*it(20)+2*s(5)+0 0.67/0.68 Such that:aux(7) =< V_x_0/2 0.67/0.68 aux(8) =< V_x_0/2+V_y_0 0.67/0.68 it(17) =< aux(7) 0.67/0.68 it(20) =< aux(7) 0.67/0.68 s(5) =< aux(8) 0.67/0.68 it(20) =< aux(8) 0.67/0.68 0.67/0.68 with precondition: [B=3,V_x_0>=4,V_y_0>=0] 0.67/0.68 0.67/0.68 * Chain [[17,18,20],22]: 2*it(17)+1*it(20)+3*s(5)+0 0.67/0.68 Such that:aux(9) =< V_x_0/2 0.67/0.68 aux(10) =< V_x_0/2+V_y_0 0.67/0.68 s(5) =< aux(10) 0.67/0.68 it(17) =< aux(9) 0.67/0.68 it(20) =< aux(9) 0.67/0.68 it(20) =< aux(10) 0.67/0.68 0.67/0.68 with precondition: [B=3,V_x_0>=4,V_y_0>=0] 0.67/0.68 0.67/0.68 * Chain [[17,18,20],21]: 2*it(17)+1*it(20)+2*s(5)+0 0.67/0.68 Such that:aux(1) =< V_x_0/2 0.67/0.68 aux(2) =< V_x_0/2+V_y_0 0.67/0.68 aux(3) =< V_x_0/2+V_y_0-E/2-H 0.67/0.68 aux(4) =< V_x_0/2-E/2 0.67/0.68 it(17) =< aux(1) 0.67/0.68 it(20) =< aux(1) 0.67/0.68 s(5) =< aux(2) 0.67/0.68 it(20) =< aux(3) 0.67/0.68 s(5) =< aux(3) 0.67/0.68 it(17) =< aux(4) 0.67/0.68 it(20) =< aux(4) 0.67/0.68 0.67/0.68 with precondition: [B=4,C=E+1,C=G+1,F=H,C+F=I+1,2>=C,V_y_0>=0,C>=1,F>=0,V_x_0>=C+1,V_x_0+2*V_y_0+1>=2*F+C] 0.67/0.68 0.67/0.68 * Chain [24]: 0 0.67/0.68 with precondition: [B=3] 0.67/0.68 0.67/0.68 * Chain [23]: 0 0.67/0.68 with precondition: [B=3,V_x_0>=2] 0.67/0.68 0.67/0.68 * Chain [22]: 1*s(7)+0 0.67/0.68 Such that:s(7) =< V_y_0+1 0.67/0.68 0.67/0.68 with precondition: [B=3,V_x_0>=2,V_y_0>=0] 0.67/0.68 0.67/0.68 * Chain [21]: 0 0.67/0.68 with precondition: [B=4,C=V_1,D=V_4,E=V_7,F=V_8,H=V_y_0,I=V_y_1,V_x_0=G,1>=V_x_0] 0.67/0.68 0.67/0.68 0.67/0.68 #### Cost of chains of eval_rank2_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J): 0.67/0.68 * Chain [26]: 0 0.67/0.68 with precondition: [A=3] 0.67/0.68 0.67/0.68 * Chain [25]: 0 0.67/0.68 with precondition: [A=4] 0.67/0.68 0.67/0.68 0.67/0.68 #### Cost of chains of eval_rank2_6(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B): 0.67/0.68 * Chain [30]: 0 0.67/0.68 with precondition: [] 0.67/0.68 0.67/0.68 * Chain [29]: 0 0.67/0.68 with precondition: [1>=V_m] 0.67/0.68 0.67/0.68 * Chain [28]: 1*s(26)+4*s(27)+2*s(28)+4*s(29)+0 0.67/0.68 Such that:s(26) =< V_m+1 0.67/0.68 aux(15) =< V_m/2 0.67/0.68 aux(16) =< 3/2*V_m 0.67/0.68 s(27) =< aux(15) 0.67/0.68 s(28) =< aux(15) 0.67/0.68 s(29) =< aux(16) 0.67/0.68 s(28) =< aux(16) 0.67/0.68 0.67/0.68 with precondition: [V_m>=2] 0.67/0.68 0.67/0.68 * Chain [27]: 5*s(39)+4*s(40)+2*s(41)+0 0.67/0.68 Such that:s(37) =< V_m/2 0.67/0.68 s(38) =< 3/2*V_m 0.67/0.68 s(39) =< s(38) 0.67/0.68 s(40) =< s(37) 0.67/0.68 s(41) =< s(37) 0.67/0.68 s(41) =< s(38) 0.67/0.68 0.67/0.68 with precondition: [V_m>=4] 0.67/0.68 0.67/0.68 0.67/0.68 #### Cost of chains of eval_rank2_start(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B): 0.67/0.68 * Chain [34]: 0 0.67/0.68 with precondition: [] 0.67/0.68 0.67/0.68 * Chain [33]: 0 0.67/0.68 with precondition: [1>=V_m] 0.67/0.68 0.67/0.68 * Chain [32]: 1*s(42)+4*s(45)+2*s(46)+4*s(47)+0 0.67/0.68 Such that:s(42) =< V_m+1 0.67/0.68 s(43) =< V_m/2 0.67/0.68 s(44) =< 3/2*V_m 0.67/0.68 s(45) =< s(43) 0.67/0.68 s(46) =< s(43) 0.67/0.68 s(47) =< s(44) 0.67/0.68 s(46) =< s(44) 0.67/0.68 0.67/0.68 with precondition: [V_m>=2] 0.67/0.68 0.67/0.68 * Chain [31]: 5*s(50)+4*s(51)+2*s(52)+0 0.67/0.68 Such that:s(48) =< V_m/2 0.67/0.68 s(49) =< 3/2*V_m 0.67/0.68 s(50) =< s(49) 0.67/0.68 s(51) =< s(48) 0.67/0.68 s(52) =< s(48) 0.67/0.68 s(52) =< s(49) 0.67/0.68 0.67/0.68 with precondition: [V_m>=4] 0.67/0.68 0.67/0.68 0.67/0.68 Closed-form bounds of eval_rank2_start(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B): 0.67/0.68 ------------------------------------- 0.67/0.68 * Chain [34] with precondition: [] 0.67/0.68 - Upper bound: 0 0.67/0.68 - Complexity: constant 0.67/0.68 * Chain [33] with precondition: [1>=V_m] 0.67/0.68 - Upper bound: 0 0.67/0.68 - Complexity: constant 0.67/0.68 * Chain [32] with precondition: [V_m>=2] 0.67/0.68 - Upper bound: 10*V_m+1 0.67/0.68 - Complexity: n 0.67/0.68 * Chain [31] with precondition: [V_m>=4] 0.67/0.68 - Upper bound: 21/2*V_m 0.67/0.68 - Complexity: n 0.67/0.68 0.67/0.68 ### Maximum cost of eval_rank2_start(V_1,V_4,V_7,V_8,V_m,V_x_0,V_y_0,V_y_1,B): nat(V_m/2)*6+nat(3/2*V_m)*4+max([nat(3/2*V_m),nat(V_m+1)]) 0.67/0.68 Asymptotic class: n 0.67/0.68 * Total analysis performed in 577 ms. 0.67/0.68 0.68/0.78 EOF