1.81/1.83 WORST_CASE(?,O(n^1)) 1.81/1.83 1.81/1.83 Preprocessing Cost Relations 1.81/1.83 ===================================== 1.81/1.83 1.81/1.83 #### Computed strongly connected components 1.81/1.83 0. recursive : [eval_start_4/9,eval_start_5/9,eval_start_6/9,eval_start_7/9,eval_start_bb2_in/9,eval_start_bb3_in/9] 1.81/1.83 1. recursive : [eval_start_10/8,eval_start_11/8,eval_start_12/8,eval_start_9/8,eval_start__critedge_in/8,eval_start_bb4_in/8] 1.81/1.83 2. recursive : [eval_start_13/17,eval_start_14/17,eval_start__critedge3_in/17,eval_start__critedge_in_loop_cont/18,eval_start_bb1_in/17,eval_start_bb2_in_loop_cont/18,eval_start_bb6_in/17] 1.81/1.83 3. non_recursive : [eval_start_stop/11] 1.81/1.83 4. non_recursive : [eval_start_bb5_in/11] 1.81/1.83 5. non_recursive : [exit_location/1] 1.81/1.83 6. non_recursive : [eval_start_bb1_in_loop_cont/12] 1.81/1.83 7. non_recursive : [eval_start_16/11] 1.81/1.83 8. non_recursive : [eval_start_15/11] 1.81/1.83 9. non_recursive : [eval_start_bb7_in/11] 1.81/1.83 10. non_recursive : [eval_start_2/11] 1.81/1.83 11. non_recursive : [eval_start_1/11] 1.81/1.83 12. non_recursive : [eval_start_0/11] 1.81/1.83 13. non_recursive : [eval_start_bb0_in/11] 1.81/1.83 14. non_recursive : [eval_start_start/11] 1.81/1.83 1.81/1.83 #### Obtained direct recursion through partial evaluation 1.81/1.83 0. SCC is partially evaluated into eval_start_bb2_in/9 1.81/1.83 1. SCC is partially evaluated into eval_start__critedge_in/8 1.81/1.83 2. SCC is partially evaluated into eval_start_bb1_in/17 1.81/1.83 3. SCC is completely evaluated into other SCCs 1.81/1.83 4. SCC is completely evaluated into other SCCs 1.81/1.83 5. SCC is completely evaluated into other SCCs 1.81/1.83 6. SCC is partially evaluated into eval_start_bb1_in_loop_cont/12 1.81/1.83 7. SCC is completely evaluated into other SCCs 1.81/1.83 8. SCC is completely evaluated into other SCCs 1.81/1.83 9. SCC is completely evaluated into other SCCs 1.81/1.83 10. SCC is partially evaluated into eval_start_2/11 1.81/1.83 11. SCC is completely evaluated into other SCCs 1.81/1.83 12. SCC is completely evaluated into other SCCs 1.81/1.83 13. SCC is completely evaluated into other SCCs 1.81/1.83 14. SCC is partially evaluated into eval_start_start/11 1.81/1.83 1.81/1.83 Control-Flow Refinement of Cost Relations 1.81/1.83 ===================================== 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start_bb2_in/9 1.81/1.83 * CE 13 is refined into CE [19] 1.81/1.83 * CE 11 is refined into CE [20] 1.81/1.83 * CE 14 is refined into CE [21] 1.81/1.83 * CE 12 is refined into CE [22] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start_bb2_in/9 1.81/1.83 * CEs [22] --> Loop 17 1.81/1.83 * CEs [19] --> Loop 18 1.81/1.83 * CEs [20] --> Loop 19 1.81/1.83 * CEs [21] --> Loop 20 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start_bb2_in(V__01,V__1,V__12,V_1,V_3,B,C,D,E) 1.81/1.83 * RF of phase [17]: [V__01-V__1-1] 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start_bb2_in(V__01,V__1,V__12,V_1,V_3,B,C,D,E) 1.81/1.83 * Partial RF of phase [17]: 1.81/1.83 - RF of loop [17:1]: 1.81/1.83 V__01-V__1-1 1.81/1.83 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start__critedge_in/8 1.81/1.83 * CE 18 is refined into CE [23] 1.81/1.83 * CE 17 is refined into CE [24] 1.81/1.83 * CE 15 is refined into CE [25] 1.81/1.83 * CE 16 is refined into CE [26] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start__critedge_in/8 1.81/1.83 * CEs [26] --> Loop 21 1.81/1.83 * CEs [23] --> Loop 22 1.81/1.83 * CEs [24] --> Loop 23 1.81/1.83 * CEs [25] --> Loop 24 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start__critedge_in(V__12,V_1,V_5,V_7,B,C,D,E) 1.81/1.83 * RF of phase [21]: [V__12-V_1-1] 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start__critedge_in(V__12,V_1,V_5,V_7,B,C,D,E) 1.81/1.83 * Partial RF of phase [21]: 1.81/1.83 - RF of loop [21:1]: 1.81/1.83 V__12-V_1-1 1.81/1.83 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start_bb1_in/17 1.81/1.83 * CE 4 is refined into CE [27,28,29,30,31,32] 1.81/1.83 * CE 6 is refined into CE [33,34,35,36,37,38] 1.81/1.83 * CE 7 is refined into CE [39,40] 1.81/1.83 * CE 8 is refined into CE [41] 1.81/1.83 * CE 5 is refined into CE [42,43,44,45] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start_bb1_in/17 1.81/1.83 * CEs [45] --> Loop 25 1.81/1.83 * CEs [44] --> Loop 26 1.81/1.83 * CEs [43] --> Loop 27 1.81/1.83 * CEs [42] --> Loop 28 1.81/1.83 * CEs [32] --> Loop 29 1.81/1.83 * CEs [31] --> Loop 30 1.81/1.83 * CEs [28] --> Loop 31 1.81/1.83 * CEs [30] --> Loop 32 1.81/1.83 * CEs [29] --> Loop 33 1.81/1.83 * CEs [27] --> Loop 34 1.81/1.83 * CEs [38] --> Loop 35 1.81/1.83 * CEs [36,37] --> Loop 36 1.81/1.83 * CEs [34,35,40] --> Loop 37 1.81/1.83 * CEs [39,41] --> Loop 38 1.81/1.83 * CEs [33] --> Loop 39 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start_bb1_in(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,B,C,D,E,F,G,H,I,J) 1.81/1.83 * RF of phase [25,26,27,28]: [-V__0/2+V__01/2-1] 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start_bb1_in(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,B,C,D,E,F,G,H,I,J) 1.81/1.83 * Partial RF of phase [25,26,27,28]: 1.81/1.83 - RF of loop [25:1]: 1.81/1.83 -V__0/4+V__01/4-1 1.81/1.83 - RF of loop [26:1,27:1]: 1.81/1.83 -V__0/3+V__01/3-1 1.81/1.83 - RF of loop [28:1]: 1.81/1.83 -V__0/2+V__01/2-1 1.81/1.83 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start_bb1_in_loop_cont/12 1.81/1.83 * CE 9 is refined into CE [46] 1.81/1.83 * CE 10 is refined into CE [47] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start_bb1_in_loop_cont/12 1.81/1.83 * CEs [46] --> Loop 40 1.81/1.83 * CEs [47] --> Loop 41 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L) 1.81/1.83 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start_2/11 1.81/1.83 * CE 3 is refined into CE [48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66] 1.81/1.83 * CE 2 is refined into CE [67] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start_2/11 1.81/1.83 * CEs [54,66] --> Loop 42 1.81/1.83 * CEs [53,63,65] --> Loop 43 1.81/1.83 * CEs [52,60,61,64] --> Loop 44 1.81/1.83 * CEs [51,58,59,62] --> Loop 45 1.81/1.83 * CEs [50,57] --> Loop 46 1.81/1.83 * CEs [49] --> Loop 47 1.81/1.83 * CEs [67] --> Loop 48 1.81/1.83 * CEs [55] --> Loop 49 1.81/1.83 * CEs [48,56] --> Loop 50 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start_2(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B) 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start_2(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B) 1.81/1.83 1.81/1.83 1.81/1.83 ### Specialization of cost equations eval_start_start/11 1.81/1.83 * CE 1 is refined into CE [68,69,70,71,72,73,74,75,76] 1.81/1.83 1.81/1.83 1.81/1.83 ### Cost equations --> "Loop" of eval_start_start/11 1.81/1.83 * CEs [76] --> Loop 51 1.81/1.83 * CEs [75] --> Loop 52 1.81/1.83 * CEs [74] --> Loop 53 1.81/1.83 * CEs [73] --> Loop 54 1.81/1.83 * CEs [72] --> Loop 55 1.81/1.83 * CEs [71] --> Loop 56 1.81/1.83 * CEs [70] --> Loop 57 1.81/1.83 * CEs [68] --> Loop 58 1.81/1.83 * CEs [69] --> Loop 59 1.81/1.83 1.81/1.83 ### Ranking functions of CR eval_start_start(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B) 1.81/1.83 1.81/1.83 #### Partial ranking functions of CR eval_start_start(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B) 1.81/1.83 1.81/1.83 1.81/1.83 Computing Bounds 1.81/1.83 ===================================== 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start_bb2_in(V__01,V__1,V__12,V_1,V_3,B,C,D,E): 1.81/1.83 * Chain [[17],20]: 1*it(17)+0 1.81/1.83 Such that:it(17) =< V__01-V__1 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__1+2] 1.81/1.83 1.81/1.83 * Chain [[17],19]: 1*it(17)+0 1.81/1.83 Such that:it(17) =< V__01-V__1 1.81/1.83 1.81/1.83 with precondition: [B=4,V__01=C+1,V__01=D,E>=1,V__01>=V__1+2] 1.81/1.83 1.81/1.83 * Chain [[17],18]: 1*it(17)+0 1.81/1.83 Such that:it(17) =< -V__1+D 1.81/1.83 1.81/1.83 with precondition: [B=4,C+1=D,0>=E,C>=V__1+1,V__01>=C+2] 1.81/1.83 1.81/1.83 * Chain [20]: 0 1.81/1.83 with precondition: [B=3,V__01>=V__1+1] 1.81/1.83 1.81/1.83 * Chain [19]: 0 1.81/1.83 with precondition: [B=4,V__01=V__1+1,E=V_3,V__01=C+1,V__01=D] 1.81/1.83 1.81/1.83 * Chain [18]: 0 1.81/1.83 with precondition: [B=4,V__1=C,V__1+1=D,0>=E,V__01>=V__1+2] 1.81/1.83 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start__critedge_in(V__12,V_1,V_5,V_7,B,C,D,E): 1.81/1.83 * Chain [[21],24]: 1*it(21)+0 1.81/1.83 Such that:it(21) =< V__12-C 1.81/1.83 1.81/1.83 with precondition: [B=2,V_1+1=C,V_1=D,E>=1,V__12>=V_1+2] 1.81/1.83 1.81/1.83 * Chain [[21],23]: 1*it(21)+0 1.81/1.83 Such that:it(21) =< V__12-C 1.81/1.83 1.81/1.83 with precondition: [B=2,C=D+1,0>=E,C>=V_1+2,V__12>=C+1] 1.81/1.83 1.81/1.83 * Chain [[21],22]: 1*it(21)+0 1.81/1.83 Such that:it(21) =< V__12-V_1 1.81/1.83 1.81/1.83 with precondition: [B=3,V__12>=V_1+2] 1.81/1.83 1.81/1.83 * Chain [24]: 0 1.81/1.83 with precondition: [B=2,E=V_7,V__12=C,V__12=D+1,V_1+1>=V__12] 1.81/1.83 1.81/1.83 * Chain [23]: 0 1.81/1.83 with precondition: [B=2,V__12=C,V__12=D+1,0>=E,V__12>=V_1+2] 1.81/1.83 1.81/1.83 * Chain [22]: 0 1.81/1.83 with precondition: [B=3] 1.81/1.83 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start_bb1_in(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,B,C,D,E,F,G,H,I,J): 1.81/1.83 * Chain [[25,26,27,28],39]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(7) =< -V__0+V__01 1.81/1.83 aux(8) =< -V__0/2+V__01/2 1.81/1.83 aux(9) =< -V__0/3+V__01/3 1.81/1.83 it(26) =< aux(7) 1.81/1.83 it(28) =< aux(7) 1.81/1.83 s(9) =< aux(7) 1.81/1.83 it(25) =< aux(8) 1.81/1.83 it(26) =< aux(8) 1.81/1.83 it(28) =< aux(8) 1.81/1.83 it(26) =< aux(9) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+3] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],38]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(10) =< -V__0+V__01 1.81/1.83 aux(11) =< -V__0/2+V__01/2 1.81/1.83 aux(12) =< -V__0/3+V__01/3 1.81/1.83 it(26) =< aux(10) 1.81/1.83 it(28) =< aux(10) 1.81/1.83 s(9) =< aux(10) 1.81/1.83 it(25) =< aux(11) 1.81/1.83 it(26) =< aux(11) 1.81/1.83 it(28) =< aux(11) 1.81/1.83 it(26) =< aux(12) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+3] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],37]: 1*it(25)+2*it(26)+1*it(28)+6*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(14) =< -V__0+V__01 1.81/1.83 aux(15) =< -V__0/2+V__01/2 1.81/1.83 aux(16) =< -V__0/3+V__01/3 1.81/1.83 aux(4) =< aux(14) 1.81/1.83 aux(6) =< aux(14) 1.81/1.83 it(25) =< aux(14) 1.81/1.83 aux(4) =< aux(15) 1.81/1.83 aux(6) =< aux(16) 1.81/1.83 s(9) =< aux(14) 1.81/1.83 it(26) =< aux(14) 1.81/1.83 it(28) =< aux(14) 1.81/1.83 it(25) =< aux(15) 1.81/1.83 it(26) =< aux(15) 1.81/1.83 it(28) =< aux(15) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(16) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+4] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],36]: 1*it(25)+2*it(26)+1*it(28)+6*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(18) =< -V__0+V__01 1.81/1.83 aux(19) =< -V__0/2+V__01/2 1.81/1.83 aux(20) =< -V__0/3+V__01/3 1.81/1.83 aux(4) =< aux(18) 1.81/1.83 aux(6) =< aux(18) 1.81/1.83 it(25) =< aux(18) 1.81/1.83 aux(4) =< aux(19) 1.81/1.83 aux(6) =< aux(20) 1.81/1.83 s(9) =< aux(18) 1.81/1.83 it(26) =< aux(18) 1.81/1.83 it(28) =< aux(18) 1.81/1.83 it(25) =< aux(19) 1.81/1.83 it(26) =< aux(19) 1.81/1.83 it(28) =< aux(19) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(20) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+5] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],35]: 1*it(25)+2*it(26)+1*it(28)+6*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(22) =< -V__0+V__01 1.81/1.83 aux(23) =< -V__0/2+V__01/2 1.81/1.83 aux(24) =< -V__0/3+V__01/3 1.81/1.83 aux(4) =< aux(22) 1.81/1.83 aux(6) =< aux(22) 1.81/1.83 it(25) =< aux(22) 1.81/1.83 aux(4) =< aux(23) 1.81/1.83 aux(6) =< aux(24) 1.81/1.83 s(9) =< aux(22) 1.81/1.83 it(26) =< aux(22) 1.81/1.83 it(28) =< aux(22) 1.81/1.83 it(25) =< aux(23) 1.81/1.83 it(26) =< aux(23) 1.81/1.83 it(28) =< aux(23) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(24) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+6] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],34]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(25) =< -V__0+V__01 1.81/1.83 aux(26) =< -V__0/2+V__01/2 1.81/1.83 aux(27) =< -V__0/3+V__01/3 1.81/1.83 it(26) =< aux(25) 1.81/1.83 it(28) =< aux(25) 1.81/1.83 s(9) =< aux(25) 1.81/1.83 it(25) =< aux(26) 1.81/1.83 it(26) =< aux(26) 1.81/1.83 it(28) =< aux(26) 1.81/1.83 it(26) =< aux(27) 1.81/1.83 1.81/1.83 with precondition: [B=5,C+1=D,C=E,C+1=F,C+1=G,C=I,0>=H,0>=J,C>=V__0+1,V__01>=C+2] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],33]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+0 1.81/1.83 Such that:it(25) =< -V__0/4+V__01/4 1.81/1.83 aux(28) =< -V__0+V__01 1.81/1.83 aux(29) =< -V__0/2+V__01/2 1.81/1.83 aux(30) =< -V__0/3+V__01/3 1.81/1.83 it(26) =< aux(28) 1.81/1.83 it(28) =< aux(28) 1.81/1.83 s(9) =< aux(28) 1.81/1.83 it(25) =< aux(29) 1.81/1.83 it(26) =< aux(29) 1.81/1.83 it(28) =< aux(29) 1.81/1.83 it(26) =< aux(30) 1.81/1.83 1.81/1.83 with precondition: [B=5,C+2=D,C=E,C+2=F,C+1=G,C+1=I,0>=H,0>=J,C>=V__0+1,V__01>=C+3] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],32]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+1*s(19)+0 1.81/1.83 Such that:aux(1) =< -V__0+V__01 1.81/1.83 aux(2) =< -V__0+V__01+C-D 1.81/1.83 aux(3) =< -V__0/2+V__01/2 1.81/1.83 aux(4) =< -V__0/2+V__01/2+C/2-D/2 1.81/1.83 aux(5) =< -V__0/3+V__01/3 1.81/1.83 aux(6) =< -V__0/3+V__01/3+C/3-D/3 1.81/1.83 it(25) =< -V__0/4+V__01/4+C/4-D/4 1.81/1.83 s(19) =< -C+D 1.81/1.83 it(26) =< aux(1) 1.81/1.83 it(28) =< aux(1) 1.81/1.83 s(9) =< aux(1) 1.81/1.83 it(26) =< aux(2) 1.81/1.83 it(28) =< aux(2) 1.81/1.83 s(9) =< aux(2) 1.81/1.83 it(25) =< aux(3) 1.81/1.83 it(26) =< aux(3) 1.81/1.83 it(28) =< aux(3) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(5) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=5,C=E,C+2=F,C+1=G,C+1=I,0>=H,J>=1,C>=V__0+1,D>=C+3,V__01>=D+1] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],31]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+1*s(20)+0 1.81/1.83 Such that:aux(1) =< -V__0+V__01 1.81/1.83 aux(2) =< -V__0+V__01+C-E 1.81/1.83 aux(3) =< -V__0/2+V__01/2 1.81/1.83 aux(4) =< -V__0/2+V__01/2+C/2-E/2 1.81/1.83 aux(5) =< -V__0/3+V__01/3 1.81/1.83 aux(6) =< -V__0/3+V__01/3+C/3-E/3 1.81/1.83 it(25) =< -V__0/4+V__01/4+C/4-E/4 1.81/1.83 s(20) =< -C+E+1 1.81/1.83 it(26) =< aux(1) 1.81/1.83 it(28) =< aux(1) 1.81/1.83 s(9) =< aux(1) 1.81/1.83 it(26) =< aux(2) 1.81/1.83 it(28) =< aux(2) 1.81/1.83 s(9) =< aux(2) 1.81/1.83 it(25) =< aux(3) 1.81/1.83 it(26) =< aux(3) 1.81/1.83 it(28) =< aux(3) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(5) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=5,D=E+1,D=F,D=G,D=I+1,0>=J,H>=1,C>=V__0+1,D>=C+2,V__01>=D+1] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],30]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+1*s(21)+0 1.81/1.83 Such that:aux(1) =< -V__0+V__01 1.81/1.83 aux(2) =< -V__0+V__01+C-D 1.81/1.83 aux(3) =< -V__0/2+V__01/2 1.81/1.83 aux(4) =< -V__0/2+V__01/2+C/2-D/2 1.81/1.83 aux(5) =< -V__0/3+V__01/3 1.81/1.83 aux(6) =< -V__0/3+V__01/3+C/3-D/3 1.81/1.83 it(25) =< -V__0/4+V__01/4+C/4-D/4 1.81/1.83 s(21) =< -C+D 1.81/1.83 it(26) =< aux(1) 1.81/1.83 it(28) =< aux(1) 1.81/1.83 s(9) =< aux(1) 1.81/1.83 it(26) =< aux(2) 1.81/1.83 it(28) =< aux(2) 1.81/1.83 s(9) =< aux(2) 1.81/1.83 it(25) =< aux(3) 1.81/1.83 it(26) =< aux(3) 1.81/1.83 it(28) =< aux(3) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(5) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=5,D=E+2,D=F,D=G+1,D=I+1,0>=H,0>=J,C>=V__0+1,D>=C+3,V__01>=D+1] 1.81/1.83 1.81/1.83 * Chain [[25,26,27,28],29]: 1*it(25)+2*it(26)+1*it(28)+4*s(9)+2*s(22)+0 1.81/1.83 Such that:aux(1) =< -V__0+V__01 1.81/1.83 aux(2) =< -V__0+V__01+C-D 1.81/1.83 aux(3) =< -V__0/2+V__01/2 1.81/1.83 aux(4) =< -V__0/2+V__01/2+C/2-D/2 1.81/1.83 aux(5) =< -V__0/3+V__01/3 1.81/1.83 aux(6) =< -V__0/3+V__01/3+C/3-D/3 1.81/1.83 it(25) =< -V__0/4+V__01/4+C/4-D/4 1.81/1.83 aux(31) =< -C+D 1.81/1.83 s(22) =< aux(31) 1.81/1.83 it(26) =< aux(1) 1.81/1.83 it(28) =< aux(1) 1.81/1.83 s(9) =< aux(1) 1.81/1.83 it(26) =< aux(2) 1.81/1.83 it(28) =< aux(2) 1.81/1.83 s(9) =< aux(2) 1.81/1.83 it(25) =< aux(3) 1.81/1.83 it(26) =< aux(3) 1.81/1.83 it(28) =< aux(3) 1.81/1.83 it(25) =< aux(4) 1.81/1.83 it(26) =< aux(4) 1.81/1.83 it(28) =< aux(4) 1.81/1.83 it(26) =< aux(5) 1.81/1.83 it(26) =< aux(6) 1.81/1.83 1.81/1.83 with precondition: [B=5,I=E+1,I+1=F,I=G,0>=H,J>=1,C>=V__0+1,I>=C+2,V__01>=D+1,D>=I+2] 1.81/1.83 1.81/1.83 * Chain [39]: 0 1.81/1.83 with precondition: [B=3,V__01=V__0+1] 1.81/1.83 1.81/1.83 * Chain [38]: 0 1.81/1.83 with precondition: [B=3,V__01>=V__0+1] 1.81/1.83 1.81/1.83 * Chain [37]: 2*s(13)+0 1.81/1.83 Such that:aux(13) =< -V__0+V__01 1.81/1.83 s(13) =< aux(13) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+2] 1.81/1.83 1.81/1.83 * Chain [36]: 2*s(15)+0 1.81/1.83 Such that:aux(17) =< -V__0+V__01 1.81/1.83 s(15) =< aux(17) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+3] 1.81/1.83 1.81/1.83 * Chain [35]: 2*s(17)+0 1.81/1.83 Such that:aux(21) =< -V__0+V__01 1.81/1.83 s(17) =< aux(21) 1.81/1.83 1.81/1.83 with precondition: [B=3,V__01>=V__0+4] 1.81/1.83 1.81/1.83 * Chain [34]: 0 1.81/1.83 with precondition: [B=5,V__0+1=V__01,H=V_3,J=V_7,V__0=C,V__0+1=D,V__0=E,V__0+1=F,V__0+1=G,V__0=I] 1.81/1.83 1.81/1.83 * Chain [33]: 0 1.81/1.83 with precondition: [B=5,V__0+2=V__01,J=V_7,V__0=C,V__0+2=D,V__0=E,V__0+2=F,V__0+1=G,V__0+1=I,0>=H] 1.81/1.83 1.81/1.83 * Chain [32]: 1*s(19)+0 1.81/1.83 Such that:s(19) =< -V__0+V__01 1.81/1.83 1.81/1.83 with precondition: [B=5,V__0=C,V__01=D,V__0=E,V__0+2=F,V__0+1=G,V__0+1=I,0>=H,J>=1,V__01>=V__0+3] 1.81/1.83 1.81/1.83 * Chain [31]: 1*s(20)+0 1.81/1.83 Such that:s(20) =< -V__0+V__01 1.81/1.83 1.81/1.83 with precondition: [B=5,J=V_7,V__0=C,V__01=D,V__01=E+1,V__01=F,V__01=G,V__01=I+1,H>=1,V__01>=V__0+2] 1.81/1.83 1.81/1.83 * Chain [30]: 1*s(21)+0 1.81/1.83 Such that:s(21) =< -V__0+V__01 1.81/1.83 1.81/1.83 with precondition: [B=5,J=V_7,V__0=C,V__01=D,V__01=E+2,V__01=F,V__01=G+1,V__01=I+1,0>=H,V__01>=V__0+3] 1.81/1.83 1.81/1.83 * Chain [29]: 2*s(22)+0 1.81/1.83 Such that:aux(31) =< -V__0+V__01 1.81/1.83 s(22) =< aux(31) 1.81/1.83 1.81/1.83 with precondition: [B=5,V__0=C,V__01=D,I=E+1,I+1=F,I=G,0>=H,J>=1,I>=V__0+2,V__01>=I+2] 1.81/1.83 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start_bb1_in_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L): 1.81/1.83 * Chain [41]: 0 1.81/1.83 with precondition: [A=3,J>=K+1] 1.81/1.83 1.81/1.83 * Chain [40]: 0 1.81/1.83 with precondition: [A=5,J>=K+1] 1.81/1.83 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start_2(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B): 1.81/1.83 * Chain [50]: 0 1.81/1.83 with precondition: [V_l+1=V_h] 1.81/1.83 1.81/1.83 * Chain [49]: 0 1.81/1.83 with precondition: [V_l+2=V_h] 1.81/1.83 1.81/1.83 * Chain [48]: 0 1.81/1.83 with precondition: [V_l>=V_h] 1.81/1.83 1.81/1.83 * Chain [47]: 0 1.81/1.83 with precondition: [V_h>=V_l+1] 1.81/1.83 1.81/1.83 * Chain [46]: 3*s(52)+0 1.81/1.83 Such that:aux(37) =< V_h-V_l 1.81/1.83 s(52) =< aux(37) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+2] 1.81/1.83 1.81/1.83 * Chain [45]: 3*s(58)+16*s(59)+6*s(60)+3*s(61)+0 1.81/1.83 Such that:aux(38) =< V_h-V_l 1.81/1.83 aux(39) =< V_h/2-V_l/2 1.81/1.83 aux(40) =< V_h/3-V_l/3 1.81/1.83 aux(41) =< V_h/4-V_l/4 1.81/1.83 s(59) =< aux(38) 1.81/1.83 s(58) =< aux(41) 1.81/1.83 s(60) =< aux(38) 1.81/1.83 s(61) =< aux(38) 1.81/1.83 s(58) =< aux(39) 1.81/1.83 s(60) =< aux(39) 1.81/1.83 s(61) =< aux(39) 1.81/1.83 s(60) =< aux(40) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+3] 1.81/1.83 1.81/1.83 * Chain [44]: 1*s(73)+14*s(75)+2*s(78)+1*s(79)+1*s(82)+2*s(86)+1*s(87)+1*s(95)+1*s(96)+2*s(97)+1*s(98)+4*s(99)+0 1.81/1.83 Such that:aux(43) =< V_h-V_l+1 1.81/1.83 aux(46) =< V_h-V_l 1.81/1.83 aux(47) =< V_h/2-V_l/2 1.81/1.83 aux(48) =< V_h/3-V_l/3 1.81/1.83 aux(49) =< V_h/4-V_l/4 1.81/1.83 s(73) =< aux(49) 1.81/1.83 s(82) =< aux(49) 1.81/1.83 s(95) =< aux(49) 1.81/1.83 s(75) =< aux(46) 1.81/1.83 s(76) =< aux(46) 1.81/1.83 s(77) =< aux(46) 1.81/1.83 s(73) =< aux(46) 1.81/1.83 s(76) =< aux(47) 1.81/1.83 s(77) =< aux(48) 1.81/1.83 s(78) =< aux(46) 1.81/1.83 s(79) =< aux(46) 1.81/1.83 s(73) =< aux(47) 1.81/1.83 s(78) =< aux(47) 1.81/1.83 s(79) =< aux(47) 1.81/1.83 s(73) =< s(76) 1.81/1.83 s(78) =< s(76) 1.81/1.83 s(79) =< s(76) 1.81/1.83 s(78) =< aux(48) 1.81/1.83 s(78) =< s(77) 1.81/1.83 s(86) =< aux(46) 1.81/1.83 s(87) =< aux(46) 1.81/1.83 s(82) =< aux(47) 1.81/1.83 s(86) =< aux(47) 1.81/1.83 s(87) =< aux(47) 1.81/1.83 s(86) =< aux(48) 1.81/1.83 s(90) =< aux(46) 1.81/1.83 s(90) =< aux(43) 1.81/1.83 s(92) =< aux(43) 1.81/1.83 s(94) =< aux(43) 1.81/1.83 s(95) =< aux(43) 1.81/1.83 s(96) =< aux(43) 1.81/1.83 s(92) =< aux(47) 1.81/1.83 s(94) =< aux(48) 1.81/1.83 s(97) =< aux(46) 1.81/1.83 s(98) =< aux(46) 1.81/1.83 s(99) =< aux(46) 1.81/1.83 s(97) =< s(90) 1.81/1.83 s(98) =< s(90) 1.81/1.83 s(99) =< s(90) 1.81/1.83 s(95) =< aux(47) 1.81/1.83 s(97) =< aux(47) 1.81/1.83 s(98) =< aux(47) 1.81/1.83 s(95) =< s(92) 1.81/1.83 s(97) =< s(92) 1.81/1.83 s(98) =< s(92) 1.81/1.83 s(97) =< aux(48) 1.81/1.83 s(97) =< s(94) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+4] 1.81/1.83 1.81/1.83 * Chain [43]: 3*s(100)+16*s(106)+6*s(107)+3*s(108)+0 1.81/1.83 Such that:aux(56) =< V_h-V_l 1.81/1.83 aux(57) =< V_h/2-V_l/2 1.81/1.83 aux(58) =< V_h/3-V_l/3 1.81/1.83 aux(59) =< V_h/4-V_l/4 1.81/1.83 s(100) =< aux(59) 1.81/1.83 s(104) =< aux(56) 1.81/1.83 s(105) =< aux(56) 1.81/1.83 s(100) =< aux(56) 1.81/1.83 s(104) =< aux(57) 1.81/1.83 s(105) =< aux(58) 1.81/1.83 s(106) =< aux(56) 1.81/1.83 s(107) =< aux(56) 1.81/1.83 s(108) =< aux(56) 1.81/1.83 s(100) =< aux(57) 1.81/1.83 s(107) =< aux(57) 1.81/1.83 s(108) =< aux(57) 1.81/1.83 s(100) =< s(104) 1.81/1.83 s(107) =< s(104) 1.81/1.83 s(108) =< s(104) 1.81/1.83 s(107) =< aux(58) 1.81/1.83 s(107) =< s(105) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+5] 1.81/1.83 1.81/1.83 * Chain [42]: 2*s(131)+12*s(137)+4*s(138)+2*s(139)+0 1.81/1.83 Such that:aux(63) =< V_h-V_l 1.81/1.83 aux(64) =< V_h/2-V_l/2 1.81/1.83 aux(65) =< V_h/3-V_l/3 1.81/1.83 aux(66) =< V_h/4-V_l/4 1.81/1.83 s(131) =< aux(66) 1.81/1.83 s(135) =< aux(63) 1.81/1.83 s(136) =< aux(63) 1.81/1.83 s(131) =< aux(63) 1.81/1.83 s(135) =< aux(64) 1.81/1.83 s(136) =< aux(65) 1.81/1.83 s(137) =< aux(63) 1.81/1.83 s(138) =< aux(63) 1.81/1.83 s(139) =< aux(63) 1.81/1.83 s(131) =< aux(64) 1.81/1.83 s(138) =< aux(64) 1.81/1.83 s(139) =< aux(64) 1.81/1.83 s(131) =< s(135) 1.81/1.83 s(138) =< s(135) 1.81/1.83 s(139) =< s(135) 1.81/1.83 s(138) =< aux(65) 1.81/1.83 s(138) =< s(136) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+6] 1.81/1.83 1.81/1.83 1.81/1.83 #### Cost of chains of eval_start_start(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B): 1.81/1.83 * Chain [59]: 0 1.81/1.83 with precondition: [V_l+1=V_h] 1.81/1.83 1.81/1.83 * Chain [58]: 0 1.81/1.83 with precondition: [V_l+2=V_h] 1.81/1.83 1.81/1.83 * Chain [57]: 0 1.81/1.83 with precondition: [V_l>=V_h] 1.81/1.83 1.81/1.83 * Chain [56]: 0 1.81/1.83 with precondition: [V_h>=V_l+1] 1.81/1.83 1.81/1.83 * Chain [55]: 3*s(153)+0 1.81/1.83 Such that:s(152) =< V_h-V_l 1.81/1.83 s(153) =< s(152) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+2] 1.81/1.83 1.81/1.83 * Chain [54]: 16*s(158)+3*s(159)+6*s(160)+3*s(161)+0 1.81/1.83 Such that:s(154) =< V_h-V_l 1.81/1.83 s(155) =< V_h/2-V_l/2 1.81/1.83 s(156) =< V_h/3-V_l/3 1.81/1.83 s(157) =< V_h/4-V_l/4 1.81/1.83 s(158) =< s(154) 1.81/1.83 s(159) =< s(157) 1.81/1.83 s(160) =< s(154) 1.81/1.83 s(161) =< s(154) 1.81/1.83 s(159) =< s(155) 1.81/1.83 s(160) =< s(155) 1.81/1.83 s(161) =< s(155) 1.81/1.83 s(160) =< s(156) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+3] 1.81/1.83 1.81/1.83 * Chain [53]: 1*s(167)+1*s(168)+1*s(169)+14*s(170)+2*s(173)+1*s(174)+2*s(175)+1*s(176)+1*s(180)+2*s(181)+1*s(182)+4*s(183)+0 1.81/1.83 Such that:s(163) =< V_h-V_l 1.81/1.83 s(162) =< V_h-V_l+1 1.81/1.83 s(164) =< V_h/2-V_l/2 1.81/1.83 s(165) =< V_h/3-V_l/3 1.81/1.83 s(166) =< V_h/4-V_l/4 1.81/1.83 s(167) =< s(166) 1.81/1.83 s(168) =< s(166) 1.81/1.83 s(169) =< s(166) 1.81/1.83 s(170) =< s(163) 1.81/1.83 s(171) =< s(163) 1.81/1.83 s(172) =< s(163) 1.81/1.83 s(167) =< s(163) 1.81/1.83 s(171) =< s(164) 1.81/1.83 s(172) =< s(165) 1.81/1.83 s(173) =< s(163) 1.81/1.83 s(174) =< s(163) 1.81/1.83 s(167) =< s(164) 1.81/1.83 s(173) =< s(164) 1.81/1.83 s(174) =< s(164) 1.81/1.83 s(167) =< s(171) 1.81/1.83 s(173) =< s(171) 1.81/1.83 s(174) =< s(171) 1.81/1.83 s(173) =< s(165) 1.81/1.83 s(173) =< s(172) 1.81/1.83 s(175) =< s(163) 1.81/1.83 s(176) =< s(163) 1.81/1.83 s(168) =< s(164) 1.81/1.83 s(175) =< s(164) 1.81/1.83 s(176) =< s(164) 1.81/1.83 s(175) =< s(165) 1.81/1.83 s(177) =< s(163) 1.81/1.83 s(177) =< s(162) 1.81/1.83 s(178) =< s(162) 1.81/1.83 s(179) =< s(162) 1.81/1.83 s(169) =< s(162) 1.81/1.83 s(180) =< s(162) 1.81/1.83 s(178) =< s(164) 1.81/1.83 s(179) =< s(165) 1.81/1.83 s(181) =< s(163) 1.81/1.83 s(182) =< s(163) 1.81/1.83 s(183) =< s(163) 1.81/1.83 s(181) =< s(177) 1.81/1.83 s(182) =< s(177) 1.81/1.83 s(183) =< s(177) 1.81/1.83 s(169) =< s(164) 1.81/1.83 s(181) =< s(164) 1.81/1.83 s(182) =< s(164) 1.81/1.83 s(169) =< s(178) 1.81/1.83 s(181) =< s(178) 1.81/1.83 s(182) =< s(178) 1.81/1.83 s(181) =< s(165) 1.81/1.83 s(181) =< s(179) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+4] 1.81/1.83 1.81/1.83 * Chain [52]: 3*s(188)+16*s(191)+6*s(192)+3*s(193)+0 1.81/1.83 Such that:s(184) =< V_h-V_l 1.81/1.83 s(185) =< V_h/2-V_l/2 1.81/1.83 s(186) =< V_h/3-V_l/3 1.81/1.83 s(187) =< V_h/4-V_l/4 1.81/1.83 s(188) =< s(187) 1.81/1.83 s(189) =< s(184) 1.81/1.83 s(190) =< s(184) 1.81/1.83 s(188) =< s(184) 1.81/1.83 s(189) =< s(185) 1.81/1.83 s(190) =< s(186) 1.81/1.83 s(191) =< s(184) 1.81/1.83 s(192) =< s(184) 1.81/1.83 s(193) =< s(184) 1.81/1.83 s(188) =< s(185) 1.81/1.83 s(192) =< s(185) 1.81/1.83 s(193) =< s(185) 1.81/1.83 s(188) =< s(189) 1.81/1.83 s(192) =< s(189) 1.81/1.83 s(193) =< s(189) 1.81/1.83 s(192) =< s(186) 1.81/1.83 s(192) =< s(190) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+5] 1.81/1.83 1.81/1.83 * Chain [51]: 2*s(198)+12*s(201)+4*s(202)+2*s(203)+0 1.81/1.83 Such that:s(194) =< V_h-V_l 1.81/1.83 s(195) =< V_h/2-V_l/2 1.81/1.83 s(196) =< V_h/3-V_l/3 1.81/1.83 s(197) =< V_h/4-V_l/4 1.81/1.83 s(198) =< s(197) 1.81/1.83 s(199) =< s(194) 1.81/1.83 s(200) =< s(194) 1.81/1.83 s(198) =< s(194) 1.81/1.83 s(199) =< s(195) 1.81/1.83 s(200) =< s(196) 1.81/1.83 s(201) =< s(194) 1.81/1.83 s(202) =< s(194) 1.81/1.83 s(203) =< s(194) 1.81/1.83 s(198) =< s(195) 1.81/1.83 s(202) =< s(195) 1.81/1.83 s(203) =< s(195) 1.81/1.83 s(198) =< s(199) 1.81/1.83 s(202) =< s(199) 1.81/1.83 s(203) =< s(199) 1.81/1.83 s(202) =< s(196) 1.81/1.83 s(202) =< s(200) 1.81/1.83 1.81/1.83 with precondition: [V_h>=V_l+6] 1.81/1.83 1.81/1.83 1.81/1.83 Closed-form bounds of eval_start_start(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B): 1.81/1.83 ------------------------------------- 1.81/1.83 * Chain [59] with precondition: [V_l+1=V_h] 1.81/1.83 - Upper bound: 0 1.81/1.83 - Complexity: constant 1.81/1.83 * Chain [58] with precondition: [V_l+2=V_h] 1.81/1.83 - Upper bound: 0 1.81/1.83 - Complexity: constant 1.81/1.83 * Chain [57] with precondition: [V_l>=V_h] 1.81/1.83 - Upper bound: 0 1.81/1.83 - Complexity: constant 1.81/1.83 * Chain [56] with precondition: [V_h>=V_l+1] 1.81/1.83 - Upper bound: 0 1.81/1.83 - Complexity: constant 1.81/1.83 * Chain [55] with precondition: [V_h>=V_l+2] 1.81/1.83 - Upper bound: 3*V_h-3*V_l 1.81/1.83 - Complexity: n 1.81/1.83 * Chain [54] with precondition: [V_h>=V_l+3] 1.81/1.83 - Upper bound: 103/4*V_h-103/4*V_l 1.81/1.83 - Complexity: n 1.81/1.83 * Chain [53] with precondition: [V_h>=V_l+4] 1.81/1.83 - Upper bound: 115/4*V_h-115/4*V_l+1 1.81/1.83 - Complexity: n 1.81/1.83 * Chain [52] with precondition: [V_h>=V_l+5] 1.81/1.83 - Upper bound: 103/4*V_h-103/4*V_l 1.81/1.83 - Complexity: n 1.81/1.83 * Chain [51] with precondition: [V_h>=V_l+6] 1.81/1.83 - Upper bound: 37/2*V_h-37/2*V_l 1.81/1.83 - Complexity: n 1.81/1.83 1.81/1.83 ### Maximum cost of eval_start_start(V__0,V__01,V__1,V__12,V_1,V_3,V_5,V_7,V_h,V_l,B): nat(V_h-V_l)*7+nat(V_h/4-V_l/4)+(nat(V_h-V_l)*2+nat(V_h-V_l+1))+(nat(V_h/4-V_l/4)*2+nat(V_h-V_l)*15)+nat(V_h-V_l)*3 1.81/1.83 Asymptotic class: n 1.81/1.83 * Total analysis performed in 1671 ms. 1.81/1.83 1.84/1.94 EOF