/export/starexec/sandbox/solver/bin/starexec_run_C /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


WORST_CASE(?,O(n^1))  

Preprocessing Cost Relations
=====================================

#### Computed strongly connected components 
0. recursive  : [eval_foo_bb1_in/5,eval_foo_bb2_in/5]
1. recursive  : [eval_foo_bb5_in/7,eval_foo_bb6_in/7]
2. recursive  : [eval_foo_bb3_in/3,eval_foo_bb4_in/3,eval_foo_bb5_in_loop_cont/4]
3. non_recursive  : [eval_foo_stop/1]
4. non_recursive  : [eval_foo_bb7_in/1]
5. non_recursive  : [eval_foo_bb3_in_loop_cont/2]
6. non_recursive  : [eval_foo_bb1_in_loop_cont/4]
7. non_recursive  : [eval_foo_bb0_in/3]
8. non_recursive  : [eval_foo_start/4]

#### Obtained direct recursion through partial evaluation 
0. SCC is partially evaluated into eval_foo_bb1_in/5
1. SCC is partially evaluated into eval_foo_bb5_in/7
2. SCC is partially evaluated into eval_foo_bb3_in/3
3. SCC is completely evaluated into other SCCs
4. SCC is completely evaluated into other SCCs
5. SCC is completely evaluated into other SCCs
6. SCC is partially evaluated into eval_foo_bb1_in_loop_cont/4
7. SCC is partially evaluated into eval_foo_bb0_in/3
8. SCC is partially evaluated into eval_foo_start/4

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations eval_foo_bb1_in/5 
* CE 4 is refined into CE [12] 
* CE 5 is refined into CE [13] 
* CE 3 is refined into CE [14] 


### Cost equations --> "Loop" of eval_foo_bb1_in/5 
* CEs [14] --> Loop 12 
* CEs [12] --> Loop 13 
* CEs [13] --> Loop 14 

### Ranking functions of CR eval_foo_bb1_in(V__01,V__0,B,C,D) 
* RF of phase [12]: [V__0,V__01]

#### Partial ranking functions of CR eval_foo_bb1_in(V__01,V__0,B,C,D) 
* Partial RF of phase [12]:
  - RF of loop [12:1]:
    V__0
    V__01


### Specialization of cost equations eval_foo_bb5_in/7 
* CE 10 is refined into CE [15] 
* CE 11 is refined into CE [16] 
* CE 9 is refined into CE [17] 


### Cost equations --> "Loop" of eval_foo_bb5_in/7 
* CEs [17] --> Loop 15 
* CEs [15] --> Loop 16 
* CEs [16] --> Loop 17 

### Ranking functions of CR eval_foo_bb5_in(V__12,V__1,V__23,V__2,B,C,D) 
* RF of phase [15]: [-V__12+V__1+V__23-1,V__12-V__1+V__2+1,V__2,V__23]

#### Partial ranking functions of CR eval_foo_bb5_in(V__12,V__1,V__23,V__2,B,C,D) 
* Partial RF of phase [15]:
  - RF of loop [15:1]:
    -V__12+V__1+V__23-1
    V__12-V__1+V__2+1
    V__2
    V__23


### Specialization of cost equations eval_foo_bb3_in/3 
* CE 8 is refined into CE [18] 
* CE 7 is refined into CE [19,20,21] 


### Cost equations --> "Loop" of eval_foo_bb3_in/3 
* CEs [21] --> Loop 18 
* CEs [20] --> Loop 19 
* CEs [19] --> Loop 20 
* CEs [18] --> Loop 21 

### Ranking functions of CR eval_foo_bb3_in(V__12,V__1,B) 
* RF of phase [18]: [-V__12]
* RF of phase [20]: [V__1,-V__12+V__1]

#### Partial ranking functions of CR eval_foo_bb3_in(V__12,V__1,B) 
* Partial RF of phase [18]:
  - RF of loop [18:1]:
    -V__12
* Partial RF of phase [20]:
  - RF of loop [20:1]:
    V__1
    -V__12+V__1


### Specialization of cost equations eval_foo_bb1_in_loop_cont/4 
* CE 6 is refined into CE [22,23,24,25,26,27,28] 


### Cost equations --> "Loop" of eval_foo_bb1_in_loop_cont/4 
* CEs [28] --> Loop 22 
* CEs [27] --> Loop 23 
* CEs [26] --> Loop 24 
* CEs [25] --> Loop 25 
* CEs [24] --> Loop 26 
* CEs [23] --> Loop 27 
* CEs [22] --> Loop 28 

### Ranking functions of CR eval_foo_bb1_in_loop_cont(A,B,C,D) 

