15.01/5.27	YES
15.01/5.28	proof of /export/starexec/sandbox2/benchmark/theBenchmark.c
15.01/5.28	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
15.01/5.28	
15.01/5.28	
15.01/5.28	Termination of the given C Problem could be proven:
15.01/5.28	
15.01/5.28	(0) C Problem
15.01/5.28	(1) CToLLVMProof [EQUIVALENT, 166 ms]
15.01/5.28	(2) LLVM problem
15.01/5.28	(3) LLVMToTerminationGraphProof [EQUIVALENT, 2267 ms]
15.01/5.28	(4) LLVM Symbolic Execution Graph
15.01/5.28	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
15.01/5.28	(6) LLVM Symbolic Execution SCC
15.01/5.28	(7) SCC2IRS [SOUND, 89 ms]
15.01/5.28	(8) IntTRS
15.01/5.28	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
15.01/5.28	(10) IntTRS
15.01/5.28	(11) RankingReductionPairProof [EQUIVALENT, 20 ms]
15.01/5.28	(12) YES
15.01/5.28	
15.01/5.28	
15.01/5.28	----------------------------------------
15.01/5.28	
15.01/5.28	(0)
15.01/5.28	Obligation:
15.01/5.28	c file /export/starexec/sandbox2/benchmark/theBenchmark.c
15.01/5.28	----------------------------------------
15.01/5.28	
15.01/5.28	(1) CToLLVMProof (EQUIVALENT)
15.01/5.28	Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM.
15.01/5.28	----------------------------------------
15.01/5.28	
15.01/5.28	(2)
15.01/5.28	Obligation:
15.01/5.28	LLVM Problem
15.01/5.28	
15.01/5.28	Aliases:
15.01/5.28	
15.01/5.28	Data layout:
15.01/5.28	
15.01/5.28	"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"
15.01/5.28	
15.01/5.28	Machine:
15.01/5.28	
15.01/5.28	"x86_64-pc-linux-gnu"
15.01/5.28	
15.01/5.28	Type definitions:
15.01/5.28	
15.01/5.28	Global variables:
15.01/5.28	
15.01/5.28	Function declarations and definitions:
15.01/5.28	
15.01/5.28	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
15.01/5.28	*BasicFunctionTypename: "cstrlen" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (s *i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc
15.01/5.28		0:
15.01/5.28			%1 = alloca *i8, align 8
15.01/5.28			%p = alloca *i8, align 8
15.01/5.28			store %s, %1
15.01/5.28			%2 = load %1
15.01/5.28			store %2, %p
15.01/5.28			br %3
15.01/5.28		3:
15.01/5.28			%4 = load %p
15.01/5.28			%5 = load %4
15.01/5.28			%6 = sext i8 %5 to i32
15.01/5.28			%7 = icmp ne %6 0
15.01/5.28			br %7, %8, %11
15.01/5.28		8:
15.01/5.28			%9 = load %p
15.01/5.28			%10 = getelementptr %9, 1
15.01/5.28			store %10, %p
15.01/5.28			br %3
15.01/5.28		11:
15.01/5.28			%12 = load %p
15.01/5.28			%13 = load %1
15.01/5.28			%14 = ptrtoint *i8 %12 to i64
15.01/5.28			%15 = ptrtoint *i8 %13 to i64
15.01/5.28			%16 = sub %14 %15
15.01/5.28			%17 = trunc i64 %16 to i32
15.01/5.28			ret %17
15.01/5.28	
15.01/5.28	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
15.01/5.29		0:
15.01/5.29			%1 = alloca i32, align 4
15.01/5.29			%length1 = alloca i32, align 4
15.01/5.29			%nondetString1 = alloca *i8, align 8
15.01/5.29			store 0, %1
15.01/5.29			%2 = call i32 @__VERIFIER_nondet_int()
15.01/5.29			store %2, %length1
15.01/5.29			%3 = load %length1
15.01/5.29			%4 = icmp slt %3 1
15.01/5.29			br %4, %5, %6
15.01/5.29		5:
15.01/5.29			store 1, %length1
15.01/5.29			br %6
15.01/5.29		6:
15.01/5.29			%7 = load %length1
15.01/5.29			%8 = sext i32 %7 to i64
15.01/5.29			%9 = mul %8 1
15.01/5.29			%10 = alloca i8, numElementsLit: %9
15.01/5.29			store %10, %nondetString1
15.01/5.29			%11 = load %length1
15.01/5.29			%12 = sub %11 1
15.01/5.29			%13 = sext i32 %12 to i64
15.01/5.29			%14 = load %nondetString1
15.01/5.29			%15 = getelementptr %14, %13
15.01/5.29			store 0, %15
15.01/5.29			%16 = load %nondetString1
15.01/5.29			%17 = call i32 @cstrlen(*i8 %16)
15.01/5.29			ret %17
15.01/5.29	
15.01/5.29	
15.01/5.29	Analyze Termination of all function calls matching the pattern:
15.01/5.29	main()
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(3) LLVMToTerminationGraphProof (EQUIVALENT)
15.01/5.29	Constructed symbolic execution graph for LLVM program and proved memory safety.
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(4)
15.01/5.29	Obligation:
15.01/5.29	SE Graph
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(5) SymbolicExecutionGraphToSCCProof (SOUND)
15.01/5.29	Splitted symbolic execution graph to 1 SCC.
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(6)
15.01/5.29	Obligation:
15.01/5.29	SCC
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(7) SCC2IRS (SOUND)
15.01/5.29	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
15.01/5.29	Generated rules. Obtained 11 rulesP rules:
15.01/5.29	f_286(v158, v159, v160, v164, v162, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_287(v158, v159, v160, v164, v180, v162, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: TRUE
15.01/5.29	f_287(v158, v159, v160, v164, v180, v162, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_288(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: 0 = 0
15.01/5.29	f_288(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_289(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: v180 != 0 && v164 < v171 && 4 <= v171
15.01/5.29	f_289(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_291(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: 0 = 0
15.01/5.29	f_291(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_293(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: TRUE
15.01/5.29	f_293(v158, v159, v160, v164, v180, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_295(v158, v159, v160, v164, v180, 1, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: 0 = 0
15.01/5.29	f_295(v158, v159, v160, v164, v180, 1, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_297(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: v199 = 1 + v164 && 4 <= v199
15.01/5.29	f_297(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_299(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: TRUE
15.01/5.29	f_299(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_301(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: TRUE
15.01/5.29	f_301(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, v161, v162, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_285(v158, v159, v160, v164, v180, 1, v199, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: TRUE
15.01/5.29	f_285(v158, v159, v160, v161, v162, 1, v164, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) -> f_286(v158, v159, v160, v164, v162, 1, v161, v165, v172, v166, v173, v167, v174, v171, v175, v176, v178, 0, v168, v177, v179, v170, 3, 7, 2, 4, 8) :|: 0 = 0
15.01/5.29	Combined rules. Obtained 2 rulesP rules:
15.01/5.29	f_286(v158:0, v159:0, v160:0, v164:0, v162:0, 1, v161:0, v165:0, v172:0, v166:0, v173:0, v167:0, v174:0, v171:0, v175:0, v176:0, v178:0, 0, v168:0, v177:0, v179:0, v170:0, 3, 7, 2, 4, 8) -> f_286(v158:0, v159:0, v160:0, 1 + v164:0, v180:0, 1, v164:0, v165:0, v172:0, v166:0, v173:0, v167:0, v174:0, v171:0, v175:0, v176:0, v178:0, 0, v168:0, v177:0, v179:0, v170:0, 3, 7, 2, 4, 8) :|: v171:0 > v164:0 && v180:0 < 0 && v164:0 > 2 && v171:0 > 3
15.01/5.29	f_286(v158:0, v159:0, v160:0, v164:0, v162:0, 1, v161:0, v165:0, v172:0, v166:0, v173:0, v167:0, v174:0, v171:0, v175:0, v176:0, v178:0, 0, v168:0, v177:0, v179:0, v170:0, 3, 7, 2, 4, 8) -> f_286(v158:0, v159:0, v160:0, 1 + v164:0, v180:0, 1, v164:0, v165:0, v172:0, v166:0, v173:0, v167:0, v174:0, v171:0, v175:0, v176:0, v178:0, 0, v168:0, v177:0, v179:0, v170:0, 3, 7, 2, 4, 8) :|: v171:0 > v164:0 && v180:0 > 0 && v164:0 > 2 && v171:0 > 3
15.01/5.29	Filtered unneeded arguments:
15.01/5.29	   f_286(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_286(x4, x14)
15.01/5.29	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
15.01/5.29	f_286(v164:0, v171:0) -> f_286(1 + v164:0, v171:0) :|: v164:0 > 2 && v171:0 > 3 && v171:0 > v164:0
15.01/5.29	
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(8)
15.01/5.29	Obligation:
15.01/5.29	Rules:
15.01/5.29	f_286(v164:0, v171:0) -> f_286(1 + v164:0, v171:0) :|: v164:0 > 2 && v171:0 > 3 && v171:0 > v164:0
15.01/5.29	
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(9) IntTRSCompressionProof (EQUIVALENT)
15.01/5.29	Compressed rules.
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(10)
15.01/5.29	Obligation:
15.01/5.29	Rules:
15.01/5.29	f_286(v164:0:0, v171:0:0) -> f_286(1 + v164:0:0, v171:0:0) :|: v164:0:0 > 2 && v171:0:0 > 3 && v171:0:0 > v164:0:0
15.01/5.29	
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(11) RankingReductionPairProof (EQUIVALENT)
15.01/5.29	Interpretation:
15.01/5.29	[ f_286 ] = -1*f_286_1 + f_286_2
15.01/5.29	
15.01/5.29	The following rules are decreasing:
15.01/5.29	f_286(v164:0:0, v171:0:0) -> f_286(1 + v164:0:0, v171:0:0) :|: v164:0:0 > 2 && v171:0:0 > 3 && v171:0:0 > v164:0:0
15.01/5.29	
15.01/5.29	The following rules are bounded:
15.01/5.29	f_286(v164:0:0, v171:0:0) -> f_286(1 + v164:0:0, v171:0:0) :|: v164:0:0 > 2 && v171:0:0 > 3 && v171:0:0 > v164:0:0
15.01/5.29	
15.01/5.29	
15.01/5.29	----------------------------------------
15.01/5.29	
15.01/5.29	(12)
15.01/5.29	YES
15.44/5.32	EOF