18.63/6.09 YES 18.83/6.18 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 18.83/6.18 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 18.83/6.18 18.83/6.18 18.83/6.18 Termination of the given C Problem could be proven: 18.83/6.18 18.83/6.18 (0) C Problem 18.83/6.18 (1) CToLLVMProof [EQUIVALENT, 172 ms] 18.83/6.18 (2) LLVM problem 18.83/6.18 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2224 ms] 18.83/6.18 (4) LLVM Symbolic Execution Graph 18.83/6.18 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 18.83/6.18 (6) LLVM Symbolic Execution SCC 18.83/6.18 (7) SCC2IRS [SOUND, 105 ms] 18.83/6.18 (8) IntTRS 18.83/6.18 (9) IRS2T2 [EQUIVALENT, 0 ms] 18.83/6.18 (10) T2IntSys 18.83/6.18 (11) T2 [EQUIVALENT, 1173 ms] 18.83/6.18 (12) YES 18.83/6.18 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (0) 18.83/6.18 Obligation: 18.83/6.18 c file /export/starexec/sandbox/benchmark/theBenchmark.c 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (1) CToLLVMProof (EQUIVALENT) 18.83/6.18 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (2) 18.83/6.18 Obligation: 18.83/6.18 LLVM Problem 18.83/6.18 18.83/6.18 Aliases: 18.83/6.18 18.83/6.18 Data layout: 18.83/6.18 18.83/6.18 "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" 18.83/6.18 18.83/6.18 Machine: 18.83/6.18 18.83/6.18 "x86_64-pc-linux-gnu" 18.83/6.18 18.83/6.18 Type definitions: 18.83/6.18 18.83/6.18 Global variables: 18.83/6.18 18.83/6.18 Function declarations and definitions: 18.83/6.18 18.83/6.18 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 18.83/6.18 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 18.83/6.18 0: 18.83/6.18 %1 = alloca i32, align 4 18.83/6.18 %x = alloca i32, align 4 18.83/6.18 %y = alloca i32, align 4 18.83/6.18 %z = alloca i32, align 4 18.83/6.18 store 0, %1 18.83/6.18 %2 = call i32 @__VERIFIER_nondet_int() 18.83/6.18 store %2, %x 18.83/6.18 %3 = load %x 18.83/6.18 %4 = icmp slt %3 0 18.83/6.18 br %4, %5, %6 18.83/6.18 5: 18.83/6.18 store 0, %1 18.83/6.18 br %16 18.83/6.18 6: 18.83/6.18 %7 = call i32 @__VERIFIER_nondet_int() 18.83/6.18 store %7, %y 18.83/6.18 %8 = load %y 18.83/6.18 %9 = icmp slt %8 0 18.83/6.18 br %9, %10, %11 18.83/6.18 10: 18.83/6.18 store 0, %1 18.83/6.18 br %16 18.83/6.18 11: 18.83/6.18 %12 = call i32 @__VERIFIER_nondet_int() 18.83/6.18 store %12, %z 18.83/6.18 %13 = load %x 18.83/6.18 %14 = load %y 18.83/6.18 %15 = call i32 @le(i32 %13, i32 %14) 18.83/6.18 br %16 18.83/6.18 16: 18.83/6.18 %17 = load %1 18.83/6.18 ret %17 18.83/6.18 18.83/6.18 *BasicFunctionTypename: "le" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 18.83/6.18 0: 18.83/6.18 %1 = alloca i32, align 4 18.83/6.18 %2 = alloca i32, align 4 18.83/6.18 %3 = alloca i32, align 4 18.83/6.18 store %x, %2 18.83/6.18 store %y, %3 18.83/6.18 %4 = load %2 18.83/6.18 %5 = icmp sgt %4 0 18.83/6.18 br %5, %6, %15 18.83/6.18 6: 18.83/6.18 %7 = load %3 18.83/6.18 %8 = icmp sgt %7 0 18.83/6.18 br %8, %9, %15 18.83/6.18 9: 18.83/6.18 %10 = load %2 18.83/6.18 %11 = sub %10 1 18.83/6.18 %12 = load %3 18.83/6.18 %13 = sub %12 1 18.83/6.18 %14 = call i32 @le(i32 %11, i32 %13) 18.83/6.18 store %14, %1 18.83/6.18 br %19 18.83/6.18 15: 18.83/6.18 %16 = load %2 18.83/6.18 %17 = icmp eq %16 0 18.83/6.18 %18 = zext i1 %17 to i32 18.83/6.18 store %18, %1 18.83/6.18 br %19 18.83/6.18 19: 18.83/6.18 %20 = load %1 18.83/6.18 ret %20 18.83/6.18 18.83/6.18 *BasicFunctionTypename: "random" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 18.83/6.18 0: 18.83/6.18 %1 = alloca i32, align 4 18.83/6.18 %x = alloca i32, align 4 18.83/6.18 %2 = call i32 @__VERIFIER_nondet_int() 18.83/6.18 store %2, %x 18.83/6.18 %3 = load %x 18.83/6.18 %4 = icmp slt %3 0 18.83/6.18 br %4, %5, %8 18.83/6.18 5: 18.83/6.18 %6 = load %x 18.83/6.18 %7 = sub 0 %6 18.83/6.18 store %7, %1 18.83/6.18 br %10 18.83/6.18 8: 18.83/6.18 %9 = load %x 18.83/6.18 store %9, %1 18.83/6.18 br %10 18.83/6.18 10: 18.83/6.18 %11 = load %1 18.83/6.18 ret %11 18.83/6.18 18.83/6.18 18.83/6.18 Analyze Termination of all function calls matching the pattern: 18.83/6.18 main() 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (3) LLVMToTerminationGraphProof (EQUIVALENT) 18.83/6.18 Constructed symbolic execution graph for LLVM program and proved memory safety. 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (4) 18.83/6.18 Obligation: 18.83/6.18 SE Graph 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (5) SymbolicExecutionGraphToSCCProof (SOUND) 18.83/6.18 Splitted symbolic execution graph to 1 SCC. 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (6) 18.83/6.18 Obligation: 18.83/6.18 SCC 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (7) SCC2IRS (SOUND) 18.83/6.18 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 18.83/6.18 Generated rules. Obtained 20 rulesP rules: 18.83/6.18 f_329(v95, v96, v109, v97, v98, v99, v100, v101, v102, v103, v104, v110, 0, v106, v107, v108, 3, 1, 4) -> f_330(v95, v96, v109, v111, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, 0, v106, v107, v108, 3, 1, 4) :|: 1 <= v111 && v112 = 3 + v111 && 4 <= v112 18.83/6.18 f_330(v95, v96, v109, v111, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, 0, v106, v107, v108, 3, 1, 4) -> f_331(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) :|: 1 <= v113 && v114 = 3 + v113 && 4 <= v114 18.83/6.18 f_331(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) -> f_332(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) :|: TRUE 18.83/6.18 f_332(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) -> f_333(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) :|: TRUE 18.83/6.18 f_333(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) -> f_334(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) :|: 0 = 0 18.83/6.18 f_334(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) -> f_335(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) :|: 0 < v95 && 1 <= v106 18.83/6.18 f_335(v95, v96, v109, v111, v113, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 1, 4) -> f_337(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 = 0 18.83/6.18 f_337(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_339(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: TRUE 18.83/6.18 f_339(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_341(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 = 0 18.83/6.18 f_341(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_343(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 < v96 && 1 <= v107 18.83/6.18 f_343(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_346(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 = 0 18.83/6.18 f_346(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_349(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: TRUE 18.83/6.18 f_349(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_352(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 = 0 18.83/6.18 f_352(v95, v96, v109, v111, v113, 1, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_355(v95, v96, v109, v111, v113, 1, v117, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 1 + v117 = v95 && 0 <= v117 18.83/6.18 f_355(v95, v96, v109, v111, v113, 1, v117, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_358(v95, v96, v109, v111, v113, 1, v117, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 0 = 0 18.83/6.18 f_358(v95, v96, v109, v111, v113, 1, v117, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_361(v95, v96, v109, v111, v113, 1, v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) :|: 1 + v136 = v96 && 0 <= v136 18.83/6.18 f_361(v95, v96, v109, v111, v113, 1, v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v110, v112, v114, 0, v106, v107, v108, 3, 4) -> f_364(v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v109, v110, v111, v112, v113, v114, 0, v106, v107, v108, v95, v96, 1, 3, 4) :|: 0 = 0 18.83/6.18 f_364(v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v109, v110, v111, v112, v113, v114, 0, v106, v107, v108, v95, v96, 1, 3, 4) -> f_367(v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v109, v110, v111, v112, v113, v114, 0, v106, v107, v108, v95, v96, 3, 1, 4) :|: TRUE 18.83/6.18 f_367(v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, v109, v110, v111, v112, v113, v114, 0, v106, v107, v108, v95, v96, 3, 1, 4) -> f_328(v117, v136, v97, v98, v99, v100, v101, v102, v103, v104, 0, v106, v107, v108, 3, 1, 4) :|: TRUE 18.83/6.18 f_328(v95, v96, v97, v98, v99, v100, v101, v102, v103, v104, 0, v106, v107, v108, 3, 1, 4) -> f_329(v95, v96, v109, v97, v98, v99, v100, v101, v102, v103, v104, v110, 0, v106, v107, v108, 3, 1, 4) :|: 1 <= v109 && v110 = 3 + v109 && 4 <= v110 18.83/6.18 Combined rules. Obtained 1 rulesP rules: 18.83/6.18 f_329(1 + v117:0, 1 + v136:0, v109:0, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, v103:0, v104:0, v110:0, 0, v106:0, v107:0, v108:0, 3, 1, 4) -> f_329(v117:0, v136:0, v109:1, v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, v103:0, v104:0, 3 + v109:1, 0, v106:0, v107:0, v108:0, 3, 1, 4) :|: v113:0 > 0 && v111:0 > 0 && v106:0 > 0 && v117:0 > -1 && v107:0 > 0 && v136:0 > -1 && v109:1 > 0 18.83/6.18 Filtered unneeded arguments: 18.83/6.18 f_329(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) -> f_329(x1, x2, x14, x15) 18.83/6.18 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 18.83/6.18 f_329(sum~cons_1~v117:0, sum~cons_1~v136:0, v106:0, v107:0) -> f_329(v117:0, v136:0, v106:0, v107:0) :|: v117:0 > -1 && v106:0 > 0 && v136:0 > -1 && v107:0 > 0 && sum~cons_1~v117:0 = 1 + v117:0 && sum~cons_1~v136:0 = 1 + v136:0 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (8) 18.83/6.18 Obligation: 18.83/6.18 Rules: 18.83/6.18 f_329(sum~cons_1~v117:0, sum~cons_1~v136:0, v106:0, v107:0) -> f_329(v117:0, v136:0, v106:0, v107:0) :|: v117:0 > -1 && v106:0 > 0 && v136:0 > -1 && v107:0 > 0 && sum~cons_1~v117:0 = 1 + v117:0 && sum~cons_1~v136:0 = 1 + v136:0 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (9) IRS2T2 (EQUIVALENT) 18.83/6.18 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 18.83/6.18 18.83/6.18 (f_329_4,1) 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (10) 18.83/6.18 Obligation: 18.83/6.18 START: 0; 18.83/6.18 18.83/6.18 FROM: 0; 18.83/6.18 TO: 1; 18.83/6.18 18.83/6.18 FROM: 1; 18.83/6.18 oldX0 := x0; 18.83/6.18 oldX1 := x1; 18.83/6.18 oldX2 := x2; 18.83/6.18 oldX3 := x3; 18.83/6.18 oldX4 := oldX0 - 1; 18.83/6.18 oldX5 := oldX1 - 1; 18.83/6.18 assume(oldX4 > -1 && oldX2 > 0 && oldX5 > -1 && oldX3 > 0 && oldX0 = 1 + oldX4 && oldX1 = 1 + oldX5); 18.83/6.18 x0 := oldX0 - 1; 18.83/6.18 x1 := oldX1 - 1; 18.83/6.18 x2 := oldX2; 18.83/6.18 x3 := oldX3; 18.83/6.18 TO: 1; 18.83/6.18 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (11) T2 (EQUIVALENT) 18.83/6.18 Initially, performed program simplifications using lexicographic rank functions: 18.83/6.18 * Removed transitions 1, 3, 4 using the following rank functions: 18.83/6.18 - Rank function 1: 18.83/6.18 RF for loc. 5: 1+x0+x1 18.83/6.18 RF for loc. 6: x0+x1 18.83/6.18 Bound for (chained) transitions 3: 2 18.83/6.18 Bound for (chained) transitions 4: 2 18.83/6.18 - Rank function 2: 18.83/6.18 RF for loc. 5: 0 18.83/6.18 RF for loc. 6: -1 18.83/6.18 Bound for (chained) transitions 1: 0 18.83/6.18 18.83/6.18 ---------------------------------------- 18.83/6.18 18.83/6.18 (12) 18.83/6.18 YES 18.91/6.54 EOF