#### Partial ranking functions of CR eval_foo_bb1_in_loop_cont(A,B,C,D) 


### Specialization of cost equations eval_foo_bb0_in/3 
* CE 2 is refined into CE [29,30,31,32,33,34,35,36,37,38,39,40,41] 


### Cost equations --> "Loop" of eval_foo_bb0_in/3 
* CEs [31] --> Loop 29 
* CEs [30] --> Loop 30 
* CEs [33] --> Loop 31 
* CEs [37] --> Loop 32 
* CEs [36] --> Loop 33 
* CEs [38] --> Loop 34 
* CEs [34] --> Loop 35 
* CEs [32] --> Loop 36 
* CEs [29] --> Loop 37 
* CEs [40] --> Loop 38 
* CEs [39] --> Loop 39 
* CEs [35] --> Loop 40 
* CEs [41] --> Loop 41 

### Ranking functions of CR eval_foo_bb0_in(V_x,V_y,B) 

#### Partial ranking functions of CR eval_foo_bb0_in(V_x,V_y,B) 


### Specialization of cost equations eval_foo_start/4 
* CE 1 is refined into CE [42,43,44,45,46,47,48,49,50,51,52,53,54] 


### Cost equations --> "Loop" of eval_foo_start/4 
* CEs [54] --> Loop 42 
* CEs [53] --> Loop 43 
* CEs [52] --> Loop 44 
* CEs [51] --> Loop 45 
* CEs [50] --> Loop 46 
* CEs [49] --> Loop 47 
* CEs [48] --> Loop 48 
* CEs [47] --> Loop 49 
* CEs [46] --> Loop 50 
* CEs [45] --> Loop 51 
* CEs [44] --> Loop 52 
* CEs [43] --> Loop 53 
* CEs [42] --> Loop 54 

### Ranking functions of CR eval_foo_start(V_x,V_y,V_res,B) 

#### Partial ranking functions of CR eval_foo_start(V_x,V_y,V_res,B) 


Computing Bounds
=====================================

#### Cost of chains of eval_foo_bb1_in(V__01,V__0,B,C,D):
* Chain [[12],14]: 1*it(12)+0
  Such that:it(12) =< V__01

  with precondition: [B=2,C=0,V__01+D=V__0,V__01>=1,V__0>=V__01] 

* Chain [[12],13]: 1*it(12)+0
  Such that:it(12) =< V__01-C

  with precondition: [B=2,D=0,V__01=V__0+C,V__0>=1,V__01>=V__0] 

* Chain [14]: 0
  with precondition: [B=2,D=V__0,V__01=C,0>=V__01] 

* Chain [13]: 0
  with precondition: [B=2,C=V__01,V__0=D,0>=V__0] 


#### Cost of chains of eval_foo_bb5_in(V__12,V__1,V__23,V__2,B,C,D):
* Chain [[15],17]: 1*it(15)+0
  Such that:it(15) =< V__2-D

  with precondition: [B=2,C=0,V__1=V__12+D+1,V__1+V__23=V__12+V__2+1,V__1>=V__12+1,V__1>=V__2,V__12+V__2>=V__1] 

* Chain [[15],16]: 1*it(15)+0
  Such that:it(15) =< V__2

  with precondition: [B=2,D=0,V__1+C=V__12+1,V__1+V__23=V__12+V__2+1,V__2>=1,V__12+1>=V__1,V__1>=V__2] 

* Chain [17]: 0
  with precondition: [B=2,V__23=C,V__2=D,V__1+V__23=V__12+V__2+1,0>=V__23,V__1>=1,V__1>=V__2] 


#### Cost of chains of eval_foo_bb3_in(V__12,V__1,B):
* Chain [[20],21]: 1*it(20)+1*s(3)+0
  Such that:it(20) =< -V__12+V__1
aux(3) =< V__1
it(20) =< aux(3)
s(3) =< aux(3)

  with precondition: [B=3,V__12>=0,V__1>=V__12+1] 

* Chain [[20],19,21]: 1*it(20)+1*s(3)+1*s(4)+1
  Such that:s(4) =< 1
it(20) =< -V__12+V__1
aux(4) =< V__1
it(20) =< aux(4)
s(3) =< aux(4)

  with precondition: [B=3,V__12>=0,V__1>=V__12+2] 

* Chain [[18],[20],21]: 1*it(18)+2*it(20)+0
  Such that:it(18) =< -V__12
aux(5) =< V__1
it(20) =< aux(5)

  with precondition: [B=3,0>=V__12+1,V__1>=1] 

