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