11.82/4.15	YES
12.08/4.22	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
12.08/4.22	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.08/4.22	
12.08/4.22	
12.08/4.22	Termination of the given C Problem could be proven:
12.08/4.22	
12.08/4.22	(0) C Problem
12.08/4.22	(1) CToLLVMProof [EQUIVALENT, 175 ms]
12.08/4.22	(2) LLVM problem
12.08/4.22	(3) LLVMToTerminationGraphProof [EQUIVALENT, 1694 ms]
12.08/4.22	(4) LLVM Symbolic Execution Graph
12.08/4.22	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
12.08/4.22	(6) LLVM Symbolic Execution SCC
12.08/4.22	(7) SCC2IRS [SOUND, 84 ms]
12.08/4.22	(8) IntTRS
12.08/4.22	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
12.08/4.22	(10) IntTRS
12.08/4.22	(11) RankingReductionPairProof [EQUIVALENT, 0 ms]
12.08/4.22	(12) YES
12.08/4.22	
12.08/4.22	
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(0)
12.08/4.22	Obligation:
12.08/4.22	c file /export/starexec/sandbox/benchmark/theBenchmark.c
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(1) CToLLVMProof (EQUIVALENT)
12.08/4.22	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(2)
12.08/4.22	Obligation:
12.08/4.22	LLVM Problem
12.08/4.22	
12.08/4.22	Aliases:
12.08/4.22	
12.08/4.22	Data layout:
12.08/4.22	
12.08/4.22	"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"
12.08/4.22	
12.08/4.22	Machine:
12.08/4.22	
12.08/4.22	"x86_64-pc-linux-gnu"
12.08/4.22	
12.08/4.22	Type definitions:
12.08/4.22	
12.08/4.22	Global variables:
12.08/4.22	
12.08/4.22	Function declarations and definitions:
12.08/4.22	
12.08/4.22	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
12.08/4.22		0:
12.08/4.22			%1 = alloca i32, align 4
12.08/4.22			%x = alloca *i32, align 8
12.08/4.22			%y = alloca *i32, align 8
12.08/4.22			store 0, %1
12.08/4.22			%2 = alloca i8, numElementsLit: 4
12.08/4.22			%3 = bitcast *i8 %2 to *i32
12.08/4.22			store %3, %x
12.08/4.22			%4 = alloca i8, numElementsLit: 4
12.08/4.22			%5 = bitcast *i8 %4 to *i32
12.08/4.22			store %5, %y
12.08/4.22			%6 = load %y
12.08/4.22			store 1, %6
12.08/4.22			br %7
12.08/4.22		7:
12.08/4.22			%8 = load %x
12.08/4.22			%9 = load %8
12.08/4.22			%10 = icmp sgt %9 0
12.08/4.22			br %10, %11, %22
12.08/4.22		11:
12.08/4.22			%12 = load %x
12.08/4.22			%13 = load %12
12.08/4.22			%14 = load %y
12.08/4.22			%15 = load %14
12.08/4.22			%16 = sub %13 %15
12.08/4.22			%17 = load %x
12.08/4.22			store %16, %17
12.08/4.22			%18 = load %y
12.08/4.22			%19 = load %18
12.08/4.22			%20 = add %19 1
12.08/4.22			%21 = load %y
12.08/4.22			store %20, %21
12.08/4.22			br %7
12.08/4.22		22:
12.08/4.22			ret 0
12.08/4.22	
12.08/4.22	
12.08/4.22	Analyze Termination of all function calls matching the pattern:
12.08/4.22	main()
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(3) LLVMToTerminationGraphProof (EQUIVALENT)
12.08/4.22	Constructed symbolic execution graph for LLVM program and proved memory safety.
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(4)
12.08/4.22	Obligation:
12.08/4.22	SE Graph
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(5) SymbolicExecutionGraphToSCCProof (SOUND)
12.08/4.22	Splitted symbolic execution graph to 1 SCC.
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(6)
12.08/4.22	Obligation:
12.08/4.22	SCC
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(7) SCC2IRS (SOUND)
12.08/4.22	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
12.08/4.22	Generated rules. Obtained 19 rulesP rules:
12.08/4.22	f_262(v119, v120, v121, v122, v123, v124, 1, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_263(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_263(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_264(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 < v127
12.08/4.22	f_264(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_266(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_266(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_268(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: TRUE
12.08/4.22	f_268(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_270(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_270(v119, v120, v121, v122, v123, v127, 1, v124, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_271(v119, v120, v121, v122, v123, v127, 1, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_271(v119, v120, v121, v122, v123, v127, 1, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_272(v119, v120, v121, v122, v123, v127, 1, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_272(v119, v120, v121, v122, v123, v127, 1, v126, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_273(v119, v120, v121, v122, v123, v127, 1, v128, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_273(v119, v120, v121, v122, v123, v127, 1, v128, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_274(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: v135 + v128 = v127
12.08/4.22	f_274(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_275(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_275(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_276(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: TRUE
12.08/4.22	f_276(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_277(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_277(v119, v120, v121, v122, v123, v127, 1, v128, v135, v126, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_278(v119, v120, v121, v122, v123, v127, 1, v128, v135, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_278(v119, v120, v121, v122, v123, v127, 1, v128, v135, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_279(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: v137 = 1 + v128 && 3 <= v137
12.08/4.22	f_279(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_280(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	f_280(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_281(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: TRUE
12.08/4.22	f_281(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_282(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: TRUE
12.08/4.22	f_282(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_261(v119, v120, v121, v122, v123, v127, 1, v128, v135, v137, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: TRUE
12.08/4.22	f_261(v119, v120, v121, v122, v123, v124, 1, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) -> f_262(v119, v120, v121, v122, v123, v124, 1, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 7, 2, 4, 8) :|: 0 = 0
12.08/4.22	Combined rules. Obtained 1 rulesP rules:
12.08/4.22	f_262(v119:0, v120:0, v121:0, v122:0, v123:0, v124:0, 1, v126:0, v135:0 + v128:0, v128:0, v129:0, v130:0, v131:0, v132:0, v133:0, 0, 3, 7, 2, 4, 8) -> f_262(v119:0, v120:0, v121:0, v122:0, v123:0, v135:0 + v128:0, 1, v128:0, v135:0, 1 + v128:0, v129:0, v130:0, v131:0, v132:0, v133:0, 0, 3, 7, 2, 4, 8) :|: v128:0 > 1 && v135:0 + v128:0 > 0
12.08/4.22	Filtered unneeded arguments:
12.08/4.22	   f_262(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) -> f_262(x9, x10)
12.08/4.22	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
12.08/4.22	f_262(sum~v135:0~v128:0, v128:0) -> f_262(v135:0, 1 + v128:0) :|: v128:0 > 1 && v135:0 + v128:0 > 0 && sum~v135:0~v128:0 = v135:0 + v128:0
12.08/4.22	
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(8)
12.08/4.22	Obligation:
12.08/4.22	Rules:
12.08/4.22	f_262(sum~v135:0~v128:0, v128:0) -> f_262(v135:0, 1 + v128:0) :|: v128:0 > 1 && v135:0 + v128:0 > 0 && sum~v135:0~v128:0 = v135:0 + v128:0
12.08/4.22	
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(9) IntTRSCompressionProof (EQUIVALENT)
12.08/4.22	Compressed rules.
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(10)
12.08/4.22	Obligation:
12.08/4.22	Rules:
12.08/4.22	f_262(sum~v135:0:0~v128:0:0, v128:0:0) -> f_262(v135:0:0, 1 + v128:0:0) :|: v128:0:0 > 1 && v135:0:0 + v128:0:0 > 0 && sum~v135:0:0~v128:0:0 = v135:0:0 + v128:0:0
12.08/4.22	
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(11) RankingReductionPairProof (EQUIVALENT)
12.08/4.22	Interpretation:
12.08/4.22	[ f_262 ] = 1/2*f_262_1
12.08/4.22	
12.08/4.22	The following rules are decreasing:
12.08/4.22	f_262(sum~v135:0:0~v128:0:0, v128:0:0) -> f_262(v135:0:0, 1 + v128:0:0) :|: v128:0:0 > 1 && v135:0:0 + v128:0:0 > 0 && sum~v135:0:0~v128:0:0 = v135:0:0 + v128:0:0
12.08/4.22	
12.08/4.22	The following rules are bounded:
12.08/4.22	f_262(sum~v135:0:0~v128:0:0, v128:0:0) -> f_262(v135:0:0, 1 + v128:0:0) :|: v128:0:0 > 1 && v135:0:0 + v128:0:0 > 0 && sum~v135:0:0~v128:0:0 = v135:0:0 + v128:0:0
12.08/4.22	
12.08/4.22	
12.08/4.22	----------------------------------------
12.08/4.22	
12.08/4.22	(12)
12.08/4.22	YES
12.08/4.26	EOF