22.18/7.68	YES
22.18/7.70	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
22.18/7.70	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
22.18/7.70	
22.18/7.70	
22.18/7.70	Termination of the given C Problem could be proven:
22.18/7.70	
22.18/7.70	(0) C Problem
22.18/7.70	(1) CToLLVMProof [EQUIVALENT, 166 ms]
22.18/7.70	(2) LLVM problem
22.18/7.70	(3) LLVMToTerminationGraphProof [EQUIVALENT, 4883 ms]
22.18/7.70	(4) LLVM Symbolic Execution Graph
22.18/7.70	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
22.18/7.70	(6) LLVM Symbolic Execution SCC
22.18/7.70	(7) SCC2IRS [SOUND, 64 ms]
22.18/7.70	(8) IntTRS
22.18/7.70	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
22.18/7.70	(10) IntTRS
22.18/7.70	(11) PolynomialOrderProcessor [EQUIVALENT, 0 ms]
22.18/7.70	(12) YES
22.18/7.70	
22.18/7.70	
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(0)
22.18/7.70	Obligation:
22.18/7.70	c file /export/starexec/sandbox/benchmark/theBenchmark.c
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(1) CToLLVMProof (EQUIVALENT)
22.18/7.70	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(2)
22.18/7.70	Obligation:
22.18/7.70	LLVM Problem
22.18/7.70	
22.18/7.70	Aliases:
22.18/7.70	
22.18/7.70	Data layout:
22.18/7.70	
22.18/7.70	"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"
22.18/7.70	
22.18/7.70	Machine:
22.18/7.70	
22.18/7.70	"x86_64-pc-linux-gnu"
22.18/7.70	
22.18/7.70	Type definitions:
22.18/7.70	
22.18/7.70	Global variables:
22.18/7.70	
22.18/7.70	Function declarations and definitions:
22.18/7.70	
22.18/7.70	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
22.18/7.70	*BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
22.18/7.70		0:
22.18/7.70			%1 = alloca i32, align 4
22.18/7.70			%2 = alloca i32, align 4
22.18/7.70			%x_ref = alloca *i32, align 8
22.18/7.70			%y_ref = alloca *i32, align 8
22.18/7.70			%c = alloca *i32, align 8
22.18/7.70			store %x, %1
22.18/7.70			store %y, %2
22.18/7.70			%3 = alloca i8, numElementsLit: 4
22.18/7.70			%4 = bitcast *i8 %3 to *i32
22.18/7.70			store %4, %x_ref
22.18/7.70			%5 = alloca i8, numElementsLit: 4
22.18/7.70			%6 = bitcast *i8 %5 to *i32
22.18/7.70			store %6, %y_ref
22.18/7.70			%7 = alloca i8, numElementsLit: 4
22.18/7.70			%8 = bitcast *i8 %7 to *i32
22.18/7.70			store %8, %c
22.18/7.70			%9 = load %1
22.18/7.70			%10 = load %x_ref
22.18/7.70			store %9, %10
22.18/7.70			%11 = load %2
22.18/7.70			%12 = load %y_ref
22.18/7.70			store %11, %12
22.18/7.70			%13 = load %c
22.18/7.70			store 0, %13
22.18/7.70			br %14
22.18/7.70		14:
22.18/7.70			%15 = load %x_ref
22.18/7.70			%16 = load %15
22.18/7.70			%17 = load %y_ref
22.18/7.70			%18 = load %17
22.18/7.70			%19 = icmp sgt %16 %18
22.18/7.70			br %19, %20, %33
22.18/7.70		20:
22.18/7.70			%21 = load %x_ref
22.18/7.70			%22 = load %21
22.18/7.70			%23 = sub %22 1
22.18/7.70			%24 = load %x_ref
22.18/7.70			store %23, %24
22.18/7.70			%25 = load %y_ref
22.18/7.70			%26 = load %25
22.18/7.70			%27 = add %26 1
22.18/7.70			%28 = load %y_ref
22.18/7.70			store %27, %28
22.18/7.70			%29 = load %c
22.18/7.70			%30 = load %29
22.18/7.70			%31 = add %30 1
22.18/7.70			%32 = load %c
22.18/7.70			store %31, %32
22.18/7.70			br %14
22.18/7.70		33:
22.18/7.70			%34 = load %c
22.18/7.70			%35 = load %34
22.18/7.70			ret %35
22.18/7.70	
22.18/7.70	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
22.18/7.70		0:
22.18/7.70			%1 = alloca i32, align 4
22.18/7.70			store 0, %1
22.18/7.70			%2 = call i32 @__VERIFIER_nondet_int()
22.18/7.70			%3 = call i32 @__VERIFIER_nondet_int()
22.18/7.70			%4 = call i32 @test_fun(i32 %2, i32 %3)
22.18/7.70			ret %4
22.18/7.70	
22.18/7.70	
22.18/7.70	Analyze Termination of all function calls matching the pattern:
22.18/7.70	main()
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(3) LLVMToTerminationGraphProof (EQUIVALENT)
22.18/7.70	Constructed symbolic execution graph for LLVM program and proved memory safety.
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(4)
22.18/7.70	Obligation:
22.18/7.70	SE Graph
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(5) SymbolicExecutionGraphToSCCProof (SOUND)
22.18/7.70	Splitted symbolic execution graph to 1 SCC.
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(6)
22.18/7.70	Obligation:
22.18/7.70	SCC
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(7) SCC2IRS (SOUND)
22.18/7.70	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
22.18/7.70	Generated rules. Obtained 24 rulesP rules:
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: v220 < v219
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: TRUE
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: 1 + v234 = v219
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: TRUE
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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
22.18/7.70	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, 4, 8) :|: v236 = 1 + v220
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: TRUE
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	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, 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, 4, 8, 2) :|: v238 = 1 + v222 && 2 <= v238
22.18/7.70	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, 4, 8, 2) -> 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, 4, 8, 2) :|: 0 = 0
22.18/7.70	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, 4, 8, 2) -> 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, 4, 8, 2) :|: TRUE
22.18/7.70	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, 4, 8, 2) -> 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, 4, 8, 2) :|: TRUE
22.18/7.70	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, 4, 8, 2) -> 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, 4, 8) :|: TRUE
22.18/7.70	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, 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, 4, 8) :|: 0 = 0
22.18/7.70	Combined rules. Obtained 1 rulesP rules:
22.18/7.70	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, 1 + v234: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, 4, 8) -> f_412(v206:0, v207:0, v208:0, v209:0, v210:0, v211:0, v212:0, v213:0, v214:0, v215:0, 1 + v234:0, v220:0, 1, v234:0, 1 + 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, 4, 8) :|: v222:0 > 0 && v220:0 < 1 + v234:0
22.18/7.70	Filtered unneeded arguments:
22.18/7.70	   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) -> f_412(x14, x15, x17)
22.18/7.70	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
22.18/7.70	f_412(sum~cons_1~v234:0, v220:0, v222:0) -> f_412(v234:0, 1 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < 1 + v234:0 && sum~cons_1~v234:0 = 1 + v234:0
22.18/7.70	
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(8)
22.18/7.70	Obligation:
22.18/7.70	Rules:
22.18/7.70	f_412(sum~cons_1~v234:0, v220:0, v222:0) -> f_412(v234:0, 1 + v220:0, 1 + v222:0) :|: v222:0 > 0 && v220:0 < 1 + v234:0 && sum~cons_1~v234:0 = 1 + v234:0
22.18/7.70	
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(9) IntTRSCompressionProof (EQUIVALENT)
22.18/7.70	Compressed rules.
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(10)
22.18/7.70	Obligation:
22.18/7.70	Rules:
22.18/7.70	f_412(sum~cons_1~v234:0:0, v220:0:0, v222:0:0) -> f_412(v234:0:0, 1 + v220:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v220:0:0 < 1 + v234:0:0 && sum~cons_1~v234:0:0 = 1 + v234:0:0
22.18/7.70	
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(11) PolynomialOrderProcessor (EQUIVALENT)
22.18/7.70	Found the following polynomial interpretation:
22.18/7.70	[f_412(x, x1, x2)] = x - x1
22.18/7.70	
22.18/7.70	The following rules are decreasing:
22.18/7.70	f_412(sum~cons_1~v234:0:0, v220:0:0, v222:0:0) -> f_412(v234:0:0, 1 + v220:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v220:0:0 < 1 + v234:0:0 && sum~cons_1~v234:0:0 = 1 + v234:0:0
22.18/7.70	The following rules are bounded:
22.18/7.70	f_412(sum~cons_1~v234:0:0, v220:0:0, v222:0:0) -> f_412(v234:0:0, 1 + v220:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v220:0:0 < 1 + v234:0:0 && sum~cons_1~v234:0:0 = 1 + v234:0:0
22.18/7.70	
22.18/7.70	----------------------------------------
22.18/7.70	
22.18/7.70	(12)
22.18/7.70	YES
24.12/8.44	EOF