0.79/0.78 WORST_CASE(?,O(n^1)) 0.79/0.78 0.79/0.78 Preprocessing Cost Relations 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 #### Computed strongly connected components 0.79/0.78 0. recursive : [evalfbb2in/5,evalfbb3in/5,evalfbb4in/5] 0.79/0.78 1. recursive : [evalfbb1in/9,evalfbb3in_loop_cont/10,evalfbb5in/9,evalfbb6in/9,evalfbb7in/9] 0.79/0.78 2. recursive : [evalfbb6in_loop_cont/14,evalfbb8in/13,evalfbb9in/13,evalfbbin/13] 0.79/0.78 3. non_recursive : [evalfstop/7] 0.79/0.78 4. non_recursive : [evalfreturnin/7] 0.79/0.78 5. non_recursive : [exit_location/1] 0.79/0.78 6. non_recursive : [evalfbb9in_loop_cont/8] 0.79/0.78 7. non_recursive : [evalfentryin/7] 0.79/0.78 8. non_recursive : [evalfstart/7] 0.79/0.78 0.79/0.78 #### Obtained direct recursion through partial evaluation 0.79/0.78 0. SCC is partially evaluated into evalfbb3in/5 0.79/0.78 1. SCC is partially evaluated into evalfbb6in/9 0.79/0.78 2. SCC is partially evaluated into evalfbb9in/13 0.79/0.78 3. SCC is completely evaluated into other SCCs 0.79/0.78 4. SCC is completely evaluated into other SCCs 0.79/0.78 5. SCC is completely evaluated into other SCCs 0.79/0.78 6. SCC is partially evaluated into evalfbb9in_loop_cont/8 0.79/0.78 7. SCC is partially evaluated into evalfentryin/7 0.79/0.78 8. SCC is partially evaluated into evalfstart/7 0.79/0.78 0.79/0.78 Control-Flow Refinement of Cost Relations 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfbb3in/5 0.79/0.78 * CE 15 is refined into CE [16] 0.79/0.78 * CE 14 is refined into CE [17] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfbb3in/5 0.79/0.78 * CEs [16] --> Loop 16 0.79/0.78 * CEs [17] --> Loop 17 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfbb3in(E,F,H,I,J) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfbb3in(E,F,H,I,J) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfbb6in/9 0.79/0.78 * CE 12 is refined into CE [18] 0.79/0.78 * CE 11 is refined into CE [19] 0.79/0.78 * CE 9 is refined into CE [20] 0.79/0.78 * CE 13 is refined into CE [21] 0.79/0.78 * CE 10 is refined into CE [22] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfbb6in/9 0.79/0.78 * CEs [22] --> Loop 18 0.79/0.78 * CEs [18] --> Loop 19 0.79/0.78 * CEs [19] --> Loop 20 0.79/0.78 * CEs [20] --> Loop 21 0.79/0.78 * CEs [21] --> Loop 22 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfbb6in(C,D,E,F,H,I,J,K,L) 0.79/0.78 * RF of phase [18]: [-C/2+D/2,D/2-1/2] 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfbb6in(C,D,E,F,H,I,J,K,L) 0.79/0.78 * Partial RF of phase [18]: 0.79/0.78 - RF of loop [18:1]: 0.79/0.78 -C/2+D/2 0.79/0.78 D/2-1/2 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfbb9in/13 0.79/0.78 * CE 5 is refined into CE [23] 0.79/0.78 * CE 3 is refined into CE [24,25,26] 0.79/0.78 * CE 6 is refined into CE [27] 0.79/0.78 * CE 4 is refined into CE [28,29,30,31] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfbb9in/13 0.79/0.78 * CEs [31] --> Loop 23 0.79/0.78 * CEs [30] --> Loop 24 0.79/0.78 * CEs [29] --> Loop 25 0.79/0.78 * CEs [28] --> Loop 26 0.79/0.78 * CEs [23] --> Loop 27 0.79/0.78 * CEs [24] --> Loop 28 0.79/0.78 * CEs [26] --> Loop 29 0.79/0.78 * CEs [25] --> Loop 30 0.79/0.78 * CEs [27] --> Loop 31 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfbb9in(A,B,C,D,E,F,H,I,J,K,L,M,N) 0.79/0.78 * RF of phase [23,24,25,26]: [B/2-1/2] 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfbb9in(A,B,C,D,E,F,H,I,J,K,L,M,N) 0.79/0.78 * Partial RF of phase [23,24,25,26]: 0.79/0.78 - RF of loop [23:1]: 0.79/0.78 A-2 depends on loops [25:1,26:1] 0.79/0.78 - RF of loop [23:1,24:1,25:1,26:1]: 0.79/0.78 B/2-1/2 0.79/0.78 - RF of loop [24:1]: 0.79/0.78 A depends on loops [25:1,26:1] 0.79/0.78 - RF of loop [25:1]: 0.79/0.78 -A+1 depends on loops [23:1,24:1] 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfbb9in_loop_cont/8 0.79/0.78 * CE 7 is refined into CE [32] 0.79/0.78 * CE 8 is refined into CE [33] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfbb9in_loop_cont/8 0.79/0.78 * CEs [32] --> Loop 32 0.79/0.78 * CEs [33] --> Loop 33 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfbb9in_loop_cont(A,B,C,D,E,F,G,H) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfbb9in_loop_cont(A,B,C,D,E,F,G,H) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfentryin/7 0.79/0.78 * CE 2 is refined into CE [34,35,36,37,38,39,40,41,42] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfentryin/7 0.79/0.78 * CEs [38,39,40] --> Loop 34 0.79/0.78 * CEs [36] --> Loop 35 0.79/0.78 * CEs [35,37,42] --> Loop 36 0.79/0.78 * CEs [41] --> Loop 37 0.79/0.78 * CEs [34] --> Loop 38 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfentryin(A,B,C,D,E,F,H) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfentryin(A,B,C,D,E,F,H) 0.79/0.78 0.79/0.78 0.79/0.78 ### Specialization of cost equations evalfstart/7 0.79/0.78 * CE 1 is refined into CE [43,44,45,46,47] 0.79/0.78 0.79/0.78 0.79/0.78 ### Cost equations --> "Loop" of evalfstart/7 0.79/0.78 * CEs [47] --> Loop 39 0.79/0.78 * CEs [46] --> Loop 40 0.79/0.78 * CEs [45] --> Loop 41 0.79/0.78 * CEs [44] --> Loop 42 0.79/0.78 * CEs [43] --> Loop 43 0.79/0.78 0.79/0.78 ### Ranking functions of CR evalfstart(A,B,C,D,E,F,H) 0.79/0.78 0.79/0.78 #### Partial ranking functions of CR evalfstart(A,B,C,D,E,F,H) 0.79/0.78 0.79/0.78 0.79/0.78 Computing Bounds 0.79/0.78 ===================================== 0.79/0.78 0.79/0.78 #### Cost of chains of evalfbb3in(E,F,H,I,J): 0.79/0.78 * Chain [17]: 0 0.79/0.78 with precondition: [H=2,E=I,F=J,F>=E] 0.79/0.78 0.79/0.78 * Chain [16]: 0 0.79/0.78 with precondition: [H=3,F>=E] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of evalfbb6in(C,D,E,F,H,I,J,K,L): 0.79/0.78 * Chain [[18],22]: 1*it(18)+0 0.79/0.78 Such that:it(18) =< -C/2+D/2 0.79/0.78 0.79/0.78 with precondition: [H=3,C>=1,D>=C+1] 0.79/0.78 0.79/0.78 * Chain [[18],21]: 1*it(18)+0 0.79/0.78 Such that:it(18) =< -C/2+D/2 0.79/0.78 0.79/0.78 with precondition: [H=3,C>=1,D>=C+3] 0.79/0.78 0.79/0.78 * Chain [[18],20]: 1*it(18)+0 0.79/0.78 Such that:it(18) =< D/2-J/2 0.79/0.78 0.79/0.78 with precondition: [H=4,C=I,C=K,J+1=L,C>=1,J>=C+1,D>=J+2] 0.79/0.78 0.79/0.78 * Chain [[18],19]: 1*it(18)+0 0.79/0.78 Such that:it(18) =< D/2-I/2 0.79/0.78 0.79/0.78 with precondition: [H=4,C=I,C=K,J+1=L,C>=1,J+1>=C,C>=J,D>=J+2] 0.79/0.78 0.79/0.78 * Chain [22]: 0 0.79/0.78 with precondition: [H=3,C>=1] 0.79/0.78 0.79/0.78 * Chain [21]: 0 0.79/0.78 with precondition: [H=3,C>=1,D>=C+1] 0.79/0.78 0.79/0.78 * Chain [20]: 0 0.79/0.78 with precondition: [H=4,K=E,L=F,C=I,D=J,C>=1,D>=C+1] 0.79/0.78 0.79/0.78 * Chain [19]: 0 0.79/0.78 with precondition: [H=4,K=E,L=F,C=I,D=J,C>=1,C>=D] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of evalfbb9in(A,B,C,D,E,F,H,I,J,K,L,M,N): 0.79/0.78 * Chain [[23,24,25,26],31]: 3*it(23)+1*it(24)+2*s(6)+0 0.79/0.78 Such that:aux(19) =< A/2+B/4 0.79/0.78 aux(23) =< B/2 0.79/0.78 s(6) =< aux(19) 0.79/0.78 it(23) =< aux(23) 0.79/0.78 it(24) =< aux(23) 0.79/0.78 0.79/0.78 with precondition: [H=3,B>=2] 0.79/0.78 0.79/0.78 * Chain [[23,24,25,26],30]: 3*it(23)+1*it(24)+3*s(6)+0 0.79/0.78 Such that:aux(24) =< A/2+B/4 0.79/0.78 aux(25) =< B/2 0.79/0.78 s(6) =< aux(24) 0.79/0.78 it(24) =< aux(24) 0.79/0.78 it(23) =< aux(25) 0.79/0.78 it(24) =< aux(25) 0.79/0.78 0.79/0.78 with precondition: [H=3,B>=4,B+2*A>=4] 0.79/0.78 0.79/0.78 * Chain [[23,24,25,26],29]: 3*it(23)+1*it(24)+3*s(6)+0 0.79/0.78 Such that:aux(26) =< A/2+B/4 0.79/0.78 aux(27) =< B/2 0.79/0.78 s(6) =< aux(26) 0.79/0.78 it(24) =< aux(26) 0.79/0.78 it(23) =< aux(27) 0.79/0.78 it(24) =< aux(27) 0.79/0.78 0.79/0.78 with precondition: [H=3,B>=4,B+2*A>=8] 0.79/0.78 0.79/0.78 * Chain [[23,24,25,26],28]: 3*it(23)+1*it(24)+2*s(6)+0 0.79/0.78 Such that:aux(19) =< A/2+B/4 0.79/0.78 aux(28) =< B/2 0.79/0.78 s(6) =< aux(19) 0.79/0.78 it(23) =< aux(28) 0.79/0.78 it(24) =< aux(28) 0.79/0.78 0.79/0.78 with precondition: [H=3,B>=4] 0.79/0.78 0.79/0.78 * Chain [[23,24,25,26],27]: 3*it(23)+1*it(24)+2*s(6)+0 0.79/0.78 Such that:aux(19) =< A/2+B/4 0.79/0.78 aux(20) =< A/2+B/4-I/4-L/4 0.79/0.78 aux(21) =< B/2 0.79/0.78 aux(22) =< B/2+I/2-L/2 0.79/0.78 s(6) =< aux(19) 0.79/0.78 it(24) =< aux(20) 0.79/0.78 s(6) =< aux(20) 0.79/0.78 it(23) =< aux(21) 0.79/0.78 it(24) =< aux(21) 0.79/0.78 it(23) =< aux(22) 0.79/0.78 it(24) =< aux(22) 0.79/0.78 0.79/0.78 with precondition: [H=5,J+1=K,I+J=L,1>=J,J>=0,B>=J+2,B+2*A>=2*I+J] 0.79/0.78 0.79/0.78 * Chain [31]: 0 0.79/0.78 with precondition: [H=3] 0.79/0.78 0.79/0.78 * Chain [30]: 1*s(8)+0 0.79/0.78 Such that:s(8) =< A/2 0.79/0.78 0.79/0.78 with precondition: [H=3,A>=1,B>=2] 0.79/0.78 0.79/0.78 * Chain [29]: 1*s(9)+0 0.79/0.78 Such that:s(9) =< A/2 0.79/0.78 0.79/0.78 with precondition: [H=3,A>=3,B>=2] 0.79/0.78 0.79/0.78 * Chain [28]: 0 0.79/0.78 with precondition: [H=3,B>=2] 0.79/0.78 0.79/0.78 * Chain [27]: 0 0.79/0.78 with precondition: [H=5,I=A,K=C,L=D,M=E,N=F,B=J,1>=B] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of evalfbb9in_loop_cont(A,B,C,D,E,F,G,H): 0.79/0.78 * Chain [33]: 0 0.79/0.78 with precondition: [A=3] 0.79/0.78 0.79/0.78 * Chain [32]: 0 0.79/0.78 with precondition: [A=5] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of evalfentryin(A,B,C,D,E,F,H): 0.79/0.78 * Chain [38]: 0 0.79/0.78 with precondition: [] 0.79/0.78 0.79/0.78 * Chain [37]: 0 0.79/0.78 with precondition: [1>=B] 0.79/0.78 0.79/0.78 * Chain [36]: 9*s(15)+4*s(18)+0 0.79/0.78 Such that:aux(30) =< B/2 0.79/0.78 aux(31) =< 3/4*B 0.79/0.78 s(15) =< aux(30) 0.79/0.78 s(18) =< aux(31) 0.79/0.78 0.79/0.78 with precondition: [B>=2] 0.79/0.78 0.79/0.78 * Chain [35]: 1*s(27)+0 0.79/0.78 Such that:s(27) =< B/2 0.79/0.78 0.79/0.78 with precondition: [B>=3] 0.79/0.78 0.79/0.78 * Chain [34]: 8*s(30)+10*s(31)+2*s(36)+0 0.79/0.78 Such that:aux(32) =< B/2 0.79/0.78 aux(33) =< 3/4*B 0.79/0.78 s(30) =< aux(33) 0.79/0.78 s(31) =< aux(32) 0.79/0.78 s(36) =< aux(33) 0.79/0.78 s(36) =< aux(32) 0.79/0.78 0.79/0.78 with precondition: [B>=4] 0.79/0.78 0.79/0.78 0.79/0.78 #### Cost of chains of evalfstart(A,B,C,D,E,F,H): 0.79/0.78 * Chain [43]: 0 0.79/0.78 with precondition: [] 0.79/0.78 0.79/0.78 * Chain [42]: 0 0.79/0.78 with precondition: [1>=B] 0.79/0.78 0.79/0.78 * Chain [41]: 9*s(45)+4*s(46)+0 0.79/0.78 Such that:s(43) =< B/2 0.79/0.78 s(44) =< 3/4*B 0.79/0.78 s(45) =< s(43) 0.79/0.78 s(46) =< s(44) 0.79/0.78 0.79/0.78 with precondition: [B>=2] 0.79/0.78 0.79/0.78 * Chain [40]: 1*s(47)+0 0.79/0.78 Such that:s(47) =< B/2 0.79/0.78 0.79/0.78 with precondition: [B>=3] 0.79/0.78 0.79/0.78 * Chain [39]: 8*s(50)+10*s(51)+2*s(52)+0 0.79/0.78 Such that:s(48) =< B/2 0.79/0.78 s(49) =< 3/4*B 0.79/0.78 s(50) =< s(49) 0.79/0.78 s(51) =< s(48) 0.79/0.78 s(52) =< s(49) 0.79/0.78 s(52) =< s(48) 0.79/0.78 0.79/0.78 with precondition: [B>=4] 0.79/0.78 0.79/0.78 0.79/0.79 Closed-form bounds of evalfstart(A,B,C,D,E,F,H): 0.79/0.79 ------------------------------------- 0.79/0.79 * Chain [43] with precondition: [] 0.79/0.79 - Upper bound: 0 0.79/0.79 - Complexity: constant 0.79/0.79 * Chain [42] with precondition: [1>=B] 0.79/0.79 - Upper bound: 0 0.79/0.79 - Complexity: constant 0.79/0.79 * Chain [41] with precondition: [B>=2] 0.79/0.79 - Upper bound: 15/2*B 0.79/0.79 - Complexity: n 0.79/0.79 * Chain [40] with precondition: [B>=3] 0.79/0.79 - Upper bound: B/2 0.79/0.79 - Complexity: n 0.79/0.79 * Chain [39] with precondition: [B>=4] 0.79/0.79 - Upper bound: 25/2*B 0.79/0.79 - Complexity: n 0.79/0.79 0.79/0.79 ### Maximum cost of evalfstart(A,B,C,D,E,F,H): nat(B/2)*8+nat(3/4*B)*4+(nat(3/4*B)*6+nat(B/2))+nat(B/2) 0.79/0.79 Asymptotic class: n 0.79/0.79 * Total analysis performed in 663 ms. 0.79/0.79 0.80/0.89 EOF