15.83/5.33 YES 15.88/5.34 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 15.88/5.34 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.88/5.34 15.88/5.34 15.88/5.34 Termination of the given C Problem could be proven: 15.88/5.34 15.88/5.34 (0) C Problem 15.88/5.34 (1) CToLLVMProof [EQUIVALENT, 169 ms] 15.88/5.34 (2) LLVM problem 15.88/5.34 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1682 ms] 15.88/5.34 (4) LLVM Symbolic Execution Graph 15.88/5.34 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 15.88/5.34 (6) LLVM Symbolic Execution SCC 15.88/5.34 (7) SCC2IRS [SOUND, 63 ms] 15.88/5.34 (8) IntTRS 15.88/5.34 (9) IRS2T2 [EQUIVALENT, 4 ms] 15.88/5.34 (10) T2IntSys 15.88/5.34 (11) T2 [EQUIVALENT, 1182 ms] 15.88/5.34 (12) YES 15.88/5.34 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (0) 15.88/5.34 Obligation: 15.88/5.34 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (1) CToLLVMProof (EQUIVALENT) 15.88/5.34 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (2) 15.88/5.34 Obligation: 15.88/5.34 LLVM Problem 15.88/5.34 15.88/5.34 Aliases: 15.88/5.34 15.88/5.34 Data layout: 15.88/5.34 15.88/5.34 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 15.88/5.34 15.88/5.34 Machine: 15.88/5.34 15.88/5.34 "x86_64-pc-linux-gnu" 15.88/5.34 15.88/5.34 Type definitions: 15.88/5.34 15.88/5.34 Global variables: 15.88/5.34 15.88/5.34 Function declarations and definitions: 15.88/5.34 15.88/5.34 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.88/5.34 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, tmp i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.88/5.34 0: 15.88/5.34 %1 = alloca i32, align 4 15.88/5.34 %2 = alloca i32, align 4 15.88/5.34 %x_ref = alloca *i32, align 8 15.88/5.34 %tmp_ref = alloca *i32, align 8 15.88/5.34 store %x, %1 15.88/5.34 store %tmp, %2 15.88/5.34 %3 = alloca i8, numElementsLit: 4 15.88/5.34 %4 = bitcast *i8 %3 to *i32 15.88/5.34 store %4, %x_ref 15.88/5.34 %5 = alloca i8, numElementsLit: 4 15.88/5.34 %6 = bitcast *i8 %5 to *i32 15.88/5.34 store %6, %tmp_ref 15.88/5.34 %7 = load %1 15.88/5.34 %8 = load %x_ref 15.88/5.34 store %7, %8 15.88/5.34 %9 = load %2 15.88/5.34 %10 = load %tmp_ref 15.88/5.34 store %9, %10 15.88/5.34 %11 = call i32 @__VERIFIER_nondet_int() 15.88/5.34 %12 = load %tmp_ref 15.88/5.34 store %11, %12 15.88/5.34 br %13 15.88/5.34 13: 15.88/5.34 %14 = load %x_ref 15.88/5.34 %15 = load %14 15.88/5.34 %16 = icmp sgt %15 0 15.88/5.34 br %16, %17, %23 15.88/5.34 17: 15.88/5.34 %18 = load %1 15.88/5.34 %19 = load %tmp_ref 15.88/5.34 %20 = load %19 15.88/5.34 %21 = mul 2 %20 15.88/5.34 %22 = icmp eq %18 %21 15.88/5.34 br %23 15.88/5.34 23: 15.88/5.34 %24 = phi [0, %13], [%22, %17] 15.88/5.34 br %24, %25, %32 15.88/5.34 25: 15.88/5.34 %26 = load %x_ref 15.88/5.34 %27 = load %26 15.88/5.34 %28 = sub %27 1 15.88/5.34 %29 = load %x_ref 15.88/5.34 store %28, %29 15.88/5.34 %30 = call i32 @__VERIFIER_nondet_int() 15.88/5.34 %31 = load %tmp_ref 15.88/5.34 store %30, %31 15.88/5.34 br %13 15.88/5.34 32: 15.88/5.34 %33 = load %x_ref 15.88/5.34 %34 = load %33 15.88/5.34 ret %34 15.88/5.34 15.88/5.34 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.88/5.34 0: 15.88/5.34 %1 = alloca i32, align 4 15.88/5.34 store 0, %1 15.88/5.34 %2 = call i32 @__VERIFIER_nondet_int() 15.88/5.34 %3 = call i32 @__VERIFIER_nondet_int() 15.88/5.34 %4 = call i32 @test_fun(i32 %2, i32 %3) 15.88/5.34 ret %4 15.88/5.34 15.88/5.34 15.88/5.34 Analyze Termination of all function calls matching the pattern: 15.88/5.34 main() 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (3) LLVMToTerminationGraphProof (EQUIVALENT) 15.88/5.34 Constructed symbolic execution graph for LLVM program and proved memory safety. 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (4) 15.88/5.34 Obligation: 15.88/5.34 SE Graph 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (5) SymbolicExecutionGraphToSCCProof (SOUND) 15.88/5.34 Splitted symbolic execution graph to 1 SCC. 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (6) 15.88/5.34 Obligation: 15.88/5.34 SCC 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (7) SCC2IRS (SOUND) 15.88/5.34 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 15.88/5.34 Generated rules. Obtained 23 rulesP rules: 15.88/5.34 f_290(v224, v225, v226, v227, v228, v229, v230, v231, v232, v233, 1, v235, v236, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_291(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_291(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_292(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 < v236 && 2 <= v233 15.88/5.34 f_292(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_294(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_294(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_296(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_296(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_298(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_298(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_300(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_300(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v235, v233, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_302(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_302(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_304(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v274, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: v274 = 2 * v237 15.88/5.34 f_304(v224, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v274, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_306(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: v224 = v274 && 1 <= v237 15.88/5.34 f_306(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_308(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_308(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_310(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_310(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_312(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_312(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_314(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_314(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v233, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_316(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_316(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_318(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 1 + v361 = v236 && 0 <= v361 15.88/5.34 f_318(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_320(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_320(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_321(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_321(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_322(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_322(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_323(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 f_323(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_324(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_324(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_325(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_325(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_289(v274, v225, v226, v227, v228, v229, v230, v231, v232, v236, 1, v237, v361, v363, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: TRUE 15.88/5.34 f_289(v224, v225, v226, v227, v228, v229, v230, v231, v232, v233, 1, v235, v236, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) -> f_290(v224, v225, v226, v227, v228, v229, v230, v231, v232, v233, 1, v235, v236, v237, v238, v239, v240, v241, v242, v243, v244, v245, 0, 3, 7, 2, 4, 8) :|: 0 = 0 15.88/5.34 Combined rules. Obtained 1 rulesP rules: 15.88/5.34 f_290(2 * v237:0, v225:0, v226:0, v227:0, v228:0, v229:0, v230:0, v231:0, v232:0, v233:0, 1, v235:0, 1 + v361:0, v237:0, v238:0, v239:0, v240:0, v241:0, v242:0, v243:0, v244:0, v245:0, 0, 3, 7, 2, 4, 8) -> f_290(2 * v237:0, v225:0, v226:0, v227:0, v228:0, v229:0, v230:0, v231:0, v232:0, 1 + v361:0, 1, v237:0, v361:0, v363:0, v238:0, v239:0, v240:0, v241:0, v242:0, v243:0, v244:0, v245:0, 0, 3, 7, 2, 4, 8) :|: v233:0 > 1 && v361:0 > -1 && v237:0 > 0 15.88/5.34 Filtered unneeded arguments: 15.88/5.34 f_290(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28) -> f_290(x1, x10, x13, x14) 15.88/5.34 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 15.88/5.34 f_290(times~cons_2~v237:0, v233:0, sum~cons_1~v361:0, v237:0) -> f_290(2 * v237:0, 1 + v361:0, v361:0, v363:0) :|: v361:0 > -1 && v237:0 > 0 && v233:0 > 1 && times~cons_2~v237:0 = 2 * v237:0 && sum~cons_1~v361:0 = 1 + v361:0 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (8) 15.88/5.34 Obligation: 15.88/5.34 Rules: 15.88/5.34 f_290(times~cons_2~v237:0, v233:0, sum~cons_1~v361:0, v237:0) -> f_290(2 * v237:0, 1 + v361:0, v361:0, v363:0) :|: v361:0 > -1 && v237:0 > 0 && v233:0 > 1 && times~cons_2~v237:0 = 2 * v237:0 && sum~cons_1~v361:0 = 1 + v361:0 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (9) IRS2T2 (EQUIVALENT) 15.88/5.34 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 15.88/5.34 15.88/5.34 (f_290_4,1) 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (10) 15.88/5.34 Obligation: 15.88/5.34 START: 0; 15.88/5.34 15.88/5.34 FROM: 0; 15.88/5.34 TO: 1; 15.88/5.34 15.88/5.34 FROM: 1; 15.88/5.34 oldX0 := x0; 15.88/5.34 oldX1 := x1; 15.88/5.34 oldX2 := x2; 15.88/5.34 oldX3 := x3; 15.88/5.34 oldX4 := oldX2 - 1; 15.88/5.34 oldX5 := nondet(); 15.88/5.34 assume(oldX4 > -1 && oldX3 > 0 && oldX1 > 1 && oldX0 = 2 * oldX3 && oldX2 = 1 + oldX4); 15.88/5.34 x0 := 2 * oldX3; 15.88/5.34 x1 := 1 + oldX4; 15.88/5.34 x2 := oldX2 - 1; 15.88/5.34 x3 := oldX5; 15.88/5.34 TO: 1; 15.88/5.34 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (11) T2 (EQUIVALENT) 15.88/5.34 Initially, performed program simplifications using lexicographic rank functions: 15.88/5.34 * Removed transitions 1, 3, 4 using the following rank functions: 15.88/5.34 - Rank function 1: 15.88/5.34 RF for loc. 5: 1+2*x2 15.88/5.34 RF for loc. 6: 2*x2 15.88/5.34 Bound for (chained) transitions 3: 2 15.88/5.34 Bound for (chained) transitions 4: 2 15.88/5.34 - Rank function 2: 15.88/5.34 RF for loc. 5: 1 15.88/5.34 RF for loc. 6: 0 15.88/5.34 Bound for (chained) transitions 1: 1 15.88/5.34 15.88/5.34 ---------------------------------------- 15.88/5.34 15.88/5.34 (12) 15.88/5.34 YES 15.92/9.75 EOF