./Ultimate.py --spec ../../sv-benchmarks/c/properties/unreach-call.prp --file ../../sv-benchmarks/c/ldv-sets/test_mutex.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 826ab2ba Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/ldv-sets/test_mutex.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash cee8df08ffad3eb9e493a0be0076215dd3a59bce6d2370397b3bb712a7fad867 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 04:34:23,615 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 04:34:23,691 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Default.epf [2024-11-14 04:34:23,696 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 04:34:23,697 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 04:34:23,723 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 04:34:23,724 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 04:34:23,724 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 04:34:23,724 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 04:34:23,724 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 04:34:23,725 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Use the RCFG-of-the-future interface=true [2024-11-14 04:34:23,725 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 04:34:23,726 INFO L151 SettingsManager]: Preferences of Sifa differ from their defaults: [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * Simplification Technique=POLY_PAC [2024-11-14 04:34:23,726 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-14 04:34:23,726 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 04:34:23,727 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 04:34:23,727 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:34:23,728 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2024-11-14 04:34:23,728 INFO L153 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> cee8df08ffad3eb9e493a0be0076215dd3a59bce6d2370397b3bb712a7fad867 [2024-11-14 04:34:24,016 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 04:34:24,028 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 04:34:24,033 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 04:34:24,034 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 04:34:24,036 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 04:34:24,037 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/ldv-sets/test_mutex.i Unable to find full path for "g++" [2024-11-14 04:34:26,152 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 04:34:26,512 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 04:34:26,513 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i [2024-11-14 04:34:26,534 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/ae49caa6a/772f1a3de64846939e76a6a3223e4652/FLAG5cedf1021 [2024-11-14 04:34:26,555 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/ae49caa6a/772f1a3de64846939e76a6a3223e4652 [2024-11-14 04:34:26,558 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 04:34:26,561 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 04:34:26,564 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 04:34:26,564 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 04:34:26,568 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 04:34:26,569 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:34:26" (1/1) ... [2024-11-14 04:34:26,572 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@26b4e12a and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:26, skipping insertion in model container [2024-11-14 04:34:26,572 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:34:26" (1/1) ... [2024-11-14 04:34:26,616 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:34:27,065 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25842,25855] [2024-11-14 04:34:27,070 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25967,25980] [2024-11-14 04:34:27,073 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[26082,26095] [2024-11-14 04:34:27,081 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:34:27,098 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 04:34:27,158 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25842,25855] [2024-11-14 04:34:27,160 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25967,25980] [2024-11-14 04:34:27,161 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[26082,26095] [2024-11-14 04:34:27,162 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:34:27,194 INFO L204 MainTranslator]: Completed translation [2024-11-14 04:34:27,195 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27 WrapperNode [2024-11-14 04:34:27,195 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 04:34:27,196 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 04:34:27,196 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 04:34:27,197 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 04:34:27,204 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,217 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,250 INFO L138 Inliner]: procedures = 139, calls = 57, calls flagged for inlining = 14, calls inlined = 13, statements flattened = 139 [2024-11-14 04:34:27,254 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 04:34:27,255 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 04:34:27,255 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 04:34:27,255 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 04:34:27,263 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,263 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,271 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,272 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,289 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,297 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,302 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,303 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,311 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 04:34:27,312 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 04:34:27,312 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 04:34:27,312 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 04:34:27,317 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (1/1) ... [2024-11-14 04:34:27,326 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:34:27,344 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:34:27,357 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 04:34:27,365 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 04:34:27,388 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2024-11-14 04:34:27,389 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2024-11-14 04:34:27,389 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_unlock [2024-11-14 04:34:27,389 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_unlock [2024-11-14 04:34:27,389 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-14 04:34:27,389 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_lock [2024-11-14 04:34:27,389 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_lock [2024-11-14 04:34:27,389 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 04:34:27,389 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2024-11-14 04:34:27,390 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2024-11-14 04:34:27,390 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2024-11-14 04:34:27,390 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2024-11-14 04:34:27,390 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 04:34:27,390 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2024-11-14 04:34:27,390 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2024-11-14 04:34:27,391 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2024-11-14 04:34:27,391 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2024-11-14 04:34:27,391 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 04:34:27,391 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 04:34:27,601 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 04:34:27,603 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 04:34:27,962 INFO L? ?]: Removed 73 outVars from TransFormulas that were not future-live. [2024-11-14 04:34:27,962 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 04:34:28,093 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 04:34:28,093 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 04:34:28,093 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:34:28 BoogieIcfgContainer [2024-11-14 04:34:28,094 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 04:34:28,110 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 04:34:28,111 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 04:34:28,115 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 04:34:28,116 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 04:34:26" (1/3) ... [2024-11-14 04:34:28,116 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c7ef813 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:34:28, skipping insertion in model container [2024-11-14 04:34:28,117 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:34:27" (2/3) ... [2024-11-14 04:34:28,117 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1c7ef813 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:34:28, skipping insertion in model container [2024-11-14 04:34:28,117 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:34:28" (3/3) ... [2024-11-14 04:34:28,119 INFO L112 eAbstractionObserver]: Analyzing ICFG test_mutex.i [2024-11-14 04:34:28,136 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 04:34:28,138 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG test_mutex.i that has 6 procedures, 49 locations, 1 initial locations, 2 loop locations, and 3 error locations. [2024-11-14 04:34:28,193 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 04:34:28,210 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@bdfb652, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 04:34:28,210 INFO L334 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2024-11-14 04:34:28,215 INFO L276 IsEmpty]: Start isEmpty. Operand has 49 states, 29 states have (on average 1.3448275862068966) internal successors, (39), 32 states have internal predecessors, (39), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:34:28,223 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2024-11-14 04:34:28,223 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:34:28,224 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:34:28,224 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:34:28,229 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:34:28,230 INFO L85 PathProgramCache]: Analyzing trace with hash -1341091286, now seen corresponding path program 1 times [2024-11-14 04:34:28,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:34:28,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1061233562] [2024-11-14 04:34:28,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:34:28,239 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:34:28,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:34:28,617 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:34:28,618 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:34:28,618 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1061233562] [2024-11-14 04:34:28,622 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1061233562] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:34:28,622 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:34:28,622 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:34:28,624 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [80047343] [2024-11-14 04:34:28,624 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:34:28,628 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:34:28,629 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:34:28,651 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:34:28,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:34:28,654 INFO L87 Difference]: Start difference. First operand has 49 states, 29 states have (on average 1.3448275862068966) internal successors, (39), 32 states have internal predecessors, (39), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:34:28,783 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:34:28,784 INFO L93 Difference]: Finished difference Result 96 states and 124 transitions. [2024-11-14 04:34:28,785 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:34:28,787 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 19 [2024-11-14 04:34:28,788 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:34:28,797 INFO L225 Difference]: With dead ends: 96 [2024-11-14 04:34:28,798 INFO L226 Difference]: Without dead ends: 51 [2024-11-14 04:34:28,802 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:34:28,807 INFO L432 NwaCegarLoop]: 46 mSDtfsCounter, 0 mSDsluCounter, 90 mSDsCounter, 0 mSdLazyCounter, 37 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 136 SdHoareTripleChecker+Invalid, 37 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 37 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2024-11-14 04:34:28,808 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 136 Invalid, 37 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 37 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2024-11-14 04:34:28,823 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 51 states. [2024-11-14 04:34:28,848 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 51 to 51. [2024-11-14 04:34:28,850 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 31 states have (on average 1.1935483870967742) internal successors, (37), 33 states have internal predecessors, (37), 11 states have call successors, (11), 5 states have call predecessors, (11), 6 states have return successors, (14), 12 states have call predecessors, (14), 11 states have call successors, (14) [2024-11-14 04:34:28,857 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 62 transitions. [2024-11-14 04:34:28,860 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 62 transitions. Word has length 19 [2024-11-14 04:34:28,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:34:28,861 INFO L471 AbstractCegarLoop]: Abstraction has 51 states and 62 transitions. [2024-11-14 04:34:28,862 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:34:28,862 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 62 transitions. [2024-11-14 04:34:28,863 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2024-11-14 04:34:28,864 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:34:28,864 INFO L215 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:34:28,865 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2024-11-14 04:34:28,865 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:34:28,866 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:34:28,866 INFO L85 PathProgramCache]: Analyzing trace with hash -1855242611, now seen corresponding path program 1 times [2024-11-14 04:34:28,866 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:34:28,867 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1084308982] [2024-11-14 04:34:28,867 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:34:28,868 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:34:28,917 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:34:29,492 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:34:29,493 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:34:29,493 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1084308982] [2024-11-14 04:34:29,494 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1084308982] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:34:29,494 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:34:29,494 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2024-11-14 04:34:29,494 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1709894497] [2024-11-14 04:34:29,494 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:34:29,496 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:34:29,496 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:34:29,497 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:34:29,497 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:34:29,497 INFO L87 Difference]: Start difference. First operand 51 states and 62 transitions. Second operand has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:34:30,031 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:34:30,032 INFO L93 Difference]: Finished difference Result 145 states and 192 transitions. [2024-11-14 04:34:30,032 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-14 04:34:30,032 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 20 [2024-11-14 04:34:30,033 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:34:30,034 INFO L225 Difference]: With dead ends: 145 [2024-11-14 04:34:30,035 INFO L226 Difference]: Without dead ends: 100 [2024-11-14 04:34:30,036 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 3 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2024-11-14 04:34:30,036 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 59 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 135 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 155 SdHoareTripleChecker+Invalid, 137 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 135 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2024-11-14 04:34:30,037 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [59 Valid, 155 Invalid, 137 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 135 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2024-11-14 04:34:30,037 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 100 states. [2024-11-14 04:34:30,055 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 100 to 82. [2024-11-14 04:34:30,056 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 50 states have (on average 1.24) internal successors, (62), 54 states have internal predecessors, (62), 18 states have call successors, (18), 9 states have call predecessors, (18), 11 states have return successors, (26), 18 states have call predecessors, (26), 18 states have call successors, (26) [2024-11-14 04:34:30,058 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 106 transitions. [2024-11-14 04:34:30,058 INFO L78 Accepts]: Start accepts. Automaton has 82 states and 106 transitions. Word has length 20 [2024-11-14 04:34:30,058 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:34:30,059 INFO L471 AbstractCegarLoop]: Abstraction has 82 states and 106 transitions. [2024-11-14 04:34:30,059 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:34:30,059 INFO L276 IsEmpty]: Start isEmpty. Operand 82 states and 106 transitions. [2024-11-14 04:34:30,061 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2024-11-14 04:34:30,061 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:34:30,061 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:34:30,061 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2024-11-14 04:34:30,061 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:34:30,062 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:34:30,062 INFO L85 PathProgramCache]: Analyzing trace with hash 970954834, now seen corresponding path program 1 times [2024-11-14 04:34:30,062 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:34:30,062 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [939183750] [2024-11-14 04:34:30,062 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:34:30,063 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:34:30,169 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:34:34,500 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 10 proven. 8 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2024-11-14 04:34:34,500 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:34:34,500 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [939183750] [2024-11-14 04:34:34,501 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [939183750] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:34:34,501 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1468260512] [2024-11-14 04:34:34,501 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:34:34,501 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:34:34,501 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:34:34,504 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:34:34,506 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-14 04:34:34,684 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:34:34,691 INFO L255 TraceCheckSpWp]: Trace formula consists of 370 conjuncts, 129 conjuncts are in the unsatisfiable core [2024-11-14 04:34:34,702 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:34:35,052 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2024-11-14 04:34:35,054 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 17 treesize of output 21 [2024-11-14 04:34:35,400 INFO L349 Elim1Store]: treesize reduction 8, result has 52.9 percent of original size [2024-11-14 04:34:35,400 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 16 treesize of output 18 [2024-11-14 04:34:36,337 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 44 [2024-11-14 04:34:36,350 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2024-11-14 04:34:36,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 51 [2024-11-14 04:34:36,391 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2024-11-14 04:34:36,422 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 44 [2024-11-14 04:34:36,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2024-11-14 04:34:36,472 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 29 treesize of output 37 [2024-11-14 04:34:36,480 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:34:36,484 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 32 treesize of output 17 [2024-11-14 04:34:36,488 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:34:36,501 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 37 [2024-11-14 04:34:36,512 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 38 [2024-11-14 04:34:37,318 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:34:38,810 INFO L349 Elim1Store]: treesize reduction 576, result has 35.1 percent of original size [2024-11-14 04:34:38,810 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 7 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 10 new quantified variables, introduced 20 case distinctions, treesize of input 1838 treesize of output 1574 [2024-11-14 04:34:39,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-14 04:34:39,526 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 90 treesize of output 84 [2024-11-14 04:34:40,120 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:34:40,121 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:34:40,125 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:34:40,134 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 206 treesize of output 156 [2024-11-14 04:34:40,139 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-14 04:34:40,151 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 46 treesize of output 39 [2024-11-14 04:34:40,519 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 1 [2024-11-14 04:34:40,761 WARN L214 Elim1Store]: Array PQE input equivalent to false [2024-11-14 04:34:40,998 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:34:41,000 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:34:41,007 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:34:41,009 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 179 treesize of output 150 [2024-11-14 04:34:41,015 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-14 04:34:41,025 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 45 treesize of output 38 [2024-11-14 04:34:46,300 INFO L134 CoverageAnalysis]: Checked inductivity of 22 backedges. 10 proven. 7 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-14 04:34:46,300 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:34:47,701 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:34:47,701 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 62 treesize of output 50 [2024-11-14 04:34:47,727 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:34:47,728 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 59 treesize of output 63 [2024-11-14 04:34:47,742 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 33 [2024-11-14 04:34:47,801 WARN L851 $PredicateComparison]: unable to prove that (and (or (< |c_ULTIMATE.start_foo_~m2~0#1.offset| 4) (forall ((|v___ldv_list_add_#in~new.base_9| Int) (v_ArrVal_115 (Array Int Int)) (v_ArrVal_117 Int)) (not (= |c_ULTIMATE.start_foo_~m2~0#1.base| (select (select (let ((.cse0 (let ((.cse2 (store |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9| (store (select |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9|) 0 |c_ULTIMATE.start_foo_~m1~0#1.base|)))) (let ((.cse1 (select (select .cse2 |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|))) (store (store |c_#memory_$Pointer$.base| .cse1 v_ArrVal_115) |v___ldv_list_add_#in~new.base_9| (store (store (select (store .cse2 .cse1 v_ArrVal_115) |v___ldv_list_add_#in~new.base_9|) 4 v_ArrVal_117) 8 |c_~#mutexes~0.base|)))))) (store .cse0 |c_~#mutexes~0.base| (store (select .cse0 |c_~#mutexes~0.base|) |c_~#mutexes~0.offset| |v___ldv_list_add_#in~new.base_9|))) |v___ldv_list_add_#in~new.base_9|) 0))))) (forall ((|v___ldv_list_add_#in~new.base_9| Int) (v_ArrVal_115 (Array Int Int))) (or (not (= (select (select (let ((.cse3 (store |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9| (store (select |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9|) 0 |c_ULTIMATE.start_foo_~m1~0#1.base|)))) (store .cse3 (select (select .cse3 |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) v_ArrVal_115)) |v___ldv_list_add_#in~new.base_9|) 0) |c_ULTIMATE.start_foo_~m2~0#1.base|)) (= |c_~#mutexes~0.base| |v___ldv_list_add_#in~new.base_9|))) (or (forall ((|v___ldv_list_add_#in~new.base_9| Int) (v_ArrVal_115 (Array Int Int))) (not (= (select (select (let ((.cse4 (store |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9| (store (select |c_#memory_$Pointer$.base| |v___ldv_list_add_#in~new.base_9|) 0 |c_ULTIMATE.start_foo_~m1~0#1.base|)))) (store .cse4 (select (select .cse4 |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) v_ArrVal_115)) |v___ldv_list_add_#in~new.base_9|) 0) |c_ULTIMATE.start_foo_~m2~0#1.base|))) (= |c_~#mutexes~0.offset| 0))) is different from false [2024-11-14 04:34:47,804 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1468260512] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:34:47,804 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1693459481] [2024-11-14 04:34:47,825 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2024-11-14 04:34:47,825 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:34:47,829 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:34:47,834 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:34:47,834 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:34:48,831 INFO L197 IcfgInterpreter]: Interpreting procedure mutex_lock with input of size 12 for LOIs [2024-11-14 04:34:49,094 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 75 for LOIs [2024-11-14 04:34:49,120 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 26 for LOIs [2024-11-14 04:34:49,131 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 16 for LOIs [2024-11-14 04:34:49,158 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:35:06,695 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '857#(and (exists ((|v_mutex_lock_#t~ret32#1_16| Int)) (and (<= 0 |v_mutex_lock_#t~ret32#1_16|) (<= |v_mutex_lock_#t~ret32#1_16| 1) (not (= |v_mutex_lock_#t~ret32#1_16| 0)))) (<= 1 |#StackHeapBarrier|) (= |mutex_lock_#in~m#1.offset| 0) (= |mutex_lock_#in~m#1.base| |mutex_lock_~m#1.base|) (= |~#mutexes~0.base| 3) (= |~#mutexes~0.offset| 0) (= |mutex_lock_~m#1.offset| 0))' at error location [2024-11-14 04:35:06,696 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:35:06,696 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:35:06,696 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 25] total 51 [2024-11-14 04:35:06,696 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1797143230] [2024-11-14 04:35:06,696 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:35:06,697 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 51 states [2024-11-14 04:35:06,697 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:35:06,698 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 51 interpolants. [2024-11-14 04:35:06,701 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=333, Invalid=6111, Unknown=40, NotChecked=158, Total=6642 [2024-11-14 04:35:06,702 INFO L87 Difference]: Start difference. First operand 82 states and 106 transitions. Second operand has 51 states, 30 states have (on average 1.8) internal successors, (54), 36 states have internal predecessors, (54), 17 states have call successors, (18), 9 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2024-11-14 04:35:24,461 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.85s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-14 04:35:27,260 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:35:27,260 INFO L93 Difference]: Finished difference Result 175 states and 224 transitions. [2024-11-14 04:35:27,261 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2024-11-14 04:35:27,261 INFO L78 Accepts]: Start accepts. Automaton has has 51 states, 30 states have (on average 1.8) internal successors, (54), 36 states have internal predecessors, (54), 17 states have call successors, (18), 9 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) Word has length 47 [2024-11-14 04:35:27,261 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:35:27,266 INFO L225 Difference]: With dead ends: 175 [2024-11-14 04:35:27,266 INFO L226 Difference]: Without dead ends: 129 [2024-11-14 04:35:27,274 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 178 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 118 ConstructedPredicates, 1 IntricatePredicates, 1 DeprecatedPredicates, 3014 ImplicationChecksByTransitivity, 34.4s TimeCoverageRelationStatistics Valid=769, Invalid=13207, Unknown=70, NotChecked=234, Total=14280 [2024-11-14 04:35:27,275 INFO L432 NwaCegarLoop]: 47 mSDtfsCounter, 329 mSDsluCounter, 961 mSDsCounter, 0 mSdLazyCounter, 3062 mSolverCounterSat, 127 mSolverCounterUnsat, 94 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 331 SdHoareTripleChecker+Valid, 1008 SdHoareTripleChecker+Invalid, 3283 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 127 IncrementalHoareTripleChecker+Valid, 3062 IncrementalHoareTripleChecker+Invalid, 94 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.9s IncrementalHoareTripleChecker+Time [2024-11-14 04:35:27,276 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [331 Valid, 1008 Invalid, 3283 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [127 Valid, 3062 Invalid, 94 Unknown, 0 Unchecked, 10.9s Time] [2024-11-14 04:35:27,278 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 129 states. [2024-11-14 04:35:27,320 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 129 to 105. [2024-11-14 04:35:27,321 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 66 states have (on average 1.2727272727272727) internal successors, (84), 73 states have internal predecessors, (84), 20 states have call successors, (20), 10 states have call predecessors, (20), 16 states have return successors, (32), 21 states have call predecessors, (32), 20 states have call successors, (32) [2024-11-14 04:35:27,322 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 136 transitions. [2024-11-14 04:35:27,323 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 136 transitions. Word has length 47 [2024-11-14 04:35:27,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:35:27,323 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 136 transitions. [2024-11-14 04:35:27,325 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 51 states, 30 states have (on average 1.8) internal successors, (54), 36 states have internal predecessors, (54), 17 states have call successors, (18), 9 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 15 states have call successors, (16) [2024-11-14 04:35:27,325 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 136 transitions. [2024-11-14 04:35:27,327 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2024-11-14 04:35:27,328 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:35:27,328 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:35:27,351 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2024-11-14 04:35:27,533 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2024-11-14 04:35:27,534 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:35:27,535 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:35:27,535 INFO L85 PathProgramCache]: Analyzing trace with hash -1084828754, now seen corresponding path program 1 times [2024-11-14 04:35:27,535 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:35:27,535 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2089543470] [2024-11-14 04:35:27,535 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:27,536 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:35:27,608 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:33,100 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 11 proven. 10 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-14 04:35:33,101 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:35:33,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2089543470] [2024-11-14 04:35:33,101 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [2089543470] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:35:33,101 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1520940690] [2024-11-14 04:35:33,101 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:35:33,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:35:33,101 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:35:33,103 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:35:33,104 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-14 04:35:33,288 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:35:33,291 INFO L255 TraceCheckSpWp]: Trace formula consists of 380 conjuncts, 111 conjuncts are in the unsatisfiable core [2024-11-14 04:35:33,297 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:35:33,658 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2024-11-14 04:35:33,658 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 16 [2024-11-14 04:35:33,760 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2024-11-14 04:35:33,761 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 16 [2024-11-14 04:35:35,456 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:35,615 INFO L349 Elim1Store]: treesize reduction 47, result has 52.5 percent of original size [2024-11-14 04:35:35,615 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 140 treesize of output 180 [2024-11-14 04:35:35,685 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2024-11-14 04:35:35,685 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 67 treesize of output 71 [2024-11-14 04:35:35,946 INFO L349 Elim1Store]: treesize reduction 52, result has 40.2 percent of original size [2024-11-14 04:35:35,946 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 108 treesize of output 224 [2024-11-14 04:35:36,007 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:35:36,038 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-14 04:35:36,336 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,337 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,355 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,355 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,356 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 24 [2024-11-14 04:35:36,376 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2024-11-14 04:35:36,443 WARN L200 Elim1Store]: Array PQE input equivalent to false [2024-11-14 04:35:36,659 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,661 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:36,668 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 190 treesize of output 157 [2024-11-14 04:35:36,704 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:36,710 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:36,754 INFO L349 Elim1Store]: treesize reduction 118, result has 10.6 percent of original size [2024-11-14 04:35:36,755 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 8 case distinctions, treesize of input 120 treesize of output 80 [2024-11-14 04:35:37,086 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:37,094 INFO L349 Elim1Store]: treesize reduction 61, result has 1.6 percent of original size [2024-11-14 04:35:37,094 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 52 treesize of output 3 [2024-11-14 04:35:37,145 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:37,378 INFO L349 Elim1Store]: treesize reduction 68, result has 50.4 percent of original size [2024-11-14 04:35:37,378 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 5 new quantified variables, introduced 8 case distinctions, treesize of input 144 treesize of output 267 [2024-11-14 04:35:37,604 INFO L349 Elim1Store]: treesize reduction 28, result has 49.1 percent of original size [2024-11-14 04:35:37,605 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 67 treesize of output 170 [2024-11-14 04:35:37,973 INFO L349 Elim1Store]: treesize reduction 28, result has 49.1 percent of original size [2024-11-14 04:35:37,973 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 51 treesize of output 94 [2024-11-14 04:35:38,229 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2024-11-14 04:35:38,229 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 67 treesize of output 71 [2024-11-14 04:35:38,259 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 160 treesize of output 126 [2024-11-14 04:35:38,412 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:38,414 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:38,437 INFO L349 Elim1Store]: treesize reduction 52, result has 1.9 percent of original size [2024-11-14 04:35:38,437 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 4 case distinctions, treesize of input 113 treesize of output 55 [2024-11-14 04:35:38,622 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:38,624 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:38,625 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 67 treesize of output 7 [2024-11-14 04:35:39,106 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:39,118 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:39,122 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:39,123 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 231 treesize of output 183 [2024-11-14 04:35:39,651 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:39,652 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 92 treesize of output 60 [2024-11-14 04:35:39,946 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:39,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 113 treesize of output 79 [2024-11-14 04:35:40,155 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,158 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,275 INFO L349 Elim1Store]: treesize reduction 34, result has 55.8 percent of original size [2024-11-14 04:35:40,275 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 4 new quantified variables, introduced 5 case distinctions, treesize of input 72 treesize of output 111 [2024-11-14 04:35:40,341 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2024-11-14 04:35:40,341 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 72 treesize of output 71 [2024-11-14 04:35:40,370 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:35:40,513 INFO L349 Elim1Store]: treesize reduction 40, result has 49.4 percent of original size [2024-11-14 04:35:40,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 193 treesize of output 283 [2024-11-14 04:35:40,618 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,630 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,640 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,648 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,650 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,659 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,671 INFO L349 Elim1Store]: treesize reduction 97, result has 1.0 percent of original size [2024-11-14 04:35:40,671 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 7 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 82 treesize of output 42 [2024-11-14 04:35:40,705 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:40,705 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 73 treesize of output 49 [2024-11-14 04:35:40,727 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:40,735 INFO L349 Elim1Store]: treesize reduction 53, result has 1.9 percent of original size [2024-11-14 04:35:40,735 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 44 treesize of output 3 [2024-11-14 04:35:41,005 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 14 treesize of output 13 [2024-11-14 04:35:41,031 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2024-11-14 04:35:41,031 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 94 treesize of output 95 [2024-11-14 04:35:41,041 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:41,055 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 47 treesize of output 36 [2024-11-14 04:35:44,255 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 37 treesize of output 33 [2024-11-14 04:35:44,310 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 83 treesize of output 73 [2024-11-14 04:35:44,621 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 98 treesize of output 92 [2024-11-14 04:35:44,930 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 85 treesize of output 75 [2024-11-14 04:35:45,076 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:45,077 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:45,077 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 3 [2024-11-14 04:35:45,187 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:45,188 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:45,189 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:45,189 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:45,190 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 3 [2024-11-14 04:35:45,208 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:45,208 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 26 treesize of output 10 [2024-11-14 04:35:45,363 INFO L349 Elim1Store]: treesize reduction 154, result has 33.3 percent of original size [2024-11-14 04:35:45,363 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 3 case distinctions, treesize of input 44 treesize of output 84 [2024-11-14 04:35:45,379 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 50 [2024-11-14 04:35:45,672 INFO L349 Elim1Store]: treesize reduction 132, result has 27.9 percent of original size [2024-11-14 04:35:45,672 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 111 treesize of output 104 [2024-11-14 04:35:45,709 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 58 treesize of output 50 [2024-11-14 04:35:45,835 INFO L349 Elim1Store]: treesize reduction 247, result has 12.7 percent of original size [2024-11-14 04:35:45,835 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 5 case distinctions, treesize of input 138 treesize of output 128 [2024-11-14 04:35:45,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 50 treesize of output 42 [2024-11-14 04:35:46,273 INFO L349 Elim1Store]: treesize reduction 319, result has 0.3 percent of original size [2024-11-14 04:35:46,273 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 4 case distinctions, treesize of input 67 treesize of output 1 [2024-11-14 04:35:46,305 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:35:46,305 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:35:46,312 INFO L349 Elim1Store]: treesize reduction 97, result has 1.0 percent of original size [2024-11-14 04:35:46,312 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 38 treesize of output 1 [2024-11-14 04:35:52,035 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 3234 treesize of output 3134 [2024-11-14 04:35:52,082 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 3451 treesize of output 3271 [2024-11-14 04:35:52,106 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1092 treesize of output 1086 [2024-11-14 04:35:52,120 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 1086 treesize of output 1084 [2024-11-14 04:35:52,285 INFO L349 Elim1Store]: treesize reduction 4, result has 66.7 percent of original size [2024-11-14 04:35:52,285 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 1090 treesize of output 1078 [2024-11-14 04:35:57,967 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 5 proven. 19 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-14 04:35:57,967 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-14 04:36:00,374 INFO L349 Elim1Store]: treesize reduction 122, result has 44.8 percent of original size [2024-11-14 04:36:00,374 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 3 case distinctions, treesize of input 208 treesize of output 225 [2024-11-14 04:36:00,411 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:36:00,411 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 891 treesize of output 884 [2024-11-14 04:36:00,485 INFO L349 Elim1Store]: treesize reduction 15, result has 61.5 percent of original size [2024-11-14 04:36:00,485 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 278 treesize of output 286 [2024-11-14 04:36:00,498 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 334 treesize of output 310 [2024-11-14 04:36:00,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 121 treesize of output 113 [2024-11-14 04:36:01,046 INFO L349 Elim1Store]: treesize reduction 24, result has 17.2 percent of original size [2024-11-14 04:36:01,047 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 30 treesize of output 27 [2024-11-14 04:36:01,080 INFO L349 Elim1Store]: treesize reduction 24, result has 17.2 percent of original size [2024-11-14 04:36:01,080 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 3 case distinctions, treesize of input 23 treesize of output 24 [2024-11-14 04:36:01,094 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:36:01,095 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 17 treesize of output 9 [2024-11-14 04:36:01,114 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:36:01,114 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 20 [2024-11-14 04:36:01,132 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:36:01,132 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 22 [2024-11-14 04:36:01,174 INFO L349 Elim1Store]: treesize reduction 10, result has 47.4 percent of original size [2024-11-14 04:36:01,175 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 23 [2024-11-14 04:36:01,219 INFO L349 Elim1Store]: treesize reduction 10, result has 47.4 percent of original size [2024-11-14 04:36:01,219 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 32 treesize of output 34 [2024-11-14 04:36:01,231 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 74 treesize of output 54 [2024-11-14 04:36:01,241 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2024-11-14 04:36:01,241 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 54 treesize of output 42 [2024-11-14 04:36:01,545 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1520940690] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:36:01,545 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [25956770] [2024-11-14 04:36:01,548 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2024-11-14 04:36:01,548 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:36:01,548 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:36:01,549 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:36:01,549 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:36:02,055 INFO L197 IcfgInterpreter]: Interpreting procedure mutex_lock with input of size 12 for LOIs [2024-11-14 04:36:02,251 INFO L197 IcfgInterpreter]: Interpreting procedure __ldv_list_add with input of size 77 for LOIs [2024-11-14 04:36:02,263 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_successful_malloc with input of size 26 for LOIs [2024-11-14 04:36:02,274 INFO L197 IcfgInterpreter]: Interpreting procedure ldv_is_in_set with input of size 16 for LOIs [2024-11-14 04:36:02,324 INFO L180 IcfgInterpreter]: Interpretation finished [2024-11-14 04:36:22,204 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1619#(and (<= 1 |#StackHeapBarrier|) (= |mutex_lock_#in~m#1.offset| 0) (= |mutex_lock_#in~m#1.base| |mutex_lock_~m#1.base|) (= |~#mutexes~0.base| 3) (= |~#mutexes~0.offset| 0) (exists ((|v_mutex_lock_#t~ret32#1_25| Int)) (and (<= |v_mutex_lock_#t~ret32#1_25| 1) (not (= |v_mutex_lock_#t~ret32#1_25| 0)) (<= 0 |v_mutex_lock_#t~ret32#1_25|))) (= |mutex_lock_~m#1.offset| 0))' at error location [2024-11-14 04:36:22,204 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2024-11-14 04:36:22,204 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2024-11-14 04:36:22,204 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [28, 21] total 48 [2024-11-14 04:36:22,204 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [872031083] [2024-11-14 04:36:22,204 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2024-11-14 04:36:22,205 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 48 states [2024-11-14 04:36:22,205 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:36:22,206 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 48 interpolants. [2024-11-14 04:36:22,208 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=306, Invalid=5523, Unknown=23, NotChecked=0, Total=5852 [2024-11-14 04:36:22,209 INFO L87 Difference]: Start difference. First operand 105 states and 136 transitions. Second operand has 48 states, 35 states have (on average 1.6857142857142857) internal successors, (59), 38 states have internal predecessors, (59), 13 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 13 states have call successors, (16) [2024-11-14 04:36:32,552 WARN L286 SmtUtils]: Spent 5.33s on a formula simplification. DAG size of input: 405 DAG size of output: 378 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:37:05,155 WARN L286 SmtUtils]: Spent 6.59s on a formula simplification. DAG size of input: 395 DAG size of output: 371 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:37:14,112 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:14,113 INFO L93 Difference]: Finished difference Result 285 states and 368 transitions. [2024-11-14 04:37:14,113 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 52 states. [2024-11-14 04:37:14,113 INFO L78 Accepts]: Start accepts. Automaton has has 48 states, 35 states have (on average 1.6857142857142857) internal successors, (59), 38 states have internal predecessors, (59), 13 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 13 states have call successors, (16) Word has length 49 [2024-11-14 04:37:14,114 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:14,116 INFO L225 Difference]: With dead ends: 285 [2024-11-14 04:37:14,116 INFO L226 Difference]: Without dead ends: 166 [2024-11-14 04:37:14,122 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 202 GetRequests, 82 SyntacticMatches, 0 SemanticMatches, 120 ConstructedPredicates, 0 IntricatePredicates, 1 DeprecatedPredicates, 3843 ImplicationChecksByTransitivity, 73.0s TimeCoverageRelationStatistics Valid=1032, Invalid=13673, Unknown=57, NotChecked=0, Total=14762 [2024-11-14 04:37:14,123 INFO L432 NwaCegarLoop]: 55 mSDtfsCounter, 451 mSDsluCounter, 1004 mSDsCounter, 0 mSdLazyCounter, 3056 mSolverCounterSat, 171 mSolverCounterUnsat, 50 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 12.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 458 SdHoareTripleChecker+Valid, 1059 SdHoareTripleChecker+Invalid, 3277 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.1s SdHoareTripleChecker+Time, 171 IncrementalHoareTripleChecker+Valid, 3056 IncrementalHoareTripleChecker+Invalid, 50 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 12.7s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:14,124 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [458 Valid, 1059 Invalid, 3277 Unknown, 0 Unchecked, 0.1s Time], IncrementalHoareTripleChecker [171 Valid, 3056 Invalid, 50 Unknown, 0 Unchecked, 12.7s Time] [2024-11-14 04:37:14,125 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 166 states. [2024-11-14 04:37:14,172 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 166 to 130. [2024-11-14 04:37:14,173 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 130 states, 82 states have (on average 1.2439024390243902) internal successors, (102), 89 states have internal predecessors, (102), 24 states have call successors, (24), 15 states have call predecessors, (24), 22 states have return successors, (40), 25 states have call predecessors, (40), 24 states have call successors, (40) [2024-11-14 04:37:14,175 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 130 states to 130 states and 166 transitions. [2024-11-14 04:37:14,175 INFO L78 Accepts]: Start accepts. Automaton has 130 states and 166 transitions. Word has length 49 [2024-11-14 04:37:14,176 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:14,176 INFO L471 AbstractCegarLoop]: Abstraction has 130 states and 166 transitions. [2024-11-14 04:37:14,176 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 48 states, 35 states have (on average 1.6857142857142857) internal successors, (59), 38 states have internal predecessors, (59), 13 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 13 states have call successors, (16) [2024-11-14 04:37:14,176 INFO L276 IsEmpty]: Start isEmpty. Operand 130 states and 166 transitions. [2024-11-14 04:37:14,178 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2024-11-14 04:37:14,178 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:14,178 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:14,194 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2024-11-14 04:37:14,378 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:14,379 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:14,379 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:14,379 INFO L85 PathProgramCache]: Analyzing trace with hash -2117721594, now seen corresponding path program 1 times [2024-11-14 04:37:14,379 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:37:14,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [834643329] [2024-11-14 04:37:14,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:14,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:37:14,401 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:14,504 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2024-11-14 04:37:14,505 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:14,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [834643329] [2024-11-14 04:37:14,506 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [834643329] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:37:14,506 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1704478602] [2024-11-14 04:37:14,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:14,507 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:14,507 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:37:14,509 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:37:14,512 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-14 04:37:14,678 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:14,680 INFO L255 TraceCheckSpWp]: Trace formula consists of 349 conjuncts, 5 conjuncts are in the unsatisfiable core [2024-11-14 04:37:14,683 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:14,718 INFO L134 CoverageAnalysis]: Checked inductivity of 52 backedges. 34 proven. 0 refuted. 0 times theorem prover too weak. 18 trivial. 0 not checked. [2024-11-14 04:37:14,719 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:14,719 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1704478602] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:14,719 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-14 04:37:14,720 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [4] total 4 [2024-11-14 04:37:14,720 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [169651649] [2024-11-14 04:37:14,720 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:14,722 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:37:14,722 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:37:14,722 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:37:14,723 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:14,723 INFO L87 Difference]: Start difference. First operand 130 states and 166 transitions. Second operand has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:37:14,927 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:14,927 INFO L93 Difference]: Finished difference Result 193 states and 235 transitions. [2024-11-14 04:37:14,928 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:37:14,928 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) Word has length 57 [2024-11-14 04:37:14,928 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:14,930 INFO L225 Difference]: With dead ends: 193 [2024-11-14 04:37:14,930 INFO L226 Difference]: Without dead ends: 109 [2024-11-14 04:37:14,931 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 60 GetRequests, 58 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:14,931 INFO L432 NwaCegarLoop]: 42 mSDtfsCounter, 0 mSDsluCounter, 81 mSDsCounter, 0 mSdLazyCounter, 33 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 33 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 33 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:14,936 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 123 Invalid, 33 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 33 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:37:14,937 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 109 states. [2024-11-14 04:37:15,007 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 109 to 105. [2024-11-14 04:37:15,008 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 105 states, 69 states have (on average 1.1884057971014492) internal successors, (82), 73 states have internal predecessors, (82), 17 states have call successors, (17), 13 states have call predecessors, (17), 17 states have return successors, (25), 18 states have call predecessors, (25), 17 states have call successors, (25) [2024-11-14 04:37:15,010 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 105 states to 105 states and 124 transitions. [2024-11-14 04:37:15,011 INFO L78 Accepts]: Start accepts. Automaton has 105 states and 124 transitions. Word has length 57 [2024-11-14 04:37:15,012 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:15,012 INFO L471 AbstractCegarLoop]: Abstraction has 105 states and 124 transitions. [2024-11-14 04:37:15,012 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 7.25) internal successors, (29), 4 states have internal predecessors, (29), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:37:15,012 INFO L276 IsEmpty]: Start isEmpty. Operand 105 states and 124 transitions. [2024-11-14 04:37:15,013 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 78 [2024-11-14 04:37:15,015 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:15,015 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:15,037 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2024-11-14 04:37:15,216 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:15,216 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:15,217 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:15,217 INFO L85 PathProgramCache]: Analyzing trace with hash -873775554, now seen corresponding path program 1 times [2024-11-14 04:37:15,217 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:37:15,217 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [199508217] [2024-11-14 04:37:15,217 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:15,217 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:37:15,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:16,291 INFO L134 CoverageAnalysis]: Checked inductivity of 80 backedges. 27 proven. 0 refuted. 0 times theorem prover too weak. 53 trivial. 0 not checked. [2024-11-14 04:37:16,292 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:16,292 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [199508217] [2024-11-14 04:37:16,292 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [199508217] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:16,292 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:16,292 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [12] imperfect sequences [] total 12 [2024-11-14 04:37:16,292 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [93529606] [2024-11-14 04:37:16,292 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:16,293 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2024-11-14 04:37:16,293 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:37:16,293 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2024-11-14 04:37:16,293 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=109, Unknown=0, NotChecked=0, Total=132 [2024-11-14 04:37:16,294 INFO L87 Difference]: Start difference. First operand 105 states and 124 transitions. Second operand has 12 states, 9 states have (on average 3.7777777777777777) internal successors, (34), 11 states have internal predecessors, (34), 5 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-14 04:37:18,064 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:18,064 INFO L93 Difference]: Finished difference Result 162 states and 196 transitions. [2024-11-14 04:37:18,064 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 04:37:18,065 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 9 states have (on average 3.7777777777777777) internal successors, (34), 11 states have internal predecessors, (34), 5 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) Word has length 77 [2024-11-14 04:37:18,065 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:18,066 INFO L225 Difference]: With dead ends: 162 [2024-11-14 04:37:18,067 INFO L226 Difference]: Without dead ends: 115 [2024-11-14 04:37:18,067 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 30 GetRequests, 6 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 102 ImplicationChecksByTransitivity, 1.0s TimeCoverageRelationStatistics Valid=109, Invalid=541, Unknown=0, NotChecked=0, Total=650 [2024-11-14 04:37:18,068 INFO L432 NwaCegarLoop]: 48 mSDtfsCounter, 117 mSDsluCounter, 238 mSDsCounter, 0 mSdLazyCounter, 363 mSolverCounterSat, 46 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 120 SdHoareTripleChecker+Valid, 286 SdHoareTripleChecker+Invalid, 409 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 46 IncrementalHoareTripleChecker+Valid, 363 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:18,068 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [120 Valid, 286 Invalid, 409 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [46 Valid, 363 Invalid, 0 Unknown, 0 Unchecked, 1.2s Time] [2024-11-14 04:37:18,069 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2024-11-14 04:37:18,119 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 95. [2024-11-14 04:37:18,120 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 62 states have (on average 1.1451612903225807) internal successors, (71), 64 states have internal predecessors, (71), 17 states have call successors, (17), 13 states have call predecessors, (17), 14 states have return successors, (20), 17 states have call predecessors, (20), 17 states have call successors, (20) [2024-11-14 04:37:18,121 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 108 transitions. [2024-11-14 04:37:18,121 INFO L78 Accepts]: Start accepts. Automaton has 95 states and 108 transitions. Word has length 77 [2024-11-14 04:37:18,123 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:18,123 INFO L471 AbstractCegarLoop]: Abstraction has 95 states and 108 transitions. [2024-11-14 04:37:18,124 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 9 states have (on average 3.7777777777777777) internal successors, (34), 11 states have internal predecessors, (34), 5 states have call successors, (13), 2 states have call predecessors, (13), 5 states have return successors, (12), 7 states have call predecessors, (12), 5 states have call successors, (12) [2024-11-14 04:37:18,124 INFO L276 IsEmpty]: Start isEmpty. Operand 95 states and 108 transitions. [2024-11-14 04:37:18,125 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2024-11-14 04:37:18,128 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:18,128 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:18,128 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5 [2024-11-14 04:37:18,128 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:18,128 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:18,128 INFO L85 PathProgramCache]: Analyzing trace with hash -250496907, now seen corresponding path program 1 times [2024-11-14 04:37:18,128 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:37:18,128 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [493121086] [2024-11-14 04:37:18,129 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:18,129 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:37:18,170 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:18,310 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 74 trivial. 0 not checked. [2024-11-14 04:37:18,311 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:18,311 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [493121086] [2024-11-14 04:37:18,311 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [493121086] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:18,311 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:18,311 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:37:18,311 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [208039101] [2024-11-14 04:37:18,311 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:18,312 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:37:18,313 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2024-11-14 04:37:18,314 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:37:18,314 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:18,314 INFO L87 Difference]: Start difference. First operand 95 states and 108 transitions. Second operand has 4 states, 4 states have (on average 6.25) internal successors, (25), 4 states have internal predecessors, (25), 1 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) [2024-11-14 04:37:18,524 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:18,525 INFO L93 Difference]: Finished difference Result 105 states and 119 transitions. [2024-11-14 04:37:18,525 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:37:18,526 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 6.25) internal successors, (25), 4 states have internal predecessors, (25), 1 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) Word has length 78 [2024-11-14 04:37:18,527 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:18,528 INFO L225 Difference]: With dead ends: 105 [2024-11-14 04:37:18,529 INFO L226 Difference]: Without dead ends: 103 [2024-11-14 04:37:18,530 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 4 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:18,530 INFO L432 NwaCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 83 mSDsCounter, 0 mSdLazyCounter, 34 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 34 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 34 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:18,532 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 126 Invalid, 34 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 34 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2024-11-14 04:37:18,533 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2024-11-14 04:37:18,577 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2024-11-14 04:37:18,577 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 68 states have (on average 1.1323529411764706) internal successors, (77), 70 states have internal predecessors, (77), 17 states have call successors, (17), 13 states have call predecessors, (17), 16 states have return successors, (22), 19 states have call predecessors, (22), 17 states have call successors, (22) [2024-11-14 04:37:18,579 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 116 transitions. [2024-11-14 04:37:18,580 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 116 transitions. Word has length 78 [2024-11-14 04:37:18,580 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:18,581 INFO L471 AbstractCegarLoop]: Abstraction has 103 states and 116 transitions. [2024-11-14 04:37:18,581 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 6.25) internal successors, (25), 4 states have internal predecessors, (25), 1 states have call successors, (10), 1 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) [2024-11-14 04:37:18,582 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 116 transitions. [2024-11-14 04:37:18,583 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 80 [2024-11-14 04:37:18,583 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:18,583 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 4, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:18,584 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6 [2024-11-14 04:37:18,585 INFO L396 AbstractCegarLoop]: === Iteration 8 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:18,586 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:18,586 INFO L85 PathProgramCache]: Analyzing trace with hash -1493508958, now seen corresponding path program 2 times [2024-11-14 04:37:18,586 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2024-11-14 04:37:18,586 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1727278399] [2024-11-14 04:37:18,586 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:18,586 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-14 04:37:18,650 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:24,197 INFO L134 CoverageAnalysis]: Checked inductivity of 89 backedges. 49 proven. 8 refuted. 0 times theorem prover too weak. 32 trivial. 0 not checked. [2024-11-14 04:37:24,197 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2024-11-14 04:37:24,197 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1727278399] [2024-11-14 04:37:24,197 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1727278399] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-14 04:37:24,197 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1723286033] [2024-11-14 04:37:24,197 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-14 04:37:24,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:24,198 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:37:24,199 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-14 04:37:24,201 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-14 04:37:25,796 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2024-11-14 04:37:25,796 INFO L228 tOrderPrioritization]: Conjunction of SSA is unsat [2024-11-14 04:37:25,803 INFO L255 TraceCheckSpWp]: Trace formula consists of 568 conjuncts, 161 conjuncts are in the unsatisfiable core [2024-11-14 04:37:25,814 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:26,385 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2024-11-14 04:37:26,385 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 16 [2024-11-14 04:37:26,609 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2024-11-14 04:37:26,609 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 11 treesize of output 11 [2024-11-14 04:37:28,477 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-14 04:37:28,490 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-14 04:37:29,944 INFO L349 Elim1Store]: treesize reduction 295, result has 27.7 percent of original size [2024-11-14 04:37:29,944 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 181 treesize of output 134 [2024-11-14 04:37:31,002 INFO L349 Elim1Store]: treesize reduction 434, result has 37.4 percent of original size [2024-11-14 04:37:31,003 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 6 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 9 new quantified variables, introduced 19 case distinctions, treesize of input 634 treesize of output 1057 [2024-11-14 04:37:33,552 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 5 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 5 new quantified variables, introduced 0 case distinctions, treesize of input 803 treesize of output 1037 [2024-11-14 04:37:35,298 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:35,299 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:35,304 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:35,322 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:35,323 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:35,323 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:35,353 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 4 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 128 treesize of output 258 [2024-11-14 04:37:36,035 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:36,036 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 12 [2024-11-14 04:37:37,073 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:37,082 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 181 treesize of output 152 [2024-11-14 04:37:37,147 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2024-11-14 04:37:37,184 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 79 treesize of output 147 [2024-11-14 04:37:37,269 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,270 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,270 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,271 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,272 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 41 treesize of output 27 [2024-11-14 04:37:37,409 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,424 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,468 INFO L349 Elim1Store]: treesize reduction 32, result has 3.0 percent of original size [2024-11-14 04:37:37,469 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 5 case distinctions, treesize of input 897 treesize of output 769 [2024-11-14 04:37:37,706 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 30 treesize of output 33 [2024-11-14 04:37:37,741 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:37,751 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 17 [2024-11-14 04:37:37,791 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:38,067 INFO L349 Elim1Store]: treesize reduction 167, result has 30.7 percent of original size [2024-11-14 04:37:38,068 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 6 new quantified variables, introduced 12 case distinctions, treesize of input 1046 treesize of output 1035 [2024-11-14 04:37:38,399 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:38,399 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:38,405 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:38,410 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:38,411 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:38,411 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:38,412 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 79 treesize of output 43 [2024-11-14 04:37:38,799 INFO L349 Elim1Store]: treesize reduction 154, result has 26.3 percent of original size [2024-11-14 04:37:38,799 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 10 case distinctions, treesize of input 350 treesize of output 328 [2024-11-14 04:37:39,041 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:39,042 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:39,046 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:39,048 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 66 treesize of output 30 [2024-11-14 04:37:39,272 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:39,456 INFO L349 Elim1Store]: treesize reduction 156, result has 4.3 percent of original size [2024-11-14 04:37:39,457 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 5 new quantified variables, introduced 5 case distinctions, treesize of input 1821 treesize of output 1680 [2024-11-14 04:37:39,554 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 0 case distinctions, treesize of input 564 treesize of output 565 [2024-11-14 04:37:39,643 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:39,651 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:39,657 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 38 treesize of output 21 [2024-11-14 04:37:39,672 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 18 treesize of output 12 [2024-11-14 04:37:40,082 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 24 treesize of output 18 [2024-11-14 04:37:40,280 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:40,283 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:40,291 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:40,296 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 160 treesize of output 122 [2024-11-14 04:37:40,323 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 22 treesize of output 16 [2024-11-14 04:37:40,345 INFO L190 IndexEqualityManager]: detected not equals via solver [2024-11-14 04:37:40,366 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 17 treesize of output 25 [2024-11-14 04:37:40,442 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:40,443 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 0 select indices, 0 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 185 treesize of output 236 [2024-11-14 04:37:40,494 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_DEPENDING: no need to replace index [2024-11-14 04:37:40,494 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [373423505] [2024-11-14 04:37:40,497 INFO L159 IcfgInterpreter]: Started Sifa with 37 locations of interest [2024-11-14 04:37:40,497 INFO L166 IcfgInterpreter]: Building call graph [2024-11-14 04:37:40,497 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2024-11-14 04:37:40,497 INFO L176 IcfgInterpreter]: Starting interpretation [2024-11-14 04:37:40,497 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2024-11-14 04:37:40,528 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2024-11-14 04:37:40,704 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-14 04:37:40,705 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: Script currently locked by de.uni_freiburg.informatik.ultimate.lib.smtlibutils.IncrementalPlicationChecker@6cade1a at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.ManagedScript.assertScriptNotLocked(ManagedScript.java:109) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:282) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminateLight(PartialQuantifierElimination.java:62) at de.uni_freiburg.informatik.ultimate.lib.sifa.SymbolicTools$TermDomainOperationProviderWithLightElimination.newQuantifier(SymbolicTools.java:281) at de.uni_freiburg.informatik.ultimate.lib.sifa.SymbolicTools$TermDomainOperationProviderWithLightElimination.projectExistentially(SymbolicTools.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.TermDomainOperationProvider.projectExistentially(TermDomainOperationProvider.java:1) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateTransformer.strongestPostcondition(PredicateTransformer.java:131) at de.uni_freiburg.informatik.ultimate.lib.sifa.SymbolicTools.post(SymbolicTools.java:114) at de.uni_freiburg.informatik.ultimate.lib.sifa.DagInterpreter.ipretInternal(DagInterpreter.java:227) at de.uni_freiburg.informatik.ultimate.lib.sifa.DagInterpreter.ipretTransAndStoreLoiPred(DagInterpreter.java:209) at de.uni_freiburg.informatik.ultimate.lib.sifa.DagInterpreter.ipretTrans(DagInterpreter.java:187) at de.uni_freiburg.informatik.ultimate.lib.sifa.DagInterpreter.ipretNode(DagInterpreter.java:165) at de.uni_freiburg.informatik.ultimate.lib.sifa.DagInterpreter.interpret(DagInterpreter.java:123) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.interpretLoisInProcedure(IcfgInterpreter.java:136) at de.uni_freiburg.informatik.ultimate.lib.sifa.IcfgInterpreter.interpret(IcfgInterpreter.java:127) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.SifaRunner.(SifaRunner.java:102) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSifa.construct(IpTcStrategyModuleSifa.java:68) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getOrConstruct(IpTcStrategyModuleBase.java:101) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleBase.getInterpolantComputationStatus(IpTcStrategyModuleBase.java:77) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.tryExecuteInterpolantGenerator(AutomatonFreeRefinementEngine.java:267) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.generateProof(AutomatonFreeRefinementEngine.java:148) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.executeStrategy(AutomatonFreeRefinementEngine.java:137) at de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.tracehandling.AutomatonFreeRefinementEngine.(AutomatonFreeRefinementEngine.java:85) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.TraceAbstractionRefinementEngine.(TraceAbstractionRefinementEngine.java:82) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.BasicCegarLoop.isCounterexampleFeasible(BasicCegarLoop.java:302) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.iterate(AbstractCegarLoop.java:407) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.startCegar(AbstractCegarLoop.java:342) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.AbstractCegarLoop.runCegar(AbstractCegarLoop.java:324) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.executeCegarLoop(TraceAbstractionStarter.java:429) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:315) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:276) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:170) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:143) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:124) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runObserver(PluginConnector.java:167) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.runTool(PluginConnector.java:150) at de.uni_freiburg.informatik.ultimate.core.coreplugin.PluginConnector.run(PluginConnector.java:127) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.executePluginConnector(ToolchainWalker.java:233) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.processPlugin(ToolchainWalker.java:227) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walkUnprotected(ToolchainWalker.java:144) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainWalker.walk(ToolchainWalker.java:106) at de.uni_freiburg.informatik.ultimate.core.coreplugin.ToolchainManager$Toolchain.processToolchain(ToolchainManager.java:319) at de.uni_freiburg.informatik.ultimate.core.coreplugin.toolchain.DefaultToolchainJob.run(DefaultToolchainJob.java:145) at org.eclipse.core.internal.jobs.Worker.run(Worker.java:63) [2024-11-14 04:37:40,711 INFO L158 Benchmark]: Toolchain (without parser) took 194150.34ms. Allocated memory was 117.4MB in the beginning and 201.3MB in the end (delta: 83.9MB). Free memory was 91.6MB in the beginning and 56.0MB in the end (delta: 35.6MB). Peak memory consumption was 120.2MB. Max. memory is 16.1GB. [2024-11-14 04:37:40,711 INFO L158 Benchmark]: CDTParser took 1.12ms. Allocated memory is still 117.4MB. Free memory is still 74.1MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 04:37:40,711 INFO L158 Benchmark]: CACSL2BoogieTranslator took 632.05ms. Allocated memory is still 117.4MB. Free memory was 91.4MB in the beginning and 71.6MB in the end (delta: 19.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:37:40,715 INFO L158 Benchmark]: Boogie Procedure Inliner took 57.91ms. Allocated memory is still 117.4MB. Free memory was 71.6MB in the beginning and 69.8MB in the end (delta: 1.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2024-11-14 04:37:40,715 INFO L158 Benchmark]: Boogie Preprocessor took 56.41ms. Allocated memory is still 117.4MB. Free memory was 69.8MB in the beginning and 67.9MB in the end (delta: 1.8MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-14 04:37:40,716 INFO L158 Benchmark]: RCFGBuilder took 782.05ms. Allocated memory is still 117.4MB. Free memory was 67.7MB in the beginning and 38.1MB in the end (delta: 29.6MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. [2024-11-14 04:37:40,716 INFO L158 Benchmark]: TraceAbstraction took 192600.59ms. Allocated memory was 117.4MB in the beginning and 201.3MB in the end (delta: 83.9MB). Free memory was 90.8MB in the beginning and 56.0MB in the end (delta: 34.8MB). Peak memory consumption was 114.6MB. Max. memory is 16.1GB. [2024-11-14 04:37:40,718 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 1.12ms. Allocated memory is still 117.4MB. Free memory is still 74.1MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 632.05ms. Allocated memory is still 117.4MB. Free memory was 91.4MB in the beginning and 71.6MB in the end (delta: 19.7MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 57.91ms. Allocated memory is still 117.4MB. Free memory was 71.6MB in the beginning and 69.8MB in the end (delta: 1.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 56.41ms. Allocated memory is still 117.4MB. Free memory was 69.8MB in the beginning and 67.9MB in the end (delta: 1.8MB). There was no memory consumed. Max. memory is 16.1GB. * RCFGBuilder took 782.05ms. Allocated memory is still 117.4MB. Free memory was 67.7MB in the beginning and 38.1MB in the end (delta: 29.6MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. * TraceAbstraction took 192600.59ms. Allocated memory was 117.4MB in the beginning and 201.3MB in the end (delta: 83.9MB). Free memory was 90.8MB in the beginning and 56.0MB in the end (delta: 34.8MB). Peak memory consumption was 114.6MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: Script currently locked by de.uni_freiburg.informatik.ultimate.lib.smtlibutils.IncrementalPlicationChecker@6cade1a de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: Script currently locked by de.uni_freiburg.informatik.ultimate.lib.smtlibutils.IncrementalPlicationChecker@6cade1a: de.uni_freiburg.informatik.ultimate.lib.smtlibutils.ManagedScript.assertScriptNotLocked(ManagedScript.java:109) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2024-11-14 04:37:40,883 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Using bit-precise analysis Retrying with bit-precise analysis ### Bit-precise run ### Calling Ultimate with: /usr/bin/java -Dosgi.configuration.area=/tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/config -Xmx15G -Xms4m -jar /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data -tc /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/TaipanReach.xml -i ../../sv-benchmarks/c/ldv-sets/test_mutex.i -s /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Taipan --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash cee8df08ffad3eb9e493a0be0076215dd3a59bce6d2370397b3bb712a7fad867 --- Real Ultimate output --- This is Ultimate 0.3.0-dev-826ab2b [2024-11-14 04:37:43,536 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-14 04:37:43,657 INFO L114 SettingsManager]: Loading settings from /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/config/svcomp-Reach-32bit-Taipan_Bitvector.epf [2024-11-14 04:37:43,667 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-14 04:37:43,667 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-14 04:37:43,702 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-14 04:37:43,703 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-14 04:37:43,703 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-14 04:37:43,703 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2024-11-14 04:37:43,704 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2024-11-14 04:37:43,705 INFO L153 SettingsManager]: * User list type=DISABLED [2024-11-14 04:37:43,706 INFO L151 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2024-11-14 04:37:43,706 INFO L153 SettingsManager]: * Explicit value domain=true [2024-11-14 04:37:43,706 INFO L153 SettingsManager]: * Octagon Domain=false [2024-11-14 04:37:43,706 INFO L153 SettingsManager]: * Abstract domain=CompoundDomain [2024-11-14 04:37:43,706 INFO L153 SettingsManager]: * Interval Domain=false [2024-11-14 04:37:43,707 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-14 04:37:43,707 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2024-11-14 04:37:43,707 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-14 04:37:43,707 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-14 04:37:43,708 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2024-11-14 04:37:43,709 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-14 04:37:43,709 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-14 04:37:43,709 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-14 04:37:43,709 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-14 04:37:43,709 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-14 04:37:43,710 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2024-11-14 04:37:43,710 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:37:43,711 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Trace refinement strategy=WALRUS [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * Trace refinement exception blacklist=NONE [2024-11-14 04:37:43,711 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Taipan Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> cee8df08ffad3eb9e493a0be0076215dd3a59bce6d2370397b3bb712a7fad867 [2024-11-14 04:37:44,012 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-14 04:37:44,021 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-14 04:37:44,025 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-14 04:37:44,026 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-14 04:37:44,029 INFO L274 PluginConnector]: CDTParser initialized [2024-11-14 04:37:44,031 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/../../sv-benchmarks/c/ldv-sets/test_mutex.i Unable to find full path for "g++" [2024-11-14 04:37:46,161 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-14 04:37:46,521 INFO L384 CDTParser]: Found 1 translation units. [2024-11-14 04:37:46,524 INFO L180 CDTParser]: Scanning /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i [2024-11-14 04:37:46,549 INFO L427 CDTParser]: About to delete temporary CDT project at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/87bfe1675/547b7d1a8bb04eadaa1df224324f0b58/FLAGf1e470842 [2024-11-14 04:37:46,575 INFO L435 CDTParser]: Successfully deleted /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/data/87bfe1675/547b7d1a8bb04eadaa1df224324f0b58 [2024-11-14 04:37:46,577 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-14 04:37:46,579 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-14 04:37:46,583 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-14 04:37:46,584 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-14 04:37:46,589 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-14 04:37:46,590 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:37:46" (1/1) ... [2024-11-14 04:37:46,591 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2c952b3c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:46, skipping insertion in model container [2024-11-14 04:37:46,594 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 14.11 04:37:46" (1/1) ... [2024-11-14 04:37:46,644 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:37:47,035 WARN L1072 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-14 04:37:47,068 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25842,25855] [2024-11-14 04:37:47,073 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25967,25980] [2024-11-14 04:37:47,075 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[26082,26095] [2024-11-14 04:37:47,079 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:37:47,098 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2024-11-14 04:37:47,118 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-14 04:37:47,192 WARN L1072 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2024-11-14 04:37:47,205 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25842,25855] [2024-11-14 04:37:47,207 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25967,25980] [2024-11-14 04:37:47,208 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[26082,26095] [2024-11-14 04:37:47,210 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:37:47,213 INFO L200 MainTranslator]: Completed pre-run [2024-11-14 04:37:47,270 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25842,25855] [2024-11-14 04:37:47,271 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[25967,25980] [2024-11-14 04:37:47,272 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/sv-benchmarks/c/ldv-sets/test_mutex.i[26082,26095] [2024-11-14 04:37:47,274 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-14 04:37:47,319 INFO L204 MainTranslator]: Completed translation [2024-11-14 04:37:47,319 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47 WrapperNode [2024-11-14 04:37:47,320 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-14 04:37:47,321 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-14 04:37:47,321 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-14 04:37:47,322 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-14 04:37:47,330 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,356 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,383 INFO L138 Inliner]: procedures = 140, calls = 57, calls flagged for inlining = 14, calls inlined = 13, statements flattened = 135 [2024-11-14 04:37:47,383 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-14 04:37:47,384 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-14 04:37:47,384 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-14 04:37:47,384 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-14 04:37:47,392 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,392 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,396 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,397 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,411 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,415 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,418 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,421 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,425 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-14 04:37:47,426 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-14 04:37:47,426 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-14 04:37:47,426 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-14 04:37:47,427 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (1/1) ... [2024-11-14 04:37:47,437 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2024-11-14 04:37:47,450 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 [2024-11-14 04:37:47,463 INFO L229 MonitoredProcess]: Starting monitored process 1 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2024-11-14 04:37:47,465 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2024-11-14 04:37:47,492 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2024-11-14 04:37:47,493 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2024-11-14 04:37:47,493 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_unlock [2024-11-14 04:37:47,493 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_unlock [2024-11-14 04:37:47,493 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-14 04:37:47,493 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_lock [2024-11-14 04:37:47,493 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_lock [2024-11-14 04:37:47,493 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-14 04:37:47,493 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$ [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2024-11-14 04:37:47,494 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$ [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$ [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1 [2024-11-14 04:37:47,494 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2024-11-14 04:37:47,494 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2024-11-14 04:37:47,495 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-14 04:37:47,495 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-14 04:37:47,686 INFO L238 CfgBuilder]: Building ICFG [2024-11-14 04:37:47,688 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-14 04:37:48,211 INFO L? ?]: Removed 73 outVars from TransFormulas that were not future-live. [2024-11-14 04:37:48,211 INFO L287 CfgBuilder]: Performing block encoding [2024-11-14 04:37:48,229 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-14 04:37:48,229 INFO L316 CfgBuilder]: Removed 2 assume(true) statements. [2024-11-14 04:37:48,229 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:37:48 BoogieIcfgContainer [2024-11-14 04:37:48,230 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-14 04:37:48,232 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2024-11-14 04:37:48,233 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2024-11-14 04:37:48,238 INFO L274 PluginConnector]: TraceAbstraction initialized [2024-11-14 04:37:48,239 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 14.11 04:37:46" (1/3) ... [2024-11-14 04:37:48,239 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@73fd594d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:37:48, skipping insertion in model container [2024-11-14 04:37:48,239 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 14.11 04:37:47" (2/3) ... [2024-11-14 04:37:48,240 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@73fd594d and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 14.11 04:37:48, skipping insertion in model container [2024-11-14 04:37:48,240 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 14.11 04:37:48" (3/3) ... [2024-11-14 04:37:48,241 INFO L112 eAbstractionObserver]: Analyzing ICFG test_mutex.i [2024-11-14 04:37:48,257 INFO L217 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2024-11-14 04:37:48,261 INFO L154 ceAbstractionStarter]: Applying trace abstraction to ICFG test_mutex.i that has 6 procedures, 66 locations, 1 initial locations, 2 loop locations, and 3 error locations. [2024-11-14 04:37:48,328 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2024-11-14 04:37:48,346 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@3ac9f4d0, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2024-11-14 04:37:48,346 INFO L334 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2024-11-14 04:37:48,350 INFO L276 IsEmpty]: Start isEmpty. Operand has 66 states, 46 states have (on average 1.3043478260869565) internal successors, (60), 49 states have internal predecessors, (60), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:37:48,358 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 04:37:48,358 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:48,359 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:48,359 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:48,366 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:48,366 INFO L85 PathProgramCache]: Analyzing trace with hash 733731333, now seen corresponding path program 1 times [2024-11-14 04:37:48,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:48,381 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [922667282] [2024-11-14 04:37:48,382 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:48,382 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:48,383 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:48,389 INFO L229 MonitoredProcess]: Starting monitored process 2 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:48,390 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (2)] Waiting until timeout for monitored process [2024-11-14 04:37:48,538 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:48,542 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 1 conjuncts are in the unsatisfiable core [2024-11-14 04:37:48,547 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:48,571 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-14 04:37:48,571 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:48,572 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 04:37:48,572 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [922667282] [2024-11-14 04:37:48,573 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [922667282] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:48,573 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:48,573 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2024-11-14 04:37:48,575 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1580303042] [2024-11-14 04:37:48,576 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:48,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2024-11-14 04:37:48,580 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 04:37:48,599 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2024-11-14 04:37:48,601 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 04:37:48,604 INFO L87 Difference]: Start difference. First operand has 66 states, 46 states have (on average 1.3043478260869565) internal successors, (60), 49 states have internal predecessors, (60), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 04:37:48,645 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:48,648 INFO L93 Difference]: Finished difference Result 128 states and 169 transitions. [2024-11-14 04:37:48,649 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2024-11-14 04:37:48,650 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 27 [2024-11-14 04:37:48,651 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:48,657 INFO L225 Difference]: With dead ends: 128 [2024-11-14 04:37:48,658 INFO L226 Difference]: Without dead ends: 61 [2024-11-14 04:37:48,663 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 26 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2024-11-14 04:37:48,667 INFO L432 NwaCegarLoop]: 76 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 76 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:48,668 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 76 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:37:48,687 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 61 states. [2024-11-14 04:37:48,709 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 61 to 61. [2024-11-14 04:37:48,710 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 42 states have (on average 1.1666666666666667) internal successors, (49), 44 states have internal predecessors, (49), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2024-11-14 04:37:48,722 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 71 transitions. [2024-11-14 04:37:48,725 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 71 transitions. Word has length 27 [2024-11-14 04:37:48,725 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:48,725 INFO L471 AbstractCegarLoop]: Abstraction has 61 states and 71 transitions. [2024-11-14 04:37:48,726 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 9.0) internal successors, (18), 2 states have internal predecessors, (18), 2 states have call successors, (4), 2 states have call predecessors, (4), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2024-11-14 04:37:48,726 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 71 transitions. [2024-11-14 04:37:48,728 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 04:37:48,728 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:48,728 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:48,732 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (2)] Ended with exit code 0 [2024-11-14 04:37:48,929 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:48,930 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:48,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:48,931 INFO L85 PathProgramCache]: Analyzing trace with hash -327277627, now seen corresponding path program 1 times [2024-11-14 04:37:48,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:48,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1410398174] [2024-11-14 04:37:48,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:48,932 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:48,932 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:48,934 INFO L229 MonitoredProcess]: Starting monitored process 3 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:48,936 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (3)] Waiting until timeout for monitored process [2024-11-14 04:37:49,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:49,058 INFO L255 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-14 04:37:49,062 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:49,608 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-14 04:37:49,608 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:49,609 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 04:37:49,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1410398174] [2024-11-14 04:37:49,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1410398174] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:49,609 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:49,609 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:37:49,609 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1427020713] [2024-11-14 04:37:49,610 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:49,611 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2024-11-14 04:37:49,611 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 04:37:49,612 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2024-11-14 04:37:49,612 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2024-11-14 04:37:49,612 INFO L87 Difference]: Start difference. First operand 61 states and 71 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:37:50,383 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:50,384 INFO L93 Difference]: Finished difference Result 166 states and 204 transitions. [2024-11-14 04:37:50,384 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2024-11-14 04:37:50,385 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2024-11-14 04:37:50,385 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:50,390 INFO L225 Difference]: With dead ends: 166 [2024-11-14 04:37:50,390 INFO L226 Difference]: Without dead ends: 113 [2024-11-14 04:37:50,391 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2024-11-14 04:37:50,392 INFO L432 NwaCegarLoop]: 65 mSDtfsCounter, 49 mSDsluCounter, 134 mSDsCounter, 0 mSdLazyCounter, 101 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 50 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 103 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 101 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:50,392 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [50 Valid, 199 Invalid, 103 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 101 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2024-11-14 04:37:50,393 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 113 states. [2024-11-14 04:37:50,421 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 113 to 99. [2024-11-14 04:37:50,422 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 99 states, 68 states have (on average 1.2205882352941178) internal successors, (83), 72 states have internal predecessors, (83), 18 states have call successors, (18), 9 states have call predecessors, (18), 10 states have return successors, (23), 17 states have call predecessors, (23), 18 states have call successors, (23) [2024-11-14 04:37:50,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 99 states to 99 states and 124 transitions. [2024-11-14 04:37:50,427 INFO L78 Accepts]: Start accepts. Automaton has 99 states and 124 transitions. Word has length 27 [2024-11-14 04:37:50,428 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:50,428 INFO L471 AbstractCegarLoop]: Abstraction has 99 states and 124 transitions. [2024-11-14 04:37:50,428 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:37:50,428 INFO L276 IsEmpty]: Start isEmpty. Operand 99 states and 124 transitions. [2024-11-14 04:37:50,428 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2024-11-14 04:37:50,429 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:50,429 INFO L215 NwaCegarLoop]: trace histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:50,434 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (3)] Ended with exit code 0 [2024-11-14 04:37:50,629 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:50,630 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:50,630 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:50,631 INFO L85 PathProgramCache]: Analyzing trace with hash -379918324, now seen corresponding path program 1 times [2024-11-14 04:37:50,631 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:50,633 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1266105634] [2024-11-14 04:37:50,634 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:50,634 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:50,634 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:50,636 INFO L229 MonitoredProcess]: Starting monitored process 4 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:50,637 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (4)] Waiting until timeout for monitored process [2024-11-14 04:37:50,739 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:50,743 INFO L255 TraceCheckSpWp]: Trace formula consists of 102 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-14 04:37:50,744 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:50,775 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2024-11-14 04:37:50,775 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:50,776 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 04:37:50,776 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1266105634] [2024-11-14 04:37:50,776 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1266105634] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:50,776 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:50,777 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:37:50,777 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2003304145] [2024-11-14 04:37:50,777 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:50,778 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:37:50,778 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 04:37:50,778 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:37:50,778 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:50,779 INFO L87 Difference]: Start difference. First operand 99 states and 124 transitions. Second operand has 4 states, 4 states have (on average 4.0) internal successors, (16), 3 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:37:50,815 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:50,818 INFO L93 Difference]: Finished difference Result 106 states and 133 transitions. [2024-11-14 04:37:50,818 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:37:50,819 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 4.0) internal successors, (16), 3 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 27 [2024-11-14 04:37:50,819 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:50,820 INFO L225 Difference]: With dead ends: 106 [2024-11-14 04:37:50,823 INFO L226 Difference]: Without dead ends: 104 [2024-11-14 04:37:50,823 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 26 GetRequests, 24 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:50,824 INFO L432 NwaCegarLoop]: 72 mSDtfsCounter, 0 mSDsluCounter, 140 mSDsCounter, 0 mSdLazyCounter, 5 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 212 SdHoareTripleChecker+Invalid, 5 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 5 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:50,825 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 212 Invalid, 5 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 5 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:37:50,826 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2024-11-14 04:37:50,855 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 102. [2024-11-14 04:37:50,856 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 70 states have (on average 1.2) internal successors, (84), 74 states have internal predecessors, (84), 18 states have call successors, (18), 9 states have call predecessors, (18), 11 states have return successors, (26), 18 states have call predecessors, (26), 18 states have call successors, (26) [2024-11-14 04:37:50,860 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 128 transitions. [2024-11-14 04:37:50,860 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 128 transitions. Word has length 27 [2024-11-14 04:37:50,860 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:50,860 INFO L471 AbstractCegarLoop]: Abstraction has 102 states and 128 transitions. [2024-11-14 04:37:50,861 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 4.0) internal successors, (16), 3 states have internal predecessors, (16), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2024-11-14 04:37:50,861 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 128 transitions. [2024-11-14 04:37:50,862 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 04:37:50,862 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:50,864 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:50,867 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (4)] Ended with exit code 0 [2024-11-14 04:37:51,068 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:51,069 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:51,072 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:51,072 INFO L85 PathProgramCache]: Analyzing trace with hash -4640649, now seen corresponding path program 1 times [2024-11-14 04:37:51,073 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:51,073 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1028166829] [2024-11-14 04:37:51,073 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:51,073 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:51,073 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:51,075 INFO L229 MonitoredProcess]: Starting monitored process 5 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:51,077 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (5)] Waiting until timeout for monitored process [2024-11-14 04:37:51,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:51,267 INFO L255 TraceCheckSpWp]: Trace formula consists of 228 conjuncts, 17 conjuncts are in the unsatisfiable core [2024-11-14 04:37:51,275 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:51,502 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-14 04:37:51,507 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-14 04:37:51,863 INFO L134 CoverageAnalysis]: Checked inductivity of 58 backedges. 39 proven. 0 refuted. 0 times theorem prover too weak. 19 trivial. 0 not checked. [2024-11-14 04:37:51,864 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:51,865 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 04:37:51,865 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1028166829] [2024-11-14 04:37:51,865 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1028166829] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:51,865 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:51,865 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2024-11-14 04:37:51,865 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1659081135] [2024-11-14 04:37:51,866 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:51,866 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2024-11-14 04:37:51,866 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 04:37:51,867 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2024-11-14 04:37:51,867 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=15, Invalid=41, Unknown=0, NotChecked=0, Total=56 [2024-11-14 04:37:51,867 INFO L87 Difference]: Start difference. First operand 102 states and 128 transitions. Second operand has 8 states, 7 states have (on average 5.428571428571429) internal successors, (38), 8 states have internal predecessors, (38), 4 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-14 04:37:54,120 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:54,120 INFO L93 Difference]: Finished difference Result 260 states and 330 transitions. [2024-11-14 04:37:54,121 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2024-11-14 04:37:54,121 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 7 states have (on average 5.428571428571429) internal successors, (38), 8 states have internal predecessors, (38), 4 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) Word has length 67 [2024-11-14 04:37:54,122 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:54,124 INFO L225 Difference]: With dead ends: 260 [2024-11-14 04:37:54,125 INFO L226 Difference]: Without dead ends: 158 [2024-11-14 04:37:54,126 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 84 GetRequests, 67 SyntacticMatches, 0 SemanticMatches, 17 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 48 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=87, Invalid=255, Unknown=0, NotChecked=0, Total=342 [2024-11-14 04:37:54,127 INFO L432 NwaCegarLoop]: 68 mSDtfsCounter, 160 mSDsluCounter, 201 mSDsCounter, 0 mSdLazyCounter, 337 mSolverCounterSat, 49 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 165 SdHoareTripleChecker+Valid, 269 SdHoareTripleChecker+Invalid, 386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 49 IncrementalHoareTripleChecker+Valid, 337 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.6s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:54,127 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [165 Valid, 269 Invalid, 386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [49 Valid, 337 Invalid, 0 Unknown, 0 Unchecked, 1.6s Time] [2024-11-14 04:37:54,128 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 158 states. [2024-11-14 04:37:54,150 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 158 to 120. [2024-11-14 04:37:54,151 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 120 states, 84 states have (on average 1.1904761904761905) internal successors, (100), 90 states have internal predecessors, (100), 19 states have call successors, (19), 10 states have call predecessors, (19), 14 states have return successors, (32), 19 states have call predecessors, (32), 19 states have call successors, (32) [2024-11-14 04:37:54,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 120 states to 120 states and 151 transitions. [2024-11-14 04:37:54,153 INFO L78 Accepts]: Start accepts. Automaton has 120 states and 151 transitions. Word has length 67 [2024-11-14 04:37:54,153 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:54,154 INFO L471 AbstractCegarLoop]: Abstraction has 120 states and 151 transitions. [2024-11-14 04:37:54,154 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 7 states have (on average 5.428571428571429) internal successors, (38), 8 states have internal predecessors, (38), 4 states have call successors, (10), 4 states have call predecessors, (10), 5 states have return successors, (9), 4 states have call predecessors, (9), 4 states have call successors, (9) [2024-11-14 04:37:54,154 INFO L276 IsEmpty]: Start isEmpty. Operand 120 states and 151 transitions. [2024-11-14 04:37:54,156 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 68 [2024-11-14 04:37:54,156 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:54,156 INFO L215 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:54,161 INFO L552 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (5)] Ended with exit code 0 [2024-11-14 04:37:54,360 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:54,360 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:54,361 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:54,361 INFO L85 PathProgramCache]: Analyzing trace with hash -1450661243, now seen corresponding path program 1 times [2024-11-14 04:37:54,362 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:54,362 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1821010164] [2024-11-14 04:37:54,362 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:54,363 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:54,363 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:54,365 INFO L229 MonitoredProcess]: Starting monitored process 6 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:54,372 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (6)] Waiting until timeout for monitored process [2024-11-14 04:37:54,547 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:54,554 INFO L255 TraceCheckSpWp]: Trace formula consists of 222 conjuncts, 3 conjuncts are in the unsatisfiable core [2024-11-14 04:37:54,557 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:54,588 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 38 proven. 0 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2024-11-14 04:37:54,588 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-14 04:37:54,588 INFO L136 FreeRefinementEngine]: Strategy WALRUS found an infeasible trace [2024-11-14 04:37:54,589 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleMathsat [1821010164] [2024-11-14 04:37:54,589 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleMathsat [1821010164] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-14 04:37:54,589 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-14 04:37:54,589 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-14 04:37:54,589 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1138951339] [2024-11-14 04:37:54,590 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-14 04:37:54,590 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2024-11-14 04:37:54,590 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy WALRUS [2024-11-14 04:37:54,591 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-14 04:37:54,591 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:54,591 INFO L87 Difference]: Start difference. First operand 120 states and 151 transitions. Second operand has 4 states, 4 states have (on average 8.0) internal successors, (32), 3 states have internal predecessors, (32), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:37:54,625 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-14 04:37:54,625 INFO L93 Difference]: Finished difference Result 193 states and 234 transitions. [2024-11-14 04:37:54,626 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-14 04:37:54,626 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 8.0) internal successors, (32), 3 states have internal predecessors, (32), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) Word has length 67 [2024-11-14 04:37:54,626 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2024-11-14 04:37:54,628 INFO L225 Difference]: With dead ends: 193 [2024-11-14 04:37:54,628 INFO L226 Difference]: Without dead ends: 107 [2024-11-14 04:37:54,629 INFO L431 NwaCegarLoop]: 0 DeclaredPredicates, 66 GetRequests, 64 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-14 04:37:54,630 INFO L432 NwaCegarLoop]: 71 mSDtfsCounter, 0 mSDsluCounter, 137 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 208 SdHoareTripleChecker+Invalid, 7 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 7 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2024-11-14 04:37:54,630 INFO L433 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 208 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2024-11-14 04:37:54,631 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states. [2024-11-14 04:37:54,648 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 101. [2024-11-14 04:37:54,649 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 71 states have (on average 1.1408450704225352) internal successors, (81), 75 states have internal predecessors, (81), 15 states have call successors, (15), 9 states have call predecessors, (15), 12 states have return successors, (23), 16 states have call predecessors, (23), 15 states have call successors, (23) [2024-11-14 04:37:54,650 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 119 transitions. [2024-11-14 04:37:54,651 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 119 transitions. Word has length 67 [2024-11-14 04:37:54,651 INFO L84 Accepts]: Finished accepts. word is rejected. [2024-11-14 04:37:54,651 INFO L471 AbstractCegarLoop]: Abstraction has 101 states and 119 transitions. [2024-11-14 04:37:54,652 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 8.0) internal successors, (32), 3 states have internal predecessors, (32), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2024-11-14 04:37:54,652 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 119 transitions. [2024-11-14 04:37:54,653 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 61 [2024-11-14 04:37:54,653 INFO L207 NwaCegarLoop]: Found error trace [2024-11-14 04:37:54,654 INFO L215 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-14 04:37:54,659 INFO L540 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (6)] Forceful destruction successful, exit code 0 [2024-11-14 04:37:54,858 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:54,858 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2024-11-14 04:37:54,858 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-14 04:37:54,858 INFO L85 PathProgramCache]: Analyzing trace with hash -1284423888, now seen corresponding path program 1 times [2024-11-14 04:37:54,859 INFO L118 FreeRefinementEngine]: Executing refinement strategy WALRUS [2024-11-14 04:37:54,859 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleMathsat [1125247645] [2024-11-14 04:37:54,859 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-14 04:37:54,859 INFO L173 SolverBuilder]: Constructing external solver with command: mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 [2024-11-14 04:37:54,859 INFO L189 MonitoredProcess]: No working directory specified, using /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat [2024-11-14 04:37:54,863 INFO L229 MonitoredProcess]: Starting monitored process 7 with /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (exit command is (exit), workingDir is null) [2024-11-14 04:37:54,864 INFO L327 MonitoredProcess]: [MP /tmp/vcloud_worker_vcloud-master_on_vcloud-master/run_dir_ecb610a2-1a17-4c8a-9c99-48a4ce641459/bin/utaipan-verify-sOmjnqqW8E/mathsat -theory.fp.to_bv_overflow_mode=1 -theory.fp.minmax_zero_mode=4 -theory.bv.div_by_zero_mode=1 -unsat_core_generation=3 (7)] Waiting until timeout for monitored process [2024-11-14 04:37:55,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-14 04:37:55,176 INFO L255 TraceCheckSpWp]: Trace formula consists of 259 conjuncts, 79 conjuncts are in the unsatisfiable core [2024-11-14 04:37:55,199 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-14 04:37:55,503 INFO L349 Elim1Store]: treesize reduction 17, result has 29.2 percent of original size [2024-11-14 04:37:55,503 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 14 treesize of output 20 [2024-11-14 04:37:55,788 INFO L349 Elim1Store]: treesize reduction 22, result has 29.0 percent of original size [2024-11-14 04:37:55,788 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 20 treesize of output 22 [2024-11-14 04:37:56,867 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 47 [2024-11-14 04:37:56,929 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2024-11-14 04:37:57,031 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 52 [2024-11-14 04:37:57,101 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2024-11-14 04:37:57,124 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 61 [2024-11-14 04:37:57,213 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 13 treesize of output 7 [2024-11-14 04:37:57,401 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 44 treesize of output 47 [2024-11-14 04:37:57,425 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2024-11-14 04:37:57,492 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 59 [2024-11-14 04:37:57,513 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 52 treesize of output 57 [2024-11-14 04:37:57,539 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:37:57,542 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 148 treesize of output 114 [2024-11-14 04:37:57,577 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:37:57,623 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 52 [2024-11-14 04:37:57,687 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2024-11-14 04:37:57,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 51 treesize of output 54 [2024-11-14 04:37:57,724 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 3 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 152 treesize of output 116 [2024-11-14 04:37:57,732 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 8 treesize of output 7 [2024-11-14 04:37:57,763 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 7 treesize of output 3 [2024-11-14 04:37:57,817 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 49 treesize of output 47 [2024-11-14 04:37:57,868 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 10 treesize of output 9 [2024-11-14 04:38:00,039 WARN L851 $PredicateComparison]: unable to prove that (and (= (_ bv0 32) |c_~#mutexes~0.offset|) (let ((.cse7 (= |c___ldv_list_add_#in~new.base| |c___ldv_list_add_#in~prev.base|)) (.cse9 (select |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~prev.base|))) (let ((.cse0 (= |c___ldv_list_add_#in~next.base| |c___ldv_list_add_#in~new.base|)) (.cse1 (= |c___ldv_list_add_#in~new.offset| (select .cse9 |c___ldv_list_add_#in~prev.offset|))) (.cse13 (= |c___ldv_list_add_#in~next.base| |c___ldv_list_add_#in~prev.base|)) (.cse2 (not .cse7)) (.cse6 (select |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base|)) (.cse5 (bvadd |c___ldv_list_add_#in~new.offset| (_ bv4 32))) (.cse17 (select |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~next.base|))) (or (and (not .cse0) (or (and .cse1 .cse2 (exists ((v_DerPreprocessor_10 (_ BitVec 32))) (= (let ((.cse3 (let ((.cse4 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 (bvadd (_ bv4 32) v_DerPreprocessor_10) |c___ldv_list_add_#in~new.base|)))) (store .cse4 |c___ldv_list_add_#in~new.base| (store (store (select .cse4 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse3 |c___ldv_list_add_#in~prev.base| (store (select .cse3 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|))) |c_#memory_$Pointer$.base|))) (and .cse7 (exists ((v_DerPreprocessor_12 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_11 (Array (_ BitVec 32) (_ BitVec 32))) (v___ldv_list_add_~next.offset_4 (_ BitVec 32))) (let ((.cse10 (bvadd (_ bv4 32) v___ldv_list_add_~next.offset_4))) (and (= (store (select (let ((.cse8 (store (store |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~prev.base| v_DerPreprocessor_11) |c___ldv_list_add_#in~next.base| v_DerPreprocessor_12))) (store .cse8 |c___ldv_list_add_#in~new.base| (store (store (select .cse8 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| v___ldv_list_add_~next.offset_4) .cse5 |c___ldv_list_add_#in~prev.offset|))) |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.offset|) .cse9) (= (select v_DerPreprocessor_12 .cse10) |c___ldv_list_add_#in~new.offset|) (= (let ((.cse11 (let ((.cse12 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 .cse10 |c___ldv_list_add_#in~new.base|)))) (store .cse12 |c___ldv_list_add_#in~new.base| (store (store (select .cse12 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse11 |c___ldv_list_add_#in~prev.base| (store (select .cse11 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|))) |c_#memory_$Pointer$.base|)))))) (not .cse13)) (and .cse0 (or (and .cse1 .cse2 (exists ((v_DerPreprocessor_8 (_ BitVec 32))) (= |c_#memory_$Pointer$.base| (let ((.cse14 (let ((.cse15 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 v_DerPreprocessor_8 |c___ldv_list_add_#in~new.base|)))) (store .cse15 |c___ldv_list_add_#in~new.base| (store (store (select .cse15 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse14 |c___ldv_list_add_#in~prev.base| (store (select .cse14 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|)))))) (and .cse7 (exists ((v___ldv_list_add_~next.offset_4 (_ BitVec 32)) (v_DerPreprocessor_6 (Array (_ BitVec 32) (_ BitVec 32))) (v_arrayElimArr_5 (Array (_ BitVec 32) (_ BitVec 32)))) (let ((.cse16 (store (store |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~prev.base| v_DerPreprocessor_6) |c___ldv_list_add_#in~next.base| v_arrayElimArr_5)) (.cse18 (bvadd (_ bv4 32) v___ldv_list_add_~next.offset_4))) (and (= (store (select (store .cse16 |c___ldv_list_add_#in~new.base| (store (store (select .cse16 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| v___ldv_list_add_~next.offset_4) .cse5 |c___ldv_list_add_#in~prev.offset|)) |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.offset|) .cse17) (= (select .cse16 |c___ldv_list_add_#in~prev.base|) v_DerPreprocessor_6) (= |c___ldv_list_add_#in~new.offset| (select v_arrayElimArr_5 .cse18)) (= (let ((.cse19 (let ((.cse20 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 .cse18 |c___ldv_list_add_#in~new.base|)))) (store .cse20 |c___ldv_list_add_#in~new.base| (store (store (select .cse20 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse19 |c___ldv_list_add_#in~prev.base| (store (select .cse19 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|))) |c_#memory_$Pointer$.base|))))))) (and .cse13 (or (and .cse2 (exists ((v_DerPreprocessor_4 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_5 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_3 (Array (_ BitVec 32) (_ BitVec 32)))) (let ((.cse25 (store (store (store |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~next.base| v_DerPreprocessor_3) |c___ldv_list_add_#in~prev.base| v_DerPreprocessor_4) |c___ldv_list_add_#in~new.base| v_DerPreprocessor_5))) (let ((.cse22 (bvadd (select v_DerPreprocessor_5 |c___ldv_list_add_#in~new.offset|) (_ bv4 32))) (.cse21 (select .cse25 |c___ldv_list_add_#in~next.base|))) (and (= |c___ldv_list_add_#in~new.offset| (select .cse21 .cse22)) (= |c___ldv_list_add_#in~prev.offset| (select v_DerPreprocessor_5 .cse5)) (= |c_#memory_$Pointer$.base| (let ((.cse23 (let ((.cse24 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 .cse22 |c___ldv_list_add_#in~new.base|)))) (store .cse24 |c___ldv_list_add_#in~new.base| (store (store (select .cse24 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse23 |c___ldv_list_add_#in~prev.base| (store (select .cse23 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|)))) (= (store (select .cse25 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.offset|) .cse17) (= v_DerPreprocessor_3 .cse21)))))) (and .cse7 (exists ((v___ldv_list_add_~next.offset_4 (_ BitVec 32)) (v_DerPreprocessor_1 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_2 (Array (_ BitVec 32) (_ BitVec 32)))) (let ((.cse29 (bvadd (_ bv4 32) v___ldv_list_add_~next.offset_4)) (.cse26 (store (store |c_#memory_$Pointer$.offset| |c___ldv_list_add_#in~prev.base| v_DerPreprocessor_1) |c___ldv_list_add_#in~next.base| v_DerPreprocessor_2))) (and (= (select .cse26 |c___ldv_list_add_#in~prev.base|) v_DerPreprocessor_1) (= (let ((.cse27 (let ((.cse28 (store |c_old(#memory_$Pointer$.base)| |c___ldv_list_add_#in~next.base| (store .cse6 .cse29 |c___ldv_list_add_#in~new.base|)))) (store .cse28 |c___ldv_list_add_#in~new.base| (store (store (select .cse28 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| |c___ldv_list_add_#in~next.base|) .cse5 |c___ldv_list_add_#in~prev.base|))))) (store .cse27 |c___ldv_list_add_#in~prev.base| (store (select .cse27 |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.base|))) |c_#memory_$Pointer$.base|) (= |c___ldv_list_add_#in~new.offset| (select v_DerPreprocessor_2 .cse29)) (= (store (select (store .cse26 |c___ldv_list_add_#in~new.base| (store (store (select .cse26 |c___ldv_list_add_#in~new.base|) |c___ldv_list_add_#in~new.offset| v___ldv_list_add_~next.offset_4) .cse5 |c___ldv_list_add_#in~prev.offset|)) |c___ldv_list_add_#in~prev.base|) |c___ldv_list_add_#in~prev.offset| |c___ldv_list_add_#in~new.offset|) .cse17)))))))))) (= (_ bv3 32) |c_~#mutexes~0.base|)) is different from false [2024-11-14 04:38:01,220 INFO L349 Elim1Store]: treesize reduction 107, result has 20.7 percent of original size [2024-11-14 04:38:01,221 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 46 [2024-11-14 04:38:02,668 INFO L349 Elim1Store]: treesize reduction 134, result has 0.7 percent of original size [2024-11-14 04:38:02,669 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 30 treesize of output 1 [2024-11-14 04:38:04,698 WARN L851 $PredicateComparison]: unable to prove that (and (= (_ bv0 32) |c_~#mutexes~0.offset|) (= (_ bv3 32) |c_~#mutexes~0.base|) (let ((.cse2 (select |c_#memory_$Pointer$.offset| (_ bv3 32))) (.cse4 (select |c_old(#memory_$Pointer$.base)| (_ bv3 32))) (.cse9 (select (select |c_#memory_$Pointer$.base| (_ bv3 32)) (_ bv0 32)))) (let ((.cse12 (store |c_old(#memory_$Pointer$.base)| .cse9 (store (select |c_old(#memory_$Pointer$.base)| .cse9) (_ bv0 32) |c_mutex_lock_#in~m#1.base|))) (.cse10 (select .cse4 (_ bv0 32))) (.cse1 (select .cse2 (_ bv4 32)))) (let ((.cse5 (= (_ bv3 32) |c_mutex_lock_#in~m#1.base|)) (.cse3 (bvadd (_ bv4 32) .cse1)) (.cse7 (= (_ bv3 32) .cse10)) (.cse0 (= (_ bv4 32) (select .cse2 (_ bv0 32)))) (.cse6 (not (= (_ bv3 32) .cse9))) (.cse14 (= .cse10 .cse9)) (.cse13 (select .cse12 .cse10))) (or (and .cse0 (or (= (_ bv4 32) .cse1) (= (_ bv4 32) (select .cse2 .cse3)) (= (_ bv0 32) .cse1)) (= (_ bv0 32) (select .cse2 (_ bv8 32))) (= |c_#memory_$Pointer$.base| (store |c_old(#memory_$Pointer$.base)| (_ bv3 32) (store (store (store (store .cse4 .cse3 (_ bv3 32)) (_ bv4 32) (_ bv3 32)) (_ bv8 32) (_ bv3 32)) (_ bv0 32) (_ bv3 32)))) .cse5) (and .cse0 .cse6 (not .cse7) (exists ((v_DerPreprocessor_10 (_ BitVec 32))) (= |c_#memory_$Pointer$.base| (let ((.cse8 (let ((.cse11 (store .cse13 (bvadd (_ bv4 32) v_DerPreprocessor_10) .cse9))) (store (store |c_old(#memory_$Pointer$.base)| .cse10 .cse11) .cse9 (store (store (select (store .cse12 .cse10 .cse11) .cse9) (_ bv4 32) .cse10) (_ bv8 32) (_ bv3 32)))))) (store .cse8 (_ bv3 32) (store (select .cse8 (_ bv3 32)) (_ bv0 32) .cse9))))) (not .cse14)) (and (= |c_#memory_$Pointer$.base| (let ((.cse16 (store |c_old(#memory_$Pointer$.base)| (_ bv3 32) (store .cse4 (_ bv0 32) |c_mutex_lock_#in~m#1.base|)))) (let ((.cse15 (store (select .cse16 |c_mutex_lock_#in~m#1.base|) .cse3 (_ bv3 32)))) (store (store |c_old(#memory_$Pointer$.base)| |c_mutex_lock_#in~m#1.base| .cse15) (_ bv3 32) (store (store (store (select (store .cse16 |c_mutex_lock_#in~m#1.base| .cse15) (_ bv3 32)) (_ bv4 32) |c_mutex_lock_#in~m#1.base|) (_ bv8 32) (_ bv3 32)) (_ bv0 32) (_ bv3 32)))))) (not .cse5) (exists ((v_DerPreprocessor_12 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_11 (Array (_ BitVec 32) (_ BitVec 32)))) (and (= .cse2 (store (store (store (select (store (store |c_#memory_$Pointer$.offset| (_ bv3 32) v_DerPreprocessor_11) |c_mutex_lock_#in~m#1.base| v_DerPreprocessor_12) (_ bv3 32)) (_ bv4 32) .cse1) (_ bv8 32) (_ bv0 32)) (_ bv0 32) (_ bv4 32))) (= (select v_DerPreprocessor_12 .cse3) (_ bv4 32))))) (exists ((|mutex_lock_ldv_list_add_~new#1.base| (_ BitVec 32))) (and .cse7 (exists ((v_DerPreprocessor_4 (Array (_ BitVec 32) (_ BitVec 32))) (v_DerPreprocessor_5 (Array (_ BitVec 32) (_ BitVec 32)))) (let ((.cse17 (select (store (store |c_#memory_$Pointer$.offset| (_ bv3 32) v_DerPreprocessor_4) |mutex_lock_ldv_list_add_~new#1.base| v_DerPreprocessor_5) (_ bv3 32))) (.cse18 (bvadd (select v_DerPreprocessor_5 (_ bv4 32)) (_ bv4 32)))) (and (= .cse2 (store .cse17 (_ bv0 32) (_ bv4 32))) (= (_ bv4 32) (select .cse17 .cse18)) (= (let ((.cse21 (store |c_old(#memory_$Pointer$.base)| |mutex_lock_ldv_list_add_~new#1.base| (store (select |c_old(#memory_$Pointer$.base)| |mutex_lock_ldv_list_add_~new#1.base|) (_ bv0 32) |c_mutex_lock_#in~m#1.base|)))) (let ((.cse20 (store (select .cse21 (_ bv3 32)) .cse18 |mutex_lock_ldv_list_add_~new#1.base|))) (let ((.cse19 (store (store (select (store .cse21 (_ bv3 32) .cse20) |mutex_lock_ldv_list_add_~new#1.base|) (_ bv4 32) (_ bv3 32)) (_ bv8 32) (_ bv3 32)))) (store (store |c_old(#memory_$Pointer$.base)| |mutex_lock_ldv_list_add_~new#1.base| .cse19) (_ bv3 32) (store (select (store (store |c_old(#memory_$Pointer$.base)| (_ bv3 32) .cse20) |mutex_lock_ldv_list_add_~new#1.base| .cse19) (_ bv3 32)) (_ bv0 32) |mutex_lock_ldv_list_add_~new#1.base|))))) |c_#memory_$Pointer$.base|) (= (select v_DerPreprocessor_5 (_ bv8 32)) (_ bv0 32))))) (not (= (_ bv3 32) |mutex_lock_ldv_list_add_~new#1.base|)))) (and .cse0 .cse6 .cse14 (exists ((v_DerPreprocessor_8 (_ BitVec 32))) (= (let ((.cse22 (let ((.cse23 (store .cse13 v_DerPreprocessor_8 .cse9))) (store (store |c_old(#memory_$Pointer$.base)| .cse10 .cse23) .cse9 (store (store (select (store .cse12 .cse10 .cse23) .cse9) (_ bv4 32) .cse10) (_ bv8 32) (_ bv3 32)))))) (store .cse22 (_ bv3 32) (store (select .cse22 (_ bv3 32)) (_ bv0 32) .cse9))) |c_#memory_$Pointer$.base|)))))))) is different from false [2024-11-14 04:38:42,254 WARN L286 SmtUtils]: Spent 11.72s on a formula simplification. DAG size of input: 139 DAG size of output: 138 (called from [L 388] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2024-11-14 04:39:52,743 WARN L286 SmtUtils]: Spent 1.08m on a formula simplification. DAG size of input: 87 DAG size of output: 47 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2024-11-14 04:39:52,743 INFO L349 Elim1Store]: treesize reduction 224, result has 31.9 percent of original size [2024-11-14 04:39:52,743 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 8 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 10 new quantified variables, introduced 10 case distinctions, treesize of input 390 treesize of output 579 [2024-11-14 04:39:53,099 INFO L224 Elim1Store]: Index analysis took 236 ms [2024-11-14 04:39:55,295 INFO L349 Elim1Store]: treesize reduction 165, result has 4.6 percent of original size [2024-11-14 04:39:55,295 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 5 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 12 case distinctions, treesize of input 662 treesize of output 584 [2024-11-14 04:40:16,544 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 163 treesize of output 157 [2024-11-14 04:40:26,080 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 186 treesize of output 178 [2024-11-14 04:43:03,139 WARN L286 SmtUtils]: Spent 2.35m on a formula simplification. DAG size of input: 116 DAG size of output: 53 (called from [L 346] de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.Elim1Store.elim1) [2024-11-14 04:43:03,140 INFO L349 Elim1Store]: treesize reduction 507, result has 15.1 percent of original size [2024-11-14 04:43:03,140 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 10 stores, 1 select indices, 1 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 10 new quantified variables, introduced 13 case distinctions, treesize of input 316 treesize of output 1985 [2024-11-14 04:45:40,153 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:45:40,154 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:45:40,155 INFO L173 IndexEqualityManager]: detected equality via solver [2024-11-14 04:45:40,156 INFO L173 IndexEqualityManager]: detected equality via solver