18.29/18.33 MAYBE 18.29/18.33 18.29/18.33 Preprocessing Cost Relations 18.29/18.33 ===================================== 18.29/18.33 18.29/18.33 #### Computed strongly connected components 18.29/18.33 0. recursive : [f11/13,f34/13,f38/13] 18.29/18.33 1. non_recursive : [exit_location/1] 18.29/18.33 2. non_recursive : [f53/8] 18.29/18.33 3. non_recursive : [f11_loop_cont/9] 18.29/18.33 4. non_recursive : [f0/8] 18.29/18.33 18.29/18.33 #### Obtained direct recursion through partial evaluation 18.29/18.33 0. SCC is partially evaluated into f11/13 18.29/18.33 1. SCC is completely evaluated into other SCCs 18.29/18.33 2. SCC is completely evaluated into other SCCs 18.29/18.33 3. SCC is partially evaluated into f11_loop_cont/9 18.29/18.33 4. SCC is partially evaluated into f0/8 18.29/18.33 18.29/18.33 Control-Flow Refinement of Cost Relations 18.29/18.33 ===================================== 18.29/18.33 18.29/18.33 ### Specialization of cost equations f11/13 18.29/18.33 * CE 25 is refined into CE [28] 18.29/18.33 * CE 24 is refined into CE [29] 18.29/18.33 * CE 19 is refined into CE [30] 18.29/18.33 * CE 10 is refined into CE [31] 18.29/18.33 * CE 12 is refined into CE [32] 18.29/18.33 * CE 7 is refined into CE [33] 18.29/18.33 * CE 8 is refined into CE [34] 18.29/18.33 * CE 16 is refined into CE [35] 18.29/18.33 * CE 9 is refined into CE [36] 18.29/18.33 * CE 3 is discarded (unfeasible) 18.29/18.33 * CE 11 is refined into CE [37] 18.29/18.33 * CE 5 is refined into CE [38] 18.29/18.33 * CE 6 is refined into CE [39] 18.29/18.33 * CE 4 is refined into CE [40] 18.29/18.33 * CE 2 is refined into CE [41] 18.29/18.33 * CE 20 is refined into CE [42] 18.29/18.33 * CE 13 is refined into CE [43] 18.29/18.33 * CE 15 is refined into CE [44] 18.29/18.33 * CE 17 is refined into CE [45] 18.29/18.33 * CE 23 is refined into CE [46] 18.29/18.33 * CE 14 is refined into CE [47] 18.29/18.33 * CE 21 is refined into CE [48] 18.29/18.33 * CE 22 is refined into CE [49] 18.29/18.33 * CE 18 is refined into CE [50] 18.29/18.33 18.29/18.33 18.29/18.33 ### Cost equations --> "Loop" of f11/13 18.29/18.33 * CEs [30] --> Loop 28 18.29/18.33 * CEs [32] --> Loop 29 18.29/18.33 * CEs [35] --> Loop 30 18.29/18.33 * CEs [42] --> Loop 31 18.29/18.33 * CEs [43] --> Loop 32 18.29/18.33 * CEs [45] --> Loop 33 18.29/18.33 * CEs [47] --> Loop 34 18.29/18.33 * CEs [48] --> Loop 35 18.29/18.33 * CEs [49] --> Loop 36 18.29/18.33 * CEs [50] --> Loop 37 18.29/18.33 * CEs [44] --> Loop 38 18.29/18.33 * CEs [46] --> Loop 39 18.29/18.33 * CEs [31] --> Loop 40 18.29/18.33 * CEs [33] --> Loop 41 18.29/18.33 * CEs [34] --> Loop 42 18.29/18.33 * CEs [36] --> Loop 43 18.29/18.33 * CEs [37] --> Loop 44 18.29/18.33 * CEs [38] --> Loop 45 18.29/18.33 * CEs [39] --> Loop 46 18.29/18.33 * CEs [40] --> Loop 47 18.29/18.33 * CEs [41] --> Loop 48 18.29/18.33 * CEs [28] --> Loop 49 18.29/18.33 * CEs [29] --> Loop 50 18.29/18.33 18.29/18.33 ### Ranking functions of CR f11(A,B,C,D,E,G,K,L,M,N,O,P,Q) 18.29/18.33 18.29/18.33 #### Partial ranking functions of CR f11(A,B,C,D,E,G,K,L,M,N,O,P,Q) 18.29/18.33 * Partial RF of phase [28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48]: 18.29/18.33 - RF of loop [28:1,29:1,30:1]: 18.29/18.33 C/2-1/2 depends on loops [31:1,32:1,33:1,40:1,41:1,43:1,45:1,46:1] 18.29/18.33 - RF of loop [29:1,30:1,32:1,33:1,34:1,37:1,38:1,41:1,42:1,43:1,45:1,47:1,48:1]: 18.29/18.33 G 18.29/18.33 - RF of loop [31:1,32:1,33:1,40:1,41:1,43:1]: 18.29/18.33 D/3-2/3 depends on loops [34:1,35:1,36:1,37:1,38:1,39:1,47:1,48:1] 18.29/18.33 - RF of loop [34:1,35:1]: 18.29/18.33 -D+3 depends on loops [31:1,32:1,33:1,40:1,41:1,42:1,43:1,44:1,45:1,46:1] 18.29/18.33 - RF of loop [34:1,35:1,36:1,37:1,38:1,39:1]: 18.29/18.33 C depends on loops [31:1,32:1,33:1,40:1,41:1,43:1,45:1,46:1] 18.29/18.33 - RF of loop [36:1,37:1]: 18.29/18.33 -D+2 depends on loops [31:1,32:1,33:1,40:1,41:1,42:1,43:1,44:1,45:1,46:1] 18.29/18.33 - RF of loop [38:1,39:1]: 18.29/18.33 -D+1 depends on loops [31:1,32:1,33:1,40:1,41:1,42:1,43:1,44:1,45:1,46:1] 18.29/18.33 - RF of loop [42:1,44:1]: 18.29/18.33 D/2-1 depends on loops [34:1,35:1,36:1,37:1,38:1,39:1,47:1,48:1] 18.29/18.33 - RF of loop [45:1,46:1]: 18.29/18.33 D/2-1/2 depends on loops [34:1,35:1,36:1,37:1,38:1,39:1,47:1,48:1] 18.29/18.33 - RF of loop [47:1]: 18.29/18.33 -D/2+1 depends on loops [31:1,32:1,33:1,40:1,41:1,42:1,43:1,44:1,45:1,46:1] 18.29/18.33 - RF of loop [48:1]: 18.29/18.33 -D/2+1/2 depends on loops [31:1,32:1,33:1,40:1,41:1,42:1,43:1,44:1,45:1,46:1] 18.29/18.33 18.29/18.33 18.29/18.33 ### Specialization of cost equations f11_loop_cont/9 18.29/18.33 * CE 27 is refined into CE [51] 18.29/18.33 * CE 26 is refined into CE [52] 18.29/18.33 18.29/18.33 18.29/18.33 ### Cost equations --> "Loop" of f11_loop_cont/9 18.29/18.33 * CEs [51] --> Loop 51 18.29/18.33 * CEs [52] --> Loop 52 18.29/18.33 18.29/18.33 ### Ranking functions of CR f11_loop_cont(A,B,C,D,E,F,G,H,I) 18.29/18.33 18.29/18.33 #### Partial ranking functions of CR f11_loop_cont(A,B,C,D,E,F,G,H,I) 18.29/18.33 18.29/18.33 18.29/18.33 ### Specialization of cost equations f0/8 18.29/18.33 * CE 1 is refined into CE [53,54,55,56,57] 18.29/18.33 18.29/18.33 18.29/18.33 ### Cost equations --> "Loop" of f0/8 18.29/18.33 * CEs [56,57] --> Loop 53 18.29/18.33 * CEs [53,54,55] --> Loop 54 18.29/18.33 18.29/18.33 ### Ranking functions of CR f0(A,B,C,D,E,F,G,K) 18.29/18.33 18.29/18.33 #### Partial ranking functions of CR f0(A,B,C,D,E,F,G,K) 18.29/18.33 18.29/18.33 18.29/18.33 Computing Bounds 18.29/18.33 ===================================== 18.29/18.33 18.29/18.33 #### Cost of chains of f11(A,B,C,D,E,G,K,L,M,N,O,P,Q): 18.29/18.33 * Chain [[28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48]]...: 8*it(28)+13*it(29)+0 18.29/18.33 Such that:aux(115) =< G 18.29/18.33 it(29) =< aux(115) 18.29/18.33 18.29/18.33 with precondition: [A>=0,1>=A,B>=0,1>=B,C>=0,D>=0,G>=1,E>=1] 18.29/18.33 18.29/18.33 * Chain [[28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48],50]: 8*it(28)+13*it(29)+0 18.29/18.33 Such that:aux(116) =< G 18.29/18.33 it(29) =< aux(116) 18.29/18.33 18.29/18.33 with precondition: [K=2,Q=0,L+M=1,1>=A,1>=B,1>=L,A>=0,B>=0,C>=0,D>=0,E>=1,G>=1,L>=0,N>=0,O>=0,P>=E,C+O+2*P>=2*E+2,C+D+G>=L+1,C+D+O+2*G>=4,O+2*C+3*P>=3*E+L+2] 18.29/18.33 18.29/18.33 * Chain [[28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48],49]: 8*it(28)+13*it(29)+0 18.29/18.33 Such that:aux(117) =< G 18.29/18.33 it(29) =< aux(117) 18.29/18.33 18.29/18.33 with precondition: [K=3,1>=A,1>=B,A>=0,B>=0,C>=0,D>=0,E>=1,G>=1] 18.29/18.33 18.29/18.33 * Chain [49]: 0 18.29/18.33 with precondition: [K=3,1>=A,1>=B,A>=0,B>=0,C>=0,D>=0,E>=1,G+1>=A+B,A+B+G>=1] 18.29/18.33 18.29/18.33 18.29/18.33 #### Cost of chains of f11_loop_cont(A,B,C,D,E,F,G,H,I): 18.29/18.33 * Chain [52]: 0 18.29/18.33 with precondition: [A=2,G>=1] 18.29/18.33 18.29/18.33 * Chain [51]: 0 18.29/18.33 with precondition: [A=3,G>=1] 18.29/18.33 18.29/18.33 18.29/18.33 #### Cost of chains of f0(A,B,C,D,E,F,G,K): 18.29/18.33 * Chain [54]: 1*aux(118)+0 18.29/18.33 with precondition: [] 18.29/18.33 18.29/18.33 * Chain [53]...: 1*aux(119)+0 18.29/18.33 with precondition: [] 18.29/18.33 18.29/18.33 18.29/18.33 Closed-form bounds of f0(A,B,C,D,E,F,G,K): 18.29/18.33 ------------------------------------- 18.29/18.33 * Chain [54] with precondition: [] 18.29/18.33 - Upper bound: inf 18.29/18.33 - Complexity: infinity 18.29/18.33 * Chain [53]... with precondition: [] 18.29/18.33 - Upper bound: inf 18.29/18.33 - Complexity: infinity 18.29/18.33 18.29/18.33 ### Maximum cost of f0(A,B,C,D,E,F,G,K): inf 18.29/18.33 Asymptotic class: infinity 18.29/18.33 * Total analysis performed in 18110 ms. 18.29/18.33 18.33/18.43 EOF