/export/starexec/sandbox2/solver/bin/starexec_run_C /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^4)) Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [eval_textbook_ex3_bb4_in/4,eval_textbook_ex3_bb5_in/4] 1. recursive : [eval_textbook_ex3_bb3_in/5,eval_textbook_ex3_bb4_in_loop_cont/6] 2. recursive : [eval_textbook_ex3_bb2_in/5,eval_textbook_ex3_bb3_in_loop_cont/8,eval_textbook_ex3_bb6_in/7] 3. recursive : [eval_textbook_ex3_bb1_in/3,eval_textbook_ex3_bb2_in_loop_cont/5,eval_textbook_ex3_bb7_in/4] 4. non_recursive : [eval_textbook_ex3_stop/1] 5. non_recursive : [eval_textbook_ex3_bb8_in/1] 6. non_recursive : [eval_textbook_ex3_bb1_in_loop_cont/2] 7. non_recursive : [eval_textbook_ex3_bb0_in/2] 8. non_recursive : [eval_textbook_ex3_start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into eval_textbook_ex3_bb4_in/4 1. SCC is partially evaluated into eval_textbook_ex3_bb3_in/5 2. SCC is partially evaluated into eval_textbook_ex3_bb2_in/5 3. SCC is partially evaluated into eval_textbook_ex3_bb1_in/3 4. SCC is completely evaluated into other SCCs 5. SCC is completely evaluated into other SCCs 6. SCC is completely evaluated into other SCCs 7. SCC is partially evaluated into eval_textbook_ex3_bb0_in/2 8. SCC is partially evaluated into eval_textbook_ex3_start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations eval_textbook_ex3_bb4_in/4 * CE 10 is refined into CE [11] * CE 9 is refined into CE [12] ### Cost equations --> "Loop" of eval_textbook_ex3_bb4_in/4 * CEs [12] --> Loop 11 * CEs [11] --> Loop 12 ### Ranking functions of CR eval_textbook_ex3_bb4_in(V_i_0_sink,V_2,V_l_0,B) * RF of phase [11]: [V_2-V_l_0+1,V_i_0_sink-V_l_0+2] #### Partial ranking functions of CR eval_textbook_ex3_bb4_in(V_i_0_sink,V_2,V_l_0,B) * Partial RF of phase [11]: - RF of loop [11:1]: V_2-V_l_0+1 V_i_0_sink-V_l_0+2 ### Specialization of cost equations eval_textbook_ex3_bb3_in/5 * CE 8 is refined into CE [13] * CE 7 is refined into CE [14] ### Cost equations --> "Loop" of eval_textbook_ex3_bb3_in/5 * CEs [14] --> Loop 13 * CEs [13] --> Loop 14 ### Ranking functions of CR eval_textbook_ex3_bb3_in(V_m,V_i_0_sink,B,C,D) * RF of phase [13]: [V_m-V_i_0_sink] #### Partial ranking functions of CR eval_textbook_ex3_bb3_in(V_m,V_i_0_sink,B,C,D) * Partial RF of phase [13]: - RF of loop [13:1]: V_m-V_i_0_sink ### Specialization of cost equations eval_textbook_ex3_bb2_in/5 * CE 6 is refined into CE [15] * CE 5 is refined into CE [16,17] ### Cost equations --> "Loop" of eval_textbook_ex3_bb2_in/5 * CEs [17] --> Loop 15 * CEs [16] --> Loop 16 * CEs [15] --> Loop 17 ### Ranking functions of CR eval_textbook_ex3_bb2_in(V_m,V_i_0,V_j_0,B,C) * RF of phase [15]: [V_i_0-V_j_0+1,V_m-V_j_0] * RF of phase [16]: [V_i_0-V_j_0+1,V_m-V_j_0+1] #### Partial ranking functions of CR eval_textbook_ex3_bb2_in(V_m,V_i_0,V_j_0,B,C) * Partial RF of phase [15]: - RF of loop [15:1]: V_i_0-V_j_0+1 V_m-V_j_0 * Partial RF of phase [16]: - RF of loop [16:1]: V_i_0-V_j_0+1 V_m-V_j_0+1 ### Specialization of cost equations eval_textbook_ex3_bb1_in/3 * CE 4 is refined into CE [18] * CE 3 is refined into CE [19,20] ### Cost equations --> "Loop" of eval_textbook_ex3_bb1_in/3 * CEs [20] --> Loop 18 * CEs [19] --> Loop 19 * CEs [18] --> Loop 20 ### Ranking functions of CR eval_textbook_ex3_bb1_in(V_m,V_i_0,B) * RF of phase [18]: [V_m-V_i_0] #### Partial ranking functions of CR eval_textbook_ex3_bb1_in(V_m,V_i_0,B) * Partial RF of phase [18]: - RF of loop [18:1]: V_m-V_i_0 ### Specialization of cost equations eval_textbook_ex3_bb0_in/2 * CE 2 is refined into CE [21,22,23] ### Cost equations --> "Loop" of eval_textbook_ex3_bb0_in/2 * CEs [23] --> Loop 21 * CEs [22] --> Loop 22 * CEs [21] --> Loop 23 ### Ranking functions of CR eval_textbook_ex3_bb0_in(V_m,B) #### Partial ranking functions of CR eval_textbook_ex3_bb0_in(V_m,B) ### Specialization of cost equations eval_textbook_ex3_start/2 * CE 1 is refined into CE [24,25,26] ### Cost equations --> "Loop" of eval_textbook_ex3_start/2 * CEs [26] --> Loop 24 * CEs [25] --> Loop 25 * CEs [24] --> Loop 26 ### Ranking functions of CR eval_textbook_ex3_start(V_m,B) #### Partial ranking functions of CR eval_textbook_ex3_start(V_m,B) Computing Bounds ===================================== #### Cost of chains of eval_textbook_ex3_bb4_in(V_i_0_sink,V_2,V_l_0,B): * Chain [[11],12]: 1*it(11)+0 Such that:it(11) =< V_i_0_sink-V_l_0+2 with precondition: [B=2,V_i_0_sink+1=V_2,V_i_0_sink>=1,V_l_0>=1,V_i_0_sink+1>=V_l_0] #### Cost of chains of eval_textbook_ex3_bb3_in(V_m,V_i_0_sink,B,C,D): * Chain [[13],14]: 1*it(13)+1*s(3)+0 Such that:it(13) =< -V_i_0_sink+D aux(1) =< D s(3) =< it(13)*aux(1) with precondition: [B=3,V_m=C,V_m+1=D,V_i_0_sink>=1,V_m>=V_i_0_sink+1] * Chain [14]: 0 with precondition: [B=3,V_i_0_sink=V_m,V_i_0_sink=C,V_i_0_sink+1=D,V_i_0_sink>=1] #### Cost of chains of eval_textbook_ex3_bb2_in(V_m,V_i_0,V_j_0,B,C): * Chain [[16],17]: 1*it(16)+0 Such that:it(16) =< -V_j_0+C with precondition: [B=4,V_m=V_i_0,V_m+1=C,V_j_0>=1,V_m>=V_j_0] * Chain [[15],17]: 1*it(15)+1*s(10)+1*s(11)+0 Such that:s(7) =< V_m+1 aux(2) =< V_m-C+2 it(15) =< -V_j_0+C s(10) =< it(15)*aux(2) s(11) =< s(10)*s(7) with precondition: [B=4,V_i_0+1=C,V_j_0>=1,V_m>=V_i_0+1,V_i_0>=V_j_0] #### Cost of chains of eval_textbook_ex3_bb1_in(V_m,V_i_0,B): * Chain [[18],19,20]: 1*it(18)+1*s(12)+1*s(23)+1*s(24)+1*s(25)+1 Such that:aux(3) =< V_m it(18) =< V_m-V_i_0 s(19) =< V_m-V_i_0+1 aux(4) =< V_m+1 s(12) =< aux(4) aux(3) =< aux(4)-1 s(23) =< it(18)*aux(3) s(24) =< s(23)*s(19) s(25) =< s(24)*aux(4) with precondition: [B=5,V_i_0>=1,V_m>=V_i_0+1] * Chain [20]: 0 with precondition: [B=5,V_i_0>=1,V_i_0>=V_m+1] * Chain [19,20]: 1*s(12)+1 Such that:s(12) =< V_m+1 with precondition: [B=5,V_m=V_i_0,V_m>=1] #### Cost of chains of eval_textbook_ex3_bb0_in(V_m,B): * Chain [23]: 1*s(26)+1 Such that:s(26) =< 2 with precondition: [V_m=1] * Chain [22]: 0 with precondition: [0>=V_m] * Chain [21]: 1*s(28)+1*s(31)+1*s(32)+1*s(33)+1*s(34)+1 Such that:s(30) =< V_m+1 aux(5) =< V_m s(27) =< aux(5) s(28) =< aux(5) s(31) =< s(30) s(27) =< s(30)-1 s(32) =< s(28)*s(27) s(33) =< s(32)*aux(5) s(34) =< s(33)*s(30) with precondition: [V_m>=2] #### Cost of chains of eval_textbook_ex3_start(V_m,B): * Chain [26]: 1*s(35)+1 Such that:s(35) =< 2 with precondition: [V_m=1] * Chain [25]: 0 with precondition: [0>=V_m] * Chain [24]: 1*s(39)+1*s(40)+1*s(41)+1*s(42)+1*s(43)+1 Such that:s(37) =< V_m s(36) =< V_m+1 s(38) =< s(37) s(39) =< s(37) s(40) =< s(36) s(38) =< s(36)-1 s(41) =< s(39)*s(38) s(42) =< s(41)*s(37) s(43) =< s(42)*s(36) with precondition: [V_m>=2] Closed-form bounds of eval_textbook_ex3_start(V_m,B): ------------------------------------- * Chain [26] with precondition: [V_m=1] - Upper bound: 3 - Complexity: constant * Chain [25] with precondition: [0>=V_m] - Upper bound: 0 - Complexity: constant * Chain [24] with precondition: [V_m>=2] - Upper bound: V_m+1+V_m*V_m+V_m*V_m*V_m+(V_m+1)*(V_m*V_m*V_m)+(V_m+1) - Complexity: n^4 ### Maximum cost of eval_textbook_ex3_start(V_m,B): max([3,nat(V_m)+1+nat(V_m)*nat(V_m)+nat(V_m)*nat(V_m)*nat(V_m)+nat(V_m)*nat(V_m)*nat(V_m)*nat(V_m+1)+nat(V_m+1)]) Asymptotic class: n^4 * Total analysis performed in 280 ms.