/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_Loopus2014_ex1_6/8,eval_Loopus2014_ex1_7/9,eval_Loopus2014_ex1_bb5_in/8,eval_Loopus2014_ex1_bb6_in/8,eval_Loopus2014_ex1_bb7_in/8,eval_Loopus2014_ex1_bb8_in/9,eval_Loopus2014_ex1_bb9_in/10] 1. recursive : [eval_Loopus2014_ex1_bb3_in/8,eval_Loopus2014_ex1_bb4_in/8,eval_Loopus2014_ex1_bb5_in_loop_cont/9] 2. recursive : [eval_Loopus2014_ex1_bb1_in/4,eval_Loopus2014_ex1_bb2_in/4,eval_Loopus2014_ex1_bb3_in_loop_cont/5] 3. non_recursive : [eval_Loopus2014_ex1_stop/1] 4. non_recursive : [eval_Loopus2014_ex1_bb10_in/1] 5. non_recursive : [eval_Loopus2014_ex1_bb1_in_loop_cont/2] 6. non_recursive : [eval_Loopus2014_ex1_bb0_in/2] 7. non_recursive : [eval_Loopus2014_ex1_start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into eval_Loopus2014_ex1_bb5_in/8 1. SCC is partially evaluated into eval_Loopus2014_ex1_bb3_in/8 2. SCC is partially evaluated into eval_Loopus2014_ex1_bb1_in/4 3. SCC is completely evaluated into other SCCs 4. SCC is completely evaluated into other SCCs 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into eval_Loopus2014_ex1_bb0_in/2 7. SCC is partially evaluated into eval_Loopus2014_ex1_start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations eval_Loopus2014_ex1_bb5_in/8 * CE 10 is refined into CE [11] * CE 7 is refined into CE [12] * CE 9 is refined into CE [13] * CE 8 is refined into CE [14] ### Cost equations --> "Loop" of eval_Loopus2014_ex1_bb5_in/8 * CEs [12] --> Loop 11 * CEs [13] --> Loop 12 * CEs [14] --> Loop 13 * CEs [11] --> Loop 14 ### Ranking functions of CR eval_Loopus2014_ex1_bb5_in(V_b_1,V_a_1,V_i_0,V_b_2,V_a_2,B,C,D) * RF of phase [11,13]: [V_i_0] * RF of phase [12]: [V_i_0] #### Partial ranking functions of CR eval_Loopus2014_ex1_bb5_in(V_b_1,V_a_1,V_i_0,V_b_2,V_a_2,B,C,D) * Partial RF of phase [11,13]: - RF of loop [11:1,13:1]: V_i_0 - RF of loop [13:1]: V_a_2 V_b_1+V_a_1-V_b_2-1 * Partial RF of phase [12]: - RF of loop [12:1]: V_i_0 ### Specialization of cost equations eval_Loopus2014_ex1_bb3_in/8 * CE 6 is refined into CE [15] * CE 5 is refined into CE [16,17,18,19] ### Cost equations --> "Loop" of eval_Loopus2014_ex1_bb3_in/8 * CEs [19] --> Loop 15 * CEs [18] --> Loop 16 * CEs [17] --> Loop 17 * CEs [16] --> Loop 18 * CEs [15] --> Loop 19 ### Ranking functions of CR eval_Loopus2014_ex1_bb3_in(V_n,V_b_0,V_a_0,V_b_1,V_a_1,B,C,D) * RF of phase [15]: [V_b_1+V_a_1-1] * RF of phase [16]: [V_b_1] * RF of phase [17]: [V_b_1] #### Partial ranking functions of CR eval_Loopus2014_ex1_bb3_in(V_n,V_b_0,V_a_0,V_b_1,V_a_1,B,C,D) * Partial RF of phase [15]: - RF of loop [15:1]: V_b_1+V_a_1-1 * Partial RF of phase [16]: - RF of loop [16:1]: V_b_1 * Partial RF of phase [17]: - RF of loop [17:1]: V_b_1 ### Specialization of cost equations eval_Loopus2014_ex1_bb1_in/4 * CE 4 is refined into CE [20] * CE 3 is refined into CE [21,22,23,24,25,26,27] ### Cost equations --> "Loop" of eval_Loopus2014_ex1_bb1_in/4 * CEs [27] --> Loop 20 * CEs [26] --> Loop 21 * CEs [25] --> Loop 22 * CEs [24] --> Loop 23 * CEs [23] --> Loop 24 * CEs [22] --> Loop 25 * CEs [21] --> Loop 26 * CEs [20] --> Loop 27 ### Ranking functions of CR eval_Loopus2014_ex1_bb1_in(V_n,V_b_0,V_a_0,B) * RF of phase [21]: [V_a_0-1] * RF of phase [22]: [V_a_0] #### Partial ranking functions of CR eval_Loopus2014_ex1_bb1_in(V_n,V_b_0,V_a_0,B) * Partial RF of phase [21]: - RF of loop [21:1]: V_a_0-1 * Partial RF of phase [22]: - RF of loop [22:1]: V_a_0 ### Specialization of cost equations eval_Loopus2014_ex1_bb0_in/2 * CE 2 is refined into CE [28,29,30,31,32] ### Cost equations --> "Loop" of eval_Loopus2014_ex1_bb0_in/2 * CEs [32] --> Loop 28 * CEs [31] --> Loop 29 * CEs [30] --> Loop 30 * CEs [29] --> Loop 31 * CEs [28] --> Loop 32 ### Ranking functions of CR eval_Loopus2014_ex1_bb0_in(V_n,B) #### Partial ranking functions of CR eval_Loopus2014_ex1_bb0_in(V_n,B) ### Specialization of cost equations eval_Loopus2014_ex1_start/2 * CE 1 is refined into CE [33,34,35,36,37] ### Cost equations --> "Loop" of eval_Loopus2014_ex1_start/2 * CEs [37] --> Loop 33 * CEs [36] --> Loop 34 * CEs [35] --> Loop 35 * CEs [34] --> Loop 36 * CEs [33] --> Loop 37 ### Ranking functions of CR eval_Loopus2014_ex1_start(V_n,B) #### Partial ranking functions of CR eval_Loopus2014_ex1_start(V_n,B) Computing Bounds ===================================== #### Cost of chains of eval_Loopus2014_ex1_bb5_in(V_b_1,V_a_1,V_i_0,V_b_2,V_a_2,B,C,D): * Chain [[12],14]: 1*it(12)+0 Such that:it(12) =< V_i_0 with precondition: [B=2,V_b_2=C,V_a_1+V_b_1=V_a_2+V_b_2+1,V_a_1+V_b_1=V_b_2+D+1,V_b_1>=1,V_i_0>=1,V_b_2+1>=V_b_1,V_b_2+1>=V_a_1+V_b_1] * Chain [[11,13],[12],14]: 1*it(11)+1*it(12)+1*it(13)+0 Such that:it(12) =< V_i_0+V_b_2-C it(13) =< -V_b_2+C aux(3) =< V_i_0 it(12) =< aux(3) it(11) =< aux(3) it(13) =< aux(3) with precondition: [B=2,D=0,V_a_1+V_b_1=C+1,V_a_1+V_b_1=V_a_2+V_b_2+1,V_b_1>=1,V_a_2>=1,V_a_1>=V_a_2,V_i_0>=V_a_2+1] * Chain [[11,13],14]: 1*it(11)+1*it(13)+0 Such that:it(13) =< V_a_2-D aux(4) =< V_i_0 it(11) =< aux(4) it(13) =< aux(4) with precondition: [B=2,V_a_1+V_b_1=V_a_2+V_b_2+1,V_a_1+V_b_1=C+D+1,V_b_1>=1,V_i_0>=1,V_a_2>=1,V_a_1>=V_a_2,V_a_1+V_b_1>=C+1,V_a_2+C+1>=V_a_1+V_b_1,V_a_1+V_b_1+V_i_0>=V_a_2+C+1] * Chain [14]: 0 with precondition: [B=2,V_b_2=C,V_a_2=D,V_a_2+V_b_2+1=V_a_1+V_b_1,0>=V_i_0,V_b_1>=1,V_b_2+1>=V_b_1] #### Cost of chains of eval_Loopus2014_ex1_bb3_in(V_n,V_b_0,V_a_0,V_b_1,V_a_1,B,C,D): * Chain [[17],19]: 1*it(17)+0 Such that:it(17) =< V_b_1 with precondition: [B=3,C=0,V_a_0=V_a_1+1,V_a_0=D+1,1>=V_n,V_a_0>=1,V_b_1>=1,V_b_0+1>=V_b_1] * Chain [[16],19]: 1*it(16)+1*s(3)+0 Such that:aux(5) =< V_n it(16) =< V_b_1 s(3) =< it(16)*aux(5) with precondition: [V_a_1=0,B=3,C=0,D=0,V_n>=2,V_a_0>=1,V_b_1>=1,V_a_0+V_b_0>=V_b_1] * Chain [[15],[16],19]: 2*it(15)+1*s(3)+1*s(10)+1*s(11)+0 Such that:s(10) =< V_a_1 aux(7) =< V_n aux(8) =< V_b_1+V_a_1 it(15) =< aux(8) s(3) =< it(15)*aux(7) s(12) =< it(15)*aux(7) s(11) =< s(12) s(10) =< s(12) with precondition: [B=3,C=0,D=0,V_n>=2,V_b_1>=1,V_a_1>=1,V_a_0>=V_a_1+1,V_a_0+V_b_0>=V_a_1+V_b_1] * Chain [[15],19]: 1*it(15)+1*s(10)+1*s(11)+0 Such that:aux(6) =< V_n it(15) =< V_b_1+V_a_1-D s(10) =< V_a_1-D s(12) =< it(15)*aux(6) s(11) =< s(12) s(10) =< s(12) with precondition: [B=3,C=0,V_n>=2,V_b_1>=1,D>=1,V_a_0>=V_a_1+1,V_a_1>=D,V_a_0+V_b_0>=V_a_1+V_b_1] * Chain [[15],18,[16],19]: 2*it(15)+1*s(3)+1*s(10)+1*s(11)+2*s(13)+1*s(14)+1 Such that:aux(10) =< V_n aux(11) =< V_b_1+V_a_1 aux(12) =< V_a_1 s(13) =< aux(10) s(14) =< aux(10) it(15) =< aux(11) s(10) =< aux(12) s(14) =< aux(12) s(3) =< it(15)*aux(10) s(12) =< it(15)*aux(10) s(11) =< s(12) s(10) =< s(12) with precondition: [B=3,C=0,D=0,V_n>=3,V_b_1>=1,V_a_1>=1,V_a_0>=V_a_1+1,V_a_1+V_b_1>=3,V_a_0+V_b_0>=V_a_1+V_b_1] * Chain [19]: 0 with precondition: [B=3,V_b_1=C,V_a_1=D,0>=V_b_1,V_a_1>=0,V_a_0>=V_a_1+1,V_a_0+V_b_0>=V_a_1+V_b_1] * Chain [18,[16],19]: 1*it(16)+1*s(3)+1*s(13)+1*s(14)+1*s(16)+1 Such that:s(13) =< V_n-V_a_1 it(16) =< V_b_1+V_a_1 s(14) =< V_a_1 aux(9) =< V_n s(3) =< it(16)*aux(9) s(13) =< aux(9) s(16) =< aux(9) s(14) =< aux(9) with precondition: [B=3,C=0,D=0,V_b_1>=1,V_a_1>=1,V_n>=V_a_1+2,V_a_0>=V_a_1+1,V_a_0+V_b_0>=V_a_1+V_b_1] #### Cost of chains of eval_Loopus2014_ex1_bb1_in(V_n,V_b_0,V_a_0,B): * Chain [[22],27]: 2*it(22)+0 Such that:aux(16) =< 1 it(22) =< aux(16) with precondition: [V_n=1,V_b_0=0,V_a_0=1,B=4] * Chain [[21],26,27]: 2*it(21)+1*s(21)+1*s(22)+1*s(35)+1*s(36)+1 Such that:s(21) =< 1 aux(20) =< V_n aux(21) =< V_a_0 s(22) =< s(21)*aux(20) it(21) =< aux(21) s(35) =< aux(21) s(37) =< it(21)*aux(20) s(36) =< s(37) s(35) =< s(37) with precondition: [V_b_0=0,B=4,V_a_0>=2,V_n>=V_a_0] * Chain [[21],25,27]: 4*it(21)+2*s(35)+2*s(36)+1*s(43)+1 Such that:aux(23) =< V_n aux(24) =< V_a_0 s(35) =< aux(24) it(21) =< aux(24) s(43) =< it(21)*aux(23) s(37) =< it(21)*aux(23) s(36) =< s(37) s(35) =< s(37) with precondition: [V_b_0=0,B=4,V_a_0>=3,V_n>=V_a_0] * Chain [[21],24,27]: 4*it(21)+2*s(35)+2*s(36)+2*s(49)+1*s(50)+1*s(53)+2 Such that:aux(26) =< V_n aux(27) =< V_a_0 s(49) =< aux(26) s(50) =< aux(26) it(21) =< aux(27) s(35) =< aux(27) s(50) =< aux(27) s(53) =< it(21)*aux(26) s(37) =< it(21)*aux(26) s(36) =< s(37) s(35) =< s(37) with precondition: [V_b_0=0,B=4,V_a_0>=4,V_n>=V_a_0] * Chain [[21],23,27]: 2*it(21)+1*s(35)+1*s(36)+1*s(56)+1*s(57)+1*s(58)+1*s(60)+1*s(61)+2 Such that:aux(29) =< V_n aux(30) =< V_n+1 aux(31) =< V_a_0 s(56) =< aux(29) aux(28) =< aux(30) s(56) =< aux(30) aux(28) =< aux(31) s(57) =< aux(28) s(58) =< aux(28) s(60) =< s(57)*aux(29) s(61) =< aux(29) s(58) =< aux(29) it(21) =< aux(31) s(35) =< aux(31) s(37) =< it(21)*aux(29) s(36) =< s(37) s(35) =< s(37) with precondition: [V_b_0=0,B=4,V_a_0>=3,V_n>=V_a_0] * Chain [27]: 0 with precondition: [V_b_0=0,B=4,0>=V_a_0,V_n>=V_a_0] * Chain [25,27]: 1*s(39)+2*s(42)+1*s(43)+1*s(45)+1 Such that:s(40) =< V_n aux(22) =< V_a_0 s(39) =< aux(22) s(42) =< aux(22) s(43) =< s(42)*s(40) s(44) =< s(42)*s(40) s(45) =< s(44) s(39) =< s(44) with precondition: [V_b_0=0,B=4,V_a_0>=2,V_n>=V_a_0] * Chain [24,27]: 2*s(49)+1*s(50)+2*s(51)+1*s(52)+1*s(53)+1*s(55)+2 Such that:s(46) =< V_n aux(25) =< V_a_0 s(49) =< s(46) s(50) =< s(46) s(51) =< aux(25) s(52) =< aux(25) s(50) =< aux(25) s(53) =< s(51)*s(46) s(54) =< s(51)*s(46) s(55) =< s(54) s(52) =< s(54) with precondition: [V_b_0=0,B=4,V_a_0>=3,V_n>=V_a_0] #### Cost of chains of eval_Loopus2014_ex1_bb0_in(V_n,B): * Chain [32]: 2*s(107)+0 Such that:s(106) =< 1 s(107) =< s(106) with precondition: [V_n=1] * Chain [31]: 0 with precondition: [0>=V_n] * Chain [30]: 1*s(108)+1*s(111)+4*s(112)+2*s(113)+2*s(115)+1*s(116)+1 Such that:s(108) =< 1 aux(36) =< V_n s(111) =< s(108)*aux(36) s(112) =< aux(36) s(113) =< aux(36) s(114) =< s(112)*aux(36) s(115) =< s(114) s(113) =< s(114) s(116) =< s(112)*aux(36) with precondition: [V_n>=2] * Chain [29]: 12*s(120)+4*s(123)+2*s(124)+4*s(126)+1*s(127)+1*s(129)+1*s(130)+1*s(131)+2 Such that:s(117) =< V_n+1 aux(37) =< V_n s(120) =< aux(37) s(123) =< aux(37) s(124) =< s(120)*aux(37) s(125) =< s(120)*aux(37) s(126) =< s(125) s(123) =< s(125) s(127) =< aux(37) s(128) =< s(117) s(127) =< s(117) s(128) =< aux(37) s(129) =< s(128) s(130) =< s(128) s(131) =< s(129)*aux(37) s(130) =< aux(37) with precondition: [V_n>=3] * Chain [28]: 7*s(134)+2*s(137)+1*s(138)+2*s(140)+2 Such that:aux(38) =< V_n s(134) =< aux(38) s(137) =< aux(38) s(138) =< s(134)*aux(38) s(139) =< s(134)*aux(38) s(140) =< s(139) s(137) =< s(139) with precondition: [V_n>=4] #### Cost of chains of eval_Loopus2014_ex1_start(V_n,B): * Chain [37]: 2*s(142)+0 Such that:s(141) =< 1 s(142) =< s(141) with precondition: [V_n=1] * Chain [36]: 0 with precondition: [0>=V_n] * Chain [35]: 1*s(143)+1*s(145)+4*s(146)+2*s(147)+2*s(149)+1*s(150)+1 Such that:s(143) =< 1 s(144) =< V_n s(145) =< s(143)*s(144) s(146) =< s(144) s(147) =< s(144) s(148) =< s(146)*s(144) s(149) =< s(148) s(147) =< s(148) s(150) =< s(146)*s(144) with precondition: [V_n>=2] * Chain [34]: 12*s(153)+4*s(154)+2*s(155)+4*s(157)+1*s(158)+1*s(160)+1*s(161)+1*s(162)+2 Such that:s(152) =< V_n s(151) =< V_n+1 s(153) =< s(152) s(154) =< s(152) s(155) =< s(153)*s(152) s(156) =< s(153)*s(152) s(157) =< s(156) s(154) =< s(156) s(158) =< s(152) s(159) =< s(151) s(158) =< s(151) s(159) =< s(152) s(160) =< s(159) s(161) =< s(159) s(162) =< s(160)*s(152) s(161) =< s(152) with precondition: [V_n>=3] * Chain [33]: 7*s(164)+2*s(165)+1*s(166)+2*s(168)+2 Such that:s(163) =< V_n s(164) =< s(163) s(165) =< s(163) s(166) =< s(164)*s(163) s(167) =< s(164)*s(163) s(168) =< s(167) s(165) =< s(167) with precondition: [V_n>=4] Closed-form bounds of eval_Loopus2014_ex1_start(V_n,B): ------------------------------------- * Chain [37] with precondition: [V_n=1] - Upper bound: 2 - Complexity: constant * Chain [36] with precondition: [0>=V_n] - Upper bound: 0 - Complexity: constant * Chain [35] with precondition: [V_n>=2] - Upper bound: 7*V_n+2+3*V_n*V_n - Complexity: n^2 * Chain [34] with precondition: [V_n>=3] - Upper bound: 17*V_n+2+6*V_n*V_n+(V_n+1)*V_n+(2*V_n+2) - Complexity: n^2 * Chain [33] with precondition: [V_n>=4] - Upper bound: 9*V_n+2+3*V_n*V_n - Complexity: n^2 ### Maximum cost of eval_Loopus2014_ex1_start(V_n,B): nat(V_n)*3*nat(V_n)+nat(V_n)*8+nat(V_n+1)*nat(V_n)+nat(V_n+1)*2+nat(V_n)*2+(nat(V_n)*3*nat(V_n)+nat(V_n)*7)+2 Asymptotic class: n^2 * Total analysis performed in 820 ms.