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