0.61/0.63 WORST_CASE(?,O(1)) 0.61/0.63 0.61/0.63 Preprocessing Cost Relations 0.61/0.63 ===================================== 0.61/0.63 0.61/0.63 #### Computed strongly connected components 0.61/0.63 0. recursive : [f15/6] 0.61/0.63 1. recursive : [f12/6,f15_loop_cont/7] 0.61/0.63 2. non_recursive : [exit_location/1] 0.61/0.63 3. recursive : [f30/6] 0.61/0.63 4. recursive : [f26/8,f30_loop_cont/9] 0.61/0.63 5. recursive : [f23/10,f26_loop_cont/11] 0.61/0.63 6. non_recursive : [f52/8] 0.61/0.63 7. non_recursive : [f23_loop_cont/9] 0.61/0.63 8. non_recursive : [f12_loop_cont/9] 0.61/0.63 9. non_recursive : [f0/8] 0.61/0.63 0.61/0.63 #### Obtained direct recursion through partial evaluation 0.61/0.63 0. SCC is partially evaluated into f15/6 0.61/0.63 1. SCC is partially evaluated into f12/6 0.61/0.63 2. SCC is completely evaluated into other SCCs 0.61/0.63 3. SCC is partially evaluated into f30/6 0.61/0.63 4. SCC is partially evaluated into f26/8 0.61/0.63 5. SCC is partially evaluated into f23/10 0.61/0.63 6. SCC is completely evaluated into other SCCs 0.61/0.63 7. SCC is partially evaluated into f23_loop_cont/9 0.61/0.63 8. SCC is partially evaluated into f12_loop_cont/9 0.61/0.63 9. SCC is partially evaluated into f0/8 0.61/0.63 0.61/0.63 Control-Flow Refinement of Cost Relations 0.61/0.63 ===================================== 0.61/0.63 0.61/0.63 ### Specialization of cost equations f15/6 0.61/0.63 * CE 9 is refined into CE [25] 0.61/0.63 * CE 10 is refined into CE [26] 0.61/0.63 * CE 8 is refined into CE [27] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f15/6 0.61/0.63 * CEs [27] --> Loop 25 0.61/0.63 * CEs [25] --> Loop 26 0.61/0.63 * CEs [26] --> Loop 27 0.61/0.63 0.61/0.63 ### Ranking functions of CR f15(A,D,E,J,K,L) 0.61/0.63 * RF of phase [25]: [-E+2] 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f15(A,D,E,J,K,L) 0.61/0.63 * Partial RF of phase [25]: 0.61/0.63 - RF of loop [25:1]: 0.61/0.63 -E+2 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f12/6 0.61/0.63 * CE 4 is refined into CE [28] 0.61/0.63 * CE 2 is refined into CE [29,30] 0.61/0.63 * CE 5 is refined into CE [31] 0.61/0.63 * CE 3 is refined into CE [32] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f12/6 0.61/0.63 * CEs [32] --> Loop 28 0.61/0.63 * CEs [28] --> Loop 29 0.61/0.63 * CEs [29,30] --> Loop 30 0.61/0.63 * CEs [31] --> Loop 31 0.61/0.63 0.61/0.63 ### Ranking functions of CR f12(A,D,E,J,K,L) 0.61/0.63 * RF of phase [28]: [-D+2] 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f12(A,D,E,J,K,L) 0.61/0.63 * Partial RF of phase [28]: 0.61/0.63 - RF of loop [28:1]: 0.61/0.63 -D+2 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f30/6 0.61/0.63 * CE 24 is refined into CE [33] 0.61/0.63 * CE 23 is refined into CE [34] 0.61/0.63 * CE 22 is refined into CE [35] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f30/6 0.61/0.63 * CEs [35] --> Loop 32 0.61/0.63 * CEs [33] --> Loop 33 0.61/0.63 * CEs [34] --> Loop 34 0.61/0.63 0.61/0.63 ### Ranking functions of CR f30(A,E,F,J,K,L) 0.61/0.63 * RF of phase [32]: [-F+2] 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f30(A,E,F,J,K,L) 0.61/0.63 * Partial RF of phase [32]: 0.61/0.63 - RF of loop [32:1]: 0.61/0.63 -F+2 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f26/8 0.61/0.63 * CE 20 is refined into CE [36] 0.61/0.63 * CE 18 is refined into CE [37,38] 0.61/0.63 * CE 21 is refined into CE [39] 0.61/0.63 * CE 19 is refined into CE [40] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f26/8 0.61/0.63 * CEs [40] --> Loop 35 0.61/0.63 * CEs [36] --> Loop 36 0.61/0.63 * CEs [37,38] --> Loop 37 0.61/0.63 * CEs [39] --> Loop 38 0.61/0.63 0.61/0.63 ### Ranking functions of CR f26(A,D,E,F,J,K,L,M) 0.61/0.63 * RF of phase [35]: [-E+2] 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f26(A,D,E,F,J,K,L,M) 0.61/0.63 * Partial RF of phase [35]: 0.61/0.63 - RF of loop [35:1]: 0.61/0.63 -E+2 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f23/10 0.61/0.63 * CE 14 is refined into CE [41] 0.61/0.63 * CE 13 is refined into CE [42] 0.61/0.63 * CE 11 is refined into CE [43,44,45] 0.61/0.63 * CE 15 is refined into CE [46] 0.61/0.63 * CE 12 is refined into CE [47] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f23/10 0.61/0.63 * CEs [47] --> Loop 39 0.61/0.63 * CEs [41] --> Loop 40 0.61/0.63 * CEs [42] --> Loop 41 0.61/0.63 * CEs [43,44,45] --> Loop 42 0.61/0.63 * CEs [46] --> Loop 43 0.61/0.63 0.61/0.63 ### Ranking functions of CR f23(A,D,E,F,G,J,K,L,M,N) 0.61/0.63 * RF of phase [39]: [-D+2] 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f23(A,D,E,F,G,J,K,L,M,N) 0.61/0.63 * Partial RF of phase [39]: 0.61/0.63 - RF of loop [39:1]: 0.61/0.63 -D+2 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f23_loop_cont/9 0.61/0.63 * CE 16 is refined into CE [48] 0.61/0.63 * CE 17 is refined into CE [49] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f23_loop_cont/9 0.61/0.63 * CEs [48] --> Loop 44 0.61/0.63 * CEs [49] --> Loop 45 0.61/0.63 0.61/0.63 ### Ranking functions of CR f23_loop_cont(A,B,C,D,E,F,G,H,I) 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f23_loop_cont(A,B,C,D,E,F,G,H,I) 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f12_loop_cont/9 0.61/0.63 * CE 7 is refined into CE [50,51,52,53,54,55,56] 0.61/0.63 * CE 6 is refined into CE [57] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f12_loop_cont/9 0.61/0.63 * CEs [55,56] --> Loop 46 0.61/0.63 * CEs [52] --> Loop 47 0.61/0.63 * CEs [51,53,54] --> Loop 48 0.61/0.63 * CEs [50] --> Loop 49 0.61/0.63 * CEs [57] --> Loop 50 0.61/0.63 0.61/0.63 ### Ranking functions of CR f12_loop_cont(A,B,C,D,E,F,G,H,I) 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f12_loop_cont(A,B,C,D,E,F,G,H,I) 0.61/0.63 0.61/0.63 0.61/0.63 ### Specialization of cost equations f0/8 0.61/0.63 * CE 1 is refined into CE [58,59,60,61,62,63] 0.61/0.63 0.61/0.63 0.61/0.63 ### Cost equations --> "Loop" of f0/8 0.61/0.63 * CEs [58,59,60,61,62,63] --> Loop 51 0.61/0.63 0.61/0.63 ### Ranking functions of CR f0(A,B,C,D,E,F,G,J) 0.61/0.63 0.61/0.63 #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,J) 0.61/0.63 0.61/0.63 0.61/0.63 Computing Bounds 0.61/0.63 ===================================== 0.61/0.63 0.61/0.63 #### Cost of chains of f15(A,D,E,J,K,L): 0.61/0.63 * Chain [[25],27]: 1*it(25)+0 0.61/0.63 Such that:it(25) =< -E+2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,1>=D,1>=E,E>=0] 0.61/0.63 0.61/0.63 * Chain [[25],26]: 1*it(25)+0 0.61/0.63 Such that:it(25) =< -E+2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=5,L=2,D+1=K,1>=D,1>=E,E>=0] 0.61/0.63 0.61/0.63 * Chain [27]: 0 0.61/0.63 with precondition: [A=2,J=3,1>=D,E>=0] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f12(A,D,E,J,K,L): 0.61/0.63 * Chain [[28],31]: 1*it(28)+1*s(3)+0 0.61/0.63 Such that:aux(4) =< -D+2 0.61/0.63 it(28) =< aux(4) 0.61/0.63 s(3) =< aux(4)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,1>=D,D>=0] 0.61/0.63 0.61/0.63 * Chain [[28],30]: 1*it(28)+1*s(3)+2 0.61/0.63 Such that:aux(3) =< 1 0.61/0.63 aux(2) =< 2 0.61/0.63 aux(1) =< aux(2) 0.61/0.63 it(28) =< aux(2) 0.61/0.63 aux(1) =< aux(3) 0.61/0.63 it(28) =< aux(3) 0.61/0.63 s(3) =< aux(1)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,D=0,J=3] 0.61/0.63 0.61/0.63 * Chain [[28],29]: 1*it(28)+1*s(3)+0 0.61/0.63 Such that:aux(5) =< -D+2 0.61/0.63 it(28) =< aux(5) 0.61/0.63 s(3) =< aux(5)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=4,K=0,L=2,1>=D,D>=0] 0.61/0.63 0.61/0.63 * Chain [31]: 0 0.61/0.63 with precondition: [A=2,J=3,D>=0] 0.61/0.63 0.61/0.63 * Chain [30]: 2 0.61/0.63 with precondition: [A=2,J=3,1>=D,D>=0] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f30(A,E,F,J,K,L): 0.61/0.63 * Chain [[32],34]: 1*it(32)+0 0.61/0.63 Such that:it(32) =< -F+2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=2,L=2,E+1=K,1>=E,1>=F,F>=0] 0.61/0.63 0.61/0.63 * Chain [[32],33]: 1*it(32)+0 0.61/0.63 Such that:it(32) =< -F+2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,1>=E,1>=F,F>=0] 0.61/0.63 0.61/0.63 * Chain [33]: 0 0.61/0.63 with precondition: [A=2,J=3,1>=E,F>=0] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f26(A,D,E,F,J,K,L,M): 0.61/0.63 * Chain [[35],38]: 1*it(35)+1*s(10)+0 0.61/0.63 Such that:aux(9) =< -E+2 0.61/0.63 it(35) =< aux(9) 0.61/0.63 s(10) =< aux(9)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,1>=D,1>=E,E>=0] 0.61/0.63 0.61/0.63 * Chain [[35],37]: 1*it(35)+1*s(10)+2 0.61/0.63 Such that:aux(8) =< 1 0.61/0.63 aux(7) =< 2 0.61/0.63 aux(6) =< aux(7) 0.61/0.63 it(35) =< aux(7) 0.61/0.63 aux(6) =< aux(8) 0.61/0.63 it(35) =< aux(8) 0.61/0.63 s(10) =< aux(6)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,E=0,J=3,1>=D] 0.61/0.63 0.61/0.63 * Chain [[35],36]: 1*it(35)+1*s(10)+0 0.61/0.63 Such that:aux(10) =< -E+2 0.61/0.63 it(35) =< aux(10) 0.61/0.63 s(10) =< aux(10)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=4,L=2,M=2,D+1=K,1>=D,1>=E,E>=0] 0.61/0.63 0.61/0.63 * Chain [38]: 0 0.61/0.63 with precondition: [A=2,J=3,1>=D,E>=0] 0.61/0.63 0.61/0.63 * Chain [37]: 2 0.61/0.63 with precondition: [A=2,J=3,1>=D,1>=E,E>=0] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f23(A,D,E,F,G,J,K,L,M,N): 0.61/0.63 * Chain [[39],43]: 1*it(39)+1*s(21)+1*s(22)+0 0.61/0.63 Such that:aux(14) =< -D+2 0.61/0.63 it(39) =< aux(14) 0.61/0.63 s(23) =< aux(14)*2 0.61/0.63 s(21) =< s(23) 0.61/0.63 s(22) =< s(23)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,1>=D] 0.61/0.63 0.61/0.63 * Chain [[39],42]: 1*it(39)+1*s(21)+1*s(22)+14 0.61/0.63 Such that:aux(13) =< -D+1 0.61/0.63 aux(12) =< -D+2 0.61/0.63 aux(11) =< aux(12) 0.61/0.63 it(39) =< aux(12) 0.61/0.63 aux(11) =< aux(13) 0.61/0.63 it(39) =< aux(13) 0.61/0.63 s(23) =< aux(11)*2 0.61/0.63 s(21) =< s(23) 0.61/0.63 s(22) =< s(23)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=3,0>=D] 0.61/0.63 0.61/0.63 * Chain [[39],41]: 1*it(39)+1*s(21)+1*s(22)+0 0.61/0.63 Such that:aux(16) =< -D+2 0.61/0.63 it(39) =< aux(16) 0.61/0.63 s(23) =< aux(16)*2 0.61/0.63 s(21) =< s(23) 0.61/0.63 s(22) =< s(23)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=6,K=2,L=2,M=2,N=0,1>=D] 0.61/0.63 0.61/0.63 * Chain [[39],40]: 1*it(39)+1*s(21)+1*s(22)+0 0.61/0.63 Such that:aux(17) =< -D+2 0.61/0.63 it(39) =< aux(17) 0.61/0.63 s(23) =< aux(17)*2 0.61/0.63 s(21) =< s(23) 0.61/0.63 s(22) =< s(23)*2 0.61/0.63 0.61/0.63 with precondition: [A=2,J=6,K=2,L=2,M=2,N=1,1>=D] 0.61/0.63 0.61/0.63 * Chain [43]: 0 0.61/0.63 with precondition: [A=2,J=3] 0.61/0.63 0.61/0.63 * Chain [42]: 14 0.61/0.63 with precondition: [A=2,J=3,1>=D] 0.61/0.63 0.61/0.63 * Chain [41]: 0 0.61/0.63 with precondition: [A=2,J=6,N=0,L=E,M=F,D=K,D>=2] 0.61/0.63 0.61/0.63 * Chain [40]: 0 0.61/0.63 with precondition: [A=2,J=6,N=1,L=E,M=F,D=K,D>=2] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f23_loop_cont(A,B,C,D,E,F,G,H,I): 0.61/0.63 * Chain [45]: 0 0.61/0.63 with precondition: [A=3,B=2] 0.61/0.63 0.61/0.63 * Chain [44]: 0 0.61/0.63 with precondition: [A=6,B=2] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f12_loop_cont(A,B,C,D,E,F,G,H,I): 0.61/0.63 * Chain [50]: 0 0.61/0.63 with precondition: [A=3,B=2] 0.61/0.63 0.61/0.63 * Chain [49]: 0 0.61/0.63 with precondition: [A=4,B=2] 0.61/0.63 0.61/0.63 * Chain [48]: 3*s(38)+3*s(40)+3*s(41)+14 0.61/0.63 Such that:aux(18) =< -E+2 0.61/0.63 s(38) =< aux(18) 0.61/0.63 s(39) =< aux(18)*2 0.61/0.63 s(40) =< s(39) 0.61/0.63 s(41) =< s(39)*2 0.61/0.63 0.61/0.63 with precondition: [A=4,B=2,1>=E] 0.61/0.63 0.61/0.63 * Chain [47]: 1*s(55)+1*s(57)+1*s(58)+14 0.61/0.63 Such that:s(52) =< -E+1 0.61/0.63 s(53) =< -E+2 0.61/0.63 s(54) =< s(53) 0.61/0.63 s(55) =< s(53) 0.61/0.63 s(54) =< s(52) 0.61/0.63 s(55) =< s(52) 0.61/0.63 s(56) =< s(54)*2 0.61/0.63 s(57) =< s(56) 0.61/0.63 s(58) =< s(56)*2 0.61/0.63 0.61/0.63 with precondition: [A=4,B=2,0>=E] 0.61/0.63 0.61/0.63 * Chain [46]: 0 0.61/0.63 with precondition: [A=4,B=2,E>=2] 0.61/0.63 0.61/0.63 0.61/0.63 #### Cost of chains of f0(A,B,C,D,E,F,G,J): 0.61/0.63 * Chain [51]: 100 0.61/0.63 with precondition: [] 0.61/0.63 0.61/0.63 0.61/0.63 Closed-form bounds of f0(A,B,C,D,E,F,G,J): 0.61/0.63 ------------------------------------- 0.61/0.63 * Chain [51] with precondition: [] 0.61/0.63 - Upper bound: 100 0.61/0.63 - Complexity: constant 0.61/0.63 0.61/0.63 ### Maximum cost of f0(A,B,C,D,E,F,G,J): 100 0.61/0.63 Asymptotic class: constant 0.61/0.63 * Total analysis performed in 536 ms. 0.61/0.63 0.62/0.73 EOF