/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_2/4,eval_foo_3/5,eval_foo_bb3_in/4,eval_foo_bb4_in/4,eval_foo_bb5_in/5] 1. recursive : [eval_foo_0/4,eval_foo_1/5,eval_foo__critedge_in/6,eval_foo_bb1_in/4,eval_foo_bb2_in/4,eval_foo_bb3_in_loop_cont/7,eval_foo_bb6_in/7] 2. non_recursive : [eval_foo_stop/1] 3. non_recursive : [eval_foo_bb7_in/1] 4. non_recursive : [eval_foo_bb1_in_loop_cont/2] 5. non_recursive : [eval_foo_bb0_in/2] 6. non_recursive : [eval_foo_start/4] #### 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/4 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/2 6. SCC is partially evaluated into eval_foo_start/4 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations eval_foo_bb3_in/4 * CE 7 is refined into CE [10] * CE 9 is refined into CE [11] * CE 8 is refined into CE [12] ### Cost equations --> "Loop" of eval_foo_bb3_in/4 * CEs [12] --> Loop 10 * CEs [10] --> Loop 11 * CEs [11] --> Loop 12 ### Ranking functions of CR eval_foo_bb3_in(V_m,V__12,B,C) * RF of phase [10]: [V_m-V__12+1] #### Partial ranking functions of CR eval_foo_bb3_in(V_m,V__12,B,C) * Partial RF of phase [10]: - RF of loop [10:1]: V_m-V__12+1 ### Specialization of cost equations eval_foo_bb1_in/4 * CE 5 is refined into CE [13] * CE 6 is refined into CE [14] * CE 4 is refined into CE [15,16,17,18] * CE 3 is refined into CE [19] ### Cost equations --> "Loop" of eval_foo_bb1_in/4 * CEs [16] --> Loop 13 * CEs [17] --> Loop 14 * CEs [19] --> Loop 15 * CEs [18] --> Loop 16 * CEs [15] --> Loop 17 * CEs [13] --> Loop 18 * CEs [14] --> Loop 19 ### Ranking functions of CR eval_foo_bb1_in(V_m,V__01,V__0,B) #### Partial ranking functions of CR eval_foo_bb1_in(V_m,V__01,V__0,B) * Partial RF of phase [13,14,15,16,17]: - RF of loop [13:1]: V__01 depends on loops [16:1,17:1] -V_m+V__01 depends on loops [16:1,17:1] - RF of loop [13:1,14:1,16:1,17:1]: V__0+1 - RF of loop [14:1,15:1]: V__01+1 depends on loops [16:1,17:1] ### Specialization of cost equations eval_foo_bb0_in/2 * CE 2 is refined into CE [20,21] ### Cost equations --> "Loop" of eval_foo_bb0_in/2 * CEs [21] --> Loop 20 * CEs [20] --> Loop 21 ### Ranking functions of CR eval_foo_bb0_in(V_m,B) #### Partial ranking functions of CR eval_foo_bb0_in(V_m,B) ### Specialization of cost equations eval_foo_start/4 * CE 1 is refined into CE [22,23] ### Cost equations --> "Loop" of eval_foo_start/4 * CEs [23] --> Loop 22 * CEs [22] --> Loop 23 ### Ranking functions of CR eval_foo_start(V_x,V_y,V_m,B) #### Partial ranking functions of CR eval_foo_start(V_x,V_y,V_m,B) Computing Bounds ===================================== #### Cost of chains of eval_foo_bb3_in(V_m,V__12,B,C): * Chain [[10],12]: 1*it(10)+0 Such that:it(10) =< -V__12+C with precondition: [B=2,V_m+1=C,V__12>=0,V_m>=V__12] * Chain [[10],11]: 1*it(10)+0 Such that:it(10) =< -V__12+C with precondition: [B=2,V__12>=0,C>=V__12+1,V_m>=C] * Chain [12]: 0 with precondition: [B=2,V__12=C,V_m>=0,V__12>=V_m+1] * Chain [11]: 0 with precondition: [B=2,V__12=C,V__12>=0,V_m>=V__12] #### Cost of chains of eval_foo_bb1_in(V_m,V__01,V__0,B): * Chain [[13,14,15,16,17],19]: 2*it(13)+1*it(15)+2*it(16)+1*s(5)+1*s(6)+0 Such that:aux(40) =< V_m aux(29) =< V_m-V__01+V__0+1 aux(41) =< -V__01+V__0 aux(41) =< V__0 aux(46) =< V__01+1 aux(47) =< V__0+1 it(13) =< aux(47) it(16) =< aux(47) aux(31) =< aux(40)+1 aux(25) =< aux(40) aux(22) =< it(16)*aux(40) s(5) =< it(16)*aux(40) aux(26) =< it(16)*aux(25) aux(7) =< aux(22) aux(7) =< aux(26) aux(33) =< it(16)*aux(31) s(6) =< it(16)*aux(31) it(13) =< aux(33)+aux(7)+aux(46) it(15) =< aux(33)+aux(7)+aux(46) s(6) =< it(15)+aux(41) s(6) =< it(15)+aux(29) with precondition: [B=3,V__01>=0,V__0>=0,V_m>=V__0] * Chain [[13,14,15,16,17],18]: 2*it(13)+1*it(15)+2*it(16)+1*s(5)+1*s(6)+0 Such that:aux(40) =< V_m aux(29) =< V_m-V__01+V__0+1 aux(41) =< V_m+V__0+1 aux(48) =< V__01+1 aux(49) =< V__0+1 it(13) =< aux(49) it(16) =< aux(49) aux(31) =< aux(40)+1 aux(25) =< aux(40) aux(22) =< it(16)*aux(40) s(5) =< it(16)*aux(40) aux(26) =< it(16)*aux(25) aux(7) =< aux(22) aux(7) =< aux(26) aux(33) =< it(16)*aux(31) s(6) =< it(16)*aux(31) it(13) =< aux(33)+aux(7)+aux(48) it(15) =< aux(33)+aux(7)+aux(48) s(6) =< it(15)+aux(41) s(6) =< it(15)+aux(29) with precondition: [B=3,V__01>=0,V__0>=0,V_m>=V__0] * Chain [18]: 0 with precondition: [B=3,0>=V__0+1,V__01+1>=0,V_m>=V__0] #### Cost of chains of eval_foo_bb0_in(V_m,B): * Chain [21]: 0 with precondition: [0>=V_m+1] * Chain [20]: 4*s(45)+4*s(46)+2*s(50)+1*s(54)+2*s(55)+1*s(56)+0 Such that:s(43) =< 1 s(44) =< V_m+1 aux(54) =< V_m aux(55) =< 2*V_m+1 s(45) =< s(44) s(46) =< s(44) s(47) =< aux(54)+1 s(48) =< aux(54) s(49) =< s(46)*aux(54) s(50) =< s(46)*aux(54) s(51) =< s(46)*s(48) s(52) =< s(49) s(52) =< s(51) s(53) =< s(46)*s(47) s(54) =< s(46)*s(47) s(45) =< s(53)+s(52)+s(43) s(55) =< s(53)+s(52)+s(43) s(54) =< s(55)+aux(55) s(56) =< s(46)*s(47) s(56) =< s(55)+aux(54) s(56) =< s(55)+aux(55) with precondition: [V_m>=0] #### Cost of chains of eval_foo_start(V_x,V_y,V_m,B): * Chain [23]: 0 with precondition: [0>=V_m+1] * Chain [22]: 4*s(61)+4*s(62)+2*s(66)+1*s(70)+2*s(71)+1*s(72)+0 Such that:s(57) =< 1 s(59) =< V_m s(58) =< V_m+1 s(60) =< 2*V_m+1 s(61) =< s(58) s(62) =< s(58) s(63) =< s(59)+1 s(64) =< s(59) s(65) =< s(62)*s(59) s(66) =< s(62)*s(59) s(67) =< s(62)*s(64) s(68) =< s(65) s(68) =< s(67) s(69) =< s(62)*s(63) s(70) =< s(62)*s(63) s(61) =< s(69)+s(68)+s(57) s(71) =< s(69)+s(68)+s(57) s(70) =< s(71)+s(60) s(72) =< s(62)*s(63) s(72) =< s(71)+s(59) s(72) =< s(71)+s(60) with precondition: [V_m>=0] Closed-form bounds of eval_foo_start(V_x,V_y,V_m,B): ------------------------------------- * Chain [23] with precondition: [0>=V_m+1] - Upper bound: 0 - Complexity: constant * Chain [22] with precondition: [V_m>=0] - Upper bound: (V_m+1)*(8*V_m)+2+(12*V_m+12) - Complexity: n^2 ### Maximum cost of eval_foo_start(V_x,V_y,V_m,B): nat(V_m)*8*nat(V_m+1)+2+nat(V_m+1)*12 Asymptotic class: n^2 * Total analysis performed in 382 ms.