/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files


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


MAYBE
proof of /export/starexec/sandbox/benchmark/theBenchmark.c
# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given C Problem could not be shown:

(0) C Problem
(1) CToLLVMProof [EQUIVALENT, 178 ms]
(2) LLVM problem


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

(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: "knapsack" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (size *i32, val *i32, N i32, cost *i32, best *i32, M i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca *i32, align 8
		%2 = alloca *i32, align 8
		%3 = alloca i32, align 4
		%4 = alloca *i32, align 8
		%5 = alloca *i32, align 8
		%6 = alloca i32, align 4
		%i = alloca i32, align 4
		%j = alloca i32, align 4
		store %size, %1
		store %val, %2
		store %N, %3
		store %cost, %4
		store %best, %5
		store %M, %6
		store 1, %j
		br %7
	7:
		%8 = load %j
		%9 = load %3
		%10 = icmp sle %8 %9
		br %10, %11, %84
	11:
		store 1, %i
		br %12
	12:
		%13 = load %i
		%14 = load %6
		%15 = icmp sle %13 %14
		br %15, %16, %80
	16:
		%17 = load %i
		%18 = load %j
		%19 = sext i32 %18 to i64
		%20 = load %1
		%21 = getelementptr %20, %19
		%22 = load %21
		%23 = icmp sge %17 %22
		br %23, %24, %76
	24:
		%25 = load %i
		%26 = sext i32 %25 to i64
		%27 = load %4
		%28 = getelementptr %27, %26
		%29 = load %28
		%30 = load %i
		%31 = load %j
		%32 = sext i32 %31 to i64
		%33 = load %1
		%34 = getelementptr %33, %32
		%35 = load %34
		%36 = sub %30 %35
		%37 = sext i32 %36 to i64
		%38 = load %4
		%39 = getelementptr %38, %37
		%40 = load %39
		%41 = load %j
		%42 = sext i32 %41 to i64
		%43 = load %2
		%44 = getelementptr %43, %42
		%45 = load %44
		%46 = add %40 %45
		%47 = icmp slt %29 %46
		br %47, %48, %75
	48:
		%49 = load %i
		%50 = load %j
		%51 = sext i32 %50 to i64
		%52 = load %1
		%53 = getelementptr %52, %51
		%54 = load %53
		%55 = sub %49 %54
		%56 = sext i32 %55 to i64
		%57 = load %4
		%58 = getelementptr %57, %56
		%59 = load %58
		%60 = load %j
		%61 = sext i32 %60 to i64
		%62 = load %2
		%63 = getelementptr %62, %61
		%64 = load %63
		%65 = add %59 %64
		%66 = load %i
		%67 = sext i32 %66 to i64
		%68 = load %4
		%69 = getelementptr %68, %67
		store %65, %69
		%70 = load %j
		%71 = load %i
		%72 = sext i32 %71 to i64
		%73 = load %5
		%74 = getelementptr %73, %72
		store %70, %74
		br %75
	75:
		br %76
	76:
		br %77
	77:
		%78 = load %i
		%79 = add %78 1
		store %79, %i
		br %12
	80:
		br %81
	81:
		%82 = load %j
		%83 = add %82 1
		store %83, %j
		br %7
	84:
		ret void

*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		%N = alloca i32, align 4
		%M = alloca i32, align 4
		%size = alloca *i32, align 8
		%val = alloca *i32, align 8
		%cost = alloca *i32, align 8
		%best = alloca *i32, align 8
		store 0, %1
		%2 = call i32 @__VERIFIER_nondet_int()
		store %2, %N
		%3 = call i32 @__VERIFIER_nondet_int()
		store %3, %M
		%4 = load %N
		%5 = icmp slt %4 1
		br %5, %6, %7
	6:
		store 1, %N
		br %7
	7:
		%8 = load %M
		%9 = icmp slt %8 1
		br %9, %10, %11
	10:
		store 1, %M
		br %11
	11:
		%12 = load %N
		%13 = sext i32 %12 to i64
		%14 = mul %13 4
		%15 = alloca i8, numElementsLit: %14
		%16 = bitcast *i8 %15 to *i32
		store %16, %size
		%17 = load %N
		%18 = sext i32 %17 to i64
		%19 = mul %18 4
		%20 = alloca i8, numElementsLit: %19
		%21 = bitcast *i8 %20 to *i32
		store %21, %val
		%22 = load %M
		%23 = sext i32 %22 to i64
		%24 = mul %23 4
		%25 = alloca i8, numElementsLit: %24
		%26 = bitcast *i8 %25 to *i32
		store %26, %cost
		%27 = load %M
		%28 = sext i32 %27 to i64
		%29 = mul %28 4
		%30 = alloca i8, numElementsLit: %29
		%31 = bitcast *i8 %30 to *i32
		store %31, %best
		%32 = load %size
		%33 = load %val
		%34 = load %N
		%35 = load %cost
		%36 = load %best
		%37 = load %M
		Unnamed Call-Instruction = call BasicVoidType @knapsack(*i32 %32, *i32 %33, i32 %34, *i32 %35, *i32 %36, i32 %37)
		ret 0


Analyze Termination of all function calls matching the pattern:
main()