0.86/0.89 WORST_CASE(?,O(1)) 0.86/0.89 0.86/0.89 Preprocessing Cost Relations 0.86/0.89 ===================================== 0.86/0.89 0.86/0.89 #### Computed strongly connected components 0.86/0.89 0. recursive : [f14/9] 0.86/0.89 1. recursive : [f11/21,f14_loop_cont/22] 0.86/0.89 2. non_recursive : [exit_location/1] 0.86/0.89 3. recursive : [f36/13] 0.86/0.89 4. recursive : [f33/25,f36_loop_cont/26] 0.86/0.89 5. non_recursive : [f58/18] 0.86/0.89 6. non_recursive : [f33_loop_cont/19] 0.86/0.89 7. non_recursive : [f11_loop_cont/19] 0.86/0.89 8. non_recursive : [f0/18] 0.86/0.89 0.86/0.89 #### Obtained direct recursion through partial evaluation 0.86/0.89 0. SCC is partially evaluated into f14/9 0.86/0.89 1. SCC is partially evaluated into f11/21 0.86/0.89 2. SCC is completely evaluated into other SCCs 0.86/0.89 3. SCC is partially evaluated into f36/13 0.86/0.89 4. SCC is partially evaluated into f33/25 0.86/0.89 5. SCC is completely evaluated into other SCCs 0.86/0.89 6. SCC is partially evaluated into f33_loop_cont/19 0.86/0.89 7. SCC is partially evaluated into f11_loop_cont/19 0.86/0.89 8. SCC is partially evaluated into f0/18 0.86/0.89 0.86/0.89 Control-Flow Refinement of Cost Relations 0.86/0.89 ===================================== 0.86/0.89 0.86/0.89 ### Specialization of cost equations f14/9 0.86/0.89 * CE 9 is refined into CE [21] 0.86/0.89 * CE 10 is refined into CE [22] 0.86/0.89 * CE 8 is refined into CE [23] 0.86/0.89 0.86/0.89 0.86/0.89 ### Cost equations --> "Loop" of f14/9 0.86/0.89 * CEs [23] --> Loop 21 0.86/0.89 * CEs [21] --> Loop 22 0.86/0.89 * CEs [22] --> Loop 23 0.86/0.89 0.86/0.89 ### Ranking functions of CR f14(A,B,O,P,T,U,V,W,X) 0.86/0.89 * RF of phase [21]: [-B+10] 0.86/0.89 0.86/0.89 #### Partial ranking functions of CR f14(A,B,O,P,T,U,V,W,X) 0.86/0.89 * Partial RF of phase [21]: 0.86/0.89 - RF of loop [21:1]: 0.86/0.89 -B+10 0.86/0.89 0.86/0.89 0.86/0.89 ### Specialization of cost equations f11/21 0.86/0.89 * CE 2 is refined into CE [24,25] 0.86/0.89 * CE 5 is refined into CE [26] 0.86/0.89 * CE 4 is refined into CE [27] 0.86/0.89 * CE 3 is refined into CE [28] 0.86/0.89 0.86/0.89 0.86/0.89 ### Cost equations --> "Loop" of f11/21 0.86/0.89 * CEs [28] --> Loop 24 0.86/0.89 * CEs [24,25] --> Loop 25 0.86/0.89 * CEs [26] --> Loop 26 0.86/0.89 * CEs [27] --> Loop 27 0.86/0.89 0.86/0.89 ### Ranking functions of CR f11(A,B,C,E,F,G,H,O,P,Q,T,U,V,W,X,Y,Z,A1,B1,C1,D1) 0.86/0.89 * RF of phase [24]: [-A+10] 0.86/0.89 0.86/0.89 #### Partial ranking functions of CR f11(A,B,C,E,F,G,H,O,P,Q,T,U,V,W,X,Y,Z,A1,B1,C1,D1) 0.86/0.89 * Partial RF of phase [24]: 0.86/0.89 - RF of loop [24:1]: 0.86/0.89 -A+10 0.86/0.89 0.86/0.90 0.86/0.90 ### Specialization of cost equations f36/13 0.86/0.90 * CE 20 is refined into CE [29] 0.86/0.90 * CE 19 is refined into CE [30] 0.86/0.90 * CE 17 is refined into CE [31] 0.86/0.90 * CE 18 is refined into CE [32] 0.86/0.90 0.86/0.90 0.86/0.90 ### Cost equations --> "Loop" of f36/13 0.86/0.90 * CEs [31] --> Loop 28 0.86/0.90 * CEs [32] --> Loop 29 0.86/0.90 * CEs [29] --> Loop 30 0.86/0.90 * CEs [30] --> Loop 31 0.86/0.90 0.86/0.90 ### Ranking functions of CR f36(C,D,E,F,G,H,T,U,V,W,X,Y,Z) 0.86/0.90 * RF of phase [28,29]: [-D+10] 0.86/0.90 0.86/0.90 #### Partial ranking functions of CR f36(C,D,E,F,G,H,T,U,V,W,X,Y,Z) 0.86/0.90 * Partial RF of phase [28,29]: 0.86/0.90 - RF of loop [28:1,29:1]: 0.86/0.90 -D+10 0.86/0.90 0.86/0.90 0.86/0.90 ### Specialization of cost equations f33/25 0.86/0.90 * CE 13 is refined into CE [33] 0.86/0.90 * CE 11 is refined into CE [34,35] 0.86/0.90 * CE 14 is refined into CE [36] 0.86/0.90 * CE 12 is refined into CE [37] 0.86/0.90 0.86/0.90 0.86/0.90 ### Cost equations --> "Loop" of f33/25 0.86/0.90 * CEs [37] --> Loop 32 0.86/0.90 * CEs [33] --> Loop 33 0.86/0.90 * CEs [34,35] --> Loop 34 0.86/0.90 * CEs [36] --> Loop 35 0.86/0.90 0.86/0.90 ### Ranking functions of CR f33(C,D,E,F,G,H,I,J,K,L,M,N,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1) 0.86/0.90 * RF of phase [32]: [-C+10] 0.86/0.90 0.86/0.90 #### Partial ranking functions of CR f33(C,D,E,F,G,H,I,J,K,L,M,N,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1) 0.86/0.90 * Partial RF of phase [32]: 0.86/0.90 - RF of loop [32:1]: 0.86/0.90 -C+10 0.86/0.90 0.86/0.90 0.86/0.90 ### Specialization of cost equations f33_loop_cont/19 0.86/0.90 * CE 15 is refined into CE [38] 0.86/0.90 * CE 16 is refined into CE [39] 0.86/0.90 0.86/0.90 0.86/0.90 ### Cost equations --> "Loop" of f33_loop_cont/19 0.86/0.90 * CEs [38] --> Loop 36 0.86/0.90 * CEs [39] --> Loop 37 0.86/0.90 0.86/0.90 ### Ranking functions of CR f33_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S) 0.86/0.90 0.86/0.90 #### Partial ranking functions of CR f33_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S) 0.86/0.90 0.86/0.90 0.86/0.90 ### Specialization of cost equations f11_loop_cont/19 0.86/0.90 * CE 6 is refined into CE [40] 0.86/0.90 * CE 7 is refined into CE [41,42,43,44,45] 0.86/0.90 0.86/0.90 0.86/0.90 ### Cost equations --> "Loop" of f11_loop_cont/19 0.86/0.90 * CEs [40] --> Loop 38 0.86/0.90 * CEs [45] --> Loop 39 0.86/0.90 * CEs [43] --> Loop 40 0.86/0.90 * CEs [42,44] --> Loop 41 0.86/0.90 * CEs [41] --> Loop 42 0.86/0.90 0.86/0.90 ### Ranking functions of CR f11_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S) 0.86/0.90 0.86/0.90 #### Partial ranking functions of CR f11_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S) 0.86/0.90 0.86/0.90 0.86/0.90 ### Specialization of cost equations f0/18 0.86/0.90 * CE 1 is refined into CE [46,47,48,49,50,51] 0.86/0.90 0.86/0.90 0.86/0.90 ### Cost equations --> "Loop" of f0/18 0.86/0.90 * CEs [46,47,48,49,50,51] --> Loop 43 0.86/0.90 0.86/0.90 ### Ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,T) 0.86/0.90 0.86/0.90 #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,T) 0.86/0.90 0.86/0.90 0.86/0.90 Computing Bounds 0.86/0.90 ===================================== 0.86/0.90 0.86/0.90 #### Cost of chains of f14(A,B,O,P,T,U,V,W,X): 0.86/0.90 * Chain [[21],23]: 1*it(21)+0 0.86/0.90 Such that:it(21) =< -B+10 0.86/0.90 0.86/0.90 with precondition: [T=3,9>=A,9>=B,B>=0] 0.86/0.90 0.86/0.90 * Chain [[21],22]: 1*it(21)+0 0.86/0.90 Such that:it(21) =< -B+10 0.86/0.90 0.86/0.90 with precondition: [T=4,V=10,A+1=U,W=X,9>=A,9>=B,B>=0] 0.86/0.90 0.86/0.90 * Chain [23]: 0 0.86/0.90 with precondition: [T=3,9>=A,B>=0] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f11(A,B,C,E,F,G,H,O,P,Q,T,U,V,W,X,Y,Z,A1,B1,C1,D1): 0.86/0.90 * Chain [[24],27]: 1*it(24)+1*s(3)+0 0.86/0.90 Such that:aux(4) =< -A+10 0.86/0.90 it(24) =< aux(4) 0.86/0.90 s(3) =< aux(4)*10 0.86/0.90 0.86/0.90 with precondition: [T=2,U=10,V=10,W=0,X=0,Y=0,Z=0,A1=0,D1=1000,B1=C1,9>=A] 0.86/0.90 0.86/0.90 * Chain [[24],26]: 1*it(24)+1*s(3)+0 0.86/0.90 Such that:aux(5) =< -A+10 0.86/0.90 it(24) =< aux(5) 0.86/0.90 s(3) =< aux(5)*10 0.86/0.90 0.86/0.90 with precondition: [T=3,9>=A,A>=0] 0.86/0.90 0.86/0.90 * Chain [[24],25]: 1*it(24)+1*s(3)+10 0.86/0.90 Such that:aux(3) =< -A+9 0.86/0.90 aux(2) =< -A+10 0.86/0.90 aux(1) =< aux(2) 0.86/0.90 it(24) =< aux(2) 0.86/0.90 aux(1) =< aux(3) 0.86/0.90 it(24) =< aux(3) 0.86/0.90 s(3) =< aux(1)*10 0.86/0.90 0.86/0.90 with precondition: [T=3,8>=A,A>=0] 0.86/0.90 0.86/0.90 * Chain [26]: 0 0.86/0.90 with precondition: [T=3,A>=0] 0.86/0.90 0.86/0.90 * Chain [25]: 10 0.86/0.90 with precondition: [T=3,9>=A,A>=0] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f36(C,D,E,F,G,H,T,U,V,W,X,Y,Z): 0.86/0.90 * Chain [[28,29],31]: 2*it(28)+0 0.86/0.90 Such that:aux(8) =< -F-H+X+Z 0.86/0.90 it(28) =< aux(8) 0.86/0.90 0.86/0.90 with precondition: [T=2,V=10,C+1=U,D+X+Z=F+H+10,9>=C,9>=D,D>=0,X>=F,F+10>=D+X] 0.86/0.90 0.86/0.90 * Chain [[28,29],30]: 2*it(28)+0 0.86/0.90 Such that:aux(9) =< -D+10 0.86/0.90 it(28) =< aux(9) 0.86/0.90 0.86/0.90 with precondition: [T=3,9>=C,9>=D,D>=0] 0.86/0.90 0.86/0.90 * Chain [30]: 0 0.86/0.90 with precondition: [T=3,9>=C,D>=0] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f33(C,D,E,F,G,H,I,J,K,L,M,N,T,U,V,W,X,Y,Z,A1,B1,C1,D1,E1,F1): 0.86/0.90 * Chain [[32],35]: 1*it(32)+2*s(12)+0 0.86/0.90 Such that:aux(13) =< -C+10 0.86/0.90 it(32) =< aux(13) 0.86/0.90 s(13) =< aux(13)*10 0.86/0.90 s(12) =< s(13) 0.86/0.90 0.86/0.90 with precondition: [T=3,9>=C] 0.86/0.90 0.86/0.90 * Chain [[32],34]: 1*it(32)+2*s(12)+20 0.86/0.90 Such that:aux(12) =< -C+9 0.86/0.90 aux(11) =< -C+10 0.86/0.90 aux(10) =< aux(11) 0.86/0.90 it(32) =< aux(11) 0.86/0.90 aux(10) =< aux(12) 0.86/0.90 it(32) =< aux(12) 0.86/0.90 s(13) =< aux(10)*10 0.86/0.90 s(12) =< s(13) 0.86/0.90 0.86/0.90 with precondition: [T=3,8>=C] 0.86/0.90 0.86/0.90 * Chain [[32],33]: 1*it(32)+2*s(12)+0 0.86/0.90 Such that:aux(14) =< -C+10 0.86/0.90 it(32) =< aux(14) 0.86/0.90 s(13) =< aux(14)*10 0.86/0.90 s(12) =< s(13) 0.86/0.90 0.86/0.90 with precondition: [T=5,U=10,V=10,E1=1500,W=A1,X=B1,Y=C1,X+Z+10*C=F+H+100,X+D1+10*C=F+H+100,9>=C,X>=F,F+100>=10*C+X] 0.86/0.90 0.86/0.90 * Chain [35]: 0 0.86/0.90 with precondition: [T=3] 0.86/0.90 0.86/0.90 * Chain [34]: 20 0.86/0.90 with precondition: [T=3,9>=C] 0.86/0.90 0.86/0.90 * Chain [33]: 0 0.86/0.90 with precondition: [T=5,E1=1500,V=D,C=U,E=W,F=X,G=Y,H=Z,E=A1,F=B1,G=C1,H=D1,C>=10] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f33_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S): 0.86/0.90 * Chain [37]: 0 0.86/0.90 with precondition: [A=3] 0.86/0.90 0.86/0.90 * Chain [36]: 0 0.86/0.90 with precondition: [A=5] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f11_loop_cont(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S): 0.86/0.90 * Chain [42]: 0 0.86/0.90 with precondition: [A=2] 0.86/0.90 0.86/0.90 * Chain [41]: 2*s(21)+4*s(23)+20 0.86/0.90 Such that:aux(15) =< -D+10 0.86/0.90 s(21) =< aux(15) 0.86/0.90 s(22) =< aux(15)*10 0.86/0.90 s(23) =< s(22) 0.86/0.90 0.86/0.90 with precondition: [A=2,9>=D] 0.86/0.90 0.86/0.90 * Chain [40]: 1*s(31)+2*s(33)+20 0.86/0.90 Such that:s(28) =< -D+9 0.86/0.90 s(29) =< -D+10 0.86/0.90 s(30) =< s(29) 0.86/0.90 s(31) =< s(29) 0.86/0.90 s(30) =< s(28) 0.86/0.90 s(31) =< s(28) 0.86/0.90 s(32) =< s(30)*10 0.86/0.90 s(33) =< s(32) 0.86/0.90 0.86/0.90 with precondition: [A=2,8>=D] 0.86/0.90 0.86/0.90 * Chain [39]: 0 0.86/0.90 with precondition: [A=2,D>=10] 0.86/0.90 0.86/0.90 * Chain [38]: 0 0.86/0.90 with precondition: [A=3] 0.86/0.90 0.86/0.90 0.86/0.90 #### Cost of chains of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,T): 0.86/0.90 * Chain [43]: 1200 0.86/0.90 with precondition: [] 0.86/0.90 0.86/0.90 0.86/0.90 Closed-form bounds of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,T): 0.86/0.90 ------------------------------------- 0.86/0.90 * Chain [43] with precondition: [] 0.86/0.90 - Upper bound: 1200 0.86/0.90 - Complexity: constant 0.86/0.90 0.86/0.90 ### Maximum cost of f0(A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,T): 1200 0.86/0.90 Asymptotic class: constant 0.86/0.90 * Total analysis performed in 789 ms. 0.86/0.90 0.90/1.00 EOF