/export/starexec/sandbox2/solver/bin/starexec_run_C /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^1)) Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [eval_foo_3/4,eval_foo_4/5,eval_foo_bb3_in/4,eval_foo_bb4_in/4,eval_foo_bb5_in/5] 1. recursive : [eval_foo__critedge_in/5,eval_foo_bb1_in/3,eval_foo_bb2_in/3,eval_foo_bb3_in_loop_cont/6] 2. non_recursive : [eval_foo_stop/1] 3. non_recursive : [eval_foo_bb6_in/1] 4. non_recursive : [eval_foo_bb1_in_loop_cont/2] 5. non_recursive : [eval_foo_bb0_in/3] 6. non_recursive : [eval_foo_start/3] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into eval_foo_bb3_in/4 1. SCC is partially evaluated into eval_foo_bb1_in/3 2. SCC is completely evaluated into other SCCs 3. SCC is completely evaluated into other SCCs 4. SCC is completely evaluated into other SCCs 5. SCC is partially evaluated into eval_foo_bb0_in/3 6. SCC is partially evaluated into eval_foo_start/3 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations eval_foo_bb3_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_bb3_in/4 * CEs [10] --> Loop 8 * CEs [8] --> Loop 9 * CEs [9] --> Loop 10 ### Ranking functions of CR eval_foo_bb3_in(V_1,V__1,B,C) * RF of phase [8]: [-V_1+V__1+1,V__1] #### Partial ranking functions of CR eval_foo_bb3_in(V_1,V__1,B,C) * Partial RF of phase [8]: - RF of loop [8:1]: -V_1+V__1+1 V__1 ### Specialization of cost equations eval_foo_bb1_in/3 * CE 4 is refined into CE [11] * CE 3 is refined into CE [12,13,14,15] ### Cost equations --> "Loop" of eval_foo_bb1_in/3 * CEs [15] --> Loop 11 * CEs [14] --> Loop 12 * CEs [13] --> Loop 13 * CEs [12] --> Loop 14 * CEs [11] --> Loop 15 ### Ranking functions of CR eval_foo_bb1_in(V__01,V__0,B) * RF of phase [11,13,14]: [V__0/2-1/2] * RF of phase [12]: [V__0/2-1/2,-V__01] #### Partial ranking functions of CR eval_foo_bb1_in(V__01,V__0,B) * Partial RF of phase [11,13,14]: - RF of loop [11:1,13:1]: V__0/2-1/2 - RF of loop [14:1]: V__0-1 * Partial RF of phase [12]: - RF of loop [12:1]: V__0/2-1/2 -V__01 ### Specialization of cost equations eval_foo_bb0_in/3 * CE 2 is refined into CE [16,17,18,19] ### Cost equations --> "Loop" of eval_foo_bb0_in/3 * CEs [19] --> Loop 16 * CEs [17] --> Loop 17 * CEs [16] --> Loop 18 * CEs [18] --> Loop 19 ### Ranking functions of CR eval_foo_bb0_in(V_x,V_y,B) #### Partial ranking functions of CR eval_foo_bb0_in(V_x,V_y,B) ### Specialization of cost equations eval_foo_start/3 * CE 1 is refined into CE [20,21,22,23] ### Cost equations --> "Loop" of eval_foo_start/3 * CEs [23] --> Loop 20 * CEs [22] --> Loop 21 * CEs [21] --> Loop 22 * CEs [20] --> Loop 23 ### Ranking functions of CR eval_foo_start(V_x,V_y,B) #### Partial ranking functions of CR eval_foo_start(V_x,V_y,B) Computing Bounds ===================================== #### Cost of chains of eval_foo_bb3_in(V_1,V__1,B,C): * Chain [[8],10]: 1*it(8)+0 Such that:it(8) =< V__1-C with precondition: [B=2,V_1>=1,C>=V_1,V__1>=C+1] * Chain [[8],9]: 1*it(8)+0 Such that:it(8) =< V__1-C with precondition: [B=2,V_1=C+1,V_1>=1,V__1>=V_1] * Chain [10]: 0 with precondition: [B=2,V__1=C,V_1>=1,V__1>=V_1] * Chain [9]: 0 with precondition: [B=2,V__1=C,V_1>=1,V_1>=V__1+1] #### Cost of chains of eval_foo_bb1_in(V__01,V__0,B): * Chain [[12],[11,13,14],15]: 4*it(11)+1*it(12)+1*it(14)+0 Such that:it(12) =< -V__01 it(14) =< 2*V__01+V__0 aux(7) =< V__01+V__0/2 it(11) =< aux(7) it(14) =< aux(7) with precondition: [B=3,0>=V__01+1,V__0+2*V__01>=2] * Chain [[12],15]: 1*it(12)+0 Such that:it(12) =< -V__01 it(12) =< V__0/2 with precondition: [B=3,0>=V__01+1,V__0>=2,1>=2*V__01+V__0] * Chain [[11,13,14],15]: 2*it(11)+1*it(14)+2*s(5)+0 Such that:it(14) =< V__0 aux(5) =< V__01+V__0/2 aux(6) =< V__0/2 s(5) =< aux(5) it(14) =< aux(5) it(11) =< aux(6) it(14) =< aux(6) with precondition: [B=3,V__01>=0,V__0>=2] * Chain [15]: 0 with precondition: [B=3,1>=V__0] #### Cost of chains of eval_foo_bb0_in(V_x,V_y,B): * Chain [19]: 0 with precondition: [1>=V_x] * Chain [18]: 1*s(7)+0 Such that:s(7) =< V_x/2 s(7) =< -V_y with precondition: [0>=V_y+1,V_x>=2,1>=2*V_y+V_x] * Chain [17]: 1*s(8)+1*s(9)+4*s(11)+0 Such that:s(9) =< V_x+2*V_y s(10) =< V_x/2+V_y s(8) =< -V_y s(11) =< s(10) s(9) =< s(10) with precondition: [0>=V_y+1,V_x+2*V_y>=2] * Chain [16]: 1*s(12)+2*s(15)+2*s(16)+0 Such that:s(12) =< V_x s(14) =< V_x/2 s(13) =< V_x/2+V_y s(15) =< s(13) s(12) =< s(13) s(16) =< s(14) s(12) =< s(14) with precondition: [V_x>=2,V_y>=0] #### Cost of chains of eval_foo_start(V_x,V_y,B): * Chain [23]: 0 with precondition: [1>=V_x] * Chain [22]: 1*s(17)+0 Such that:s(17) =< V_x/2 s(17) =< -V_y with precondition: [0>=V_y+1,V_x>=2,1>=2*V_y+V_x] * Chain [21]: 1*s(18)+1*s(20)+4*s(21)+0 Such that:s(18) =< V_x+2*V_y s(19) =< V_x/2+V_y s(20) =< -V_y s(21) =< s(19) s(18) =< s(19) with precondition: [0>=V_y+1,V_x+2*V_y>=2] * Chain [20]: 1*s(22)+2*s(25)+2*s(26)+0 Such that:s(22) =< V_x s(23) =< V_x/2 s(24) =< V_x/2+V_y s(25) =< s(24) s(22) =< s(24) s(26) =< s(23) s(22) =< s(23) with precondition: [V_x>=2,V_y>=0] Closed-form bounds of eval_foo_start(V_x,V_y,B): ------------------------------------- * Chain [23] with precondition: [1>=V_x] - Upper bound: 0 - Complexity: constant * Chain [22] with precondition: [0>=V_y+1,V_x>=2,1>=2*V_y+V_x] - Upper bound: V_x/2 - Complexity: n * Chain [21] with precondition: [0>=V_y+1,V_x+2*V_y>=2] - Upper bound: 3*V_x+5*V_y - Complexity: n * Chain [20] with precondition: [V_x>=2,V_y>=0] - Upper bound: 3*V_x+2*V_y - Complexity: n ### Maximum cost of eval_foo_start(V_x,V_y,B): max([nat(V_x/2),nat(V_x/2+V_y)*2+max([nat(V_x/2)*2+nat(V_x),nat(V_x+2*V_y)+nat(-V_y)+nat(V_x/2+V_y)*2])]) Asymptotic class: n * Total analysis performed in 204 ms.