/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.c
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given C Problem could be proven:

(0) C Problem
(1) CToLLVMProof [EQUIVALENT, 179 ms]
(2) LLVM problem
(3) LLVMToTerminationGraphProof [EQUIVALENT, 1986 ms]
(4) LLVM Symbolic Execution Graph
(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
(6) LLVM Symbolic Execution SCC
(7) SCC2IRS [SOUND, 84 ms]
(8) IntTRS
(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(10) IntTRS
(11) PolynomialOrderProcessor [EQUIVALENT, 14 ms]
(12) YES


----------------------------------------

(0)
Obligation:
c file /export/starexec/sandbox/benchmark/theBenchmark.c
----------------------------------------

(1) CToLLVMProof (EQUIVALENT)
Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
----------------------------------------

(2)
Obligation:
LLVM Problem

Aliases:

Data layout:

"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"

Machine:

"x86_64-pc-linux-gnu"

Type definitions:

Global variables:

Function declarations and definitions:

*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "malloc" returnParam: *i8 parameters: (i64) variableLength: false visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "__VERIFIER_nondet_String" linkageType: EXTERNALLY_VISIBLE returnParam: *i8 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%length = alloca i32, align 4
		%nondetString = alloca *i8, align 8
		%1 = call i32 @__VERIFIER_nondet_int()
		store %1, %length
		%2 = load %length
		%3 = icmp slt %2 1
		br %3, %4, %5
	4:
		store 1, %length
		br %5
	5:
		%6 = load %length
		%7 = sext i32 %6 to i64
		%8 = mul %7 1
		%9 = call *i8 @malloc(i64 %8)
		store %9, %nondetString
		%10 = load %length
		%11 = sub %10 1
		%12 = sext i32 %11 to i64
		%13 = load %nondetString
		%14 = getelementptr %13, %12
		store 0, %14
		%15 = load %nondetString
		ret %15

*BasicFunctionTypename: "cstrcmp" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (s1 *i8, s2 *i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca *i8, align 8
		%2 = alloca *i8, align 8
		%uc1 = alloca i8, align 1
		%uc2 = alloca i8, align 1
		store %s1, %1
		store %s2, %2
		br %3
	3:
		%4 = load %1
		%5 = load %4
		%6 = sext i8 %5 to i32
		%7 = icmp ne %6 0
		br %7, %8, %16
	8:
		%9 = load %1
		%10 = load %9
		%11 = sext i8 %10 to i32
		%12 = load %2
		%13 = load %12
		%14 = sext i8 %13 to i32
		%15 = icmp eq %11 %14
		br %16
	16:
		%17 = phi [0, %3], [%15, %8]
		br %17, %18, %23
	18:
		%19 = load %1
		%20 = getelementptr %19, 1
		store %20, %1
		%21 = load %2
		%22 = getelementptr %21, 1
		store %22, %2
		br %3
	23:
		%24 = load %1
		%25 = load %24
		store %25, %uc1
		%26 = load %2
		%27 = load %26
		store %27, %uc2
		%28 = load %uc1
		%29 = zext i8 %28 to i32
		%30 = load %uc2
		%31 = zext i8 %30 to i32
		%32 = icmp slt %29 %31
		br %32, %33, %34
	33:
		br %41
	34:
		%35 = load %uc1
		%36 = zext i8 %35 to i32
		%37 = load %uc2
		%38 = zext i8 %37 to i32
		%39 = icmp sgt %36 %38
		%40 = zext i1 %39 to i32
		br %41
	41:
		%42 = phi [-1, %33], [%40, %34]
		ret %42

*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		store 0, %1
		%2 = call *i8 @__VERIFIER_nondet_String()
		%3 = call *i8 @__VERIFIER_nondet_String()
		%4 = call i32 @cstrcmp(*i8 %2, *i8 %3)
		ret %4


Analyze Termination of all function calls matching the pattern:
main()
----------------------------------------

(3) LLVMToTerminationGraphProof (EQUIVALENT)
Constructed symbolic execution graph for LLVM program and proved memory safety.
----------------------------------------

(4)
Obligation:
SE Graph
----------------------------------------

(5) SymbolicExecutionGraphToSCCProof (SOUND)
Splitted symbolic execution graph to 1 SCC.
----------------------------------------

(6)
Obligation:
SCC
----------------------------------------

(7) SCC2IRS (SOUND)
Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
Generated rules. Obtained 24 rulesP rules:
f_467(v466, v467, v468, v469, v470, v471, v476, v473, 1, v472, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_468(v466, v467, v468, v469, v470, v471, v476, v486, v473, 1, v472, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: TRUE
f_468(v466, v467, v468, v469, v470, v471, v476, v486, v473, 1, v472, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_469(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_469(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_470(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: v486 != 0 && v476 < v480 && 3 <= v480
f_470(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_472(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_472(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_474(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: TRUE
f_474(v466, v467, v468, v469, v470, v471, v476, v486, 1, v472, v473, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_476(v466, v467, v468, v469, v470, v471, v476, v486, 1, v473, v475, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_476(v466, v467, v468, v469, v470, v471, v476, v486, 1, v473, v475, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_478(v466, v467, v468, v469, v470, v471, v476, v486, 1, v473, v475, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_478(v466, v467, v468, v469, v470, v471, v476, v486, 1, v473, v475, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_480(v466, v467, v468, v469, v470, v471, v476, v486, 1, v475, v473, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_480(v466, v467, v468, v469, v470, v471, v476, v486, 1, v475, v473, v472, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_482(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v473, v472, v475, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_482(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v473, v472, v475, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_484(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v509, v473, v472, v475, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: TRUE
f_484(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v509, v473, v472, v475, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_486(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v509, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_486(v466, v467, v468, v469, v470, v471, v476, v486, 1, v477, v509, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) -> f_488(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) :|: v486 = v509 && v477 < v481 && 3 <= v481
f_488(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) -> f_491(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_491(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) -> f_494(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_494(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) -> f_497(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) :|: TRUE
f_497(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v472, v475, v478, v479, v480, v481, v482, v483, v484, v473, 0, 3, 7, 2, 4, 8) -> f_500(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_500(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) -> f_503(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) :|: v581 = 1 + v476 && 3 <= v581
f_503(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) -> f_507(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) :|: TRUE
f_507(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v475, v478, v479, v480, v481, v482, v483, v484, v472, v473, 0, 3, 7, 2, 4, 8) -> f_511(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) :|: 0 = 0
f_511(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) -> f_515(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) :|: v598 = 1 + v477 && 3 <= v598
f_515(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) -> f_519(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) :|: TRUE
f_519(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) -> f_523(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) :|: TRUE
f_523(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, v472, v473, v475, 0, 3, 7, 2, 4, 8) -> f_466(v466, v467, v468, v469, v470, v471, v476, v509, 1, v477, v581, v598, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: TRUE
f_466(v466, v467, v468, v469, v470, v471, v472, v473, 1, v475, v476, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) -> f_467(v466, v467, v468, v469, v470, v471, v476, v473, 1, v472, v475, v477, v478, v479, v480, v481, v482, v483, v484, 0, 3, 7, 2, 4, 8) :|: 0 = 0
Combined rules. Obtained 2 rulesP rules:
f_467(v466:0, v467:0, v468:0, v469:0, v470:0, v471:0, v476:0, v473:0, 1, v472:0, v475:0, v477:0, v478:0, v479:0, v480:0, v481:0, v482:0, v483:0, v484:0, 0, 3, 7, 2, 4, 8) -> f_467(v466:0, v467:0, v468:0, v469:0, v470:0, v471:0, 1 + v476:0, v486:0, 1, v476:0, v477:0, 1 + v477:0, v478:0, v479:0, v480:0, v481:0, v482:0, v483:0, v484:0, 0, 3, 7, 2, 4, 8) :|: v480:0 > v476:0 && v486:0 < 0 && v480:0 > 2 && v481:0 > v477:0 && v481:0 > 2 && v477:0 > 1 && v476:0 > 1
f_467(v466:0, v467:0, v468:0, v469:0, v470:0, v471:0, v476:0, v473:0, 1, v472:0, v475:0, v477:0, v478:0, v479:0, v480:0, v481:0, v482:0, v483:0, v484:0, 0, 3, 7, 2, 4, 8) -> f_467(v466:0, v467:0, v468:0, v469:0, v470:0, v471:0, 1 + v476:0, v486:0, 1, v476:0, v477:0, 1 + v477:0, v478:0, v479:0, v480:0, v481:0, v482:0, v483:0, v484:0, 0, 3, 7, 2, 4, 8) :|: v480:0 > v476:0 && v486:0 > 0 && v480:0 > 2 && v481:0 > v477:0 && v481:0 > 2 && v477:0 > 1 && v476:0 > 1
Filtered unneeded arguments:
   f_467(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) -> f_467(x7, x12, x15, x16)
Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
f_467(v476:0, v477:0, v480:0, v481:0) -> f_467(1 + v476:0, 1 + v477:0, v480:0, v481:0) :|: v480:0 > 2 && v480:0 > v476:0 && v481:0 > v477:0 && v481:0 > 2 && v476:0 > 1 && v477:0 > 1

----------------------------------------

(8)
Obligation:
Rules:
f_467(v476:0, v477:0, v480:0, v481:0) -> f_467(1 + v476:0, 1 + v477:0, v480:0, v481:0) :|: v480:0 > 2 && v480:0 > v476:0 && v481:0 > v477:0 && v481:0 > 2 && v476:0 > 1 && v477:0 > 1

----------------------------------------

(9) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(10)
Obligation:
Rules:
f_467(v476:0:0, v477:0:0, v480:0:0, v481:0:0) -> f_467(1 + v476:0:0, 1 + v477:0:0, v480:0:0, v481:0:0) :|: v476:0:0 > 1 && v477:0:0 > 1 && v481:0:0 > 2 && v481:0:0 > v477:0:0 && v480:0:0 > v476:0:0 && v480:0:0 > 2

----------------------------------------

(11) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f_467(x, x1, x2, x3)] = -1 - x1 + x3

The following rules are decreasing:
f_467(v476:0:0, v477:0:0, v480:0:0, v481:0:0) -> f_467(1 + v476:0:0, 1 + v477:0:0, v480:0:0, v481:0:0) :|: v476:0:0 > 1 && v477:0:0 > 1 && v481:0:0 > 2 && v481:0:0 > v477:0:0 && v480:0:0 > v476:0:0 && v480:0:0 > 2
The following rules are bounded:
f_467(v476:0:0, v477:0:0, v480:0:0, v481:0:0) -> f_467(1 + v476:0:0, 1 + v477:0:0, v480:0:0, v481:0:0) :|: v476:0:0 > 1 && v477:0:0 > 1 && v481:0:0 > 2 && v481:0:0 > v477:0:0 && v480:0:0 > v476:0:0 && v480:0:0 > 2

----------------------------------------

(12)
YES