24.38/7.83 YES 25.84/8.80 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 25.84/8.80 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 25.84/8.80 25.84/8.80 25.84/8.80 Termination of the given C Problem could be proven: 25.84/8.80 25.84/8.80 (0) C Problem 25.84/8.80 (1) CToLLVMProof [EQUIVALENT, 174 ms] 25.84/8.80 (2) LLVM problem 25.84/8.80 (3) LLVMToTerminationGraphProof [EQUIVALENT, 4016 ms] 25.84/8.80 (4) LLVM Symbolic Execution Graph 25.84/8.80 (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] 25.84/8.80 (6) LLVM Symbolic Execution Lasso 25.84/8.80 (7) Lasso2IRS [SOUND, 67 ms] 25.84/8.80 (8) IntTRS 25.84/8.80 (9) IRS2T2 [EQUIVALENT, 0 ms] 25.84/8.80 (10) T2IntSys 25.84/8.80 (11) T2 [EQUIVALENT, 1212 ms] 25.84/8.80 (12) YES 25.84/8.80 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (0) 25.84/8.80 Obligation: 25.84/8.80 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (1) CToLLVMProof (EQUIVALENT) 25.84/8.80 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (2) 25.84/8.80 Obligation: 25.84/8.80 LLVM Problem 25.84/8.80 25.84/8.80 Aliases: 25.84/8.80 25.84/8.80 Data layout: 25.84/8.80 25.84/8.80 "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" 25.84/8.80 25.84/8.80 Machine: 25.84/8.80 25.84/8.80 "x86_64-pc-linux-gnu" 25.84/8.80 25.84/8.80 Type definitions: 25.84/8.80 25.84/8.80 Global variables: 25.84/8.80 25.84/8.80 Function declarations and definitions: 25.84/8.80 25.84/8.80 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.84/8.80 *BasicFunctionTypename: "r1" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (ls i32, a i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.84/8.80 0: 25.84/8.80 %1 = alloca i32, align 4 25.84/8.80 %2 = alloca i32, align 4 25.84/8.80 %3 = alloca i32, align 4 25.84/8.80 store %ls, %2 25.84/8.80 store %a, %3 25.84/8.80 %4 = load %2 25.84/8.80 %5 = icmp eq %4 0 25.84/8.80 br %5, %6, %8 25.84/8.80 6: 25.84/8.80 %7 = load %3 25.84/8.80 store %7, %1 25.84/8.80 br %16 25.84/8.80 8: 25.84/8.80 %9 = load %2 25.84/8.80 %10 = sub %9 1 25.84/8.80 %11 = load %2 25.84/8.80 %12 = add %11 1 25.84/8.80 %13 = load %3 25.84/8.80 %14 = add %12 %13 25.84/8.80 %15 = call i32 @r1(i32 %10, i32 %14) 25.84/8.80 store %15, %1 25.84/8.80 br %16 25.84/8.80 16: 25.84/8.80 %17 = load %1 25.84/8.80 ret %17 25.84/8.80 25.84/8.80 *BasicFunctionTypename: "rev" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (ls i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.84/8.80 0: 25.84/8.80 %1 = alloca i32, align 4 25.84/8.80 store %ls, %1 25.84/8.80 %2 = load %1 25.84/8.80 %3 = call i32 @r1(i32 %2, i32 0) 25.84/8.80 ret %3 25.84/8.80 25.84/8.80 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 25.84/8.80 0: 25.84/8.80 %1 = alloca i32, align 4 25.84/8.80 %ls = alloca i32, align 4 25.84/8.80 store 0, %1 25.84/8.80 %2 = call i32 @__VERIFIER_nondet_int() 25.84/8.80 store %2, %ls 25.84/8.80 %3 = load %ls 25.84/8.80 %4 = icmp sge %3 0 25.84/8.80 br %4, %5, %8 25.84/8.80 5: 25.84/8.80 %6 = load %ls 25.84/8.80 %7 = call i32 @rev(i32 %6) 25.84/8.80 br %8 25.84/8.80 8: 25.84/8.80 ret 0 25.84/8.80 25.84/8.80 25.84/8.80 Analyze Termination of all function calls matching the pattern: 25.84/8.80 main() 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (3) LLVMToTerminationGraphProof (EQUIVALENT) 25.84/8.80 Constructed symbolic execution graph for LLVM program and proved memory safety. 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (4) 25.84/8.80 Obligation: 25.84/8.80 SE Graph 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) 25.84/8.80 Converted SEGraph to 1 independent lasso. 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (6) 25.84/8.80 Obligation: 25.84/8.80 Lasso 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (7) Lasso2IRS (SOUND) 25.84/8.80 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 25.84/8.80 Generated rules. Obtained 36 rulesP rules: 25.84/8.80 f_200(v67, v68, v77, v69, v70, v71, v72, v73, v74, v78, 0, v76, 3, 1, 4) -> f_201(v67, v68, v77, v79, v69, v70, v71, v72, v73, v74, v78, v80, 0, v76, 3, 1, 4) :|: 1 <= v79 && v80 = 3 + v79 && 4 <= v80 25.84/8.80 f_201(v67, v68, v77, v79, v69, v70, v71, v72, v73, v74, v78, v80, 0, v76, 3, 1, 4) -> f_202(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) :|: 1 <= v81 && v82 = 3 + v81 && 4 <= v82 25.84/8.80 f_202(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) -> f_203(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) :|: TRUE 25.84/8.80 f_203(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) -> f_204(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) :|: TRUE 25.84/8.80 f_204(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) -> f_205(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) :|: 0 = 0 25.84/8.80 f_205(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) -> f_207(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) :|: v67 != 0 && 1 <= v76 25.84/8.80 f_207(v67, v68, v77, v79, v81, v69, v70, v71, v72, v73, v74, v78, v80, v82, 0, v76, 3, 1, 4) -> f_209(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) :|: 0 = 0 25.84/8.80 f_209(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) -> f_211(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) :|: TRUE 25.84/8.80 f_211(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) -> f_213(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) :|: 0 = 0 25.84/8.80 f_213(v67, v68, v77, v79, v81, 0, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) -> f_215(v67, v68, v77, v79, v81, 0, v86, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) :|: 1 + v86 = v67 && 0 <= v86 25.84/8.80 f_215(v67, v68, v77, v79, v81, 0, v86, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) -> f_217(v67, v68, v77, v79, v81, 0, v86, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) :|: 0 = 0 25.84/8.80 f_217(v67, v68, v77, v79, v81, 0, v86, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4) -> f_219(v67, v68, v77, v79, v81, 0, v86, v87, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) :|: v87 = 1 + v67 && 2 <= v87 25.84/8.80 f_219(v67, v68, v77, v79, v81, 0, v86, v87, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) -> f_221(v67, v68, v77, v79, v81, 0, v86, v87, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) :|: 0 = 0 25.84/8.80 f_221(v67, v68, v77, v79, v81, 0, v86, v87, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) -> f_223(v67, v68, v77, v79, v81, 0, v86, v87, v102, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) :|: v102 = v87 + v68 && 2 <= v102 25.84/8.80 f_223(v67, v68, v77, v79, v81, 0, v86, v87, v102, v69, v70, v71, v72, v73, v74, v78, v80, v82, v76, 3, 1, 4, 2) -> f_225(v86, v102, v69, v70, v71, v72, v73, v74, v77, v78, v79, v80, v81, v82, 0, v76, v67, v68, v87, 3, 1, 4, 2) :|: 0 = 0 25.84/8.80 f_225(v86, v102, v69, v70, v71, v72, v73, v74, v77, v78, v79, v80, v81, v82, 0, v76, v67, v68, v87, 3, 1, 4, 2) -> f_227(v86, v102, v69, v70, v71, v72, v73, v74, v77, v78, v79, v80, v81, v82, 0, v76, v67, v68, 3, 1, 4, 2) :|: TRUE 25.84/8.80 f_227(v86, v102, v69, v70, v71, v72, v73, v74, v77, v78, v79, v80, v81, v82, 0, v76, v67, v68, 3, 1, 4, 2) -> f_199(v86, v102, v69, v70, v71, v72, v73, v74, 0, v76, 3, 1, 4) :|: TRUE 25.84/8.80 f_199(v67, v68, v69, v70, v71, v72, v73, v74, 0, v76, 3, 1, 4) -> f_200(v67, v68, v77, v69, v70, v71, v72, v73, v74, v78, 0, v76, 3, 1, 4) :|: 1 <= v77 && v78 = 3 + v77 && 4 <= v78 25.84/8.80 f_122 -> f_123(v1, v2, 3, 1, 4) :|: 1 <= v1 && v2 = 3 + v1 && 4 <= v2 25.84/8.80 f_123(v1, v2, 3, 1, 4) -> f_124(v1, v3, v2, v4, 3, 1, 4) :|: 1 <= v3 && v4 = 3 + v3 && 4 <= v4 25.84/8.80 f_124(v1, v3, v2, v4, 3, 1, 4) -> f_125(v1, v3, v2, v4, 0, 3, 1, 4) :|: TRUE 25.84/8.80 f_125(v1, v3, v2, v4, 0, 3, 1, 4) -> f_126(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 25.84/8.80 f_126(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_127(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: TRUE 25.84/8.80 f_127(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_128(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 = 0 25.84/8.80 f_128(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_129(v1, v3, v5, v2, v4, 0, 3, 1, 4) :|: 0 <= v5 25.84/8.80 f_129(v1, v3, v5, v2, v4, 0, 3, 1, 4) -> f_131(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: 0 = 0 25.84/8.80 f_131(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_133(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: TRUE 25.84/8.80 f_133(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_135(v1, v3, v5, 1, v2, v4, 0, 3, 4) :|: 0 = 0 25.84/8.80 f_135(v1, v3, v5, 1, v2, v4, 0, 3, 4) -> f_136(v5, v1, v2, v3, v4, 0, 1, 3, 4) :|: 0 = 0 25.84/8.80 f_136(v5, v1, v2, v3, v4, 0, 1, 3, 4) -> f_137(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) :|: 1 <= v7 && v8 = 3 + v7 && 4 <= v8 25.84/8.80 f_137(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) -> f_138(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) :|: TRUE 25.84/8.80 f_138(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) -> f_139(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) :|: 0 = 0 25.84/8.80 f_139(v5, v7, v1, v2, v3, v4, v8, 0, 1, 3, 4) -> f_140(v5, 0, v1, v2, v3, v4, v7, v8, 1, 3, 4) :|: 0 = 0 25.84/8.80 f_140(v5, 0, v1, v2, v3, v4, v7, v8, 1, 3, 4) -> f_141(v5, 0, v1, v2, v3, v4, v7, v8, 3, 1, 4) :|: TRUE 25.84/8.80 f_141(v5, 0, v1, v2, v3, v4, v7, v8, 3, 1, 4) -> f_170(v5, 0, v1, v2, v3, v4, v7, v8, 0, v5, 3, 1, 4) :|: TRUE 25.84/8.80 f_170(v31, v32, v33, v34, v35, v36, v37, v38, 0, v40, 3, 1, 4) -> f_199(v31, v32, v33, v34, v35, v36, v37, v38, 0, v40, 3, 1, 4) :|: TRUE 25.84/8.80 Combined rules. Obtained 2 rulesP rules: 25.84/8.80 f_200(1 + v86:0, v68:0, v77:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, v78:0, 0, v76:0, 3, 1, 4) -> f_200(v86:0, 1 + (1 + v86:0) + v68:0, v77:1, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, 3 + v77:1, 0, v76:0, 3, 1, 4) :|: v81:0 > 0 && v79:0 > 0 && v76:0 > 0 && v86:0 > -1 && 1 + (1 + v86:0) + v68:0 > 1 && v77:1 > 0 25.84/8.80 f_122 -> f_200(v5:0, 0, v77:0, v1:0, 3 + v1:0, v3:0, 3 + v3:0, v7:0, 3 + v7:0, 3 + v77:0, 0, v5:0, 3, 1, 4) :|: v3:0 > 0 && v1:0 > 0 && v5:0 > -1 && v7:0 > 0 && v77:0 > 0 25.84/8.80 Filtered unneeded arguments: 25.84/8.80 f_200(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) -> f_200(x1, x2, x12) 25.84/8.80 Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: 25.84/8.80 f_200(sum~cons_1~v86:0, v68:0, v76:0) -> f_200(v86:0, 1 + (1 + v86:0) + v68:0, v76:0) :|: v86:0 > -1 && 1 + (1 + v86:0) + v68:0 > 1 && v76:0 > 0 && sum~cons_1~v86:0 = 1 + v86:0 25.84/8.80 f_122 -> f_200(v5:0, 0, v5:0) :|: v5:0 > -1 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (8) 25.84/8.80 Obligation: 25.84/8.80 Rules: 25.84/8.80 f_200(sum~cons_1~v86:0, v68:0, v76:0) -> f_200(v86:0, 1 + (1 + v86:0) + v68:0, v76:0) :|: v86:0 > -1 && 1 + (1 + v86:0) + v68:0 > 1 && v76:0 > 0 && sum~cons_1~v86:0 = 1 + v86:0 25.84/8.80 f_122 -> f_200(v5:0, 0, v5:0) :|: v5:0 > -1 25.84/8.80 Start term: f_122 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (9) IRS2T2 (EQUIVALENT) 25.84/8.80 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 25.84/8.80 25.84/8.80 (f_200_3,1) 25.84/8.80 (f_122_3,2) 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (10) 25.84/8.80 Obligation: 25.84/8.80 START: 2; 25.84/8.80 25.84/8.80 FROM: 1; 25.84/8.80 oldX0 := x0; 25.84/8.80 oldX1 := x1; 25.84/8.80 oldX2 := x2; 25.84/8.80 oldX3 := oldX0 - 1; 25.84/8.80 assume(oldX3 > -1 && 1 + (1 + oldX3) + oldX1 > 1 && oldX2 > 0 && oldX0 = 1 + oldX3); 25.84/8.80 x0 := oldX0 - 1; 25.84/8.80 x1 := 1 + (1 + oldX3) + oldX1; 25.84/8.80 x2 := oldX2; 25.84/8.80 TO: 1; 25.84/8.80 25.84/8.80 FROM: 2; 25.84/8.80 oldX0 := x0; 25.84/8.80 oldX1 := x1; 25.84/8.80 oldX2 := x2; 25.84/8.80 oldX3 := nondet(); 25.84/8.80 assume(oldX3 > -1); 25.84/8.80 x0 := oldX3; 25.84/8.80 x1 := 0; 25.84/8.80 x2 := oldX3; 25.84/8.80 TO: 1; 25.84/8.80 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (11) T2 (EQUIVALENT) 25.84/8.80 Initially, performed program simplifications using lexicographic rank functions: 25.84/8.80 * Removed transitions 1, 3, 4 using the following rank functions: 25.84/8.80 - Rank function 1: 25.84/8.80 RF for loc. 5: 1+2*x0 25.84/8.80 RF for loc. 6: 2*x0 25.84/8.80 Bound for (chained) transitions 3: 2 25.84/8.80 Bound for (chained) transitions 4: 2 25.84/8.80 - Rank function 2: 25.84/8.80 RF for loc. 5: 0 25.84/8.80 RF for loc. 6: -1 25.84/8.80 Bound for (chained) transitions 1: 0 25.84/8.80 25.84/8.80 ---------------------------------------- 25.84/8.80 25.84/8.80 (12) 25.84/8.80 YES 25.86/10.37 EOF