23.35/7.94 YES 23.35/7.95 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 23.35/7.95 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 23.35/7.95 23.35/7.95 23.35/7.95 Termination of the given C Problem could be proven: 23.35/7.95 23.35/7.95 (0) C Problem 23.35/7.95 (1) CToLLVMProof [EQUIVALENT, 174 ms] 23.35/7.95 (2) LLVM problem 23.35/7.95 (3) LLVMToTerminationGraphProof [EQUIVALENT, 4600 ms] 23.35/7.95 (4) LLVM Symbolic Execution Graph 23.35/7.95 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 23.35/7.95 (6) LLVM Symbolic Execution SCC 23.35/7.95 (7) SCC2IRS [SOUND, 125 ms] 23.35/7.95 (8) IntTRS 23.35/7.95 (9) RankingReductionPairProof [EQUIVALENT, 19 ms] 23.35/7.95 (10) YES 23.35/7.95 23.35/7.95 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (0) 23.35/7.95 Obligation: 23.35/7.95 c file /export/starexec/sandbox/benchmark/theBenchmark.c 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (1) CToLLVMProof (EQUIVALENT) 23.35/7.95 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (2) 23.35/7.95 Obligation: 23.35/7.95 LLVM Problem 23.35/7.95 23.35/7.95 Aliases: 23.35/7.95 23.35/7.95 Data layout: 23.35/7.95 23.35/7.95 "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" 23.35/7.95 23.35/7.95 Machine: 23.35/7.95 23.35/7.95 "x86_64-pc-linux-gnu" 23.35/7.95 23.35/7.95 Type definitions: 23.35/7.95 23.35/7.95 Global variables: 23.35/7.95 23.35/7.95 Function declarations and definitions: 23.35/7.95 23.35/7.95 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.35/7.95 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.35/7.95 0: 23.35/7.95 %1 = alloca i32, align 4 23.35/7.95 %2 = alloca i32, align 4 23.35/7.95 %x_ref = alloca *i32, align 8 23.35/7.95 %y_ref = alloca *i32, align 8 23.35/7.95 %c = alloca *i32, align 8 23.35/7.95 store %x, %1 23.35/7.95 store %y, %2 23.35/7.95 %3 = alloca i8, numElementsLit: 4 23.35/7.95 %4 = bitcast *i8 %3 to *i32 23.35/7.95 store %4, %x_ref 23.35/7.95 %5 = alloca i8, numElementsLit: 4 23.35/7.95 %6 = bitcast *i8 %5 to *i32 23.35/7.95 store %6, %y_ref 23.35/7.95 %7 = alloca i8, numElementsLit: 4 23.35/7.95 %8 = bitcast *i8 %7 to *i32 23.35/7.95 store %8, %c 23.35/7.95 %9 = load %1 23.35/7.95 %10 = load %x_ref 23.35/7.95 store %9, %10 23.35/7.95 %11 = load %2 23.35/7.95 %12 = load %y_ref 23.35/7.95 store %11, %12 23.35/7.95 %13 = load %c 23.35/7.95 store 0, %13 23.35/7.95 br %14 23.35/7.95 14: 23.35/7.95 %15 = load %x_ref 23.35/7.95 %16 = load %15 23.35/7.95 %17 = load %y_ref 23.35/7.95 %18 = load %17 23.35/7.95 %19 = icmp sgt %16 %18 23.35/7.95 br %19, %20, %33 23.35/7.95 20: 23.35/7.95 %21 = load %x_ref 23.35/7.95 %22 = load %21 23.35/7.95 %23 = add %22 1 23.35/7.95 %24 = load %x_ref 23.35/7.95 store %23, %24 23.35/7.95 %25 = load %y_ref 23.35/7.95 %26 = load %25 23.35/7.95 %27 = add %26 2 23.35/7.95 %28 = load %y_ref 23.35/7.95 store %27, %28 23.35/7.95 %29 = load %c 23.35/7.95 %30 = load %29 23.35/7.95 %31 = add %30 1 23.35/7.95 %32 = load %c 23.35/7.95 store %31, %32 23.35/7.95 br %14 23.35/7.95 33: 23.35/7.95 %34 = load %c 23.35/7.95 %35 = load %34 23.35/7.95 ret %35 23.35/7.95 23.35/7.95 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 23.35/7.95 0: 23.35/7.95 %1 = alloca i32, align 4 23.35/7.95 store 0, %1 23.35/7.95 %2 = call i32 @__VERIFIER_nondet_int() 23.35/7.95 %3 = call i32 @__VERIFIER_nondet_int() 23.35/7.95 %4 = call i32 @test_fun(i32 %2, i32 %3) 23.35/7.95 ret %4 23.35/7.95 23.35/7.95 23.35/7.95 Analyze Termination of all function calls matching the pattern: 23.35/7.95 main() 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (3) LLVMToTerminationGraphProof (EQUIVALENT) 23.35/7.95 Constructed symbolic execution graph for LLVM program and proved memory safety. 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (4) 23.35/7.95 Obligation: 23.35/7.95 SE Graph 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (5) SymbolicExecutionGraphToSCCProof (SOUND) 23.35/7.95 Splitted symbolic execution graph to 1 SCC. 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (6) 23.35/7.95 Obligation: 23.35/7.95 SCC 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (7) SCC2IRS (SOUND) 23.35/7.95 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 23.35/7.95 Generated rules. Obtained 24 rulesP rules: 23.35/7.95 f_412(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v216, v217, 1, v219, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_413(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v217, 1, v216, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_413(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v217, 1, v216, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_414(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v217, 1, v216, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_414(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v217, 1, v216, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_415(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_415(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_416(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: v220 < v219 23.35/7.95 f_416(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_418(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_418(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_420(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_420(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_422(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_422(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v216, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_424(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_424(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_426(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: v234 = 1 + v219 23.35/7.95 f_426(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_428(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_428(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_429(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_429(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_430(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_430(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v217, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_431(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 4, 8) :|: 0 = 0 23.35/7.95 f_431(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 4, 8) -> f_432(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: v236 = 2 + v220 23.35/7.95 f_432(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_433(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_433(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_434(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_434(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_435(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_435(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_436(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_436(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_437(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: v238 = 1 + v222 && 2 <= v238 23.35/7.95 f_437(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_438(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 f_438(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_439(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_439(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_440(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_440(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_411(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v219, v220, 1, v234, v236, v222, v238, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: TRUE 23.35/7.95 f_411(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v216, v217, 1, v219, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) -> f_412(v206, v207, v208, v209, v210, v211, v212, v213, v214, v215, v216, v217, 1, v219, v220, v221, v222, v223, v224, v225, v226, v227, v228, v229, v230, v231, v232, 0, 3, 7, 2, 4, 8) :|: 0 = 0 23.35/7.95 Combined rules. Obtained 1 rulesP rules: 23.35/7.95 f_412(v206:0, v207:0, v208:0, v209:0, v210:0, v211:0, v212:0, v213:0, v214:0, v215:0, v216:0, v217:0, 1, v219:0, v220:0, v221:0, v222:0, v223:0, v224:0, v225:0, v226:0, v227:0, v228:0, v229:0, v230:0, v231:0, v232:0, 0, 3, 7, 2, 4, 8) -> f_412(v206:0, v207:0, v208:0, v209:0, v210:0, v211:0, v212:0, v213:0, v214:0, v215:0, v219:0, v220:0, 1, 1 + v219:0, 2 + v220:0, v222:0, 1 + v222:0, v223:0, v224:0, v225:0, v226:0, v227:0, v228:0, v229:0, v230:0, v231:0, v232:0, 0, 3, 7, 2, 4, 8) :|: v222:0 > 0 && v220:0 < v219:0 23.35/7.95 Filtered unneeded arguments: 23.35/7.95 f_412(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, x29, x30, x31, x32, x33) -> f_412(x14, x15, x17) 23.35/7.95 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 23.35/7.95 f_412(v219:0, v220:0, v222:0) -> f_412(1 + v219:0, 2 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < v219:0 23.35/7.95 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (8) 23.35/7.95 Obligation: 23.35/7.95 Rules: 23.35/7.95 f_412(v219:0, v220:0, v222:0) -> f_412(1 + v219:0, 2 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < v219:0 23.35/7.95 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (9) RankingReductionPairProof (EQUIVALENT) 23.35/7.95 Interpretation: 23.35/7.95 [ f_412 ] = -1*f_412_2 + f_412_1 23.35/7.95 23.35/7.95 The following rules are decreasing: 23.35/7.95 f_412(v219:0, v220:0, v222:0) -> f_412(1 + v219:0, 2 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < v219:0 23.35/7.95 23.35/7.95 The following rules are bounded: 23.35/7.95 f_412(v219:0, v220:0, v222:0) -> f_412(1 + v219:0, 2 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < v219:0 23.35/7.95 23.35/7.95 23.35/7.95 ---------------------------------------- 23.35/7.95 23.35/7.95 (10) 23.35/7.95 YES 23.84/8.14 EOF