/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, 178 ms]
(2) LLVM problem
(3) LLVMToTerminationGraphProof [EQUIVALENT, 6507 ms]
(4) LLVM Symbolic Execution Graph
(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
(6) LLVM Symbolic Execution SCC
(7) SCC2IRS [SOUND, 113 ms]
(8) IntTRS
(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(10) IntTRS
(11) PolynomialOrderProcessor [EQUIVALENT, 15 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: "cstrnlen" linkageType: EXTERNALLY_VISIBLE returnParam: i64 parameters: (str *i8, maxlen i64) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca *i8, align 8
		%2 = alloca i64, align 8
		%cp = alloca *i8, align 8
		store %str, %1
		store %maxlen, %2
		%3 = load %1
		store %3, %cp
		br %4
	4:
		%5 = load %2
		%6 = icmp ne %5 0
		br %6, %7, %12
	7:
		%8 = load %cp
		%9 = load %8
		%10 = sext i8 %9 to i32
		%11 = icmp ne %10 0
		br %12
	12:
		%13 = phi [0, %4], [%11, %7]
		br %13, %14, %20
	14:
		br %15
	15:
		%16 = load %cp
		%17 = getelementptr %16, 1
		store %17, %cp
		%18 = load %2
		%19 = add %18 -1
		store %19, %2
		br %4
	20:
		%21 = load %cp
		%22 = load %1
		%23 = ptrtoint *i8 %21 to i64
		%24 = ptrtoint *i8 %22 to i64
		%25 = sub %23 %24
		ret %25

*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		%length1 = alloca i32, align 4
		%n = alloca i32, align 4
		%nondetString1 = alloca *i8, align 8
		store 0, %1
		%2 = call i32 @__VERIFIER_nondet_int()
		store %2, %length1
		%3 = call i32 @__VERIFIER_nondet_int()
		store %3, %n
		%4 = load %length1
		%5 = icmp slt %4 1
		br %5, %6, %7
	6:
		store 1, %length1
		br %7
	7:
		%8 = load %n
		%9 = icmp slt %8 1
		br %9, %10, %11
	10:
		store 1, %n
		br %11
	11:
		%12 = load %length1
		%13 = sext i32 %12 to i64
		%14 = mul %13 1
		%15 = alloca i8, numElementsLit: %14
		store %15, %nondetString1
		%16 = load %length1
		%17 = sub %16 1
		%18 = sext i32 %17 to i64
		%19 = load %nondetString1
		%20 = getelementptr %19, %18
		store 0, %20
		%21 = load %nondetString1
		%22 = load %n
		%23 = sext i32 %22 to i64
		%24 = call i64 @cstrnlen(*i8 %21, i64 %23)
		%25 = trunc i64 %24 to i32
		ret %25


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 20 rulesP rules:
f_565(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_566(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: v1031 != 0 && 2 <= v1026
f_566(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_568(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_568(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_570(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_570(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_572(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1029, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_572(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1029, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_574(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1029, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_574(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1029, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_576(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_576(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_578(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: v1105 != 0 && v1030 < v1039 && 4 <= v1039
f_578(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_581(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_581(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_584(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_584(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_587(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_587(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_590(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_590(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1028, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_593(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_593(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_595(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: v1244 = 1 + v1030 && 4 <= v1244
f_595(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_597(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_597(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_599(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
f_599(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_601(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 1 + v1247 = v1031 && 0 <= v1247
f_601(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_603(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_603(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_605(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_605(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, v1028, v1029, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_564(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1030, v1105, v1244, v1247, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: TRUE
f_564(v1021, v1022, v1023, v1024, v1025, v1026, 1, v1028, v1029, v1030, v1031, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) -> f_565(v1021, v1022, v1023, v1024, v1025, v1031, 1, v1028, v1029, v1030, v1026, v1032, v1040, v1033, v1041, v1034, v1042, v1035, v1043, v1039, v1044, v1045, v1046, v1048, 0, v1036, v1047, v1049, v1038, 3, 7, 2, 4, 8) :|: 0 = 0
Combined rules. Obtained 2 rulesP rules:
f_565(v1021:0, v1022:0, v1023:0, v1024:0, v1025:0, 1 + v1247:0, 1, v1028:0, v1029:0, v1030:0, v1026:0, v1032:0, v1040:0, v1033:0, v1041:0, v1034:0, v1042:0, v1035:0, v1043:0, v1039:0, v1044:0, v1045:0, v1046:0, v1048:0, 0, v1036:0, v1047:0, v1049:0, v1038:0, 3, 7, 2, 4, 8) -> f_565(v1021:0, v1022:0, v1023:0, v1024:0, v1025:0, v1247:0, 1, v1030:0, v1105:0, 1 + v1030:0, 1 + v1247:0, v1032:0, v1040:0, v1033:0, v1041:0, v1034:0, v1042:0, v1035:0, v1043:0, v1039:0, v1044:0, v1045:0, v1046:0, v1048:0, 0, v1036:0, v1047:0, v1049:0, v1038:0, 3, 7, 2, 4, 8) :|: v1026:0 > 1 && v1247:0 > -1 && v1039:0 > v1030:0 && v1105:0 < 0 && v1039:0 > 3 && v1030:0 > 2
f_565(v1021:0, v1022:0, v1023:0, v1024:0, v1025:0, 1 + v1247:0, 1, v1028:0, v1029:0, v1030:0, v1026:0, v1032:0, v1040:0, v1033:0, v1041:0, v1034:0, v1042:0, v1035:0, v1043:0, v1039:0, v1044:0, v1045:0, v1046:0, v1048:0, 0, v1036:0, v1047:0, v1049:0, v1038:0, 3, 7, 2, 4, 8) -> f_565(v1021:0, v1022:0, v1023:0, v1024:0, v1025:0, v1247:0, 1, v1030:0, v1105:0, 1 + v1030:0, 1 + v1247:0, v1032:0, v1040:0, v1033:0, v1041:0, v1034:0, v1042:0, v1035:0, v1043:0, v1039:0, v1044:0, v1045:0, v1046:0, v1048:0, 0, v1036:0, v1047:0, v1049:0, v1038:0, 3, 7, 2, 4, 8) :|: v1026:0 > 1 && v1247:0 > -1 && v1039:0 > v1030:0 && v1105:0 > 0 && v1039:0 > 3 && v1030:0 > 2
Filtered unneeded arguments:
   f_565(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, x34) -> f_565(x6, x10, x11, x20)
Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
f_565(sum~cons_1~v1247:0, v1030:0, v1026:0, v1039:0) -> f_565(v1247:0, 1 + v1030:0, 1 + v1247:0, v1039:0) :|: v1247:0 > -1 && v1026:0 > 1 && v1039:0 > v1030:0 && v1030:0 > 2 && v1039:0 > 3 && sum~cons_1~v1247:0 = 1 + v1247:0

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

(8)
Obligation:
Rules:
f_565(sum~cons_1~v1247:0, v1030:0, v1026:0, v1039:0) -> f_565(v1247:0, 1 + v1030:0, 1 + v1247:0, v1039:0) :|: v1247:0 > -1 && v1026:0 > 1 && v1039:0 > v1030:0 && v1030:0 > 2 && v1039:0 > 3 && sum~cons_1~v1247:0 = 1 + v1247:0

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

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

(10)
Obligation:
Rules:
f_565(sum~cons_1~v1247:0:0, v1030:0:0, v1026:0:0, v1039:0:0) -> f_565(v1247:0:0, 1 + v1030:0:0, 1 + v1247:0:0, v1039:0:0) :|: v1030:0:0 > 2 && v1039:0:0 > 3 && v1039:0:0 > v1030:0:0 && v1026:0:0 > 1 && v1247:0:0 > -1 && sum~cons_1~v1247:0:0 = 1 + v1247:0:0

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

(11) PolynomialOrderProcessor (EQUIVALENT)
Found the following polynomial interpretation:
[f_565(x, x1, x2, x3)] = x

The following rules are decreasing:
f_565(sum~cons_1~v1247:0:0, v1030:0:0, v1026:0:0, v1039:0:0) -> f_565(v1247:0:0, 1 + v1030:0:0, 1 + v1247:0:0, v1039:0:0) :|: v1030:0:0 > 2 && v1039:0:0 > 3 && v1039:0:0 > v1030:0:0 && v1026:0:0 > 1 && v1247:0:0 > -1 && sum~cons_1~v1247:0:0 = 1 + v1247:0:0
The following rules are bounded:
f_565(sum~cons_1~v1247:0:0, v1030:0:0, v1026:0:0, v1039:0:0) -> f_565(v1247:0:0, 1 + v1030:0:0, 1 + v1247:0:0, v1039:0:0) :|: v1030:0:0 > 2 && v1039:0:0 > 3 && v1039:0:0 > v1030:0:0 && v1026:0:0 > 1 && v1247:0:0 > -1 && sum~cons_1~v1247:0:0 = 1 + v1247:0:0

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

(12)
YES