10.15/3.86 MAYBE 10.15/3.86 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 10.15/3.86 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.15/3.86 10.15/3.86 10.15/3.86 Termination of the given C Problem could not be shown: 10.15/3.86 10.15/3.86 (0) C Problem 10.15/3.86 (1) CToLLVMProof [EQUIVALENT, 166 ms] 10.15/3.86 (2) LLVM problem 10.15/3.86 10.15/3.86 10.15/3.86 ---------------------------------------- 10.15/3.86 10.15/3.86 (0) 10.15/3.86 Obligation: 10.15/3.86 c file /export/starexec/sandbox/benchmark/theBenchmark.c 10.15/3.86 ---------------------------------------- 10.15/3.86 10.15/3.86 (1) CToLLVMProof (EQUIVALENT) 10.15/3.86 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 10.15/3.86 ---------------------------------------- 10.15/3.86 10.15/3.86 (2) 10.15/3.86 Obligation: 10.15/3.86 LLVM Problem 10.15/3.86 10.15/3.86 Aliases: 10.15/3.86 10.15/3.86 Data layout: 10.15/3.86 10.15/3.86 "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" 10.15/3.86 10.15/3.86 Machine: 10.15/3.86 10.15/3.86 "x86_64-pc-linux-gnu" 10.15/3.86 10.15/3.86 Type definitions: 10.15/3.86 10.15/3.86 struct.cell --> BasicStructureType(elementType: i32, elementType: *struct.cell) 10.15/3.86 10.15/3.86 Global variables: 10.15/3.86 10.15/3.86 Name: pc1 initVal: 1 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: null section: null 10.15/3.86 10.15/3.86 Name: pc4 initVal: 1 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: null section: null 10.15/3.86 10.15/3.86 Name: push.t1 initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: INTERNAL section: null 10.15/3.86 10.15/3.86 Name: push.x1 initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: INTERNAL section: null 10.15/3.86 10.15/3.86 Name: S initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: COMMON section: null 10.15/3.86 10.15/3.86 Name: pop.t4 initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: INTERNAL section: null 10.15/3.86 10.15/3.86 Name: pop.x4 initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: INTERNAL section: null 10.15/3.86 10.15/3.86 Name: pop.res4 initVal: 0 type: i32 addrSpace: null alignment: 4 threadLocal: false constant: false linkageType: INTERNAL section: null 10.15/3.86 10.15/3.86 Name: garbage initVal: null type: *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) addrSpace: null alignment: 8 threadLocal: false constant: false linkageType: COMMON section: null 10.15/3.86 10.15/3.86 Function declarations and definitions: 10.15/3.86 10.15/3.86 *BasicFunctionTypename: "malloc" returnParam: *i8 noalias parameters: (i64) variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 *BasicFunctionTypename: "free" returnParam: BasicVoidType parameters: (*i8) variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 *BasicFunctionTypename: "push" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 0: 10.15/3.86 %1 = load @pc1 10.15/3.86 %2 = add %1 1 10.15/3.86 store %2, @pc1 10.15/3.86 switch %1, %28 [1, %3 2, %10 3, %13 4, %15 5, %19 6, %27] 10.15/3.86 3: 10.15/3.86 %4 = call noalias *i8 @malloc(i64 16) nounwind 10.15/3.86 %5 = bitcast *i8 %4 to *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) 10.15/3.86 store %5, @push.x1 10.15/3.86 %6 = load @push.x1 10.15/3.86 %7 = getelementptr %6, 0, 0 10.15/3.86 store 0, %7 10.15/3.86 %8 = load @push.x1 10.15/3.86 %9 = getelementptr %8, 0, 1 10.15/3.86 store null, %9 10.15/3.86 br %28 10.15/3.86 10: 10.15/3.86 %11 = load @push.x1 10.15/3.86 %12 = getelementptr %11, 0, 0 10.15/3.86 store 4, %12 10.15/3.86 br %28 10.15/3.86 13: 10.15/3.86 %14 = load @S 10.15/3.86 store %14, @push.t1 10.15/3.86 br %28 10.15/3.86 15: 10.15/3.86 %16 = load @push.t1 10.15/3.86 %17 = load @push.x1 10.15/3.86 %18 = getelementptr %17, 0, 1 10.15/3.86 store %16, %18 10.15/3.86 br %28 10.15/3.86 19: 10.15/3.86 %20 = load @S 10.15/3.86 %21 = load @push.t1 10.15/3.86 %22 = icmp eq %20 %21 10.15/3.86 br %22, %23, %25 10.15/3.86 23: 10.15/3.86 %24 = load @push.x1 10.15/3.86 store %24, @S 10.15/3.86 br %26 10.15/3.86 25: 10.15/3.86 store 3, @pc1 10.15/3.86 br %26 10.15/3.86 26: 10.15/3.86 br %28 10.15/3.86 27: 10.15/3.86 store 1, @pc1 10.15/3.86 br %28 10.15/3.86 28: 10.15/3.86 ret void 10.15/3.86 10.15/3.86 *BasicFunctionTypename: "pop" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 0: 10.15/3.86 %1 = load @pc4 10.15/3.86 %2 = add %1 1 10.15/3.86 store %2, @pc4 10.15/3.86 switch %1, %30 [1, %3 2, %5 3, %10 4, %14 5, %22] 10.15/3.86 3: 10.15/3.86 %4 = load @S 10.15/3.86 store %4, @pop.t4 10.15/3.86 br %30 10.15/3.86 5: 10.15/3.86 %6 = load @pop.t4 10.15/3.86 %7 = icmp eq %6 null 10.15/3.86 br %7, %8, %9 10.15/3.86 8: 10.15/3.86 store 1, @pc4 10.15/3.86 br %9 10.15/3.86 9: 10.15/3.86 br %30 10.15/3.86 10: 10.15/3.86 %11 = load @pop.t4 10.15/3.86 %12 = getelementptr %11, 0, 1 10.15/3.86 %13 = load %12 10.15/3.86 store %13, @pop.x4 10.15/3.86 br %30 10.15/3.86 14: 10.15/3.86 %15 = load @S 10.15/3.86 %16 = load @pop.t4 10.15/3.86 %17 = icmp eq %15 %16 10.15/3.86 br %17, %18, %20 10.15/3.86 18: 10.15/3.86 %19 = load @pop.x4 10.15/3.86 store %19, @S 10.15/3.86 br %21 10.15/3.86 20: 10.15/3.86 store 1, @pc4 10.15/3.86 br %21 10.15/3.86 21: 10.15/3.86 br %30 10.15/3.86 22: 10.15/3.86 %23 = load @pop.t4 10.15/3.86 %24 = getelementptr %23, 0, 0 10.15/3.86 %25 = load %24 10.15/3.86 store %25, @pop.res4 10.15/3.86 %26 = load @garbage 10.15/3.86 %27 = load @pop.t4 10.15/3.86 %28 = getelementptr %27, 0, 1 10.15/3.86 store %26, %28 10.15/3.86 %29 = load @pop.t4 10.15/3.86 store %29, @garbage 10.15/3.86 store 1, @pc4 10.15/3.86 br %30 10.15/3.86 30: 10.15/3.86 ret void 10.15/3.86 10.15/3.86 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 10.15/3.86 0: 10.15/3.86 %1 = alloca i32, align 4 10.15/3.86 %next = alloca *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell), align 8 10.15/3.86 store 0, %1 10.15/3.86 br %2 10.15/3.86 2: 10.15/3.86 %3 = load @S 10.15/3.86 %4 = icmp ne %3 null 10.15/3.86 br %4, %14, %5 10.15/3.86 5: 10.15/3.86 %6 = load @pc1 10.15/3.86 %7 = icmp ne 1 %6 10.15/3.86 br %7, %14, %8 10.15/3.86 8: 10.15/3.86 %9 = load @pc4 10.15/3.86 %10 = icmp ne 1 %9 10.15/3.86 br %10, %14, %11 10.15/3.86 11: 10.15/3.86 %12 = call i32 @__VERIFIER_nondet_int() 10.15/3.86 %13 = icmp ne %12 0 10.15/3.86 br %14 10.15/3.86 14: 10.15/3.86 %15 = phi [1, %8], [1, %5], [1, %2], [%13, %11] 10.15/3.86 br %15, %16, %22 10.15/3.86 16: 10.15/3.86 %17 = call i32 @__VERIFIER_nondet_int() 10.15/3.86 %18 = icmp ne %17 0 10.15/3.86 br %18, %19, %20 10.15/3.86 19: 10.15/3.86 Unnamed Call-Instruction = call BasicVoidType @push() 10.15/3.86 br %21 10.15/3.86 20: 10.15/3.86 Unnamed Call-Instruction = call BasicVoidType @pop() 10.15/3.86 br %21 10.15/3.86 21: 10.15/3.86 br %2 10.15/3.86 22: 10.15/3.86 br %23 10.15/3.86 23: 10.15/3.86 %24 = load @garbage 10.15/3.86 %25 = icmp ne %24 null 10.15/3.86 br %25, %26, %33 10.15/3.86 26: 10.15/3.86 %27 = load @garbage 10.15/3.86 %28 = getelementptr %27, 0, 1 10.15/3.86 %29 = load %28 10.15/3.86 store %29, %next 10.15/3.86 %30 = load @garbage 10.15/3.86 %31 = bitcast *BasicTypeName typeName: struct.cellBasicStructureType(elementType: i32, elementType: *struct.cell) %30 to *i8 10.15/3.86 Unnamed Call-Instruction = call BasicVoidType @free(*i8 %31) nounwind 10.15/3.86 %32 = load %next 10.15/3.86 store %32, @garbage 10.15/3.86 br %23 10.15/3.86 33: 10.15/3.86 %34 = load @garbage 10.15/3.86 %35 = icmp ne %34 null 10.15/3.86 %36 = xor %35 1 10.15/3.86 %37 = xor %36 1 10.15/3.86 %38 = zext i1 %37 to i32 10.15/3.86 ret %38 10.15/3.86 10.15/3.86 10.15/3.86 Analyze Termination of all function calls matching the pattern: 10.15/3.86 main() 10.34/3.93 EOF