YES(?, 18*a*b + 4590*b + 4584*a + 1168925)

Initial complexity problem:
1:	T:
		(1, 1)    evalfstart(a, b) -> evalfentryin(a, b)
		(?, 1)    evalfentryin(a, b) -> evalfbb3in(b, a)
		(?, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(?, 1)    evalfbb3in(a, b) -> evalfreturnin(a, b) [ 0 >= b ]
		(?, 1)    evalfbb3in(a, b) -> evalfreturnin(a, b) [ b >= 255 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ 0 >= a + 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ a >= 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ a = 0 ]
		(?, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1)
		(?, 1)    evalfbb2in(a, b) -> evalfbb3in(a, b - 1)
		(?, 1)    evalfreturnin(a, b) -> evalfstop(a, b)
	start location:	evalfstart
	leaf cost:	0

Repeatedly removing leaves of the complexity graph in problem 1 produces the following problem:
2:	T:
		(1, 1)    evalfstart(a, b) -> evalfentryin(a, b)
		(?, 1)    evalfentryin(a, b) -> evalfbb3in(b, a)
		(?, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ 0 >= a + 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ a >= 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ a = 0 ]
		(?, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1)
		(?, 1)    evalfbb2in(a, b) -> evalfbb3in(a, b - 1)
	start location:	evalfstart
	leaf cost:	3

Repeatedly propagating knowledge in problem 2 produces the following problem:
3:	T:
		(1, 1)    evalfstart(a, b) -> evalfentryin(a, b)
		(1, 1)    evalfentryin(a, b) -> evalfbb3in(b, a)
		(?, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ 0 >= a + 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ a >= 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ a = 0 ]
		(?, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1)
		(?, 1)    evalfbb2in(a, b) -> evalfbb3in(a, b - 1)
	start location:	evalfstart
	leaf cost:	3

Applied AI with 'oct' on problem 3 to obtain the following invariants:
  For symbol evalfbb1in: -X_2 + 254 >= 0 /\ X_2 - 1 >= 0
  For symbol evalfbb2in: -X_2 + 254 >= 0 /\ X_1 - X_2 + 254 >= 0 /\ -X_1 - X_2 + 254 >= 0 /\ X_2 - 1 >= 0 /\ X_1 + X_2 - 1 >= 0 /\ -X_1 + X_2 - 1 >= 0 /\ -X_1 >= 0 /\ X_1 >= 0
  For symbol evalfbbin: -X_2 + 254 >= 0 /\ X_2 - 1 >= 0


This yielded the following problem:
4:	T:
		(?, 1)    evalfbb2in(a, b) -> evalfbb3in(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 ]
		(?, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
		(?, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(1, 1)    evalfentryin(a, b) -> evalfbb3in(b, a)
		(1, 1)    evalfstart(a, b) -> evalfentryin(a, b)
	start location:	evalfstart
	leaf cost:	3

By chaining the transition evalfbb2in(a, b) -> evalfbb3in(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 ] with all transitions in problem 4, the following new transition is obtained:
	evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
We thus obtain the following problem:
5:	T:
		(?, 2)    evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
		(?, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
		(?, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
		(?, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(1, 1)    evalfentryin(a, b) -> evalfbb3in(b, a)
		(1, 1)    evalfstart(a, b) -> evalfentryin(a, b)
	start location:	evalfstart
	leaf cost:	3

A polynomial rank function with
	Pol(evalfbb1in) = -3*V_2 + 763
	Pol(evalfbb3in) = -3*V_2 + 765
	Pol(evalfbbin) = -3*V_2 + 764
and size complexities
	S("evalfstart(a, b) -> evalfentryin(a, b)", 0-0) = a
	S("evalfstart(a, b) -> evalfentryin(a, b)", 0-1) = b
	S("evalfentryin(a, b) -> evalfbb3in(b, a)", 0-0) = b
	S("evalfentryin(a, b) -> evalfbb3in(b, a)", 0-1) = a
	S("evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\\ 254 >= b ]", 0-0) = b
	S("evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\\ 254 >= b ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ 0 >= a + 1 ]", 0-0) = b
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ 0 >= a + 1 ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a >= 1 ]", 0-0) = b
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a >= 1 ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a = 0 ]", 0-0) = 0
	S("evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a = 0 ]", 0-1) = 254
	S("evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\\ b - 1 >= 0 ]", 0-0) = b
	S("evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\\ b - 1 >= 0 ]", 0-1) = 255
	S("evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\\ a - b + 254 >= 0 /\\ -a - b + 254 >= 0 /\\ b - 1 >= 0 /\\ a + b - 1 >= 0 /\\ -a + b - 1 >= 0 /\\ -a >= 0 /\\ a >= 0 /\\ b - 1 >= 1 /\\ 254 >= b - 1 ]", 0-0) = 0
	S("evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\\ a - b + 254 >= 0 /\\ -a - b + 254 >= 0 /\\ b - 1 >= 0 /\\ a + b - 1 >= 0 /\\ -a + b - 1 >= 0 /\\ -a >= 0 /\\ a >= 0 /\\ b - 1 >= 1 /\\ 254 >= b - 1 ]", 0-1) = 253
orients the transitions
	evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
	evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
	evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
	evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
weakly and the transitions
	evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
	evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
	evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
	evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
strictly and produces the following problem:
6:	T:
		(?, 2)            evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
		(3*a + 765, 1)    evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
		(?, 1)            evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
		(3*a + 765, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
		(3*a + 765, 1)    evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
		(3*a + 765, 1)    evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(1, 1)            evalfentryin(a, b) -> evalfbb3in(b, a)
		(1, 1)            evalfstart(a, b) -> evalfentryin(a, b)
	start location:	evalfstart
	leaf cost:	3

A polynomial rank function with
	Pol(evalfbbin) = 2*V_1 + 2*V_2
	Pol(evalfbb2in) = 2*V_1 + 2*V_2 - 1
and size complexities
	S("evalfstart(a, b) -> evalfentryin(a, b)", 0-0) = a
	S("evalfstart(a, b) -> evalfentryin(a, b)", 0-1) = b
	S("evalfentryin(a, b) -> evalfbb3in(b, a)", 0-0) = b
	S("evalfentryin(a, b) -> evalfbb3in(b, a)", 0-1) = a
	S("evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\\ 254 >= b ]", 0-0) = b
	S("evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\\ 254 >= b ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ 0 >= a + 1 ]", 0-0) = b
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ 0 >= a + 1 ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a >= 1 ]", 0-0) = b
	S("evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a >= 1 ]", 0-1) = 254
	S("evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a = 0 ]", 0-0) = 0
	S("evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\\ b - 1 >= 0 /\\ a = 0 ]", 0-1) = 254
	S("evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\\ b - 1 >= 0 ]", 0-0) = b
	S("evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\\ b - 1 >= 0 ]", 0-1) = 255
	S("evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\\ a - b + 254 >= 0 /\\ -a - b + 254 >= 0 /\\ b - 1 >= 0 /\\ a + b - 1 >= 0 /\\ -a + b - 1 >= 0 /\\ -a >= 0 /\\ a >= 0 /\\ b - 1 >= 1 /\\ 254 >= b - 1 ]", 0-0) = 0
	S("evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\\ a - b + 254 >= 0 /\\ -a - b + 254 >= 0 /\\ b - 1 >= 0 /\\ a + b - 1 >= 0 /\\ -a + b - 1 >= 0 /\\ -a >= 0 /\\ a >= 0 /\\ b - 1 >= 1 /\\ 254 >= b - 1 ]", 0-1) = 253
orients the transitions
	evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
	evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
weakly and the transitions
	evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
	evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
strictly and produces the following problem:
7:	T:
		(6*a*b + 1530*b + 1524*a + 388620, 2)    evalfbb2in(a, b) -> evalfbbin(a, b - 1) [ -b + 254 >= 0 /\ a - b + 254 >= 0 /\ -a - b + 254 >= 0 /\ b - 1 >= 0 /\ a + b - 1 >= 0 /\ -a + b - 1 >= 0 /\ -a >= 0 /\ a >= 0 /\ b - 1 >= 1 /\ 254 >= b - 1 ]
		(3*a + 765, 1)                           evalfbb1in(a, b) -> evalfbb3in(a, b + 1) [ -b + 254 >= 0 /\ b - 1 >= 0 ]
		(6*a*b + 1530*b + 1524*a + 388620, 1)    evalfbbin(a, b) -> evalfbb2in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a = 0 ]
		(3*a + 765, 1)                           evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ a >= 1 ]
		(3*a + 765, 1)                           evalfbbin(a, b) -> evalfbb1in(a, b) [ -b + 254 >= 0 /\ b - 1 >= 0 /\ 0 >= a + 1 ]
		(3*a + 765, 1)                           evalfbb3in(a, b) -> evalfbbin(a, b) [ b >= 1 /\ 254 >= b ]
		(1, 1)                                   evalfentryin(a, b) -> evalfbb3in(b, a)
		(1, 1)                                   evalfstart(a, b) -> evalfentryin(a, b)
	start location:	evalfstart
	leaf cost:	3

Complexity upper bound 18*a*b + 4590*b + 4584*a + 1168925

Time: 0.757 sec (SMT: 0.718 sec)