* Chain [[18],[20],19,21]: 1*it(18)+2*it(20)+1*s(4)+1
  Such that:s(4) =< 1
it(18) =< -V__12
aux(6) =< V__1
it(20) =< aux(6)

  with precondition: [B=3,0>=V__12+1,V__1>=2] 

* Chain [[18],19,21]: 1*it(18)+1*s(4)+1
  Such that:s(4) =< 1
it(18) =< -V__12

  with precondition: [V__1=1,B=3,0>=V__12+1] 

* Chain [21]: 0
  with precondition: [B=3,0>=V__1] 

* Chain [19,21]: 1*s(4)+1
  Such that:s(4) =< V__1

  with precondition: [B=3,V__1>=1,V__12+1>=V__1] 


#### Cost of chains of eval_foo_bb1_in_loop_cont(A,B,C,D):
* Chain [28]: 1*s(5)+1*s(6)+1
  Such that:s(5) =< 1
s(6) =< -B

  with precondition: [A=2,C=1,0>=B+1] 

* Chain [27]: 1*s(7)+2*s(9)+0
  Such that:s(7) =< -B
s(8) =< C
s(9) =< s(8)

  with precondition: [A=2,0>=B+1,C>=1] 

* Chain [26]: 1*s(10)+1*s(11)+2*s(13)+1
  Such that:s(10) =< 1
s(11) =< -B
s(12) =< C
s(13) =< s(12)

  with precondition: [A=2,0>=B+1,C>=2] 

* Chain [25]: 0
  with precondition: [A=2,0>=C] 

* Chain [24]: 1*s(14)+1*s(16)+0
  Such that:s(14) =< -B+C
s(15) =< C
s(14) =< s(15)
s(16) =< s(15)

  with precondition: [A=2,B>=0,C>=B+1] 

* Chain [23]: 1*s(17)+1*s(18)+1*s(20)+1
  Such that:s(17) =< 1
s(18) =< -B+C
s(19) =< C
s(18) =< s(19)
s(20) =< s(19)

  with precondition: [A=2,B>=0,C>=B+2] 

* Chain [22]: 1*s(21)+1
  Such that:s(21) =< C

  with precondition: [A=2,C>=1,B+1>=C] 


#### Cost of chains of eval_foo_bb0_in(V_x,V_y,B):
* Chain [41]: 1*s(22)+1
  Such that:s(22) =< 1

  with precondition: [V_x=1,V_y=0] 

* Chain [40]: 1*s(23)+1*s(24)+1
  Such that:s(23) =< 1
s(24) =< -V_y

  with precondition: [V_x=1,0>=V_y+1] 

* Chain [39]: 2*s(25)+0
  Such that:aux(7) =< V_x
s(25) =< aux(7)

  with precondition: [V_y=0,V_x>=1] 

* Chain [38]: 1*s(28)+2*s(29)+1
  Such that:s(28) =< 1
aux(8) =< V_x
s(29) =< aux(8)

  with precondition: [V_y=0,V_x>=2] 

* Chain [37]: 1*s(32)+0
  Such that:s(32) =< V_y

  with precondition: [V_x=V_y,V_x>=1] 

* Chain [36]: 1*s(33)+1*s(34)+1
  Such that:s(34) =< 1
s(33) =< V_y

  with precondition: [V_x=V_y+1,V_x>=2] 

* Chain [35]: 0
  with precondition: [0>=V_x] 

* Chain [34]: 0
  with precondition: [0>=V_x,0>=V_y] 

* Chain [33]: 1*s(35)+2*s(37)+0
  Such that:s(36) =< V_x
s(35) =< -V_y
s(37) =< s(36)

  with precondition: [0>=V_y+1,V_x>=1] 

* Chain [32]: 1*s(38)+1*s(39)+2*s(41)+1
  Such that:s(38) =< 1
s(40) =< V_x
s(39) =< -V_y
s(41) =< s(40)

  with precondition: [0>=V_y+1,V_x>=2] 

* Chain [31]: 1*s(42)+0
  Such that:s(42) =< V_x

  with precondition: [V_x>=1,V_y>=V_x] 

* Chain [30]: 1*s(43)+2*s(44)+0
  Such that:s(43) =< V_y
aux(9) =< V_x-V_y
s(44) =< aux(9)

  with precondition: [V_y>=1,V_x>=V_y+1] 

* Chain [29]: 1*s(47)+1*s(48)+2*s(49)+1
  Such that:s(48) =< 1
s(47) =< V_y
aux(10) =< V_x-V_y
s(49) =< aux(10)

  with precondition: [V_y>=1,V_x>=V_y+2] 


