87.97/50.07 YES 87.97/50.08 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 87.97/50.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 87.97/50.08 87.97/50.08 87.97/50.08 Termination of the given C Problem could be proven: 87.97/50.08 87.97/50.08 (0) C Problem 87.97/50.08 (1) CToLLVMProof [EQUIVALENT, 165 ms] 87.97/50.08 (2) LLVM problem 87.97/50.08 (3) LLVMToTerminationGraphProof [EQUIVALENT, 47.2 s] 87.97/50.08 (4) LLVM Symbolic Execution Graph 87.97/50.08 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 87.97/50.08 (6) LLVM Symbolic Execution SCC 87.97/50.08 (7) SCC2IRS [SOUND, 122 ms] 87.97/50.08 (8) IntTRS 87.97/50.08 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 87.97/50.08 (10) IntTRS 87.97/50.08 (11) PolynomialOrderProcessor [EQUIVALENT, 13 ms] 87.97/50.08 (12) YES 87.97/50.08 87.97/50.08 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (0) 87.97/50.08 Obligation: 87.97/50.08 c file /export/starexec/sandbox/benchmark/theBenchmark.c 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (1) CToLLVMProof (EQUIVALENT) 87.97/50.08 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (2) 87.97/50.08 Obligation: 87.97/50.08 LLVM Problem 87.97/50.08 87.97/50.08 Aliases: 87.97/50.08 87.97/50.08 Data layout: 87.97/50.08 87.97/50.08 "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" 87.97/50.08 87.97/50.08 Machine: 87.97/50.08 87.97/50.08 "x86_64-pc-linux-gnu" 87.97/50.08 87.97/50.08 Type definitions: 87.97/50.08 87.97/50.08 Global variables: 87.97/50.08 87.97/50.08 Function declarations and definitions: 87.97/50.08 87.97/50.08 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 87.97/50.08 *BasicFunctionTypename: "iterate" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (bound i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 87.97/50.08 0: 87.97/50.08 %1 = alloca i32, align 4 87.97/50.08 %bound_ref = alloca *i32, align 8 87.97/50.08 %i = alloca *i32, align 8 87.97/50.08 %sum = alloca *i32, align 8 87.97/50.08 store %bound, %1 87.97/50.08 %2 = alloca i8, numElementsLit: 4 87.97/50.08 %3 = bitcast *i8 %2 to *i32 87.97/50.08 store %3, %bound_ref 87.97/50.08 %4 = alloca i8, numElementsLit: 4 87.97/50.08 %5 = bitcast *i8 %4 to *i32 87.97/50.08 store %5, %i 87.97/50.08 %6 = alloca i8, numElementsLit: 4 87.97/50.08 %7 = bitcast *i8 %6 to *i32 87.97/50.08 store %7, %sum 87.97/50.08 %8 = load %1 87.97/50.08 %9 = load %bound_ref 87.97/50.08 store %8, %9 87.97/50.08 %10 = load %sum 87.97/50.08 store 0, %10 87.97/50.08 %11 = load %i 87.97/50.08 store 0, %11 87.97/50.08 br %12 87.97/50.08 12: 87.97/50.08 %13 = load %i 87.97/50.08 %14 = load %13 87.97/50.08 %15 = load %bound_ref 87.97/50.08 %16 = load %15 87.97/50.08 %17 = icmp slt %14 %16 87.97/50.08 br %17, %18, %28 87.97/50.08 18: 87.97/50.08 %19 = load %i 87.97/50.08 %20 = load %19 87.97/50.08 %21 = load %sum 87.97/50.08 %22 = load %21 87.97/50.08 %23 = add %22 %20 87.97/50.08 store %23, %21 87.97/50.08 br %24 87.97/50.08 24: 87.97/50.08 %25 = load %i 87.97/50.08 %26 = load %25 87.97/50.08 %27 = add %26 1 87.97/50.08 store %27, %25 87.97/50.08 br %12 87.97/50.08 28: 87.97/50.08 %29 = load %sum 87.97/50.08 %30 = load %29 87.97/50.08 ret %30 87.97/50.08 87.97/50.08 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 87.97/50.08 0: 87.97/50.08 %1 = alloca i32, align 4 87.97/50.08 store 0, %1 87.97/50.08 %2 = call i32 @__VERIFIER_nondet_int() 87.97/50.08 %3 = call i32 @iterate(i32 %2) 87.97/50.08 ret %3 87.97/50.08 87.97/50.08 87.97/50.08 Analyze Termination of all function calls matching the pattern: 87.97/50.08 main() 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (3) LLVMToTerminationGraphProof (EQUIVALENT) 87.97/50.08 Constructed symbolic execution graph for LLVM program and proved memory safety. 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (4) 87.97/50.08 Obligation: 87.97/50.08 SE Graph 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (5) SymbolicExecutionGraphToSCCProof (SOUND) 87.97/50.08 Splitted symbolic execution graph to 1 SCC. 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (6) 87.97/50.08 Obligation: 87.97/50.08 SCC 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (7) SCC2IRS (SOUND) 87.97/50.08 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 87.97/50.08 Generated rules. Obtained 20 rulesP rules: 87.97/50.08 f_356(v156, v157, v158, v159, v160, v161, v162, v163, v164, 1, v166, v167, v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) -> f_357(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) :|: 0 = 0 87.97/50.08 f_357(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) -> f_358(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) :|: 0 = 0 87.97/50.08 f_358(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) -> f_359(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) :|: 0 = 0 87.97/50.08 f_359(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) -> f_360(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: v168 < v156 && 2 <= v156 87.97/50.08 f_360(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_362(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_362(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_364(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: TRUE 87.97/50.08 f_364(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_366(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_366(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v164, v166, v167, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_368(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v166, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_368(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v166, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_370(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v166, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_370(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v166, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_372(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_372(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_373(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: v179 = v167 + v168 && 1 <= v179 87.97/50.08 f_373(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_374(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: TRUE 87.97/50.08 f_374(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_375(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: TRUE 87.97/50.08 f_375(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_376(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_376(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v164, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_377(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: 0 = 0 87.97/50.08 f_377(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_378(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: v181 = 1 + v168 && 2 <= v181 87.97/50.08 f_378(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_379(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: TRUE 87.97/50.08 f_379(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_380(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) :|: TRUE 87.97/50.08 f_380(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 2, 4, 8) -> f_355(v156, v157, v158, v159, v160, v161, v162, v163, v168, 1, v167, v179, v181, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) :|: TRUE 87.97/50.08 f_355(v156, v157, v158, v159, v160, v161, v162, v163, v164, 1, v166, v167, v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) -> f_356(v156, v157, v158, v159, v160, v161, v162, v163, v164, 1, v166, v167, v168, v169, v170, v171, v172, v173, v174, v175, v176, v177, 0, 3, 7, 4, 8) :|: 0 = 0 87.97/50.08 Combined rules. Obtained 1 rulesP rules: 87.97/50.08 f_356(v156:0, v157:0, v158:0, v159:0, v160:0, v161:0, v162:0, v163:0, v164:0, 1, v166:0, v167:0, v168:0, v169:0, v170:0, v171:0, v172:0, v173:0, v174:0, v175:0, v176:0, v177:0, 0, 3, 7, 4, 8) -> f_356(v156:0, v157:0, v158:0, v159:0, v160:0, v161:0, v162:0, v163:0, v168:0, 1, v167:0, v167:0 + v168:0, 1 + v168:0, v169:0, v170:0, v171:0, v172:0, v173:0, v174:0, v175:0, v176:0, v177:0, 0, 3, 7, 4, 8) :|: v156:0 > 1 && v168:0 < v156:0 && v168:0 > 0 && v167:0 + v168:0 > 0 87.97/50.08 Filtered unneeded arguments: 87.97/50.08 f_356(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) -> f_356(x1, x12, x13) 87.97/50.08 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 87.97/50.08 f_356(v156:0, v167:0, v168:0) -> f_356(v156:0, v167:0 + v168:0, 1 + v168:0) :|: v168:0 < v156:0 && v156:0 > 1 && v167:0 + v168:0 > 0 && v168:0 > 0 87.97/50.08 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (8) 87.97/50.08 Obligation: 87.97/50.08 Rules: 87.97/50.08 f_356(v156:0, v167:0, v168:0) -> f_356(v156:0, v167:0 + v168:0, 1 + v168:0) :|: v168:0 < v156:0 && v156:0 > 1 && v167:0 + v168:0 > 0 && v168:0 > 0 87.97/50.08 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (9) IntTRSCompressionProof (EQUIVALENT) 87.97/50.08 Compressed rules. 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (10) 87.97/50.08 Obligation: 87.97/50.08 Rules: 87.97/50.08 f_356(v156:0:0, v167:0:0, v168:0:0) -> f_356(v156:0:0, v167:0:0 + v168:0:0, 1 + v168:0:0) :|: v167:0:0 + v168:0:0 > 0 && v168:0:0 > 0 && v156:0:0 > 1 && v168:0:0 < v156:0:0 87.97/50.08 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (11) PolynomialOrderProcessor (EQUIVALENT) 87.97/50.08 Found the following polynomial interpretation: 87.97/50.08 [f_356(x, x1, x2)] = x - x2 87.97/50.08 87.97/50.08 The following rules are decreasing: 87.97/50.08 f_356(v156:0:0, v167:0:0, v168:0:0) -> f_356(v156:0:0, v167:0:0 + v168:0:0, 1 + v168:0:0) :|: v167:0:0 + v168:0:0 > 0 && v168:0:0 > 0 && v156:0:0 > 1 && v168:0:0 < v156:0:0 87.97/50.08 The following rules are bounded: 87.97/50.08 f_356(v156:0:0, v167:0:0, v168:0:0) -> f_356(v156:0:0, v167:0:0 + v168:0:0, 1 + v168:0:0) :|: v167:0:0 + v168:0:0 > 0 && v168:0:0 > 0 && v156:0:0 > 1 && v168:0:0 < v156:0:0 87.97/50.08 87.97/50.08 ---------------------------------------- 87.97/50.08 87.97/50.08 (12) 87.97/50.08 YES 87.97/50.12 EOF