21.15/6.75	YES
21.15/6.76	proof of /export/starexec/sandbox2/benchmark/theBenchmark.c
21.15/6.76	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
21.15/6.76	
21.15/6.76	
21.15/6.76	Termination of the given C Problem could be proven:
21.15/6.76	
21.15/6.76	(0) C Problem
21.15/6.76	(1) CToLLVMProof [EQUIVALENT, 174 ms]
21.15/6.76	(2) LLVM problem
21.15/6.76	(3) LLVMToTerminationGraphProof [EQUIVALENT, 2521 ms]
21.15/6.76	(4) LLVM Symbolic Execution Graph
21.15/6.76	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
21.15/6.76	(6) LLVM Symbolic Execution SCC
21.15/6.76	(7) SCC2IRS [SOUND, 18 ms]
21.15/6.76	(8) IntTRS
21.15/6.76	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
21.15/6.76	(10) IntTRS
21.15/6.76	(11) RankingReductionPairProof [EQUIVALENT, 8 ms]
21.15/6.76	(12) YES
21.15/6.76	
21.15/6.76	
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(0)
21.15/6.76	Obligation:
21.15/6.76	c file /export/starexec/sandbox2/benchmark/theBenchmark.c
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(1) CToLLVMProof (EQUIVALENT)
21.15/6.76	Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM.
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(2)
21.15/6.76	Obligation:
21.15/6.76	LLVM Problem
21.15/6.76	
21.15/6.76	Aliases:
21.15/6.76	
21.15/6.76	Data layout:
21.15/6.76	
21.15/6.76	"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"
21.15/6.76	
21.15/6.76	Machine:
21.15/6.76	
21.15/6.76	"x86_64-pc-linux-gnu"
21.15/6.76	
21.15/6.76	Type definitions:
21.15/6.76	
21.15/6.76	Global variables:
21.15/6.76	
21.15/6.76	Function declarations and definitions:
21.15/6.76	
21.15/6.76	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
21.15/6.76	*BasicFunctionTypename: "__VERIFIER_error" returnParam: BasicVoidType parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc
21.15/6.76	*BasicFunctionTypename: "gcd" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (y1 i32, y2 i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
21.15/6.76		0:
21.15/6.76			%1 = alloca i32, align 4
21.15/6.76			%2 = alloca i32, align 4
21.15/6.76			%3 = alloca i32, align 4
21.15/6.76			store %y1, %2
21.15/6.76			store %y2, %3
21.15/6.76			%4 = load %2
21.15/6.76			%5 = icmp sle %4 0
21.15/6.76			br %5, %9, %6
21.15/6.76		6:
21.15/6.76			%7 = load %3
21.15/6.76			%8 = icmp sle %7 0
21.15/6.76			br %8, %9, %10
21.15/6.76		9:
21.15/6.76			store 0, %1
21.15/6.76			br %32
21.15/6.76		10:
21.15/6.76			%11 = load %2
21.15/6.76			%12 = load %3
21.15/6.76			%13 = icmp eq %11 %12
21.15/6.76			br %13, %14, %16
21.15/6.76		14:
21.15/6.76			%15 = load %2
21.15/6.76			store %15, %1
21.15/6.76			br %32
21.15/6.76		16:
21.15/6.76			%17 = load %2
21.15/6.76			%18 = load %3
21.15/6.76			%19 = icmp sgt %17 %18
21.15/6.76			br %19, %20, %26
21.15/6.76		20:
21.15/6.76			%21 = load %2
21.15/6.76			%22 = load %3
21.15/6.76			%23 = sub %21 %22
21.15/6.76			%24 = load %3
21.15/6.76			%25 = call i32 @gcd(i32 %23, i32 %24)
21.15/6.76			store %25, %1
21.15/6.76			br %32
21.15/6.76		26:
21.15/6.76			%27 = load %2
21.15/6.76			%28 = load %3
21.15/6.76			%29 = load %2
21.15/6.76			%30 = sub %28 %29
21.15/6.76			%31 = call i32 @gcd(i32 %27, i32 %30)
21.15/6.76			store %31, %1
21.15/6.76			br %32
21.15/6.76		32:
21.15/6.76			%33 = load %1
21.15/6.76			ret %33
21.15/6.76	
21.15/6.76	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
21.15/6.76		0:
21.15/6.76			%1 = alloca i32, align 4
21.15/6.76			%m = alloca i32, align 4
21.15/6.76			%n = alloca i32, align 4
21.15/6.76			%z = alloca i32, align 4
21.15/6.76			store 0, %1
21.15/6.76			%2 = call i32 @__VERIFIER_nondet_int()
21.15/6.76			store %2, %m
21.15/6.76			%3 = load %m
21.15/6.76			%4 = icmp sle %3 0
21.15/6.76			br %4, %5, %6
21.15/6.76		5:
21.15/6.76			store 0, %1
21.15/6.76			br %26
21.15/6.76		6:
21.15/6.76			%7 = call i32 @__VERIFIER_nondet_int()
21.15/6.76			store %7, %n
21.15/6.76			%8 = load %n
21.15/6.76			%9 = icmp sle %8 0
21.15/6.76			br %9, %10, %11
21.15/6.76		10:
21.15/6.76			store 0, %1
21.15/6.76			br %26
21.15/6.76		11:
21.15/6.76			%12 = load %m
21.15/6.76			%13 = load %n
21.15/6.76			%14 = call i32 @gcd(i32 %12, i32 %13)
21.15/6.76			store %14, %z
21.15/6.76			%15 = load %z
21.15/6.76			%16 = icmp slt %15 1
21.15/6.76			br %16, %17, %25
21.15/6.76		17:
21.15/6.76			%18 = load %m
21.15/6.76			%19 = icmp sgt %18 0
21.15/6.76			br %19, %20, %25
21.15/6.76		20:
21.15/6.76			%21 = load %n
21.15/6.76			%22 = icmp sgt %21 0
21.15/6.76			br %22, %23, %25
21.15/6.76		23:
21.15/6.76			br %24
21.15/6.76		24:
21.15/6.76			Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() noreturn
21.15/6.76			unreachable
21.15/6.76		25:
21.15/6.76			store 0, %1
21.15/6.76			br %26
21.15/6.76		26:
21.15/6.76			%27 = load %1
21.15/6.76			ret %27
21.15/6.76	
21.15/6.76	
21.15/6.76	Analyze Termination of all function calls matching the pattern:
21.15/6.76	main()
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(3) LLVMToTerminationGraphProof (EQUIVALENT)
21.15/6.76	Constructed symbolic execution graph for LLVM program and proved memory safety.
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(4)
21.15/6.76	Obligation:
21.15/6.76	SE Graph
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(5) SymbolicExecutionGraphToSCCProof (SOUND)
21.15/6.76	Splitted symbolic execution graph to 1 SCC.
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(6)
21.15/6.76	Obligation:
21.15/6.76	SCC
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(7) SCC2IRS (SOUND)
21.15/6.76	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
21.15/6.76	Generated rules. Obtained 38 rulesP rules:
21.15/6.76	f_330(v58, v59, v60, v61, 3, 1, 4) -> f_331(v58, v59, v60, v62, v61, v63, 3, 1, 4) :|: 1 <= v62 && v63 = 3 + v62 && 4 <= v63
21.15/6.76	f_331(v58, v59, v60, v62, v61, v63, 3, 1, 4) -> f_332(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) :|: 1 <= v64 && v65 = 3 + v64 && 4 <= v65
21.15/6.76	f_332(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) -> f_333(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) :|: TRUE
21.15/6.76	f_333(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) -> f_334(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) :|: TRUE
21.15/6.76	f_334(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) -> f_335(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_335(v58, v59, v60, v62, v64, v61, v63, v65, 3, 1, 4) -> f_336(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_336(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_337(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: TRUE
21.15/6.76	f_337(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_338(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_338(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_339(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_339(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_340(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: TRUE
21.15/6.76	f_340(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_341(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_341(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_342(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_342(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_344(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: v58 != v59
21.15/6.76	f_344(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_346(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_346(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_348(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: TRUE
21.15/6.76	f_348(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_350(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_350(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_352(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) :|: 0 = 0
21.15/6.76	f_352(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_354(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 2, 1, 4) :|: v59 < v58 && 2 <= v58
21.15/6.76	f_352(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 4) -> f_355(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: v58 <= v59 && 2 <= v59
21.15/6.76	f_354(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 2, 1, 4) -> f_357(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) :|: 0 = 0
21.15/6.76	f_357(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) -> f_360(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) :|: TRUE
21.15/6.76	f_360(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) -> f_363(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) :|: 0 = 0
21.15/6.76	f_363(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) -> f_366(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) :|: 0 = 0
21.15/6.76	f_366(v58, v59, v60, v62, v64, 0, 1, v61, v63, v65, 3, 2, 4) -> f_369(v58, v59, v60, v62, v64, 0, 1, v77, v61, v63, v65, 3, 2, 4) :|: v77 + v59 = v58 && 1 <= v77
21.15/6.76	f_369(v58, v59, v60, v62, v64, 0, 1, v77, v61, v63, v65, 3, 2, 4) -> f_372(v58, v59, v60, v62, v64, 0, 1, v77, v61, v63, v65, 3, 2, 4) :|: 0 = 0
21.15/6.76	f_372(v58, v59, v60, v62, v64, 0, 1, v77, v61, v63, v65, 3, 2, 4) -> f_375(v77, v59, v60, v61, v62, v63, v64, v65, v58, 0, 1, 3, 2, 4) :|: 0 = 0
21.15/6.76	f_375(v77, v59, v60, v61, v62, v63, v64, v65, v58, 0, 1, 3, 2, 4) -> f_378(v77, v59, v60, v61, v62, v63, v64, v65, v58, 3, 2, 1, 4) :|: TRUE
21.15/6.76	f_378(v77, v59, v60, v61, v62, v63, v64, v65, v58, 3, 2, 1, 4) -> f_328(v77, v59, 1) :|: 1 <= v77 && 1 <= v59
21.15/6.76	f_328(v58, v59, 1) -> f_330(v58, v59, v60, v61, 3, 1, 4) :|: 1 <= v60 && v61 = 3 + v60 && 4 <= v61
21.15/6.76	f_355(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_358(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: 0 = 0
21.15/6.76	f_358(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_361(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: TRUE
21.15/6.76	f_361(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_364(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: 0 = 0
21.15/6.76	f_364(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_367(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: 0 = 0
21.15/6.76	f_367(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_370(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) :|: 0 = 0
21.15/6.76	f_370(v58, v59, v60, v62, v64, 0, v61, v63, v65, 3, 1, 2, 4) -> f_373(v58, v59, v60, v62, v64, 0, v78, v61, v63, v65, 3, 1, 2, 4) :|: v78 + v58 = v59 && 1 <= v78
21.15/6.76	f_373(v58, v59, v60, v62, v64, 0, v78, v61, v63, v65, 3, 1, 2, 4) -> f_376(v58, v78, v60, v61, v62, v63, v64, v65, v59, 0, 3, 1, 2, 4) :|: 0 = 0
21.15/6.76	f_376(v58, v78, v60, v61, v62, v63, v64, v65, v59, 0, 3, 1, 2, 4) -> f_379(v58, v78, v60, v61, v62, v63, v64, v65, v59, 3, 1, 2, 4) :|: TRUE
21.15/6.76	f_379(v58, v78, v60, v61, v62, v63, v64, v65, v59, 3, 1, 2, 4) -> f_328(v58, v78, 1) :|: 1 <= v58 && 1 <= v78
21.15/6.76	Combined rules. Obtained 2 rulesP rules:
21.15/6.76	f_330(v58:0, v78:0 + v58:0, v60:0, v61:0, 3, 1, 4) -> f_330(v58:0, v78:0, v60:1, 3 + v60:1, 3, 1, 4) :|: v78:0 + v58:0 > v58:0 && v64:0 > 0 && v62:0 > 0 && v78:0 + v58:0 > 1 && v78:0 > 0 && v60:1 > 0 && v58:0 > 0
21.15/6.76	f_330(v77:0 + v59:0, v59:0, v60:0, v61:0, 3, 1, 4) -> f_330(v77:0, v59:0, v60:1, 3 + v60:1, 3, 1, 4) :|: v64:0 > 0 && v62:0 > 0 && v77:0 + v59:0 > v59:0 && v77:0 + v59:0 > 1 && v77:0 > 0 && v60:1 > 0 && v59:0 > 0
21.15/6.76	Filtered unneeded arguments:
21.15/6.76	   f_330(x1, x2, x3, x4, x5, x6, x7) -> f_330(x1, x2)
21.15/6.76	Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules:
21.15/6.76	f_330(v58:0, sum~v78:0~v58:0) -> f_330(v58:0, v78:0) :|: v78:0 + v58:0 > 1 && v78:0 + v58:0 > v58:0 && v58:0 > 0 && v78:0 > 0 && sum~v78:0~v58:0 = v78:0 + v58:0
21.15/6.76	f_330(sum~v77:0~v59:0, v59:0) -> f_330(v77:0, v59:0) :|: v77:0 + v59:0 > 1 && v77:0 + v59:0 > v59:0 && v59:0 > 0 && v77:0 > 0 && sum~v77:0~v59:0 = v77:0 + v59:0
21.15/6.76	
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(8)
21.15/6.76	Obligation:
21.15/6.76	Rules:
21.15/6.76	f_330(v58:0, sum~v78:0~v58:0) -> f_330(v58:0, v78:0) :|: v78:0 + v58:0 > 1 && v78:0 + v58:0 > v58:0 && v58:0 > 0 && v78:0 > 0 && sum~v78:0~v58:0 = v78:0 + v58:0
21.15/6.76	f_330(sum~v77:0~v59:0, v59:0) -> f_330(v77:0, v59:0) :|: v77:0 + v59:0 > 1 && v77:0 + v59:0 > v59:0 && v59:0 > 0 && v77:0 > 0 && sum~v77:0~v59:0 = v77:0 + v59:0
21.15/6.76	
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(9) IntTRSCompressionProof (EQUIVALENT)
21.15/6.76	Compressed rules.
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(10)
21.15/6.76	Obligation:
21.15/6.76	Rules:
21.15/6.76	f_330(sum~v77:0:0~v59:0:0, v59:0:0) -> f_330(v77:0:0, v59:0:0) :|: v59:0:0 > 0 && v77:0:0 > 0 && v77:0:0 + v59:0:0 > v59:0:0 && v77:0:0 + v59:0:0 > 1 && sum~v77:0:0~v59:0:0 = v77:0:0 + v59:0:0
21.15/6.76	f_330(v58:0:0, sum~v78:0:0~v58:0:0) -> f_330(v58:0:0, v78:0:0) :|: v58:0:0 > 0 && v78:0:0 > 0 && v78:0:0 + v58:0:0 > v58:0:0 && v78:0:0 + v58:0:0 > 1 && sum~v78:0:0~v58:0:0 = v78:0:0 + v58:0:0
21.15/6.76	
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(11) RankingReductionPairProof (EQUIVALENT)
21.15/6.76	Interpretation:
21.15/6.76	[ f_330 ] = f_330_2 + f_330_1
21.15/6.76	
21.15/6.76	The following rules are decreasing:
21.15/6.76	f_330(sum~v77:0:0~v59:0:0, v59:0:0) -> f_330(v77:0:0, v59:0:0) :|: v59:0:0 > 0 && v77:0:0 > 0 && v77:0:0 + v59:0:0 > v59:0:0 && v77:0:0 + v59:0:0 > 1 && sum~v77:0:0~v59:0:0 = v77:0:0 + v59:0:0
21.15/6.76	f_330(v58:0:0, sum~v78:0:0~v58:0:0) -> f_330(v58:0:0, v78:0:0) :|: v58:0:0 > 0 && v78:0:0 > 0 && v78:0:0 + v58:0:0 > v58:0:0 && v78:0:0 + v58:0:0 > 1 && sum~v78:0:0~v58:0:0 = v78:0:0 + v58:0:0
21.15/6.76	
21.15/6.76	The following rules are bounded:
21.15/6.76	f_330(sum~v77:0:0~v59:0:0, v59:0:0) -> f_330(v77:0:0, v59:0:0) :|: v59:0:0 > 0 && v77:0:0 > 0 && v77:0:0 + v59:0:0 > v59:0:0 && v77:0:0 + v59:0:0 > 1 && sum~v77:0:0~v59:0:0 = v77:0:0 + v59:0:0
21.15/6.76	f_330(v58:0:0, sum~v78:0:0~v58:0:0) -> f_330(v58:0:0, v78:0:0) :|: v58:0:0 > 0 && v78:0:0 > 0 && v78:0:0 + v58:0:0 > v58:0:0 && v78:0:0 + v58:0:0 > 1 && sum~v78:0:0~v58:0:0 = v78:0:0 + v58:0:0
21.15/6.76	
21.15/6.76	
21.15/6.76	----------------------------------------
21.15/6.76	
21.15/6.76	(12)
21.15/6.76	YES
21.53/6.81	EOF