0.05/0.33 WORST_CASE(?,O(n^1)) 0.05/0.33 0.05/0.33 Preprocessing Cost Relations 0.05/0.33 ===================================== 0.05/0.33 0.05/0.33 #### Computed strongly connected components 0.05/0.33 0. recursive : [eval_rsd_3/4,eval_rsd_4/5,eval_rsd_bb2_in/4,eval_rsd_bb3_in/4] 0.05/0.33 1. non_recursive : [eval_rsd_stop/1] 0.05/0.33 2. non_recursive : [eval_rsd_bb4_in/1] 0.05/0.33 3. non_recursive : [eval_rsd_bb2_in_loop_cont/2] 0.05/0.33 4. non_recursive : [eval_rsd_bb1_in/2] 0.05/0.33 5. non_recursive : [eval_rsd_bb0_in/2] 0.05/0.33 6. non_recursive : [eval_rsd_start/2] 0.05/0.33 0.05/0.33 #### Obtained direct recursion through partial evaluation 0.05/0.33 0. SCC is partially evaluated into eval_rsd_bb2_in/4 0.05/0.33 1. SCC is completely evaluated into other SCCs 0.05/0.33 2. SCC is completely evaluated into other SCCs 0.05/0.33 3. SCC is completely evaluated into other SCCs 0.05/0.33 4. SCC is partially evaluated into eval_rsd_bb1_in/2 0.05/0.33 5. SCC is partially evaluated into eval_rsd_bb0_in/2 0.05/0.33 6. SCC is partially evaluated into eval_rsd_start/2 0.05/0.33 0.05/0.33 Control-Flow Refinement of Cost Relations 0.05/0.33 ===================================== 0.05/0.33 0.05/0.33 ### Specialization of cost equations eval_rsd_bb2_in/4 0.05/0.33 * CE 7 is refined into CE [8] 0.05/0.33 * CE 5 is refined into CE [9] 0.05/0.33 * CE 6 is refined into CE [10] 0.05/0.33 0.05/0.33 0.05/0.33 ### Cost equations --> "Loop" of eval_rsd_bb2_in/4 0.05/0.33 * CEs [9] --> Loop 8 0.05/0.33 * CEs [10] --> Loop 9 0.05/0.33 * CEs [8] --> Loop 10 0.05/0.33 0.05/0.33 ### Ranking functions of CR eval_rsd_bb2_in(V_r,V_db_0,V_da_0,B) 0.05/0.33 * RF of phase [8,9]: [V_db_0+V_da_0+1,-2*V_r+V_db_0+V_da_0+1] 0.05/0.33 0.05/0.33 #### Partial ranking functions of CR eval_rsd_bb2_in(V_r,V_db_0,V_da_0,B) 0.05/0.33 * Partial RF of phase [8,9]: 0.05/0.33 - RF of loop [8:1]: 0.05/0.33 V_db_0+V_da_0+1 0.05/0.33 -2*V_r+V_db_0+V_da_0+1 0.05/0.33 - RF of loop [9:1]: 0.05/0.33 V_da_0+1 depends on loops [8:1] 0.05/0.33 -V_db_0/2+V_da_0+1/2 depends on loops [8:1] 0.05/0.33 -V_r+V_da_0+1 depends on loops [8:1] 0.05/0.33 0.05/0.33 0.05/0.33 ### Specialization of cost equations eval_rsd_bb1_in/2 0.05/0.33 * CE 4 is refined into CE [11] 0.05/0.33 0.05/0.33 0.05/0.33 ### Cost equations --> "Loop" of eval_rsd_bb1_in/2 0.05/0.33 * CEs [11] --> Loop 11 0.05/0.33 0.05/0.33 ### Ranking functions of CR eval_rsd_bb1_in(V_r,B) 0.05/0.33 0.05/0.33 #### Partial ranking functions of CR eval_rsd_bb1_in(V_r,B) 0.05/0.33 0.05/0.33 0.05/0.33 ### Specialization of cost equations eval_rsd_bb0_in/2 0.05/0.33 * CE 2 is refined into CE [12] 0.05/0.33 * CE 3 is refined into CE [13] 0.05/0.33 0.05/0.33 0.05/0.33 ### Cost equations --> "Loop" of eval_rsd_bb0_in/2 0.05/0.33 * CEs [12] --> Loop 12 0.05/0.33 * CEs [13] --> Loop 13 0.05/0.33 0.05/0.33 ### Ranking functions of CR eval_rsd_bb0_in(V_r,B) 0.05/0.33 0.05/0.33 #### Partial ranking functions of CR eval_rsd_bb0_in(V_r,B) 0.05/0.33 0.05/0.33 0.05/0.33 ### Specialization of cost equations eval_rsd_start/2 0.05/0.33 * CE 1 is refined into CE [14,15] 0.05/0.33 0.05/0.33 0.05/0.33 ### Cost equations --> "Loop" of eval_rsd_start/2 0.05/0.33 * CEs [15] --> Loop 14 0.05/0.33 * CEs [14] --> Loop 15 0.05/0.33 0.05/0.33 ### Ranking functions of CR eval_rsd_start(V_r,B) 0.05/0.33 0.05/0.33 #### Partial ranking functions of CR eval_rsd_start(V_r,B) 0.05/0.33 0.05/0.33 0.05/0.33 Computing Bounds 0.05/0.33 ===================================== 0.05/0.33 0.05/0.33 #### Cost of chains of eval_rsd_bb2_in(V_r,V_db_0,V_da_0,B): 0.05/0.33 * Chain [[8,9],10]: 1*it(8)+1*it(9)+0 0.05/0.33 Such that:aux(15) =< -2*V_r+V_db_0+V_da_0 0.05/0.33 aux(19) =< -V_r+V_db_0+V_da_0 0.05/0.33 aux(15) =< V_r 0.05/0.33 aux(19) =< 2*V_r 0.05/0.33 aux(21) =< 3*V_r 0.05/0.33 aux(21) =< -3/2*V_r+3/2*V_db_0+3/2*V_da_0 0.05/0.33 aux(12) =< -3/2*V_r+3/2*V_da_0+1 0.05/0.33 aux(13) =< 3/2*V_r 0.05/0.33 aux(27) =< V_db_0+V_da_0+1 0.05/0.33 aux(12) =< -V_db_0/2+V_da_0+1 0.05/0.33 aux(6) =< -V_db_0/2+V_da_0+1/2 0.05/0.33 aux(2) =< V_da_0+1 0.05/0.33 aux(29) =< -2*V_r+V_db_0+V_da_0+1 0.05/0.33 aux(30) =< -V_r+V_da_0+1 0.05/0.33 it(8) =< aux(29) 0.05/0.33 it(9) =< aux(29) 0.05/0.33 it(8) =< aux(27) 0.05/0.33 it(9) =< aux(27) 0.05/0.33 aux(23) =< aux(13)*(4/3)+1/3 0.05/0.33 aux(21) =< aux(13) 0.05/0.33 aux(19) =< aux(15) 0.05/0.33 aux(16) =< it(8)*aux(15) 0.05/0.33 aux(1) =< it(8)*aux(15) 0.05/0.33 aux(14) =< it(8)*aux(13) 0.05/0.33 aux(5) =< it(8)*aux(13) 0.05/0.33 aux(23) =< aux(19) 0.05/0.33 aux(22) =< it(8)*aux(21) 0.05/0.33 aux(5) =< it(8)*aux(21) 0.05/0.33 aux(20) =< it(8)*aux(19) 0.05/0.33 aux(1) =< it(8)*aux(19) 0.05/0.33 aux(9) =< aux(16) 0.05/0.33 aux(7) =< aux(16) 0.05/0.33 aux(3) =< aux(16) 0.05/0.33 aux(11) =< aux(14) 0.05/0.33 aux(24) =< it(8)*aux(23) 0.05/0.33 aux(3) =< it(8)*aux(23) 0.05/0.33 aux(11) =< aux(22) 0.05/0.33 aux(7) =< aux(20) 0.05/0.33 it(9) =< aux(5)+aux(6) 0.05/0.33 it(9) =< aux(1)+aux(2) 0.05/0.33 aux(9) =< aux(24) 0.05/0.33 it(9) =< aux(11)+aux(12) 0.05/0.33 it(9) =< aux(7)+aux(30) 0.05/0.33 it(9) =< aux(3)+aux(30) 0.05/0.33 it(9) =< aux(9)+aux(30) 0.05/0.33 0.05/0.33 with precondition: [B=2,V_db_0>=V_r,V_da_0>=V_r,2*V_r>=V_db_0,2*V_r>=V_da_0] 0.05/0.33 0.05/0.33 0.05/0.33 #### Cost of chains of eval_rsd_bb1_in(V_r,B): 0.05/0.33 * Chain [11]: 1*s(11)+1*s(12)+0 0.05/0.33 Such that:s(1) =< V_r 0.05/0.33 s(7) =< V_r+1/2 0.05/0.33 s(2) =< 2*V_r 0.05/0.33 s(3) =< 3*V_r 0.05/0.33 s(6) =< 4*V_r+1 0.05/0.33 s(5) =< 3/2*V_r 0.05/0.33 aux(31) =< V_r+1 0.05/0.33 aux(32) =< 2*V_r+1 0.05/0.33 s(11) =< aux(32) 0.05/0.33 s(12) =< aux(32) 0.05/0.33 s(11) =< s(6) 0.05/0.33 s(12) =< s(6) 0.05/0.33 s(13) =< s(5)*(4/3)+1/3 0.05/0.33 s(3) =< s(5) 0.05/0.33 s(2) =< s(1) 0.05/0.33 s(14) =< s(11)*s(1) 0.05/0.33 s(15) =< s(11)*s(1) 0.05/0.33 s(16) =< s(11)*s(5) 0.05/0.33 s(17) =< s(11)*s(5) 0.05/0.33 s(13) =< s(2) 0.05/0.33 s(18) =< s(11)*s(3) 0.05/0.33 s(17) =< s(11)*s(3) 0.05/0.33 s(19) =< s(11)*s(2) 0.05/0.33 s(15) =< s(11)*s(2) 0.05/0.33 s(20) =< s(14) 0.05/0.33 s(21) =< s(14) 0.05/0.33 s(22) =< s(14) 0.05/0.33 s(23) =< s(16) 0.05/0.33 s(24) =< s(11)*s(13) 0.05/0.33 s(22) =< s(11)*s(13) 0.05/0.33 s(23) =< s(18) 0.05/0.33 s(21) =< s(19) 0.05/0.33 s(12) =< s(17)+s(7) 0.05/0.33 s(12) =< s(15)+aux(32) 0.05/0.33 s(20) =< s(24) 0.05/0.33 s(12) =< s(23)+aux(31) 0.05/0.33 s(12) =< s(21)+aux(31) 0.05/0.33 s(12) =< s(22)+aux(31) 0.05/0.33 s(12) =< s(20)+aux(31) 0.05/0.33 0.05/0.33 with precondition: [V_r>=0] 0.05/0.33 0.05/0.33 0.05/0.33 #### Cost of chains of eval_rsd_bb0_in(V_r,B): 0.05/0.33 * Chain [13]: 0 0.05/0.33 with precondition: [0>=V_r+1] 0.05/0.33 0.05/0.33 * Chain [12]: 1*s(33)+1*s(34)+0 0.05/0.33 Such that:s(25) =< V_r 0.05/0.33 s(31) =< V_r+1 0.05/0.33 s(26) =< V_r+1/2 0.05/0.33 s(27) =< 2*V_r 0.05/0.33 s(32) =< 2*V_r+1 0.05/0.33 s(28) =< 3*V_r 0.05/0.33 s(29) =< 4*V_r+1 0.05/0.33 s(30) =< 3/2*V_r 0.05/0.33 s(33) =< s(32) 0.05/0.33 s(34) =< s(32) 0.05/0.33 s(33) =< s(29) 0.05/0.33 s(34) =< s(29) 0.05/0.33 s(35) =< s(30)*(4/3)+1/3 0.05/0.33 s(28) =< s(30) 0.05/0.33 s(27) =< s(25) 0.05/0.33 s(36) =< s(33)*s(25) 0.05/0.33 s(37) =< s(33)*s(25) 0.05/0.33 s(38) =< s(33)*s(30) 0.05/0.33 s(39) =< s(33)*s(30) 0.05/0.33 s(35) =< s(27) 0.05/0.33 s(40) =< s(33)*s(28) 0.05/0.33 s(39) =< s(33)*s(28) 0.05/0.33 s(41) =< s(33)*s(27) 0.05/0.33 s(37) =< s(33)*s(27) 0.05/0.33 s(42) =< s(36) 0.05/0.33 s(43) =< s(36) 0.05/0.33 s(44) =< s(36) 0.05/0.33 s(45) =< s(38) 0.05/0.33 s(46) =< s(33)*s(35) 0.05/0.33 s(44) =< s(33)*s(35) 0.05/0.33 s(45) =< s(40) 0.05/0.33 s(43) =< s(41) 0.05/0.33 s(34) =< s(39)+s(26) 0.05/0.33 s(34) =< s(37)+s(32) 0.05/0.33 s(42) =< s(46) 0.05/0.33 s(34) =< s(45)+s(31) 0.05/0.33 s(34) =< s(43)+s(31) 0.05/0.33 s(34) =< s(44)+s(31) 0.05/0.33 s(34) =< s(42)+s(31) 0.05/0.33 0.05/0.33 with precondition: [V_r>=0] 0.05/0.33 0.05/0.33 0.05/0.33 #### Cost of chains of eval_rsd_start(V_r,B): 0.05/0.33 * Chain [15]: 0 0.05/0.33 with precondition: [0>=V_r+1] 0.05/0.33 0.05/0.33 * Chain [14]: 1*s(55)+1*s(56)+0 0.05/0.33 Such that:s(47) =< V_r 0.05/0.33 s(48) =< V_r+1 0.05/0.33 s(49) =< V_r+1/2 0.05/0.33 s(50) =< 2*V_r 0.05/0.33 s(51) =< 2*V_r+1 0.05/0.33 s(52) =< 3*V_r 0.05/0.33 s(53) =< 4*V_r+1 0.05/0.33 s(54) =< 3/2*V_r 0.05/0.33 s(55) =< s(51) 0.05/0.33 s(56) =< s(51) 0.05/0.33 s(55) =< s(53) 0.05/0.33 s(56) =< s(53) 0.05/0.33 s(57) =< s(54)*(4/3)+1/3 0.05/0.33 s(52) =< s(54) 0.05/0.33 s(50) =< s(47) 0.05/0.33 s(58) =< s(55)*s(47) 0.05/0.33 s(59) =< s(55)*s(47) 0.05/0.33 s(60) =< s(55)*s(54) 0.05/0.33 s(61) =< s(55)*s(54) 0.05/0.33 s(57) =< s(50) 0.05/0.33 s(62) =< s(55)*s(52) 0.05/0.33 s(61) =< s(55)*s(52) 0.05/0.33 s(63) =< s(55)*s(50) 0.05/0.33 s(59) =< s(55)*s(50) 0.05/0.33 s(64) =< s(58) 0.05/0.33 s(65) =< s(58) 0.05/0.33 s(66) =< s(58) 0.05/0.33 s(67) =< s(60) 0.05/0.33 s(68) =< s(55)*s(57) 0.05/0.33 s(66) =< s(55)*s(57) 0.05/0.33 s(67) =< s(62) 0.05/0.33 s(65) =< s(63) 0.05/0.33 s(56) =< s(61)+s(49) 0.05/0.33 s(56) =< s(59)+s(51) 0.05/0.33 s(64) =< s(68) 0.05/0.33 s(56) =< s(67)+s(48) 0.05/0.33 s(56) =< s(65)+s(48) 0.05/0.33 s(56) =< s(66)+s(48) 0.05/0.33 s(56) =< s(64)+s(48) 0.05/0.33 0.05/0.33 with precondition: [V_r>=0] 0.05/0.33 0.05/0.33 0.05/0.33 Closed-form bounds of eval_rsd_start(V_r,B): 0.05/0.33 ------------------------------------- 0.05/0.33 * Chain [15] with precondition: [0>=V_r+1] 0.05/0.33 - Upper bound: 0 0.05/0.33 - Complexity: constant 0.05/0.33 * Chain [14] with precondition: [V_r>=0] 0.05/0.33 - Upper bound: 4*V_r+2 0.05/0.33 - Complexity: n 0.05/0.33 0.05/0.33 ### Maximum cost of eval_rsd_start(V_r,B): nat(2*V_r+1)*2 0.05/0.33 Asymptotic class: n 0.05/0.33 * Total analysis performed in 237 ms. 0.05/0.33 0.05/0.43 EOF