#### Cost of chains of eval_foo_start(V_x,V_y,V_res,B):
* Chain [54]: 1*s(52)+1
  Such that:s(52) =< 1

  with precondition: [V_x=1,V_y=0] 

* Chain [53]: 1*s(53)+1*s(54)+1
  Such that:s(53) =< 1
s(54) =< -V_y

  with precondition: [V_x=1,0>=V_y+1] 

* Chain [52]: 2*s(56)+0
  Such that:s(55) =< V_x
s(56) =< s(55)

  with precondition: [V_y=0,V_x>=1] 

* Chain [51]: 1*s(57)+2*s(59)+1
  Such that:s(57) =< 1
s(58) =< V_x
s(59) =< s(58)

  with precondition: [V_y=0,V_x>=2] 

* Chain [50]: 1*s(60)+0
  Such that:s(60) =< V_y

  with precondition: [V_x=V_y,V_x>=1] 

* Chain [49]: 1*s(61)+1*s(62)+1
  Such that:s(61) =< 1
s(62) =< V_y

  with precondition: [V_x=V_y+1,V_x>=2] 

* Chain [48]: 0
  with precondition: [0>=V_x] 

* Chain [47]: 0
  with precondition: [0>=V_x,0>=V_y] 

* Chain [46]: 1*s(64)+2*s(65)+0
  Such that:s(63) =< V_x
s(64) =< -V_y
s(65) =< s(63)

  with precondition: [0>=V_y+1,V_x>=1] 

* Chain [45]: 1*s(66)+1*s(68)+2*s(69)+1
  Such that:s(66) =< 1
s(67) =< V_x
s(68) =< -V_y
s(69) =< s(67)

  with precondition: [0>=V_y+1,V_x>=2] 

* Chain [44]: 1*s(70)+0
  Such that:s(70) =< V_x

  with precondition: [V_x>=1,V_y>=V_x] 

* Chain [43]: 1*s(71)+2*s(73)+0
  Such that:s(72) =< V_x-V_y
s(71) =< V_y
s(73) =< s(72)

  with precondition: [V_y>=1,V_x>=V_y+1] 

* Chain [42]: 1*s(74)+1*s(75)+2*s(77)+1
  Such that:s(74) =< 1
s(76) =< V_x-V_y
s(75) =< V_y
s(77) =< s(76)

  with precondition: [V_y>=1,V_x>=V_y+2] 


Closed-form bounds of eval_foo_start(V_x,V_y,V_res,B): 
-------------------------------------
* Chain [54] with precondition: [V_x=1,V_y=0] 
    - Upper bound: 2 
    - Complexity: constant 
* Chain [53] with precondition: [V_x=1,0>=V_y+1] 
    - Upper bound: -V_y+2 
    - Complexity: n 
* Chain [52] with precondition: [V_y=0,V_x>=1] 
    - Upper bound: 2*V_x 
    - Complexity: n 
* Chain [51] with precondition: [V_y=0,V_x>=2] 
    - Upper bound: 2*V_x+2 
    - Complexity: n 
* Chain [50] with precondition: [V_x=V_y,V_x>=1] 
    - Upper bound: V_y 
    - Complexity: n 
* Chain [49] with precondition: [V_x=V_y+1,V_x>=2] 
    - Upper bound: V_y+2 
    - Complexity: n 
* Chain [48] with precondition: [0>=V_x] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [47] with precondition: [0>=V_x,0>=V_y] 
    - Upper bound: 0 
    - Complexity: constant 
* Chain [46] with precondition: [0>=V_y+1,V_x>=1] 
    - Upper bound: 2*V_x-V_y 
    - Complexity: n 
* Chain [45] with precondition: [0>=V_y+1,V_x>=2] 
    - Upper bound: 2*V_x-V_y+2 
    - Complexity: n 
* Chain [44] with precondition: [V_x>=1,V_y>=V_x] 
    - Upper bound: V_x 
    - Complexity: n 
* Chain [43] with precondition: [V_y>=1,V_x>=V_y+1] 
    - Upper bound: 2*V_x-V_y 
    - Complexity: n 
* Chain [42] with precondition: [V_y>=1,V_x>=V_y+2] 
    - Upper bound: 2*V_x-V_y+2 
    - Complexity: n 

### Maximum cost of eval_foo_start(V_x,V_y,V_res,B): max([max([max([2,nat(-V_y)+2]),nat(V_y)+2+nat(V_x-V_y)*2]),nat(V_x)+2+nat(-V_y)+nat(V_x)]) 
Asymptotic class: n 
* Total analysis performed in 393 ms.