0.79/0.78 WORST_CASE(?,O(n^2)) 0.79/0.78 0.79/0.78 Preprocessing Cost Relations 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 #### Computed strongly connected components 0.79/0.78 0. recursive : [eval_unperfect_bb4_in/4,eval_unperfect_bb5_in/4] 0.79/0.78 1. recursive : [eval_unperfect_10/14,eval_unperfect_11/14,eval_unperfect_12/14,eval_unperfect_9/14,eval_unperfect_bb1_in/14,eval_unperfect_bb4_in_loop_cont/15,eval_unperfect_bb6_in/14] 0.79/0.78 2. non_recursive : [eval_unperfect_stop/8] 0.79/0.78 3. non_recursive : [eval_unperfect_bb3_in/8] 0.79/0.78 4. non_recursive : [eval_unperfect_bb2_in/8] 0.79/0.78 5. non_recursive : [exit_location/1] 0.79/0.78 6. non_recursive : [eval_unperfect_bb1_in_loop_cont/9] 0.79/0.78 7. non_recursive : [eval_unperfect_1/8] 0.79/0.78 8. non_recursive : [eval_unperfect_0/8] 0.79/0.78 9. non_recursive : [eval_unperfect_bb0_in/8] 0.79/0.78 10. non_recursive : [eval_unperfect_start/8] 0.79/0.78 0.79/0.78 #### Obtained direct recursion through partial evaluation 0.79/0.78 0. SCC is partially evaluated into eval_unperfect_bb4_in/4 0.79/0.78 1. SCC is partially evaluated into eval_unperfect_bb1_in/14 0.79/0.78 2. SCC is completely evaluated into other SCCs 0.79/0.78 3. SCC is completely evaluated into other SCCs 0.79/0.78 4. SCC is partially evaluated into eval_unperfect_bb2_in/8 0.79/0.78 5. SCC is completely evaluated into other SCCs 0.79/0.78 6. SCC is partially evaluated into eval_unperfect_bb1_in_loop_cont/9 0.79/0.78 7. SCC is partially evaluated into eval_unperfect_1/8 0.79/0.78 8. SCC is completely evaluated into other SCCs 0.79/0.78 9. SCC is completely evaluated into other SCCs 0.79/0.78 10. SCC is partially evaluated into eval_unperfect_start/8 0.79/0.78 0.79/0.78 Control-Flow Refinement of Cost Relations 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_bb4_in/4 0.79/0.78 * CE 18 is refined into CE [22] 0.79/0.78 * CE 17 is refined into CE [23] 0.79/0.78 * CE 16 is refined into CE [24] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_bb4_in/4 0.79/0.78 * CEs [24] --> Loop 22 0.79/0.78 * CEs [22] --> Loop 23 0.79/0.78 * CEs [23] --> Loop 24 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_bb4_in(V_1,V_y2_1,B,C) 0.79/0.78 * RF of phase [22]: [-V_1+V_y2_1+1,V_y2_1] 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_bb4_in(V_1,V_y2_1,B,C) 0.79/0.78 * Partial RF of phase [22]: 0.79/0.78 - RF of loop [22:1]: 0.79/0.78 -V_1+V_y2_1+1 0.79/0.78 V_y2_1 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_bb1_in/14 0.79/0.78 * CE 10 is refined into CE [25,26] 0.79/0.78 * CE 11 is discarded (unfeasible) 0.79/0.78 * CE 13 is refined into CE [27] 0.79/0.78 * CE 12 is refined into CE [28] 0.79/0.78 * CE 8 is refined into CE [29] 0.79/0.78 * CE 6 is discarded (unfeasible) 0.79/0.78 * CE 9 is discarded (unfeasible) 0.79/0.78 * CE 7 is discarded (unfeasible) 0.79/0.78 * CE 4 is refined into CE [30] 0.79/0.78 * CE 5 is discarded (unfeasible) 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_bb1_in/14 0.79/0.78 * CEs [29] --> Loop 25 0.79/0.78 * CEs [30] --> Loop 26 0.79/0.78 * CEs [25,26] --> Loop 27 0.79/0.78 * CEs [27] --> Loop 28 0.79/0.78 * CEs [28] --> Loop 29 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_bb1_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B,C,D,E,F,G,H) 0.79/0.78 * RF of phase [25,26]: [V_y1_0-1] 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_bb1_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B,C,D,E,F,G,H) 0.79/0.78 * Partial RF of phase [25,26]: 0.79/0.78 - RF of loop [25:1]: 0.79/0.78 V_y1_0-2 0.79/0.78 - RF of loop [26:1]: 0.79/0.78 V_y1_0-1 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_bb2_in/8 0.79/0.78 * CE 20 is refined into CE [31] 0.79/0.78 * CE 19 is refined into CE [32] 0.79/0.78 * CE 21 is refined into CE [33] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_bb2_in/8 0.79/0.78 * CEs [31] --> Loop 30 0.79/0.78 * CEs [32] --> Loop 31 0.79/0.78 * CEs [33] --> Loop 32 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_bb2_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_bb2_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_bb1_in_loop_cont/9 0.79/0.78 * CE 14 is refined into CE [34,35,36] 0.79/0.78 * CE 15 is refined into CE [37] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_bb1_in_loop_cont/9 0.79/0.78 * CEs [36] --> Loop 33 0.79/0.78 * CEs [35] --> Loop 34 0.79/0.78 * CEs [34] --> Loop 35 0.79/0.78 * CEs [37] --> Loop 36 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_1/8 0.79/0.78 * CE 3 is refined into CE [38,39,40,41,42,43,44] 0.79/0.78 * CE 2 is refined into CE [45] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_1/8 0.79/0.78 * CEs [41] --> Loop 37 0.79/0.78 * CEs [40,42,43,44] --> Loop 38 0.79/0.78 * CEs [39] --> Loop 39 0.79/0.78 * CEs [45] --> Loop 40 0.79/0.78 * CEs [38] --> Loop 41 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_1(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_1(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations eval_unperfect_start/8 0.79/0.78 * CE 1 is refined into CE [46,47,48,49,50] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of eval_unperfect_start/8 0.79/0.78 * CEs [50] --> Loop 42 0.79/0.78 * CEs [49] --> Loop 43 0.79/0.78 * CEs [48] --> Loop 44 0.79/0.78 * CEs [47] --> Loop 45 0.79/0.78 * CEs [46] --> Loop 46 0.79/0.78 0.79/0.78 ### Ranking functions of CR eval_unperfect_start(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR eval_unperfect_start(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B) 0.79/0.78 0.79/0.78 0.79/0.78 Computing Bounds 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_bb4_in(V_1,V_y2_1,B,C): 0.79/0.78 * Chain [[22],24]: 1*it(22)+0 0.79/0.78 Such that:it(22) =< -V_1+V_y2_1+1 0.79/0.78 0.79/0.78 with precondition: [B=2,C>=0,V_1>=C+1,V_y2_1>=V_1+C] 0.79/0.78 0.79/0.78 * Chain [[22],23]: 1*it(22)+0 0.79/0.78 Such that:it(22) =< -V_1+V_y2_1+1 0.79/0.78 0.79/0.78 with precondition: [B=3,V_1>=1,V_y2_1>=V_1] 0.79/0.78 0.79/0.78 * Chain [23]: 0 0.79/0.78 with precondition: [B=3,V_1>=1] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_bb1_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B,C,D,E,F,G,H): 0.79/0.78 * Chain [[25,26],29]: 2*it(25)+1*s(5)+1*s(6)+0 0.79/0.78 Such that:aux(1) =< V_x 0.79/0.78 aux(5) =< V_y1_0 0.79/0.78 it(25) =< aux(5) 0.79/0.78 aux(2) =< aux(1) 0.79/0.78 s(5) =< it(25)*aux(1) 0.79/0.78 s(6) =< it(25)*aux(2) 0.79/0.78 0.79/0.78 with precondition: [B=4,D=1,F=1,G=0,C=E,C=H,V_y1_0>=2,V_x>=V_y1_0,V_x>=V_y3_0,V_y3_0>=C+1] 0.79/0.78 0.79/0.78 * Chain [[25,26],28]: 2*it(25)+1*s(5)+1*s(6)+0 0.79/0.78 Such that:aux(1) =< V_x 0.79/0.78 aux(6) =< V_y1_0 0.79/0.78 it(25) =< aux(6) 0.79/0.78 aux(2) =< aux(1) 0.79/0.78 s(5) =< it(25)*aux(1) 0.79/0.78 s(6) =< it(25)*aux(2) 0.79/0.78 0.79/0.78 with precondition: [B=3,V_y1_0>=2,V_x>=V_y1_0,V_x>=V_y3_0] 0.79/0.78 0.79/0.78 * Chain [[25,26],27]: 2*it(25)+1*s(5)+1*s(6)+1*s(7)+0 0.79/0.78 Such that:aux(7) =< V_x 0.79/0.78 aux(8) =< V_y1_0 0.79/0.78 s(7) =< aux(7) 0.79/0.78 it(25) =< aux(8) 0.79/0.78 aux(2) =< aux(7) 0.79/0.78 s(5) =< it(25)*aux(7) 0.79/0.78 s(6) =< it(25)*aux(2) 0.79/0.78 0.79/0.78 with precondition: [B=3,V_y1_0>=3,V_x>=V_y1_0,V_x>=V_y3_0] 0.79/0.78 0.79/0.78 * Chain [29]: 0 0.79/0.78 with precondition: [V_y1_0=1,B=4,F=1,C=V__y3_0,D=V_1,E=V_8,G=V_y2_1,V_y3_0=H,V_x>=1,V_x>=V_y3_0] 0.79/0.78 0.79/0.78 * Chain [28]: 0 0.79/0.78 with precondition: [B=3,V_y1_0>=1,V_x>=V_y1_0,V_x>=V_y3_0] 0.79/0.78 0.79/0.78 * Chain [27]: 1*s(7)+0 0.79/0.78 Such that:s(7) =< V_x-V_y1_0+2 0.79/0.78 0.79/0.78 with precondition: [B=3,V_y1_0>=2,V_x>=V_y1_0,V_x>=V_y3_0] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_bb2_in(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B): 0.79/0.78 * Chain [32]: 0 0.79/0.78 with precondition: [V_y3_0=0,V_x>=1] 0.79/0.78 0.79/0.78 * Chain [31]: 0 0.79/0.78 with precondition: [0>=V_y3_0+1,V_x>=1] 0.79/0.78 0.79/0.78 * Chain [30]: 0 0.79/0.78 with precondition: [V_x>=1,V_y3_0>=1] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I): 0.79/0.78 * Chain [36]: 0 0.79/0.78 with precondition: [A=3,E>=1] 0.79/0.78 0.79/0.78 * Chain [35]: 0 0.79/0.78 with precondition: [A=4,H=0,E>=1] 0.79/0.78 0.79/0.78 * Chain [34]: 0 0.79/0.78 with precondition: [A=4,0>=H+1,E>=1] 0.79/0.78 0.79/0.78 * Chain [33]: 0 0.79/0.78 with precondition: [A=4,E>=1,H>=1] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_1(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B): 0.79/0.78 * Chain [41]: 0 0.79/0.78 with precondition: [V_x=1] 0.79/0.78 0.79/0.78 * Chain [40]: 0 0.79/0.78 with precondition: [0>=V_x] 0.79/0.78 0.79/0.78 * Chain [39]: 0 0.79/0.78 with precondition: [V_x>=1] 0.79/0.78 0.79/0.78 * Chain [38]: 1*s(16)+8*s(18)+4*s(20)+4*s(21)+0 0.79/0.78 Such that:s(16) =< 2 0.79/0.78 aux(13) =< V_x 0.79/0.78 s(18) =< aux(13) 0.79/0.78 s(19) =< aux(13) 0.79/0.78 s(20) =< s(18)*aux(13) 0.79/0.78 s(21) =< s(18)*s(19) 0.79/0.78 0.79/0.78 with precondition: [V_x>=2] 0.79/0.78 0.79/0.78 * Chain [37]: 3*s(42)+1*s(45)+1*s(46)+0 0.79/0.78 Such that:aux(14) =< V_x 0.79/0.78 s(42) =< aux(14) 0.79/0.78 s(44) =< aux(14) 0.79/0.78 s(45) =< s(42)*aux(14) 0.79/0.78 s(46) =< s(42)*s(44) 0.79/0.78 0.79/0.78 with precondition: [V_x>=3] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of eval_unperfect_start(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B): 0.79/0.78 * Chain [46]: 0 0.79/0.78 with precondition: [V_x=1] 0.79/0.78 0.79/0.78 * Chain [45]: 0 0.79/0.78 with precondition: [0>=V_x] 0.79/0.78 0.79/0.78 * Chain [44]: 0 0.79/0.78 with precondition: [V_x>=1] 0.79/0.78 0.79/0.78 * Chain [43]: 1*s(47)+8*s(49)+4*s(51)+4*s(52)+0 0.79/0.78 Such that:s(47) =< 2 0.79/0.78 s(48) =< V_x 0.79/0.78 s(49) =< s(48) 0.79/0.78 s(50) =< s(48) 0.79/0.78 s(51) =< s(49)*s(48) 0.79/0.78 s(52) =< s(49)*s(50) 0.79/0.78 0.79/0.78 with precondition: [V_x>=2] 0.79/0.78 0.79/0.78 * Chain [42]: 3*s(54)+1*s(56)+1*s(57)+0 0.79/0.78 Such that:s(53) =< V_x 0.79/0.78 s(54) =< s(53) 0.79/0.78 s(55) =< s(53) 0.79/0.78 s(56) =< s(54)*s(53) 0.79/0.78 s(57) =< s(54)*s(55) 0.79/0.78 0.79/0.78 with precondition: [V_x>=3] 0.79/0.78 0.79/0.78 0.79/0.78 Closed-form bounds of eval_unperfect_start(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B): 0.79/0.78 ------------------------------------- 0.79/0.78 * Chain [46] with precondition: [V_x=1] 0.79/0.78 - Upper bound: 0 0.79/0.78 - Complexity: constant 0.79/0.78 * Chain [45] with precondition: [0>=V_x] 0.79/0.78 - Upper bound: 0 0.79/0.78 - Complexity: constant 0.79/0.78 * Chain [44] with precondition: [V_x>=1] 0.79/0.78 - Upper bound: 0 0.79/0.78 - Complexity: constant 0.79/0.78 * Chain [43] with precondition: [V_x>=2] 0.79/0.78 - Upper bound: 8*V_x+2+8*V_x*V_x 0.79/0.78 - Complexity: n^2 0.79/0.78 * Chain [42] with precondition: [V_x>=3] 0.79/0.78 - Upper bound: 2*V_x*V_x+3*V_x 0.79/0.78 - Complexity: n^2 0.79/0.78 0.79/0.78 ### Maximum cost of eval_unperfect_start(V__y3_0,V_1,V_8,V_x,V_y1_0,V_y2_1,V_y3_0,B): nat(V_x)*5+2+nat(V_x)*6*nat(V_x)+(nat(V_x)*2*nat(V_x)+nat(V_x)*3) 0.79/0.78 Asymptotic class: n^2 0.79/0.78 * Total analysis performed in 667 ms. 0.79/0.78 0.79/0.88 EOF