19.13/6.17 YES 19.13/6.17 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 19.13/6.17 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.13/6.17 19.13/6.17 19.13/6.17 Termination of the given C Problem could be proven: 19.13/6.17 19.13/6.17 (0) C Problem 19.13/6.17 (1) CToLLVMProof [EQUIVALENT, 174 ms] 19.13/6.17 (2) LLVM problem 19.13/6.17 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1899 ms] 19.13/6.17 (4) LLVM Symbolic Execution Graph 19.13/6.17 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 19.13/6.17 (6) LLVM Symbolic Execution SCC 19.13/6.17 (7) SCC2IRS [SOUND, 51 ms] 19.13/6.17 (8) IntTRS 19.13/6.17 (9) IRS2T2 [EQUIVALENT, 0 ms] 19.13/6.17 (10) T2IntSys 19.13/6.17 (11) T2 [EQUIVALENT, 1331 ms] 19.13/6.17 (12) YES 19.13/6.17 19.13/6.17 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (0) 19.13/6.17 Obligation: 19.13/6.17 c file /export/starexec/sandbox/benchmark/theBenchmark.c 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (1) CToLLVMProof (EQUIVALENT) 19.13/6.17 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (2) 19.13/6.17 Obligation: 19.13/6.17 LLVM Problem 19.13/6.17 19.13/6.17 Aliases: 19.13/6.17 19.13/6.17 Data layout: 19.13/6.17 19.13/6.17 "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" 19.13/6.17 19.13/6.17 Machine: 19.13/6.17 19.13/6.17 "x86_64-pc-linux-gnu" 19.13/6.17 19.13/6.17 Type definitions: 19.13/6.17 19.13/6.17 Global variables: 19.13/6.17 19.13/6.17 Function declarations and definitions: 19.13/6.17 19.13/6.17 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 19.13/6.17 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 19.13/6.17 0: 19.13/6.17 %1 = alloca i32, align 4 19.13/6.17 %x = alloca i32, align 4 19.13/6.17 %y = alloca i32, align 4 19.13/6.17 %z = alloca i32, align 4 19.13/6.17 store 0, %1 19.13/6.17 %2 = call i32 (...)* @__VERIFIER_nondet_int() 19.13/6.17 store %2, %x 19.13/6.17 %3 = call i32 (...)* @__VERIFIER_nondet_int() 19.13/6.17 store %3, %y 19.13/6.17 %4 = call i32 (...)* @__VERIFIER_nondet_int() 19.13/6.17 store %4, %z 19.13/6.17 br %5 19.13/6.17 5: 19.13/6.17 %6 = load %x 19.13/6.17 %7 = icmp sge %6 0 19.13/6.17 br %7, %8, %12 19.13/6.17 8: 19.13/6.17 %9 = load %x 19.13/6.17 %10 = load %z 19.13/6.17 %11 = icmp sle %9 %10 19.13/6.17 br %12 19.13/6.17 12: 19.13/6.17 %13 = phi [0, %5], [%11, %8] 19.13/6.17 br %13, %14, %21 19.13/6.17 14: 19.13/6.17 %15 = load %x 19.13/6.17 %16 = mul 2 %15 19.13/6.17 %17 = load %y 19.13/6.17 %18 = add %16 %17 19.13/6.17 store %18, %x 19.13/6.17 %19 = load %y 19.13/6.17 %20 = add %19 1 19.13/6.17 store %20, %y 19.13/6.17 br %5 19.13/6.17 21: 19.13/6.17 ret 0 19.13/6.17 19.13/6.17 19.13/6.17 Analyze Termination of all function calls matching the pattern: 19.13/6.17 main() 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (3) LLVMToTerminationGraphProof (EQUIVALENT) 19.13/6.17 Constructed symbolic execution graph for LLVM program and proved memory safety. 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (4) 19.13/6.17 Obligation: 19.13/6.17 SE Graph 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (5) SymbolicExecutionGraphToSCCProof (SOUND) 19.13/6.17 Splitted symbolic execution graph to 1 SCC. 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (6) 19.13/6.17 Obligation: 19.13/6.17 SCC 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (7) SCC2IRS (SOUND) 19.13/6.17 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 19.13/6.17 Generated rules. Obtained 20 rulesP rules: 19.13/6.17 f_192(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_193(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 <= v248 19.13/6.17 f_193(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_195(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_195(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_197(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_197(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_199(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_199(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_201(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_201(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_202(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: v248 <= v243 19.13/6.17 f_202(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_204(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_204(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_206(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_206(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_208(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_208(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_210(v237, v238, v239, v240, v241, v242, v243, v248, 1, v246, v247, v249, v250, v251, v252, v253, 0, 3, 4) :|: 0 = 0 19.13/6.17 f_210(v237, v238, v239, v240, v241, v242, v243, v248, 1, v246, v247, v249, v250, v251, v252, v253, 0, 3, 4) -> f_211(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: v340 = 2 * v248 && 0 <= v340 19.13/6.17 f_211(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_212(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v247, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_212(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v247, v250, v251, v252, v253, 0, 3, 2, 4) -> f_213(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v247, v250, v251, v252, v253, 0, 3, 2, 4) :|: v341 = v340 + v249 19.13/6.17 f_213(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v247, v250, v251, v252, v253, 0, 3, 2, 4) -> f_214(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v247, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_214(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v247, v250, v251, v252, v253, 0, 3, 2, 4) -> f_215(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 f_215(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v250, v251, v252, v253, 0, 3, 2, 4) -> f_216(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) :|: v343 = 1 + v249 19.13/6.17 f_216(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) -> f_217(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_217(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) -> f_218(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_218(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) -> f_191(v237, v238, v239, v240, v241, v242, v243, v248, 1, v340, v249, v341, v343, v250, v251, v252, v253, 0, 3, 2, 4) :|: TRUE 19.13/6.17 f_191(v237, v238, v239, v240, v241, v242, v243, v244, 1, v246, v247, v248, v249, v250, v251, v252, v253, 0, 3, 2, 4) -> f_192(v237, v238, v239, v240, v241, v242, v243, v248, 1, v244, v246, v247, v249, v250, v251, v252, v253, 0, 3, 2, 4) :|: 0 = 0 19.13/6.17 Combined rules. Obtained 1 rulesP rules: 19.13/6.17 f_192(v237:0, v238:0, v239:0, v240:0, v241:0, v242:0, v243:0, v248:0, 1, v244:0, v246:0, v247:0, v249:0, v250:0, v251:0, v252:0, v253:0, 0, 3, 2, 4) -> f_192(v237:0, v238:0, v239:0, v240:0, v241:0, v242:0, v243:0, 2 * v248:0 + v249:0, 1, v248:0, 2 * v248:0, v249:0, 1 + v249:0, v250:0, v251:0, v252:0, v253:0, 0, 3, 2, 4) :|: v248:0 > -1 && 2 * v248:0 > -1 && v248:0 <= v243:0 19.13/6.17 Filtered unneeded arguments: 19.13/6.17 f_192(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) -> f_192(x7, x8, x13) 19.13/6.17 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 19.13/6.17 f_192(v243:0, v248:0, v249:0) -> f_192(v243:0, 2 * v248:0 + v249:0, 1 + v249:0) :|: 2 * v248:0 > -1 && v248:0 <= v243:0 && v248:0 > -1 19.13/6.17 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (8) 19.13/6.17 Obligation: 19.13/6.17 Rules: 19.13/6.17 f_192(v243:0, v248:0, v249:0) -> f_192(v243:0, 2 * v248:0 + v249:0, 1 + v249:0) :|: 2 * v248:0 > -1 && v248:0 <= v243:0 && v248:0 > -1 19.13/6.17 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (9) IRS2T2 (EQUIVALENT) 19.13/6.17 Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: 19.13/6.17 19.13/6.17 (f_192_3,1) 19.13/6.17 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (10) 19.13/6.17 Obligation: 19.13/6.17 START: 0; 19.13/6.17 19.13/6.17 FROM: 0; 19.13/6.17 TO: 1; 19.13/6.17 19.13/6.17 FROM: 1; 19.13/6.17 oldX0 := x0; 19.13/6.17 oldX1 := x1; 19.13/6.17 oldX2 := x2; 19.13/6.17 assume(2 * oldX1 > -1 && oldX1 <= oldX0 && oldX1 > -1); 19.13/6.17 x0 := oldX0; 19.13/6.17 x1 := 2 * oldX1 + oldX2; 19.13/6.17 x2 := 1 + oldX2; 19.13/6.17 TO: 1; 19.13/6.17 19.13/6.17 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (11) T2 (EQUIVALENT) 19.13/6.17 No proof given by T2 19.13/6.17 ---------------------------------------- 19.13/6.17 19.13/6.17 (12) 19.13/6.17 YES 19.22/6.22 EOF