0.64/0.69 MAYBE 0.64/0.69 0.64/0.69 Preprocessing Cost Relations 0.64/0.69 ===================================== 0.64/0.69 0.64/0.69 #### Computed strongly connected components 0.64/0.69 0. non_recursive : [eval_realheapsort_stop/1] 0.64/0.69 1. non_recursive : [eval_realheapsort_bb15_in/1] 0.64/0.69 2. recursive : [eval_realheapsort_2/3,eval_realheapsort_3/4,eval_realheapsort_4/5,eval_realheapsort_5/5,eval_realheapsort_6/5,eval_realheapsort_bb2_in/3,eval_realheapsort_bb3_in/3,eval_realheapsort_bb4_in/5] 0.64/0.69 3. recursive : [eval_realheapsort__critedge_in/5,eval_realheapsort_bb1_in/4,eval_realheapsort_bb2_in_loop_cont/6] 0.64/0.69 4. recursive : [eval_realheapsort_26/5,eval_realheapsort_27/6,eval_realheapsort_28/7,eval_realheapsort_35/6,eval_realheapsort_36/7,eval_realheapsort_37/8,eval_realheapsort_38/8,eval_realheapsort_39/8,eval_realheapsort_bb10_in/5,eval_realheapsort_bb11_in/7,eval_realheapsort_bb12_in/6,eval_realheapsort_bb13_in/8,eval_realheapsort_bb7_in/5,eval_realheapsort_bb8_in/5,eval_realheapsort_bb9_in/5] 0.64/0.69 5. recursive : [eval_realheapsort_14/3,eval_realheapsort_15/3,eval_realheapsort_bb14_in/4,eval_realheapsort_bb5_in/3,eval_realheapsort_bb6_in/3,eval_realheapsort_bb7_in_loop_cont/5] 0.64/0.69 6. non_recursive : [eval_realheapsort_bb5_in_loop_cont/2] 0.64/0.69 7. non_recursive : [eval_realheapsort_bb1_in_loop_cont/4] 0.64/0.69 8. non_recursive : [eval_realheapsort_bb0_in/2] 0.64/0.69 9. non_recursive : [eval_realheapsort_start/2] 0.64/0.69 0.64/0.69 #### Obtained direct recursion through partial evaluation 0.64/0.69 0. SCC is completely evaluated into other SCCs 0.64/0.69 1. SCC is completely evaluated into other SCCs 0.64/0.69 2. SCC is partially evaluated into eval_realheapsort_bb2_in/3 0.64/0.69 3. SCC is partially evaluated into eval_realheapsort_bb1_in/4 0.64/0.69 4. SCC is partially evaluated into eval_realheapsort_bb7_in/5 0.64/0.69 5. SCC is partially evaluated into eval_realheapsort_bb5_in/3 0.64/0.69 6. SCC is completely evaluated into other SCCs 0.64/0.69 7. SCC is partially evaluated into eval_realheapsort_bb1_in_loop_cont/4 0.64/0.69 8. SCC is partially evaluated into eval_realheapsort_bb0_in/2 0.64/0.69 9. SCC is partially evaluated into eval_realheapsort_start/2 0.64/0.69 0.64/0.69 Control-Flow Refinement of Cost Relations 0.64/0.69 ===================================== 0.64/0.69 0.64/0.69 ### Specialization of cost equations eval_realheapsort_bb2_in/3 0.64/0.69 * CE 8 is refined into CE [18] 0.64/0.69 * CE 9 is refined into CE [19] 0.64/0.69 * CE 7 is refined into CE [20] 0.64/0.69 0.64/0.69 0.64/0.69 ### Cost equations --> "Loop" of eval_realheapsort_bb2_in/3 0.64/0.69 * CEs [20] --> Loop 18 0.64/0.69 * CEs [18] --> Loop 19 0.64/0.69 * CEs [19] --> Loop 20 0.64/0.69 0.64/0.69 ### Ranking functions of CR eval_realheapsort_bb2_in(V_j_0,B,C) 0.64/0.69 * RF of phase [18]: [V_j_0] 0.64/0.69 0.64/0.69 #### Partial ranking functions of CR eval_realheapsort_bb2_in(V_j_0,B,C) 0.64/0.69 * Partial RF of phase [18]: 0.64/0.69 - RF of loop [18:1]: 0.64/0.69 V_j_0 0.64/0.69 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_bb1_in/4 0.64/0.70 * CE 5 is refined into CE [21] 0.64/0.70 * CE 4 is refined into CE [22,23,24] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_bb1_in/4 0.64/0.70 * CEs [22,23] --> Loop 21 0.64/0.70 * CEs [24] --> Loop 22 0.64/0.70 * CEs [21] --> Loop 23 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_bb1_in(V_N,V_k_0,B,C) 0.64/0.70 * RF of phase [21,22]: [V_N-V_k_0] 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_bb1_in(V_N,V_k_0,B,C) 0.64/0.70 * Partial RF of phase [21,22]: 0.64/0.70 - RF of loop [21:1,22:1]: 0.64/0.70 V_N-V_k_0 0.64/0.70 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_bb7_in/5 0.64/0.70 * CE 17 is refined into CE [25] 0.64/0.70 * CE 15 is refined into CE [26] 0.64/0.70 * CE 12 is refined into CE [27] 0.64/0.70 * CE 13 is refined into CE [28] 0.64/0.70 * CE 14 is refined into CE [29] 0.64/0.70 * CE 16 is refined into CE [30] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_bb7_in/5 0.64/0.70 * CEs [26] --> Loop 24 0.64/0.70 * CEs [30] --> Loop 25 0.64/0.70 * CEs [27] --> Loop 26 0.64/0.70 * CEs [28] --> Loop 27 0.64/0.70 * CEs [29] --> Loop 28 0.64/0.70 * CEs [25] --> Loop 29 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_bb7_in(V_N,V_k_1,V_j_1,B,C) 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_bb7_in(V_N,V_k_1,V_j_1,B,C) 0.64/0.70 * Partial RF of phase [25,26,27,28]: 0.64/0.70 - RF of loop [26:1]: 0.64/0.70 V_N/2-V_k_1/2-V_j_1-3/2 depends on loops [25:1,28:1] 0.64/0.70 - RF of loop [27:1]: 0.64/0.70 V_N/4-V_k_1/4-V_j_1/2-3/4 depends on loops [25:1,28:1] 0.64/0.70 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_bb5_in/3 0.64/0.70 * CE 11 is refined into CE [31] 0.64/0.70 * CE 10 is refined into CE [32,33,34,35,36] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_bb5_in/3 0.64/0.70 * CEs [36] --> Loop 30 0.64/0.70 * CEs [34] --> Loop 31 0.64/0.70 * CEs [35] --> Loop 32 0.64/0.70 * CEs [33] --> Loop 33 0.64/0.70 * CEs [32] --> Loop 34 0.64/0.70 * CEs [31] --> Loop 35 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_bb5_in(V_N,V_k_1,B) 0.64/0.70 * RF of phase [30,31,32]: [V_N-V_k_1-2] 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_bb5_in(V_N,V_k_1,B) 0.64/0.70 * Partial RF of phase [30,31,32]: 0.64/0.70 - RF of loop [30:1,32:1]: 0.64/0.70 V_N-V_k_1-2 0.64/0.70 - RF of loop [31:1]: 0.64/0.70 V_N-V_k_1-4 0.64/0.70 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_bb1_in_loop_cont/4 0.64/0.70 * CE 6 is refined into CE [37,38,39,40,41] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_bb1_in_loop_cont/4 0.64/0.70 * CEs [41] --> Loop 36 0.64/0.70 * CEs [40] --> Loop 37 0.64/0.70 * CEs [39] --> Loop 38 0.64/0.70 * CEs [38] --> Loop 39 0.64/0.70 * CEs [37] --> Loop 40 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_bb1_in_loop_cont(A,B,C,D) 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_bb1_in_loop_cont(A,B,C,D) 0.64/0.70 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_bb0_in/2 0.64/0.70 * CE 3 is refined into CE [42,43,44] 0.64/0.70 * CE 2 is refined into CE [45] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_bb0_in/2 0.64/0.70 * CEs [44] --> Loop 41 0.64/0.70 * CEs [43] --> Loop 42 0.64/0.70 * CEs [45] --> Loop 43 0.64/0.70 * CEs [42] --> Loop 44 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_bb0_in(V_N,B) 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_bb0_in(V_N,B) 0.64/0.70 0.64/0.70 0.64/0.70 ### Specialization of cost equations eval_realheapsort_start/2 0.64/0.70 * CE 1 is refined into CE [46,47,48,49] 0.64/0.70 0.64/0.70 0.64/0.70 ### Cost equations --> "Loop" of eval_realheapsort_start/2 0.64/0.70 * CEs [49] --> Loop 45 0.64/0.70 * CEs [48] --> Loop 46 0.64/0.70 * CEs [47] --> Loop 47 0.64/0.70 * CEs [46] --> Loop 48 0.64/0.70 0.64/0.70 ### Ranking functions of CR eval_realheapsort_start(V_N,B) 0.64/0.70 0.64/0.70 #### Partial ranking functions of CR eval_realheapsort_start(V_N,B) 0.64/0.70 0.64/0.70 0.64/0.70 Computing Bounds 0.64/0.70 ===================================== 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb2_in(V_j_0,B,C): 0.64/0.70 * Chain [[18],20]: 1*it(18)+0 0.64/0.70 Such that:it(18) =< V_j_0 0.64/0.70 0.64/0.70 with precondition: [B=3,0>=C,V_j_0>=1,2*C+1>=0] 0.64/0.70 0.64/0.70 * Chain [[18],19]: 1*it(18)+0 0.64/0.70 Such that:it(18) =< V_j_0-C 0.64/0.70 0.64/0.70 with precondition: [B=3,C>=1,V_j_0>=2*C+1] 0.64/0.70 0.64/0.70 * Chain [19]: 0 0.64/0.70 with precondition: [B=3,V_j_0=C,V_j_0>=1] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb1_in(V_N,V_k_0,B,C): 0.64/0.70 * Chain [[21,22],23]: 2*it(21)+1*s(5)+1*s(6)+0 0.64/0.70 Such that:aux(1) =< V_N 0.64/0.70 aux(5) =< V_N-V_k_0 0.64/0.70 it(21) =< aux(5) 0.64/0.70 aux(2) =< aux(1) 0.64/0.70 s(5) =< it(21)*aux(1) 0.64/0.70 s(6) =< it(21)*aux(2) 0.64/0.70 0.64/0.70 with precondition: [B=5,C=0,V_N>=3,V_k_0>=1,V_N>=V_k_0+1] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb7_in(V_N,V_k_1,V_j_1,B,C): 0.64/0.70 * Chain [[25,26,27,28]]...: 4*it(25)+0 0.64/0.70 with precondition: [V_N>=2*V_j_1+V_k_1+3,V_j_1>=0,V_N>=3,B=2] 0.64/0.70 0.64/0.70 * Chain [[25,26,27,28],29]: 4*it(25)+0 0.64/0.70 with precondition: [B=2,V_N>=3,V_j_1>=0,V_N>=2*V_j_1+V_k_1+3,V_k_1+2*C+2>=V_N,2*V_N>=V_k_1+C+3,C+2*V_N>=4*V_j_1+2*V_k_1+9] 0.64/0.70 0.64/0.70 * Chain [[25,26,27,28],24,29]: 4*it(25)+1 0.64/0.70 with precondition: [B=2,V_N=V_k_1+C+2,V_N>=3,V_j_1>=0,3*V_N>=4*V_j_1+3*V_k_1+15,V_N>=2*V_j_1+V_k_1+3] 0.64/0.70 0.64/0.70 * Chain [29]: 0 0.64/0.70 with precondition: [B=2,V_j_1=C,V_N>=3,V_N>=V_k_1+2,4*V_N>=3*V_k_1+V_j_1+9,V_k_1+2*V_j_1+2>=V_N] 0.64/0.70 0.64/0.70 * Chain [24,29]: 1 0.64/0.70 with precondition: [B=2,V_N=2*V_j_1+V_k_1+3,V_N=V_k_1+C+2,V_N>=3,V_N>=V_k_1+3] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb5_in(V_N,V_k_1,B): 0.64/0.70 * Chain [[30,31,32],34,35]: 4*it(30)+12*s(13)+1 0.64/0.70 Such that:aux(24) =< V_N-V_k_1 0.64/0.70 it(30) =< aux(24) 0.64/0.70 0.64/0.70 with precondition: [B=4,V_N>=3,V_N>=V_k_1+3] 0.64/0.70 0.64/0.70 * Chain [[30,31,32],33,34,35]: 4*it(30)+12*s(13)+3 0.64/0.70 Such that:aux(25) =< V_N-V_k_1 0.64/0.70 it(30) =< aux(25) 0.64/0.70 0.64/0.70 with precondition: [B=4,V_N>=3,V_N>=V_k_1+4] 0.64/0.70 0.64/0.70 * Chain [35]: 0 0.64/0.70 with precondition: [B=4,V_N>=3,V_k_1+1>=V_N] 0.64/0.70 0.64/0.70 * Chain [34,35]: 1 0.64/0.70 with precondition: [B=4,V_N=V_k_1+2,V_N>=3] 0.64/0.70 0.64/0.70 * Chain [33,34,35]: 3 0.64/0.70 with precondition: [B=4,V_N=V_k_1+3,V_N>=3] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb1_in_loop_cont(A,B,C,D): 0.64/0.70 * Chain [40]: 1 0.64/0.70 with precondition: [A=5,B=C+2,B>=3] 0.64/0.70 0.64/0.70 * Chain [39]: 3 0.64/0.70 with precondition: [A=5,B=C+3,B>=3] 0.64/0.70 0.64/0.70 * Chain [38]: 0 0.64/0.70 with precondition: [A=5,B>=3,C+1>=B] 0.64/0.70 0.64/0.70 * Chain [37]: 4*s(17)+12*s(18)+1 0.64/0.70 Such that:s(16) =< B-C 0.64/0.70 s(17) =< s(16) 0.64/0.70 0.64/0.70 with precondition: [A=5,B>=3,B>=C+3] 0.64/0.70 0.64/0.70 * Chain [36]: 4*s(20)+12*s(21)+3 0.64/0.70 Such that:s(19) =< B-C 0.64/0.70 s(20) =< s(19) 0.64/0.70 0.64/0.70 with precondition: [A=5,B>=3,B>=C+4] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_bb0_in(V_N,B): 0.64/0.70 * Chain [44]: 2*s(24)+1*s(26)+1*s(27)+3 0.64/0.70 Such that:s(23) =< 2 0.64/0.70 s(22) =< 3 0.64/0.70 s(24) =< s(23) 0.64/0.70 s(25) =< s(22) 0.64/0.70 s(26) =< s(24)*s(22) 0.64/0.70 s(27) =< s(24)*s(25) 0.64/0.70 0.64/0.70 with precondition: [V_N=3] 0.64/0.70 0.64/0.70 * Chain [43]: 0 0.64/0.70 with precondition: [2>=V_N] 0.64/0.70 0.64/0.70 * Chain [42]: 6*s(30)+1*s(32)+1*s(33)+12*s(36)+1 0.64/0.70 Such that:aux(26) =< V_N 0.64/0.70 s(30) =< aux(26) 0.64/0.70 s(31) =< aux(26) 0.64/0.70 s(32) =< s(30)*aux(26) 0.64/0.70 s(33) =< s(30)*s(31) 0.64/0.70 0.64/0.70 with precondition: [V_N>=3] 0.64/0.70 0.64/0.70 * Chain [41]: 6*s(39)+1*s(41)+1*s(42)+12*s(45)+3 0.64/0.70 Such that:aux(27) =< V_N 0.64/0.70 s(39) =< aux(27) 0.64/0.70 s(40) =< aux(27) 0.64/0.70 s(41) =< s(39)*aux(27) 0.64/0.70 s(42) =< s(39)*s(40) 0.64/0.70 0.64/0.70 with precondition: [V_N>=4] 0.64/0.70 0.64/0.70 0.64/0.70 #### Cost of chains of eval_realheapsort_start(V_N,B): 0.64/0.70 * Chain [48]: 2*s(48)+1*s(50)+1*s(51)+3 0.64/0.70 Such that:s(46) =< 2 0.64/0.70 s(47) =< 3 0.64/0.70 s(48) =< s(46) 0.64/0.70 s(49) =< s(47) 0.64/0.70 s(50) =< s(48)*s(47) 0.64/0.70 s(51) =< s(48)*s(49) 0.64/0.70 0.64/0.70 with precondition: [V_N=3] 0.64/0.70 0.64/0.70 * Chain [47]: 0 0.64/0.70 with precondition: [2>=V_N] 0.64/0.70 0.64/0.70 * Chain [46]: 6*s(53)+1*s(55)+1*s(56)+12*s(57)+1 0.64/0.70 Such that:s(52) =< V_N 0.64/0.70 s(53) =< s(52) 0.64/0.70 s(54) =< s(52) 0.64/0.70 s(55) =< s(53)*s(52) 0.64/0.70 s(56) =< s(53)*s(54) 0.64/0.70 0.64/0.70 with precondition: [V_N>=3] 0.64/0.70 0.64/0.70 * Chain [45]: 6*s(59)+1*s(61)+1*s(62)+12*s(63)+3 0.64/0.70 Such that:s(58) =< V_N 0.64/0.70 s(59) =< s(58) 0.64/0.70 s(60) =< s(58) 0.64/0.70 s(61) =< s(59)*s(58) 0.64/0.70 s(62) =< s(59)*s(60) 0.64/0.70 0.64/0.70 with precondition: [V_N>=4] 0.64/0.70 0.64/0.70 0.64/0.70 Closed-form bounds of eval_realheapsort_start(V_N,B): 0.64/0.70 ------------------------------------- 0.64/0.70 * Chain [48] with precondition: [V_N=3] 0.64/0.70 - Upper bound: 19 0.64/0.70 - Complexity: constant 0.64/0.70 * Chain [47] with precondition: [2>=V_N] 0.64/0.70 - Upper bound: 0 0.64/0.70 - Complexity: constant 0.64/0.70 * Chain [46] with precondition: [V_N>=3] 0.64/0.70 - Upper bound: inf 0.64/0.70 - Complexity: infinity 0.64/0.70 * Chain [45] with precondition: [V_N>=4] 0.64/0.70 - Upper bound: inf 0.64/0.70 - Complexity: infinity 0.64/0.70 0.64/0.70 ### Maximum cost of eval_realheapsort_start(V_N,B): inf 0.64/0.70 Asymptotic class: infinity 0.64/0.70 * Total analysis performed in 575 ms. 0.64/0.70 0.72/0.80 EOF