/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, 176 ms]
(2) LLVM problem
(3) LLVMToTerminationGraphProof [EQUIVALENT, 10.1 s]
(4) LLVM Symbolic Execution Graph
(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
(6) AND
    (7) LLVM Symbolic Execution SCC
    (8) LLVM Symbolic Execution SCC
    (9) LLVM Symbolic Execution SCC
(10) SymbolicExecutionGraphToLassoProof [COMPLETE, 19 ms]
(11) AND
    (12) LLVM Symbolic Execution Lasso
    (13) LLVM Symbolic Execution Lasso
    (14) LLVM Symbolic Execution Lasso
    (15) LLVM Symbolic Execution Lasso


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

(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:

Name: nomsg initVal: -1 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: null section: null

Name: mode1 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: r1 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p3_old initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: id1 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: send1 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: st1 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p1_new initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: mode2 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p1_old initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: id2 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: send2 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: st2 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p2_new initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: mode3 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p2_old initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: id3 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: send3 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: st3 initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: p3_new initVal: 0 type: i8 addrSpace: null alignment: 1 threadLocal: false constant: false linkageType: COMMON section: null

Name: nodes initVal: (@node1,@node2,@node3) type: [3 x *BasicFunctionType varArgs: falsereturnType: BasicVoidTypeparamTypes: ()] addrSpace: null alignment: 16 threadLocal: false constant: false linkageType: null section: null

Name: p1 initVal: 0 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: COMMON section: null

Name: p2 initVal: 0 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: COMMON section: null

Name: p3 initVal: 0 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: COMMON section: null

Function declarations and definitions:

*BasicFunctionTypename: "__VERIFIER_nondet_char" returnParam: i8 signext parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "__VERIFIER_nondet_msg_t" returnParam: i8 signext parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "__VERIFIER_nondet__Bool" returnParam: i1 zeroext parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "__VERIFIER_error" returnParam: BasicVoidType parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc
*BasicFunctionTypename: "node1" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%m1 = alloca i8, align 1
		%1 = load @nomsg
		store %1, %m1
		%2 = load @mode1
		%3 = trunc i8 %2 to i1
		br %3, %4, %36
	4:
		%5 = load @r1
		%6 = sext i8 %5 to i32
		%7 = add %6 1
		%8 = trunc i32 %7 to i8
		store %8, @r1
		%9 = load @p3_old
		store %9, %m1
		%10 = load @nomsg
		store %10, @p3_old
		%11 = load %m1
		%12 = sext i8 %11 to i32
		%13 = load @nomsg
		%14 = sext i8 %13 to i32
		%15 = icmp ne %12 %14
		br %15, %16, %35
	16:
		%17 = load %m1
		%18 = sext i8 %17 to i32
		%19 = load @id1
		%20 = sext i8 %19 to i32
		%21 = icmp sgt %18 %20
		br %21, %22, %24
	22:
		%23 = load %m1
		store %23, @send1
		br %34
	24:
		%25 = load %m1
		%26 = sext i8 %25 to i32
		%27 = load @id1
		%28 = sext i8 %27 to i32
		%29 = icmp eq %26 %28
		br %29, %30, %31
	30:
		store 1, @st1
		br %33
	31:
		%32 = load %m1
		store %32, @send1
		br %33
	33:
		br %34
	34:
		br %35
	35:
		store 0, @mode1
		br %57
	36:
		%37 = load @send1
		%38 = sext i8 %37 to i32
		%39 = load @nomsg
		%40 = sext i8 %39 to i32
		%41 = icmp ne %38 %40
		br %41, %42, %51
	42:
		%43 = load @p1_new
		%44 = sext i8 %43 to i32
		%45 = load @nomsg
		%46 = sext i8 %45 to i32
		%47 = icmp eq %44 %46
		br %47, %48, %51
	48:
		%49 = load @send1
		%50 = sext i8 %49 to i32
		br %54
	51:
		%52 = load @p1_new
		%53 = sext i8 %52 to i32
		br %54
	54:
		%55 = phi [%50, %48], [%53, %51]
		%56 = trunc i32 %55 to i8
		store %56, @p1_new
		store 1, @mode1
		br %57
	57:
		ret void

*BasicFunctionTypename: "node2" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%m2 = alloca i8, align 1
		%1 = load @nomsg
		store %1, %m2
		%2 = load @mode2
		%3 = trunc i8 %2 to i1
		br %3, %4, %30
	4:
		%5 = load @p1_old
		store %5, %m2
		%6 = load @nomsg
		store %6, @p1_old
		%7 = load %m2
		%8 = sext i8 %7 to i32
		%9 = load @nomsg
		%10 = sext i8 %9 to i32
		%11 = icmp ne %8 %10
		br %11, %12, %29
	12:
		%13 = load %m2
		%14 = sext i8 %13 to i32
		%15 = load @id2
		%16 = sext i8 %15 to i32
		%17 = icmp sgt %14 %16
		br %17, %18, %20
	18:
		%19 = load %m2
		store %19, @send2
		br %28
	20:
		%21 = load %m2
		%22 = sext i8 %21 to i32
		%23 = load @id2
		%24 = sext i8 %23 to i32
		%25 = icmp eq %22 %24
		br %25, %26, %27
	26:
		store 1, @st2
		br %27
	27:
		br %28
	28:
		br %29
	29:
		store 0, @mode2
		br %51
	30:
		%31 = load @send2
		%32 = sext i8 %31 to i32
		%33 = load @nomsg
		%34 = sext i8 %33 to i32
		%35 = icmp ne %32 %34
		br %35, %36, %45
	36:
		%37 = load @p2_new
		%38 = sext i8 %37 to i32
		%39 = load @nomsg
		%40 = sext i8 %39 to i32
		%41 = icmp eq %38 %40
		br %41, %42, %45
	42:
		%43 = load @send2
		%44 = sext i8 %43 to i32
		br %48
	45:
		%46 = load @p2_new
		%47 = sext i8 %46 to i32
		br %48
	48:
		%49 = phi [%44, %42], [%47, %45]
		%50 = trunc i32 %49 to i8
		store %50, @p2_new
		store 1, @mode2
		br %51
	51:
		ret void

*BasicFunctionTypename: "node3" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%m3 = alloca i8, align 1
		%1 = load @nomsg
		store %1, %m3
		%2 = load @mode3
		%3 = trunc i8 %2 to i1
		br %3, %4, %30
	4:
		%5 = load @p2_old
		store %5, %m3
		%6 = load @nomsg
		store %6, @p2_old
		%7 = load %m3
		%8 = sext i8 %7 to i32
		%9 = load @nomsg
		%10 = sext i8 %9 to i32
		%11 = icmp ne %8 %10
		br %11, %12, %29
	12:
		%13 = load %m3
		%14 = sext i8 %13 to i32
		%15 = load @id3
		%16 = sext i8 %15 to i32
		%17 = icmp sgt %14 %16
		br %17, %18, %20
	18:
		%19 = load %m3
		store %19, @send3
		br %28
	20:
		%21 = load %m3
		%22 = sext i8 %21 to i32
		%23 = load @id3
		%24 = sext i8 %23 to i32
		%25 = icmp eq %22 %24
		br %25, %26, %27
	26:
		store 1, @st3
		br %27
	27:
		br %28
	28:
		br %29
	29:
		store 0, @mode3
		br %51
	30:
		%31 = load @send3
		%32 = sext i8 %31 to i32
		%33 = load @nomsg
		%34 = sext i8 %33 to i32
		%35 = icmp ne %32 %34
		br %35, %36, %45
	36:
		%37 = load @p3_new
		%38 = sext i8 %37 to i32
		%39 = load @nomsg
		%40 = sext i8 %39 to i32
		%41 = icmp eq %38 %40
		br %41, %42, %45
	42:
		%43 = load @send3
		%44 = sext i8 %43 to i32
		br %48
	45:
		%46 = load @p3_new
		%47 = sext i8 %46 to i32
		br %48
	48:
		%49 = phi [%44, %42], [%47, %45]
		%50 = trunc i32 %49 to i8
		store %50, @p3_new
		store 1, @mode3
		br %51
	51:
		ret void

*BasicFunctionTypename: "init" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%tmp = alloca i32, align 4
		%1 = load @r1
		%2 = sext i8 %1 to i32
		%3 = icmp eq %2 0
		br %3, %4, %110
	4:
		%5 = load @id1
		%6 = sext i8 %5 to i32
		%7 = icmp sge %6 0
		br %7, %8, %108
	8:
		%9 = load @st1
		%10 = sext i8 %9 to i32
		%11 = icmp eq %10 0
		br %11, %12, %106
	12:
		%13 = load @send1
		%14 = sext i8 %13 to i32
		%15 = load @id1
		%16 = sext i8 %15 to i32
		%17 = icmp eq %14 %16
		br %17, %18, %104
	18:
		%19 = load @mode1
		%20 = trunc i8 %19 to i1
		%21 = zext i1 %20 to i32
		%22 = icmp eq %21 0
		br %22, %23, %102
	23:
		%24 = load @id2
		%25 = sext i8 %24 to i32
		%26 = icmp sge %25 0
		br %26, %27, %100
	27:
		%28 = load @st2
		%29 = sext i8 %28 to i32
		%30 = icmp eq %29 0
		br %30, %31, %98
	31:
		%32 = load @send2
		%33 = sext i8 %32 to i32
		%34 = load @id2
		%35 = sext i8 %34 to i32
		%36 = icmp eq %33 %35
		br %36, %37, %96
	37:
		%38 = load @mode2
		%39 = trunc i8 %38 to i1
		%40 = zext i1 %39 to i32
		%41 = icmp eq %40 0
		br %41, %42, %94
	42:
		%43 = load @id3
		%44 = sext i8 %43 to i32
		%45 = icmp sge %44 0
		br %45, %46, %92
	46:
		%47 = load @st3
		%48 = sext i8 %47 to i32
		%49 = icmp eq %48 0
		br %49, %50, %90
	50:
		%51 = load @send3
		%52 = sext i8 %51 to i32
		%53 = load @id3
		%54 = sext i8 %53 to i32
		%55 = icmp eq %52 %54
		br %55, %56, %88
	56:
		%57 = load @mode3
		%58 = trunc i8 %57 to i1
		%59 = zext i1 %58 to i32
		%60 = icmp eq %59 0
		br %60, %61, %86
	61:
		%62 = load @id1
		%63 = sext i8 %62 to i32
		%64 = load @id2
		%65 = sext i8 %64 to i32
		%66 = icmp ne %63 %65
		br %66, %67, %84
	67:
		%68 = load @id1
		%69 = sext i8 %68 to i32
		%70 = load @id3
		%71 = sext i8 %70 to i32
		%72 = icmp ne %69 %71
		br %72, %73, %82
	73:
		%74 = load @id2
		%75 = sext i8 %74 to i32
		%76 = load @id3
		%77 = sext i8 %76 to i32
		%78 = icmp ne %75 %77
		br %78, %79, %80
	79:
		store 1, %tmp
		br %81
	80:
		store 0, %tmp
		br %81
	81:
		br %83
	82:
		store 0, %tmp
		br %83
	83:
		br %85
	84:
		store 0, %tmp
		br %85
	85:
		br %87
	86:
		store 0, %tmp
		br %87
	87:
		br %89
	88:
		store 0, %tmp
		br %89
	89:
		br %91
	90:
		store 0, %tmp
		br %91
	91:
		br %93
	92:
		store 0, %tmp
		br %93
	93:
		br %95
	94:
		store 0, %tmp
		br %95
	95:
		br %97
	96:
		store 0, %tmp
		br %97
	97:
		br %99
	98:
		store 0, %tmp
		br %99
	99:
		br %101
	100:
		store 0, %tmp
		br %101
	101:
		br %103
	102:
		store 0, %tmp
		br %103
	103:
		br %105
	104:
		store 0, %tmp
		br %105
	105:
		br %107
	106:
		store 0, %tmp
		br %107
	107:
		br %109
	108:
		store 0, %tmp
		br %109
	109:
		br %111
	110:
		store 0, %tmp
		br %111
	111:
		%112 = load %tmp
		ret %112

*BasicFunctionTypename: "check" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%tmp = alloca i32, align 4
		%1 = load @st1
		%2 = sext i8 %1 to i32
		%3 = load @st2
		%4 = sext i8 %3 to i32
		%5 = add %2 %4
		%6 = load @st3
		%7 = sext i8 %6 to i32
		%8 = add %5 %7
		%9 = icmp sle %8 1
		br %9, %10, %48
	10:
		%11 = load @r1
		%12 = sext i8 %11 to i32
		%13 = icmp sge %12 3
		br %13, %14, %15
	14:
		br %26
	15:
		%16 = load @st1
		%17 = sext i8 %16 to i32
		%18 = load @st2
		%19 = sext i8 %18 to i32
		%20 = add %17 %19
		%21 = load @st3
		%22 = sext i8 %21 to i32
		%23 = add %20 %22
		%24 = icmp eq %23 0
		br %24, %25, %45
	25:
		br %26
	26:
		%27 = load @r1
		%28 = sext i8 %27 to i32
		%29 = icmp slt %28 3
		br %29, %30, %31
	30:
		store 1, %tmp
		br %44
	31:
		%32 = load @st1
		%33 = sext i8 %32 to i32
		%34 = load @st2
		%35 = sext i8 %34 to i32
		%36 = add %33 %35
		%37 = load @st3
		%38 = sext i8 %37 to i32
		%39 = add %36 %38
		%40 = icmp eq %39 1
		br %40, %41, %42
	41:
		store 1, %tmp
		br %43
	42:
		store 0, %tmp
		br %43
	43:
		br %44
	44:
		br %46
	45:
		store 0, %tmp
		br %46
	46:
		br %47
	47:
		br %49
	48:
		store 0, %tmp
		br %49
	49:
		%50 = load %tmp
		ret %50

*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		%c1 = alloca i32, align 4
		%i2 = alloca i32, align 4
		store 0, %1
		store 0, %c1
		%2 = call signext i8 @__VERIFIER_nondet_char()
		store %2, @r1
		%3 = call signext i8 @__VERIFIER_nondet_char()
		store %3, @id1
		%4 = call signext i8 @__VERIFIER_nondet_char()
		store %4, @st1
		%5 = call signext i8 @__VERIFIER_nondet_msg_t()
		store %5, @send1
		%6 = call zeroext i1 @__VERIFIER_nondet__Bool()
		%7 = zext i1 %6 to i8
		store %7, @mode1
		%8 = call signext i8 @__VERIFIER_nondet_char()
		store %8, @id2
		%9 = call signext i8 @__VERIFIER_nondet_char()
		store %9, @st2
		%10 = call signext i8 @__VERIFIER_nondet_msg_t()
		store %10, @send2
		%11 = call zeroext i1 @__VERIFIER_nondet__Bool()
		%12 = zext i1 %11 to i8
		store %12, @mode2
		%13 = call signext i8 @__VERIFIER_nondet_char()
		store %13, @id3
		%14 = call signext i8 @__VERIFIER_nondet_char()
		store %14, @st3
		%15 = call signext i8 @__VERIFIER_nondet_msg_t()
		store %15, @send3
		%16 = call zeroext i1 @__VERIFIER_nondet__Bool()
		%17 = zext i1 %16 to i8
		store %17, @mode3
		%18 = call i32 @init()
		store %18, %i2
		%19 = load %i2
		%20 = icmp ne %19 0
		Unnamed Call-Instruction = call BasicVoidType @__VERIFIER_assume(i1 zeroext %20)
		%21 = load @nomsg
		store %21, @p1_old
		%22 = load @nomsg
		store %22, @p1_new
		%23 = load @nomsg
		store %23, @p2_old
		%24 = load @nomsg
		store %24, @p2_new
		%25 = load @nomsg
		store %25, @p3_old
		%26 = load @nomsg
		store %26, @p3_new
		store 0, %i2
		br %27
	27:
		%28 = load %i2
		%29 = icmp slt %28 6
		br %29, %30, %42
	30:
		Unnamed Call-Instruction = call BasicVoidType @node1()
		Unnamed Call-Instruction = call BasicVoidType @node2()
		Unnamed Call-Instruction = call BasicVoidType @node3()
		%31 = load @p1_new
		store %31, @p1_old
		%32 = load @nomsg
		store %32, @p1_new
		%33 = load @p2_new
		store %33, @p2_old
		%34 = load @nomsg
		store %34, @p2_new
		%35 = load @p3_new
		store %35, @p3_old
		%36 = load @nomsg
		store %36, @p3_new
		%37 = call i32 @check()
		store %37, %c1
		%38 = load %c1
		%39 = icmp ne %38 0
		Unnamed Call-Instruction = call BasicVoidType @assert(i1 zeroext %39)
		%40 = load %i2
		%41 = add %40 1
		store %41, %i2
		br %27
	42:
		%43 = load %1
		ret %43

*BasicFunctionTypename: "__VERIFIER_assume" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (arg i1 zeroext) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i8, align 1
		%2 = zext i1 %arg to i8
		store %2, %1
		br %3
	3:
		%4 = load %1
		%5 = trunc i8 %4 to i1
		%6 = xor %5 1
		br %6, %7, %8
	7:
		br %3
	8:
		ret void

*BasicFunctionTypename: "assert" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (arg i1 zeroext) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i8, align 1
		%2 = zext i1 %arg to i8
		store %2, %1
		%3 = load %1
		%4 = trunc i8 %3 to i1
		br %4, %7, %5
	5:
		br %6
	6:
		Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() noreturn
		unreachable
	7:
		ret void


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

(3) LLVMToTerminationGraphProof (EQUIVALENT)
Constructed symbolic execution graph for LLVM program and proved memory safety.
----------------------------------------

(4)
Obligation:
SE Graph
----------------------------------------

(5) SymbolicExecutionGraphToSCCProof (SOUND)
Splitted symbolic execution graph to 3 SCCs.
----------------------------------------

(6)
Complex Obligation (AND)

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

(7)
Obligation:
SCC
----------------------------------------

(8)
Obligation:
SCC
----------------------------------------

(9)
Obligation:
SCC
----------------------------------------

(10) SymbolicExecutionGraphToLassoProof (COMPLETE)
Converted SEGraph to 4 dependent lassos.
----------------------------------------

(11)
Complex Obligation (AND)

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

(12)
Obligation:
Lasso
----------------------------------------

(13)
Obligation:
Lasso
----------------------------------------

(14)
Obligation:
Lasso
----------------------------------------

(15)
Obligation:
Lasso