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