0.05/0.48 WORST_CASE(?,O(n^3)) 0.05/0.48 0.05/0.48 Preprocessing Cost Relations 0.05/0.48 ===================================== 0.05/0.48 0.05/0.48 #### Computed strongly connected components 0.05/0.48 0. recursive : [eval_jama_ex6_bb4_in/5,eval_jama_ex6_bb5_in/5] 0.05/0.48 1. recursive : [eval_jama_ex6_bb2_in/5,eval_jama_ex6_bb3_in/5,eval_jama_ex6_bb4_in_loop_cont/7,eval_jama_ex6_bb6_in/6] 0.05/0.48 2. recursive : [eval_jama_ex6_bb1_in/5,eval_jama_ex6_bb2_in_loop_cont/7,eval_jama_ex6_bb7_in/6] 0.05/0.48 3. non_recursive : [eval_jama_ex6_stop/1] 0.05/0.48 4. non_recursive : [eval_jama_ex6_bb8_in/1] 0.05/0.48 5. non_recursive : [eval_jama_ex6_bb1_in_loop_cont/2] 0.05/0.48 6. non_recursive : [eval_jama_ex6_bb0_in/5] 0.05/0.48 7. non_recursive : [eval_jama_ex6_start/5] 0.05/0.48 0.05/0.48 #### Obtained direct recursion through partial evaluation 0.05/0.48 0. SCC is partially evaluated into eval_jama_ex6_bb4_in/5 0.05/0.48 1. SCC is partially evaluated into eval_jama_ex6_bb2_in/5 0.05/0.48 2. SCC is partially evaluated into eval_jama_ex6_bb1_in/5 0.05/0.48 3. SCC is completely evaluated into other SCCs 0.05/0.48 4. SCC is completely evaluated into other SCCs 0.05/0.48 5. SCC is completely evaluated into other SCCs 0.05/0.48 6. SCC is partially evaluated into eval_jama_ex6_bb0_in/5 0.05/0.48 7. SCC is partially evaluated into eval_jama_ex6_start/5 0.05/0.48 0.05/0.48 Control-Flow Refinement of Cost Relations 0.05/0.48 ===================================== 0.05/0.48 0.05/0.48 ### Specialization of cost equations eval_jama_ex6_bb4_in/5 0.05/0.48 * CE 8 is refined into CE [9] 0.05/0.48 * CE 7 is refined into CE [10] 0.05/0.48 0.05/0.48 0.05/0.48 ### Cost equations --> "Loop" of eval_jama_ex6_bb4_in/5 0.05/0.48 * CEs [10] --> Loop 9 0.05/0.48 * CEs [9] --> Loop 10 0.05/0.48 0.05/0.48 ### Ranking functions of CR eval_jama_ex6_bb4_in(V_i_0,V_j_0,V_k_0,B,C) 0.05/0.48 * RF of phase [9]: [V_i_0+V_j_0-V_k_0+1] 0.05/0.48 0.05/0.48 #### Partial ranking functions of CR eval_jama_ex6_bb4_in(V_i_0,V_j_0,V_k_0,B,C) 0.05/0.48 * Partial RF of phase [9]: 0.05/0.48 - RF of loop [9:1]: 0.05/0.48 V_i_0+V_j_0-V_k_0+1 0.05/0.48 0.05/0.48 0.05/0.48 ### Specialization of cost equations eval_jama_ex6_bb2_in/5 0.05/0.48 * CE 6 is refined into CE [11] 0.05/0.48 * CE 5 is refined into CE [12,13] 0.05/0.48 0.05/0.48 0.05/0.48 ### Cost equations --> "Loop" of eval_jama_ex6_bb2_in/5 0.05/0.48 * CEs [13] --> Loop 11 0.05/0.48 * CEs [12] --> Loop 12 0.05/0.48 * CEs [11] --> Loop 13 0.05/0.48 0.05/0.48 ### Ranking functions of CR eval_jama_ex6_bb2_in(V_d,V_i_0,V_j_0,B,C) 0.05/0.48 * RF of phase [11]: [V_d-V_j_0+1] 0.05/0.48 * RF of phase [12]: [V_d-V_j_0+1,-V_j_0+1] 0.05/0.48 0.05/0.48 #### Partial ranking functions of CR eval_jama_ex6_bb2_in(V_d,V_i_0,V_j_0,B,C) 0.05/0.48 * Partial RF of phase [11]: 0.05/0.48 - RF of loop [11:1]: 0.05/0.48 V_d-V_j_0+1 0.05/0.48 * Partial RF of phase [12]: 0.05/0.48 - RF of loop [12:1]: 0.05/0.48 V_d-V_j_0+1 0.05/0.48 -V_j_0+1 0.05/0.48 0.05/0.48 0.05/0.48 ### Specialization of cost equations eval_jama_ex6_bb1_in/5 0.05/0.48 * CE 4 is refined into CE [14] 0.05/0.48 * CE 3 is refined into CE [15,16,17,18] 0.05/0.48 0.05/0.48 0.05/0.48 ### Cost equations --> "Loop" of eval_jama_ex6_bb1_in/5 0.05/0.48 * CEs [18] --> Loop 14 0.05/0.48 * CEs [15] --> Loop 15 0.05/0.48 * CEs [16] --> Loop 16 0.05/0.48 * CEs [17] --> Loop 17 0.05/0.48 * CEs [14] --> Loop 18 0.05/0.48 0.05/0.48 ### Ranking functions of CR eval_jama_ex6_bb1_in(V_b,V_c,V_d,V_i_0,B) 0.05/0.48 * RF of phase [14]: [V_b-V_i_0+1] 0.05/0.48 * RF of phase [15]: [V_b-V_i_0+1] 0.05/0.48 * RF of phase [16]: [V_b-V_i_0+1] 0.05/0.48 * RF of phase [17]: [V_b-V_i_0+1] 0.05/0.48 0.05/0.48 #### Partial ranking functions of CR eval_jama_ex6_bb1_in(V_b,V_c,V_d,V_i_0,B) 0.05/0.48 * Partial RF of phase [14]: 0.05/0.48 - RF of loop [14:1]: 0.05/0.48 V_b-V_i_0+1 0.05/0.48 * Partial RF of phase [15]: 0.05/0.48 - RF of loop [15:1]: 0.05/0.48 V_b-V_i_0+1 0.05/0.48 * Partial RF of phase [16]: 0.05/0.48 - RF of loop [16:1]: 0.05/0.48 V_b-V_i_0+1 0.05/0.48 * Partial RF of phase [17]: 0.05/0.48 - RF of loop [17:1]: 0.05/0.48 V_b-V_i_0+1 0.05/0.48 0.05/0.48 0.05/0.48 ### Specialization of cost equations eval_jama_ex6_bb0_in/5 0.05/0.48 * CE 2 is refined into CE [19,20,21,22,23] 0.05/0.48 0.05/0.48 0.05/0.48 ### Cost equations --> "Loop" of eval_jama_ex6_bb0_in/5 0.05/0.48 * CEs [22] --> Loop 19 0.05/0.48 * CEs [23] --> Loop 20 0.05/0.48 * CEs [21] --> Loop 21 0.05/0.48 * CEs [20] --> Loop 22 0.05/0.48 * CEs [19] --> Loop 23 0.05/0.48 0.05/0.48 ### Ranking functions of CR eval_jama_ex6_bb0_in(V_a,V_b,V_c,V_d,B) 0.05/0.48 0.05/0.48 #### Partial ranking functions of CR eval_jama_ex6_bb0_in(V_a,V_b,V_c,V_d,B) 0.05/0.48 0.05/0.48 0.05/0.48 ### Specialization of cost equations eval_jama_ex6_start/5 0.05/0.48 * CE 1 is refined into CE [24,25,26,27,28] 0.05/0.48 0.05/0.48 0.05/0.48 ### Cost equations --> "Loop" of eval_jama_ex6_start/5 0.05/0.48 * CEs [28] --> Loop 24 0.05/0.48 * CEs [27] --> Loop 25 0.05/0.48 * CEs [26] --> Loop 26 0.05/0.48 * CEs [25] --> Loop 27 0.05/0.48 * CEs [24] --> Loop 28 0.05/0.48 0.05/0.48 ### Ranking functions of CR eval_jama_ex6_start(V_a,V_b,V_c,V_d,B) 0.05/0.48 0.05/0.48 #### Partial ranking functions of CR eval_jama_ex6_start(V_a,V_b,V_c,V_d,B) 0.05/0.48 0.05/0.48 0.05/0.48 Computing Bounds 0.05/0.48 ===================================== 0.05/0.48 0.05/0.48 #### Cost of chains of eval_jama_ex6_bb4_in(V_i_0,V_j_0,V_k_0,B,C): 0.05/0.48 * Chain [[9],10]: 1*it(9)+0 0.05/0.48 Such that:it(9) =< -V_k_0+C 0.05/0.48 0.05/0.48 with precondition: [B=2,V_i_0+V_j_0+1=C,V_j_0+V_k_0>=V_i_0,V_i_0+V_j_0>=V_k_0] 0.05/0.48 0.05/0.48 * Chain [10]: 0 0.05/0.48 with precondition: [B=2,V_k_0=C,V_k_0>=V_i_0+V_j_0+1,V_j_0+V_k_0>=V_i_0] 0.05/0.48 0.05/0.48 0.05/0.48 #### Cost of chains of eval_jama_ex6_bb2_in(V_d,V_i_0,V_j_0,B,C): 0.05/0.48 * Chain [[12],[11],13]: 1*it(11)+1*it(12)+1*s(3)+0 0.05/0.48 Such that:it(11) =< V_d+1 0.05/0.48 it(12) =< V_d-V_j_0 0.05/0.48 aux(1) =< 2*V_d+2 0.05/0.48 aux(2) =< V_d-V_j_0+1 0.05/0.48 it(11) =< aux(2) 0.05/0.48 it(12) =< aux(2) 0.05/0.48 s(3) =< it(11)*aux(1) 0.05/0.48 0.05/0.48 with precondition: [B=3,V_d+1=C,0>=2*V_j_0+1,V_d>=0,V_d>=V_j_0+1] 0.05/0.48 0.05/0.48 * Chain [[12],13]: 1*it(12)+0 0.05/0.48 Such that:it(12) =< V_d-V_j_0+1 0.05/0.48 0.05/0.48 with precondition: [B=3,V_d+1=C,0>=2*V_d+1,V_d>=V_j_0] 0.05/0.48 0.05/0.48 * Chain [[11],13]: 1*it(11)+1*s(3)+0 0.05/0.48 Such that:it(11) =< -V_j_0+C 0.05/0.48 aux(1) =< 2*C 0.05/0.48 s(3) =< it(11)*aux(1) 0.05/0.48 0.05/0.48 with precondition: [B=3,V_d+1=C,V_j_0>=0,V_d>=V_j_0] 0.05/0.48 0.05/0.48 * Chain [13]: 0 0.05/0.48 with precondition: [B=3,V_j_0=C,V_j_0>=V_d+1] 0.05/0.48 0.05/0.48 0.05/0.48 #### Cost of chains of eval_jama_ex6_bb1_in(V_b,V_c,V_d,V_i_0,B): 0.05/0.48 * Chain [[17],18]: 1*it(17)+1*s(10)+1*s(11)+0 0.05/0.48 Such that:it(17) =< V_b-V_i_0+1 0.05/0.48 aux(3) =< -V_c+V_d+1 0.05/0.48 s(8) =< 2*V_d+2 0.05/0.48 aux(3) =< s(8)*(1/2) 0.05/0.48 s(10) =< it(17)*aux(3) 0.05/0.48 s(11) =< s(10)*s(8) 0.05/0.48 0.05/0.48 with precondition: [B=4,V_c>=0,V_d>=V_c,V_b>=V_i_0] 0.05/0.48 0.05/0.48 * Chain [[16],18]: 1*it(16)+1*s(22)+1*s(23)+1*s(24)+0 0.05/0.48 Such that:it(16) =< V_b-V_i_0+1 0.05/0.48 aux(4) =< -V_c+V_d 0.05/0.48 s(20) =< 2*V_d+2 0.05/0.48 aux(6) =< s(20)*(1/2) 0.05/0.48 aux(5) =< aux(4)+1 0.05/0.48 s(23) =< it(16)*aux(4) 0.05/0.48 s(22) =< it(16)*aux(6) 0.05/0.48 s(25) =< it(16)*aux(5) 0.05/0.48 s(22) =< s(25) 0.05/0.48 s(23) =< s(25) 0.05/0.48 s(24) =< s(22)*s(20) 0.05/0.48 0.05/0.48 with precondition: [B=4,0>=2*V_c+1,V_d>=0,V_d>=V_c+1,V_b>=V_i_0] 0.05/0.48 0.05/0.48 * Chain [[15],18]: 1*it(15)+1*s(28)+0 0.05/0.48 Such that:it(15) =< V_b-V_i_0+1 0.05/0.48 aux(7) =< -V_c+V_d+1 0.05/0.48 s(28) =< it(15)*aux(7) 0.05/0.48 0.05/0.48 with precondition: [B=4,0>=2*V_d+1,V_d>=V_c,V_b>=V_i_0] 0.05/0.48 0.05/0.48 * Chain [[14],18]: 1*it(14)+0 0.05/0.48 Such that:it(14) =< V_b-V_i_0+1 0.05/0.48 0.05/0.48 with precondition: [B=4,V_c>=V_d+1,V_b>=V_i_0] 0.05/0.48 0.05/0.48 * Chain [18]: 0 0.05/0.48 with precondition: [B=4,V_i_0>=V_b+1] 0.05/0.48 0.05/0.48 0.05/0.48 #### Cost of chains of eval_jama_ex6_bb0_in(V_a,V_b,V_c,V_d,B): 0.05/0.48 * Chain [23]: 1*s(29)+1*s(34)+1*s(35)+1*s(37)+0 0.05/0.48 Such that:s(29) =< -V_a+V_b+1 0.05/0.48 s(30) =< -V_c+V_d 0.05/0.48 s(31) =< 2*V_d+2 0.05/0.48 s(32) =< s(31)*(1/2) 0.05/0.48 s(33) =< s(30)+1 0.05/0.48 s(34) =< s(29)*s(30) 0.05/0.48 s(35) =< s(29)*s(32) 0.05/0.48 s(36) =< s(29)*s(33) 0.05/0.48 s(35) =< s(36) 0.05/0.48 s(34) =< s(36) 0.05/0.48 s(37) =< s(35)*s(31) 0.05/0.48 0.05/0.48 with precondition: [0>=2*V_c+1,V_d>=0,V_b>=V_a,V_d>=V_c+1] 0.05/0.48 0.05/0.48 * Chain [22]: 1*s(38)+1*s(40)+0 0.05/0.48 Such that:s(38) =< -V_a+V_b+1 0.05/0.48 s(39) =< -V_c+V_d+1 0.05/0.48 s(40) =< s(38)*s(39) 0.05/0.48 0.05/0.48 with precondition: [0>=2*V_d+1,V_b>=V_a,V_d>=V_c] 0.05/0.48 0.05/0.48 * Chain [21]: 1*s(41)+1*s(44)+1*s(45)+0 0.05/0.48 Such that:s(41) =< -V_a+V_b+1 0.05/0.48 s(42) =< -V_c+V_d+1 0.05/0.48 s(43) =< 2*V_d+2 0.05/0.48 s(42) =< s(43)*(1/2) 0.05/0.48 s(44) =< s(41)*s(42) 0.05/0.48 s(45) =< s(44)*s(43) 0.05/0.48 0.05/0.48 with precondition: [V_c>=0,V_b>=V_a,V_d>=V_c] 0.05/0.48 0.05/0.48 * Chain [20]: 1*s(46)+0 0.05/0.48 Such that:s(46) =< -V_a+V_b+1 0.05/0.48 0.05/0.48 with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.48 0.05/0.48 * Chain [19]: 0 0.05/0.48 with precondition: [V_a>=V_b+1] 0.05/0.48 0.05/0.48 0.05/0.48 #### Cost of chains of eval_jama_ex6_start(V_a,V_b,V_c,V_d,B): 0.05/0.48 * Chain [28]: 1*s(47)+1*s(52)+1*s(53)+1*s(55)+0 0.05/0.48 Such that:s(47) =< -V_a+V_b+1 0.05/0.48 s(48) =< -V_c+V_d 0.05/0.48 s(49) =< 2*V_d+2 0.05/0.48 s(50) =< s(49)*(1/2) 0.05/0.48 s(51) =< s(48)+1 0.05/0.48 s(52) =< s(47)*s(48) 0.05/0.48 s(53) =< s(47)*s(50) 0.05/0.48 s(54) =< s(47)*s(51) 0.05/0.48 s(53) =< s(54) 0.05/0.48 s(52) =< s(54) 0.05/0.48 s(55) =< s(53)*s(49) 0.05/0.48 0.05/0.48 with precondition: [0>=2*V_c+1,V_d>=0,V_b>=V_a,V_d>=V_c+1] 0.05/0.48 0.05/0.48 * Chain [27]: 1*s(56)+1*s(58)+0 0.05/0.48 Such that:s(56) =< -V_a+V_b+1 0.05/0.48 s(57) =< -V_c+V_d+1 0.05/0.48 s(58) =< s(56)*s(57) 0.05/0.48 0.05/0.48 with precondition: [0>=2*V_d+1,V_b>=V_a,V_d>=V_c] 0.05/0.48 0.05/0.48 * Chain [26]: 1*s(59)+1*s(62)+1*s(63)+0 0.05/0.48 Such that:s(59) =< -V_a+V_b+1 0.05/0.48 s(60) =< -V_c+V_d+1 0.05/0.48 s(61) =< 2*V_d+2 0.05/0.48 s(60) =< s(61)*(1/2) 0.05/0.48 s(62) =< s(59)*s(60) 0.05/0.48 s(63) =< s(62)*s(61) 0.05/0.48 0.05/0.48 with precondition: [V_c>=0,V_b>=V_a,V_d>=V_c] 0.05/0.48 0.05/0.48 * Chain [25]: 1*s(64)+0 0.05/0.48 Such that:s(64) =< -V_a+V_b+1 0.05/0.48 0.05/0.48 with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.48 0.05/0.48 * Chain [24]: 0 0.05/0.48 with precondition: [V_a>=V_b+1] 0.05/0.48 0.05/0.48 0.05/0.48 Closed-form bounds of eval_jama_ex6_start(V_a,V_b,V_c,V_d,B): 0.05/0.48 ------------------------------------- 0.05/0.48 * Chain [28] with precondition: [0>=2*V_c+1,V_d>=0,V_b>=V_a,V_d>=V_c+1] 0.05/0.48 - Upper bound: (-V_a+V_b+1)*(-V_c+V_d)+(-V_a+V_b+1)*((2*V_d+2)*(V_d+1))+(-V_a+V_b+1)*(V_d+1)+(-V_a+V_b+1) 0.05/0.48 - Complexity: n^3 0.05/0.48 * Chain [27] with precondition: [0>=2*V_d+1,V_b>=V_a,V_d>=V_c] 0.05/0.48 - Upper bound: -V_a+V_b+1+(-V_c+V_d+1)*(-V_a+V_b+1) 0.05/0.48 - Complexity: n^2 0.05/0.48 * Chain [26] with precondition: [V_c>=0,V_b>=V_a,V_d>=V_c] 0.05/0.48 - Upper bound: -V_a+V_b+1+(-V_c+V_d+1)*((-V_a+V_b+1)*(2*V_d+2))+(-V_c+V_d+1)*(-V_a+V_b+1) 0.05/0.48 - Complexity: n^3 0.05/0.48 * Chain [25] with precondition: [V_b>=V_a,V_c>=V_d+1] 0.05/0.48 - Upper bound: -V_a+V_b+1 0.05/0.48 - Complexity: n 0.05/0.48 * Chain [24] with precondition: [V_a>=V_b+1] 0.05/0.48 - Upper bound: 0 0.05/0.48 - Complexity: constant 0.05/0.48 0.05/0.48 ### Maximum cost of eval_jama_ex6_start(V_a,V_b,V_c,V_d,B): nat(-V_a+V_b+1)+max([nat(-V_a+V_b+1)*nat(2*V_d+2)*nat(-V_c+V_d+1)+nat(-V_c+V_d+1)*nat(-V_a+V_b+1),1/2*nat(2*V_d+2)*nat(2*V_d+2)*nat(-V_a+V_b+1)+nat(-V_a+V_b+1)*nat(-V_c+V_d)+1/2*nat(2*V_d+2)*nat(-V_a+V_b+1)]) 0.05/0.48 Asymptotic class: n^3 0.05/0.48 * Total analysis performed in 385 ms. 0.05/0.48 0.49/0.58 EOF