0.73/0.74 WORST_CASE(?,O(1)) 0.73/0.74 0.73/0.74 Preprocessing Cost Relations 0.73/0.74 ===================================== 0.73/0.74 0.73/0.74 #### Computed strongly connected components 0.73/0.74 0. recursive : [f28/5] 0.73/0.74 1. non_recursive : [exit_location/1] 0.73/0.74 2. recursive : [f39/10] 0.73/0.74 3. recursive : [f36/11,f39_loop_cont/12] 0.73/0.74 4. recursive : [f50/8] 0.73/0.74 5. non_recursive : [f56/8] 0.73/0.74 6. recursive : [f60/4] 0.73/0.74 7. non_recursive : [f60_loop_cont/9] 0.73/0.74 8. non_recursive : [f50_loop_cont/9] 0.73/0.74 9. non_recursive : [f36_loop_cont/9] 0.73/0.74 10. non_recursive : [f28_loop_cont/9] 0.73/0.74 11. non_recursive : [f0/8] 0.73/0.74 0.73/0.74 #### Obtained direct recursion through partial evaluation 0.73/0.74 0. SCC is partially evaluated into f28/5 0.73/0.74 1. SCC is completely evaluated into other SCCs 0.73/0.74 2. SCC is partially evaluated into f39/10 0.73/0.74 3. SCC is partially evaluated into f36/11 0.73/0.74 4. SCC is partially evaluated into f50/8 0.73/0.74 5. SCC is completely evaluated into other SCCs 0.73/0.74 6. SCC is partially evaluated into f60/4 0.73/0.74 7. SCC is partially evaluated into f60_loop_cont/9 0.73/0.74 8. SCC is partially evaluated into f50_loop_cont/9 0.73/0.74 9. SCC is partially evaluated into f36_loop_cont/9 0.73/0.74 10. SCC is partially evaluated into f28_loop_cont/9 0.73/0.74 11. SCC is partially evaluated into f0/8 0.73/0.74 0.73/0.74 Control-Flow Refinement of Cost Relations 0.73/0.74 ===================================== 0.73/0.74 0.73/0.74 ### Specialization of cost equations f28/5 0.73/0.74 * CE 6 is refined into CE [30] 0.73/0.74 * CE 5 is refined into CE [31] 0.73/0.74 * CE 3 is discarded (unfeasible) 0.73/0.74 * CE 4 is refined into CE [32] 0.73/0.74 * CE 2 is refined into CE [33] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f28/5 0.73/0.74 * CEs [32] --> Loop 30 0.73/0.74 * CEs [33] --> Loop 31 0.73/0.74 * CEs [30] --> Loop 32 0.73/0.74 * CEs [31] --> Loop 33 0.73/0.74 0.73/0.74 ### Ranking functions of CR f28(A,C,D,J,K) 0.73/0.74 * RF of phase [30]: [-D+5] 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f28(A,C,D,J,K) 0.73/0.74 * Partial RF of phase [30]: 0.73/0.74 - RF of loop [30:1]: 0.73/0.74 -D+5 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f39/10 0.73/0.74 * CE 17 is refined into CE [34] 0.73/0.74 * CE 16 is refined into CE [35] 0.73/0.74 * CE 15 is refined into CE [36] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f39/10 0.73/0.74 * CEs [36] --> Loop 34 0.73/0.74 * CEs [34] --> Loop 35 0.73/0.74 * CEs [35] --> Loop 36 0.73/0.74 0.73/0.74 ### Ranking functions of CR f39(B,D,E,F,G,J,K,L,M,N) 0.73/0.74 * RF of phase [34]: [-E+6] 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f39(B,D,E,F,G,J,K,L,M,N) 0.73/0.74 * Partial RF of phase [34]: 0.73/0.74 - RF of loop [34:1]: 0.73/0.74 -E+6 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f36/11 0.73/0.74 * CE 11 is refined into CE [37] 0.73/0.74 * CE 9 is refined into CE [38,39] 0.73/0.74 * CE 12 is refined into CE [40] 0.73/0.74 * CE 10 is refined into CE [41] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f36/11 0.73/0.74 * CEs [41] --> Loop 37 0.73/0.74 * CEs [37] --> Loop 38 0.73/0.74 * CEs [38,39] --> Loop 39 0.73/0.74 * CEs [40] --> Loop 40 0.73/0.74 0.73/0.74 ### Ranking functions of CR f36(A,B,D,E,F,G,J,K,L,M,N) 0.73/0.74 * RF of phase [37]: [-D+5] 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f36(A,B,D,E,F,G,J,K,L,M,N) 0.73/0.74 * Partial RF of phase [37]: 0.73/0.74 - RF of loop [37:1]: 0.73/0.74 -D+5 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f50/8 0.73/0.74 * CE 20 is refined into CE [42] 0.73/0.74 * CE 18 is refined into CE [43] 0.73/0.74 * CE 21 is refined into CE [44] 0.73/0.74 * CE 19 is refined into CE [45] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f50/8 0.73/0.74 * CEs [45] --> Loop 41 0.73/0.74 * CEs [42] --> Loop 42 0.73/0.74 * CEs [43] --> Loop 43 0.73/0.74 * CEs [44] --> Loop 44 0.73/0.74 0.73/0.74 ### Ranking functions of CR f50(B,D,F,G,J,K,L,M) 0.73/0.74 * RF of phase [41]: [-D+6] 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f50(B,D,F,G,J,K,L,M) 0.73/0.74 * Partial RF of phase [41]: 0.73/0.74 - RF of loop [41:1]: 0.73/0.74 -D+6 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f60/4 0.73/0.74 * CE 26 is refined into CE [46] 0.73/0.74 * CE 27 is refined into CE [47] 0.73/0.74 * CE 25 is refined into CE [48] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f60/4 0.73/0.74 * CEs [48] --> Loop 45 0.73/0.74 * CEs [46] --> Loop 46 0.73/0.74 * CEs [47] --> Loop 47 0.73/0.74 0.73/0.74 ### Ranking functions of CR f60(A,D,J,K) 0.73/0.74 * RF of phase [45]: [-D+5] 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f60(A,D,J,K) 0.73/0.74 * Partial RF of phase [45]: 0.73/0.74 - RF of loop [45:1]: 0.73/0.74 -D+5 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f60_loop_cont/9 0.73/0.74 * CE 28 is refined into CE [49] 0.73/0.74 * CE 29 is refined into CE [50] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f60_loop_cont/9 0.73/0.74 * CEs [49] --> Loop 48 0.73/0.74 * CEs [50] --> Loop 49 0.73/0.74 0.73/0.74 ### Ranking functions of CR f60_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f60_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f50_loop_cont/9 0.73/0.74 * CE 24 is refined into CE [51,52,53,54] 0.73/0.74 * CE 22 is refined into CE [55] 0.73/0.74 * CE 23 is refined into CE [56] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f50_loop_cont/9 0.73/0.74 * CEs [54] --> Loop 50 0.73/0.74 * CEs [52,53] --> Loop 51 0.73/0.74 * CEs [51] --> Loop 52 0.73/0.74 * CEs [55] --> Loop 53 0.73/0.74 * CEs [56] --> Loop 54 0.73/0.74 0.73/0.74 ### Ranking functions of CR f50_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f50_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f36_loop_cont/9 0.73/0.74 * CE 14 is refined into CE [57,58,59,60,61,62,63,64] 0.73/0.74 * CE 13 is refined into CE [65] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f36_loop_cont/9 0.73/0.74 * CEs [61,62] --> Loop 55 0.73/0.74 * CEs [60] --> Loop 56 0.73/0.74 * CEs [58,59,63,64] --> Loop 57 0.73/0.74 * CEs [57] --> Loop 58 0.73/0.74 * CEs [65] --> Loop 59 0.73/0.74 0.73/0.74 ### Ranking functions of CR f36_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f36_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f28_loop_cont/9 0.73/0.74 * CE 7 is refined into CE [66] 0.73/0.74 * CE 8 is refined into CE [67,68,69,70,71,72,73,74,75] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f28_loop_cont/9 0.73/0.74 * CEs [66] --> Loop 60 0.73/0.74 * CEs [73,74,75] --> Loop 61 0.73/0.74 * CEs [69] --> Loop 62 0.73/0.74 * CEs [68,70,71,72] --> Loop 63 0.73/0.74 * CEs [67] --> Loop 64 0.73/0.74 0.73/0.74 ### Ranking functions of CR f28_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f28_loop_cont(A,B,C,D,E,F,G,H,I) 0.73/0.74 0.73/0.74 0.73/0.74 ### Specialization of cost equations f0/8 0.73/0.74 * CE 1 is refined into CE [76,77,78,79,80] 0.73/0.74 0.73/0.74 0.73/0.74 ### Cost equations --> "Loop" of f0/8 0.73/0.74 * CEs [76,77,78,79,80] --> Loop 65 0.73/0.74 0.73/0.74 ### Ranking functions of CR f0(A,B,C,D,E,F,G,J) 0.73/0.74 0.73/0.74 #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,J) 0.73/0.74 0.73/0.74 0.73/0.74 Computing Bounds 0.73/0.74 ===================================== 0.73/0.74 0.73/0.74 #### Cost of chains of f28(A,C,D,J,K): 0.73/0.74 * Chain [32]: 0 0.73/0.74 with precondition: [A=5,C=0,J=3,D>=0] 0.73/0.74 0.73/0.74 * Chain [31,[30],33]: 1*it(30)+1 0.73/0.74 Such that:it(30) =< 4 0.73/0.74 0.73/0.74 with precondition: [A=5,C=0,D=0,J=2,K=0] 0.73/0.74 0.73/0.74 * Chain [31,[30],32]: 1*it(30)+1 0.73/0.74 Such that:it(30) =< 4 0.73/0.74 0.73/0.74 with precondition: [A=5,C=0,D=0,J=3] 0.73/0.74 0.73/0.74 * Chain [31,32]: 1 0.73/0.74 with precondition: [A=5,C=0,D=0,J=3] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f39(B,D,E,F,G,J,K,L,M,N): 0.73/0.74 * Chain [[34],36]: 1*it(34)+0 0.73/0.74 Such that:it(34) =< -E+6 0.73/0.74 0.73/0.74 with precondition: [B=6,J=2,L=6,D+1=K,4>=D,5>=E,E>=0] 0.73/0.74 0.73/0.74 * Chain [[34],35]: 1*it(34)+0 0.73/0.74 Such that:it(34) =< -E+6 0.73/0.74 0.73/0.74 with precondition: [B=6,J=3,4>=D,5>=E,E>=0] 0.73/0.74 0.73/0.74 * Chain [35]: 0 0.73/0.74 with precondition: [B=6,J=3,4>=D,E>=0] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f36(A,B,D,E,F,G,J,K,L,M,N): 0.73/0.74 * Chain [[37],40]: 1*it(37)+1*s(4)+0 0.73/0.74 Such that:aux(4) =< -D+5 0.73/0.74 it(37) =< aux(4) 0.73/0.74 s(4) =< aux(4)*6 0.73/0.74 0.73/0.74 with precondition: [A=5,B=6,J=3,4>=D] 0.73/0.74 0.73/0.74 * Chain [[37],39]: 1*it(37)+1*s(4)+6 0.73/0.74 Such that:aux(3) =< -D+4 0.73/0.74 aux(2) =< -D+5 0.73/0.74 aux(1) =< aux(2) 0.73/0.74 it(37) =< aux(2) 0.73/0.74 aux(1) =< aux(3) 0.73/0.74 it(37) =< aux(3) 0.73/0.74 s(4) =< aux(1)*6 0.73/0.74 0.73/0.74 with precondition: [A=5,B=6,J=3,3>=D] 0.73/0.74 0.73/0.74 * Chain [[37],38]: 1*it(37)+1*s(4)+0 0.73/0.74 Such that:aux(5) =< -D+5 0.73/0.74 it(37) =< aux(5) 0.73/0.74 s(4) =< aux(5)*6 0.73/0.74 0.73/0.74 with precondition: [A=5,B=6,J=6,K=0,L=6,4>=D] 0.73/0.74 0.73/0.74 * Chain [40]: 0 0.73/0.74 with precondition: [A=5,B=6,J=3] 0.73/0.74 0.73/0.74 * Chain [39]: 6 0.73/0.74 with precondition: [A=5,B=6,J=3,4>=D] 0.73/0.74 0.73/0.74 * Chain [38]: 0 0.73/0.74 with precondition: [A=5,B=6,J=6,K=0,L=E,M=F,N=G,D>=5] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f50(B,D,F,G,J,K,L,M): 0.73/0.74 * Chain [[41],44]: 1*it(41)+0 0.73/0.74 Such that:it(41) =< -D+6 0.73/0.74 0.73/0.74 with precondition: [B=6,J=3,5>=D] 0.73/0.74 0.73/0.74 * Chain [[41],43]: 1*it(41)+0 0.73/0.74 Such that:it(41) =< -D+K 0.73/0.74 0.73/0.74 with precondition: [B=6,J=4,5>=K,K>=D+1] 0.73/0.74 0.73/0.74 * Chain [[41],42]: 1*it(41)+0 0.73/0.74 Such that:it(41) =< -D+6 0.73/0.74 0.73/0.74 with precondition: [B=6,J=5,K=0,5>=D] 0.73/0.74 0.73/0.74 * Chain [44]: 0 0.73/0.74 with precondition: [B=6,J=3] 0.73/0.74 0.73/0.74 * Chain [43]: 0 0.73/0.74 with precondition: [B=6,J=4,D=K,5>=D] 0.73/0.74 0.73/0.74 * Chain [42]: 0 0.73/0.74 with precondition: [B=6,J=5,K=0,L=F,M=G,D>=6] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f60(A,D,J,K): 0.73/0.74 * Chain [[45],47]: 1*it(45)+0 0.73/0.74 Such that:it(45) =< -D+5 0.73/0.74 0.73/0.74 with precondition: [A=5,J=3,4>=D] 0.73/0.74 0.73/0.74 * Chain [[45],46]: 1*it(45)+0 0.73/0.74 Such that:it(45) =< -D+5 0.73/0.74 0.73/0.74 with precondition: [A=5,J=4,K=5,4>=D] 0.73/0.74 0.73/0.74 * Chain [47]: 0 0.73/0.74 with precondition: [A=5,J=3] 0.73/0.74 0.73/0.74 * Chain [46]: 0 0.73/0.74 with precondition: [A=5,J=4,D=K,D>=5] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f60_loop_cont(A,B,C,D,E,F,G,H,I): 0.73/0.74 * Chain [49]: 0 0.73/0.74 with precondition: [A=3,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [48]: 0 0.73/0.74 with precondition: [A=4,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f50_loop_cont(A,B,C,D,E,F,G,H,I): 0.73/0.74 * Chain [54]: 0 0.73/0.74 with precondition: [A=3,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [53]: 0 0.73/0.74 with precondition: [A=4,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [52]: 0 0.73/0.74 with precondition: [A=5,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [51]: 2*s(9)+0 0.73/0.74 Such that:aux(6) =< -E+5 0.73/0.74 s(9) =< aux(6) 0.73/0.74 0.73/0.74 with precondition: [A=5,B=5,C=6,D=0,4>=E] 0.73/0.74 0.73/0.74 * Chain [50]: 0 0.73/0.74 with precondition: [A=5,B=5,C=6,D=0,E>=5] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f36_loop_cont(A,B,C,D,E,F,G,H,I): 0.73/0.74 * Chain [59]: 0 0.73/0.74 with precondition: [A=3,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [58]: 0 0.73/0.74 with precondition: [A=6,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [57]: 3*s(11)+2*s(15)+0 0.73/0.74 Such that:s(14) =< 5 0.73/0.74 aux(7) =< -E+6 0.73/0.74 s(11) =< aux(7) 0.73/0.74 s(15) =< s(14) 0.73/0.74 0.73/0.74 with precondition: [A=6,B=5,C=6,D=0,5>=E] 0.73/0.74 0.73/0.74 * Chain [56]: 1*s(16)+0 0.73/0.74 Such that:s(16) =< -E+5 0.73/0.74 0.73/0.74 with precondition: [A=6,B=5,C=6,D=0,4>=E] 0.73/0.74 0.73/0.74 * Chain [55]: 10 0.73/0.74 with precondition: [A=6,B=5,C=6,D=0,E>=6] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f28_loop_cont(A,B,C,D,E,F,G,H,I): 0.73/0.74 * Chain [64]: 0 0.73/0.74 with precondition: [A=2,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 * Chain [63]: 4*s(20)+4*s(21)+3*s(30)+3*s(31)+6 0.73/0.74 Such that:s(29) =< 6 0.73/0.74 aux(8) =< 5 0.73/0.74 aux(9) =< -E+5 0.73/0.74 s(31) =< aux(8) 0.73/0.74 s(30) =< s(29) 0.73/0.74 s(20) =< aux(9) 0.73/0.74 s(21) =< aux(9)*6 0.73/0.74 0.73/0.74 with precondition: [A=2,B=5,C=6,D=0,4>=E] 0.73/0.74 0.73/0.74 * Chain [62]: 1*s(39)+1*s(40)+6 0.73/0.74 Such that:s(36) =< -E+4 0.73/0.74 s(37) =< -E+5 0.73/0.74 s(38) =< s(37) 0.73/0.74 s(39) =< s(37) 0.73/0.74 s(38) =< s(36) 0.73/0.74 s(39) =< s(36) 0.73/0.74 s(40) =< s(38)*6 0.73/0.74 0.73/0.74 with precondition: [A=2,B=5,C=6,D=0,3>=E] 0.73/0.74 0.73/0.74 * Chain [61]: 33 0.73/0.74 with precondition: [A=2,B=5,C=6,D=0,E>=5] 0.73/0.74 0.73/0.74 * Chain [60]: 0 0.73/0.74 with precondition: [A=3,B=5,C=6,D=0] 0.73/0.74 0.73/0.74 0.73/0.74 #### Cost of chains of f0(A,B,C,D,E,F,G,J): 0.73/0.74 * Chain [65]: 227 0.73/0.74 with precondition: [] 0.73/0.74 0.73/0.74 0.73/0.74 Closed-form bounds of f0(A,B,C,D,E,F,G,J): 0.73/0.74 ------------------------------------- 0.73/0.74 * Chain [65] with precondition: [] 0.73/0.74 - Upper bound: 227 0.73/0.74 - Complexity: constant 0.73/0.74 0.73/0.74 ### Maximum cost of f0(A,B,C,D,E,F,G,J): 227 0.73/0.74 Asymptotic class: constant 0.73/0.74 * Total analysis performed in 640 ms. 0.73/0.74 0.74/0.84 EOF