./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 798a7b37 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --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 Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:15:08,560 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:15:08,620 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-03-03 13:15:08,624 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:15:08,624 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:15:08,641 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:15:08,641 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:15:08,642 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:15:08,642 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:15:08,642 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:15:08,642 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:15:08,642 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:15:08,642 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:15:08,642 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:15:08,643 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:15:08,643 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:15:08,644 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:15:08,644 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:15:08,644 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux 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 -> Automizer 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 -> 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 [2025-03-03 13:15:08,850 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:15:08,858 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:15:08,860 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:15:08,861 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:15:08,861 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:15:08,861 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2025-03-03 13:15:10,019 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3f0707b11/8255c64d96b3494f967e92c60f42c7eb/FLAGa7c8ea823 [2025-03-03 13:15:10,292 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:15:10,294 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2025-03-03 13:15:10,311 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3f0707b11/8255c64d96b3494f967e92c60f42c7eb/FLAGa7c8ea823 [2025-03-03 13:15:10,587 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3f0707b11/8255c64d96b3494f967e92c60f42c7eb [2025-03-03 13:15:10,588 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:15:10,589 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:15:10,590 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:15:10,590 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:15:10,593 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:15:10,593 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,594 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@21ae5052 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10, skipping insertion in model container [2025-03-03 13:15:10,594 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,622 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:15:10,818 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2025-03-03 13:15:10,822 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2025-03-03 13:15:10,823 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2025-03-03 13:15:10,829 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:15:10,837 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:15:10,891 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2025-03-03 13:15:10,891 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2025-03-03 13:15:10,892 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2025-03-03 13:15:10,897 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:15:10,916 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:15:10,917 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10 WrapperNode [2025-03-03 13:15:10,917 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:15:10,918 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:15:10,918 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:15:10,918 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:15:10,922 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,933 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,956 INFO L138 Inliner]: procedures = 142, calls = 62, calls flagged for inlining = 15, calls inlined = 14, statements flattened = 174 [2025-03-03 13:15:10,958 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:15:10,959 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:15:10,959 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:15:10,959 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:15:10,965 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,966 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:10,968 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,001 INFO L175 MemorySlicer]: Split 28 memory accesses to 2 slices as follows [2, 26]. 93 percent of accesses are in the largest equivalence class. The 6 initializations are split as follows [2, 4]. The 7 writes are split as follows [0, 7]. [2025-03-03 13:15:11,001 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,001 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,013 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,015 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,018 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,018 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,022 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:15:11,023 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:15:11,026 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:15:11,026 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:15:11,027 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (1/1) ... [2025-03-03 13:15:11,033 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:15:11,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:15:11,054 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 13:15:11,059 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 13:15:11,074 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2025-03-03 13:15:11,074 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_list_add [2025-03-03 13:15:11,075 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_list_add [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2025-03-03 13:15:11,075 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2025-03-03 13:15:11,075 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2025-03-03 13:15:11,075 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:15:11,075 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:15:11,199 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:15:11,202 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:15:11,409 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L667: havoc ldv_set_empty_#t~ret31#1; [2025-03-03 13:15:11,409 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L624: havoc ldv_list_empty_#t~mem10#1.base, ldv_list_empty_#t~mem10#1.offset; [2025-03-03 13:15:11,455 INFO L? ?]: Removed 73 outVars from TransFormulas that were not future-live. [2025-03-03 13:15:11,455 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:15:11,465 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:15:11,466 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:15:11,466 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:15:11 BoogieIcfgContainer [2025-03-03 13:15:11,466 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:15:11,469 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:15:11,470 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:15:11,473 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:15:11,473 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:15:10" (1/3) ... [2025-03-03 13:15:11,474 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@51a14e81 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:15:11, skipping insertion in model container [2025-03-03 13:15:11,474 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:15:10" (2/3) ... [2025-03-03 13:15:11,474 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@51a14e81 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:15:11, skipping insertion in model container [2025-03-03 13:15:11,474 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:15:11" (3/3) ... [2025-03-03 13:15:11,475 INFO L128 eAbstractionObserver]: Analyzing ICFG test_mutex_unbounded-1.i [2025-03-03 13:15:11,486 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:15:11,488 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG test_mutex_unbounded-1.i that has 5 procedures, 66 locations, 1 initial locations, 5 loop locations, and 3 error locations. [2025-03-03 13:15:11,530 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:15:11,540 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=PETRI_NET, 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;@11112e93, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:15:11,542 INFO L334 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2025-03-03 13:15:11,546 INFO L276 IsEmpty]: Start isEmpty. Operand has 66 states, 50 states have (on average 1.3) internal successors, (65), 53 states have internal predecessors, (65), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:15:11,550 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 13:15:11,550 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:15:11,551 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:15:11,551 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:15:11,554 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:15:11,554 INFO L85 PathProgramCache]: Analyzing trace with hash 164153700, now seen corresponding path program 1 times [2025-03-03 13:15:11,559 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:15:11,559 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1105046061] [2025-03-03 13:15:11,560 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:11,560 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:15:11,621 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 13:15:11,644 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 13:15:11,645 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:11,645 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:11,923 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:11,924 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:15:11,924 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1105046061] [2025-03-03 13:15:11,925 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1105046061] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:15:11,925 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:15:11,925 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:15:11,926 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1089001149] [2025-03-03 13:15:11,926 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:15:11,929 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:15:11,930 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:15:11,944 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:15:11,944 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-03 13:15:11,946 INFO L87 Difference]: Start difference. First operand has 66 states, 50 states have (on average 1.3) internal successors, (65), 53 states have internal predecessors, (65), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 13:15:12,175 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:15:12,176 INFO L93 Difference]: Finished difference Result 180 states and 230 transitions. [2025-03-03 13:15:12,177 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:15:12,178 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2025-03-03 13:15:12,179 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:15:12,184 INFO L225 Difference]: With dead ends: 180 [2025-03-03 13:15:12,185 INFO L226 Difference]: Without dead ends: 104 [2025-03-03 13:15:12,189 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 1 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:15:12,191 INFO L435 NwaCegarLoop]: 56 mSDtfsCounter, 56 mSDsluCounter, 214 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 56 SdHoareTripleChecker+Valid, 270 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2025-03-03 13:15:12,193 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [56 Valid, 270 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2025-03-03 13:15:12,205 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states. [2025-03-03 13:15:12,221 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 87. [2025-03-03 13:15:12,223 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 68 states have (on average 1.2794117647058822) internal successors, (87), 70 states have internal predecessors, (87), 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) [2025-03-03 13:15:12,227 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 109 transitions. [2025-03-03 13:15:12,229 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 109 transitions. Word has length 10 [2025-03-03 13:15:12,229 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:15:12,229 INFO L471 AbstractCegarLoop]: Abstraction has 87 states and 109 transitions. [2025-03-03 13:15:12,229 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 13:15:12,229 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 109 transitions. [2025-03-03 13:15:12,230 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-03 13:15:12,230 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:15:12,231 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:15:12,231 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-03-03 13:15:12,231 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:15:12,231 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:15:12,231 INFO L85 PathProgramCache]: Analyzing trace with hash 1511701405, now seen corresponding path program 1 times [2025-03-03 13:15:12,232 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:15:12,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1121228200] [2025-03-03 13:15:12,232 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:12,232 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:15:12,257 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-03 13:15:12,263 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-03 13:15:12,264 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:12,264 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:12,344 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:12,348 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:15:12,348 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1121228200] [2025-03-03 13:15:12,348 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1121228200] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:15:12,348 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:15:12,348 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:15:12,349 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412569517] [2025-03-03 13:15:12,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:15:12,349 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:15:12,349 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:15:12,350 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:15:12,350 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:15:12,350 INFO L87 Difference]: Start difference. First operand 87 states and 109 transitions. 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, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:15:12,445 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:15:12,445 INFO L93 Difference]: Finished difference Result 153 states and 186 transitions. [2025-03-03 13:15:12,446 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:15:12,446 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, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2025-03-03 13:15:12,446 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:15:12,447 INFO L225 Difference]: With dead ends: 153 [2025-03-03 13:15:12,448 INFO L226 Difference]: Without dead ends: 73 [2025-03-03 13:15:12,448 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 5 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:15:12,449 INFO L435 NwaCegarLoop]: 68 mSDtfsCounter, 13 mSDsluCounter, 104 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 172 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-03-03 13:15:12,449 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 172 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-03-03 13:15:12,450 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-03-03 13:15:12,457 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 68. [2025-03-03 13:15:12,458 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 51 states have (on average 1.196078431372549) internal successors, (61), 54 states have internal predecessors, (61), 9 states have call successors, (9), 5 states have call predecessors, (9), 5 states have return successors, (9), 8 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:15:12,459 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 79 transitions. [2025-03-03 13:15:12,459 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 79 transitions. Word has length 13 [2025-03-03 13:15:12,459 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:15:12,460 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 79 transitions. [2025-03-03 13:15:12,460 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, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:15:12,460 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 79 transitions. [2025-03-03 13:15:12,460 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:15:12,461 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:15:12,461 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:15:12,461 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2025-03-03 13:15:12,461 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:15:12,462 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:15:12,464 INFO L85 PathProgramCache]: Analyzing trace with hash -670609863, now seen corresponding path program 1 times [2025-03-03 13:15:12,465 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:15:12,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [605667375] [2025-03-03 13:15:12,465 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:12,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:15:12,489 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:15:12,512 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:15:12,512 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:12,512 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:12,862 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:12,863 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:15:12,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [605667375] [2025-03-03 13:15:12,863 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [605667375] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:15:12,863 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1420031916] [2025-03-03 13:15:12,865 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:12,865 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:15:12,865 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:15:12,867 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:15:12,868 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 13:15:12,936 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:15:12,966 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:15:12,967 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:12,967 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:12,969 INFO L256 TraceCheckSpWp]: Trace formula consists of 242 conjuncts, 44 conjuncts are in the unsatisfiable core [2025-03-03 13:15:12,974 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:15:13,121 INFO L349 Elim1Store]: treesize reduction 4, result has 50.0 percent of original size [2025-03-03 13:15:13,122 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 [2025-03-03 13:15:13,222 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 42 [2025-03-03 13:15:13,230 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 39 treesize of output 37 [2025-03-03 13:15:13,244 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 [2025-03-03 13:15:13,247 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 47 treesize of output 50 [2025-03-03 13:15:13,253 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 10 treesize of output 9 [2025-03-03 13:15:13,260 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 [2025-03-03 13:15:13,286 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 [2025-03-03 13:15:13,295 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 87 treesize of output 74 [2025-03-03 13:15:13,317 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 [2025-03-03 13:15:13,328 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 62 treesize of output 54 [2025-03-03 13:15:13,353 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 29 treesize of output 42 [2025-03-03 13:15:13,376 INFO L349 Elim1Store]: treesize reduction 41, result has 26.8 percent of original size [2025-03-03 13:15:13,376 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 1 case distinctions, treesize of input 22 treesize of output 25 [2025-03-03 13:15:13,400 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 34 treesize of output 42 [2025-03-03 13:15:13,418 INFO L349 Elim1Store]: treesize reduction 38, result has 32.1 percent of original size [2025-03-03 13:15:13,418 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 1 case distinctions, treesize of input 22 treesize of output 28 [2025-03-03 13:15:17,170 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 1472 treesize of output 1362 [2025-03-03 13:15:17,177 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 73 [2025-03-03 13:15:17,191 INFO L349 Elim1Store]: treesize reduction 17, result has 43.3 percent of original size [2025-03-03 13:15:17,191 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 73 treesize of output 85 [2025-03-03 13:15:17,197 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 64 treesize of output 60 [2025-03-03 13:15:17,203 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 60 treesize of output 63 [2025-03-03 13:15:17,208 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 55 treesize of output 51 [2025-03-03 13:15:17,213 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 51 treesize of output 54 [2025-03-03 13:15:17,234 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 5 [2025-03-03 13:15:17,237 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 5 [2025-03-03 13:15:17,240 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 12 treesize of output 8 [2025-03-03 13:15:17,274 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:17,274 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:15:17,633 INFO L349 Elim1Store]: treesize reduction 125, result has 41.9 percent of original size [2025-03-03 13:15:17,633 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 2 new quantified variables, introduced 4 case distinctions, treesize of input 1118 treesize of output 664 [2025-03-03 13:15:17,649 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 136 treesize of output 134 [2025-03-03 13:15:17,657 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 134 treesize of output 130 [2025-03-03 13:15:17,687 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:17,687 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 4 select indices, 4 select index equivalence classes, 1 disjoint index pairs (out of 6 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 212 treesize of output 246 [2025-03-03 13:15:17,837 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 8 treesize of output 4 [2025-03-03 13:15:17,918 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 8 treesize of output 4 [2025-03-03 13:15:17,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 8 treesize of output 4 [2025-03-03 13:15:17,943 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:17,943 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 26 treesize of output 26 [2025-03-03 13:15:18,165 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:18,165 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 19 treesize of output 23 [2025-03-03 13:15:18,183 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:18,183 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 21 treesize of output 21 [2025-03-03 13:15:18,202 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:18,202 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 37 treesize of output 41 [2025-03-03 13:15:18,221 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:18,223 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 13 treesize of output 9 [2025-03-03 13:15:18,226 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:18,230 INFO L349 Elim1Store]: treesize reduction 7, result has 12.5 percent of original size [2025-03-03 13:15:18,231 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 25 treesize of output 1 [2025-03-03 13:15:18,337 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:15:18,338 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:18,345 INFO L349 Elim1Store]: treesize reduction 94, result has 1.1 percent of original size [2025-03-03 13:15:18,346 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 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 1 [2025-03-03 13:15:18,520 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:18,520 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1420031916] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:15:18,520 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2025-03-03 13:15:18,521 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 13, 13] total 35 [2025-03-03 13:15:18,521 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1009710926] [2025-03-03 13:15:18,521 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2025-03-03 13:15:18,521 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 35 states [2025-03-03 13:15:18,521 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:15:18,522 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2025-03-03 13:15:18,522 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=1089, Unknown=4, NotChecked=0, Total=1190 [2025-03-03 13:15:18,522 INFO L87 Difference]: Start difference. First operand 68 states and 79 transitions. Second operand has 35 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 28 states have internal predecessors, (56), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:15:27,633 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-03 13:15:32,205 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.01s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-03 13:15:36,871 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-03 13:15:37,193 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:15:37,193 INFO L93 Difference]: Finished difference Result 201 states and 242 transitions. [2025-03-03 13:15:37,193 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-03 13:15:37,193 INFO L78 Accepts]: Start accepts. Automaton has has 35 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 28 states have internal predecessors, (56), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Word has length 28 [2025-03-03 13:15:37,194 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:15:37,195 INFO L225 Difference]: With dead ends: 201 [2025-03-03 13:15:37,195 INFO L226 Difference]: Without dead ends: 177 [2025-03-03 13:15:37,196 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 89 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 54 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 377 ImplicationChecksByTransitivity, 8.8s TimeCoverageRelationStatistics Valid=388, Invalid=2680, Unknown=12, NotChecked=0, Total=3080 [2025-03-03 13:15:37,196 INFO L435 NwaCegarLoop]: 41 mSDtfsCounter, 532 mSDsluCounter, 835 mSDsCounter, 0 mSdLazyCounter, 1264 mSolverCounterSat, 152 mSolverCounterUnsat, 25 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 13.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 532 SdHoareTripleChecker+Valid, 876 SdHoareTripleChecker+Invalid, 1441 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 152 IncrementalHoareTripleChecker+Valid, 1264 IncrementalHoareTripleChecker+Invalid, 25 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 13.5s IncrementalHoareTripleChecker+Time [2025-03-03 13:15:37,196 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [532 Valid, 876 Invalid, 1441 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [152 Valid, 1264 Invalid, 25 Unknown, 0 Unchecked, 13.5s Time] [2025-03-03 13:15:37,197 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2025-03-03 13:15:37,208 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 116. [2025-03-03 13:15:37,208 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 91 states have (on average 1.2747252747252746) internal successors, (116), 95 states have internal predecessors, (116), 14 states have call successors, (14), 8 states have call predecessors, (14), 8 states have return successors, (14), 12 states have call predecessors, (14), 14 states have call successors, (14) [2025-03-03 13:15:37,209 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 144 transitions. [2025-03-03 13:15:37,209 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 144 transitions. Word has length 28 [2025-03-03 13:15:37,209 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:15:37,210 INFO L471 AbstractCegarLoop]: Abstraction has 116 states and 144 transitions. [2025-03-03 13:15:37,210 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 35 states, 29 states have (on average 1.9310344827586208) internal successors, (56), 28 states have internal predecessors, (56), 9 states have call successors, (9), 4 states have call predecessors, (9), 9 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2025-03-03 13:15:37,210 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 144 transitions. [2025-03-03 13:15:37,210 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 13:15:37,210 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:15:37,210 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:15:37,217 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2025-03-03 13:15:37,411 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:15:37,411 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:15:37,412 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:15:37,412 INFO L85 PathProgramCache]: Analyzing trace with hash 931039912, now seen corresponding path program 1 times [2025-03-03 13:15:37,412 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:15:37,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [903239010] [2025-03-03 13:15:37,412 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:37,412 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:15:37,429 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 13:15:37,436 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 13:15:37,437 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:37,437 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:37,483 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-03-03 13:15:37,484 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:15:37,484 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [903239010] [2025-03-03 13:15:37,484 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [903239010] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:15:37,484 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:15:37,484 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:15:37,484 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [854216368] [2025-03-03 13:15:37,484 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:15:37,484 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:15:37,484 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:15:37,485 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:15:37,485 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:15:37,485 INFO L87 Difference]: Start difference. First operand 116 states and 144 transitions. Second operand has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-03 13:15:37,513 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:15:37,513 INFO L93 Difference]: Finished difference Result 128 states and 161 transitions. [2025-03-03 13:15:37,513 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:15:37,513 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) Word has length 31 [2025-03-03 13:15:37,514 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:15:37,514 INFO L225 Difference]: With dead ends: 128 [2025-03-03 13:15:37,515 INFO L226 Difference]: Without dead ends: 126 [2025-03-03 13:15:37,515 INFO L434 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 [2025-03-03 13:15:37,515 INFO L435 NwaCegarLoop]: 70 mSDtfsCounter, 0 mSDsluCounter, 135 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 205 SdHoareTripleChecker+Invalid, 10 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-03-03 13:15:37,517 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 205 Invalid, 10 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:15:37,518 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 126 states. [2025-03-03 13:15:37,536 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 126 to 124. [2025-03-03 13:15:37,537 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 124 states, 97 states have (on average 1.2577319587628866) internal successors, (122), 101 states have internal predecessors, (122), 14 states have call successors, (14), 8 states have call predecessors, (14), 10 states have return successors, (20), 14 states have call predecessors, (20), 14 states have call successors, (20) [2025-03-03 13:15:37,538 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 124 states to 124 states and 156 transitions. [2025-03-03 13:15:37,540 INFO L78 Accepts]: Start accepts. Automaton has 124 states and 156 transitions. Word has length 31 [2025-03-03 13:15:37,540 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:15:37,540 INFO L471 AbstractCegarLoop]: Abstraction has 124 states and 156 transitions. [2025-03-03 13:15:37,540 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 5.75) internal successors, (23), 4 states have internal predecessors, (23), 1 states have call successors, (4), 1 states have call predecessors, (4), 2 states have return successors, (4), 2 states have call predecessors, (4), 1 states have call successors, (4) [2025-03-03 13:15:37,540 INFO L276 IsEmpty]: Start isEmpty. Operand 124 states and 156 transitions. [2025-03-03 13:15:37,540 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2025-03-03 13:15:37,540 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:15:37,540 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:15:37,541 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3 [2025-03-03 13:15:37,541 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:15:37,541 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:15:37,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1213255377, now seen corresponding path program 1 times [2025-03-03 13:15:37,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:15:37,541 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1480739797] [2025-03-03 13:15:37,541 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:37,541 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:15:37,550 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:15:37,563 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:15:37,563 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:37,563 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:39,126 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:39,126 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:15:39,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1480739797] [2025-03-03 13:15:39,126 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1480739797] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:15:39,126 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [489052273] [2025-03-03 13:15:39,126 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:15:39,126 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:15:39,126 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:15:39,128 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:15:39,129 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 13:15:39,192 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 32 statements into 1 equivalence classes. [2025-03-03 13:15:39,217 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 32 of 32 statements. [2025-03-03 13:15:39,217 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:15:39,217 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:15:39,219 INFO L256 TraceCheckSpWp]: Trace formula consists of 250 conjuncts, 103 conjuncts are in the unsatisfiable core [2025-03-03 13:15:39,222 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:15:39,529 INFO L349 Elim1Store]: treesize reduction 8, result has 52.9 percent of original size [2025-03-03 13:15:39,529 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 [2025-03-03 13:15:39,618 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 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 15 treesize of output 7 [2025-03-03 13:15:39,626 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 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 15 treesize of output 7 [2025-03-03 13:15:39,878 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:39,924 INFO L349 Elim1Store]: treesize reduction 97, result has 30.2 percent of original size [2025-03-03 13:15:39,924 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 5 new quantified variables, introduced 4 case distinctions, treesize of input 154 treesize of output 206 [2025-03-03 13:15:39,962 INFO L349 Elim1Store]: treesize reduction 16, result has 55.6 percent of original size [2025-03-03 13:15:39,962 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 180 treesize of output 166 [2025-03-03 13:15:40,001 INFO L349 Elim1Store]: treesize reduction 36, result has 49.3 percent of original size [2025-03-03 13:15:40,001 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 3 new quantified variables, introduced 2 case distinctions, treesize of input 64 treesize of output 79 [2025-03-03 13:15:40,011 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:40,035 INFO L349 Elim1Store]: treesize reduction 42, result has 37.3 percent of original size [2025-03-03 13:15:40,035 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 3 case distinctions, treesize of input 66 treesize of output 88 [2025-03-03 13:15:40,081 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 [2025-03-03 13:15:40,099 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:15:40,099 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 12 treesize of output 1 [2025-03-03 13:15:40,105 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 12 treesize of output 11 [2025-03-03 13:15:40,192 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:40,194 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 18 treesize of output 11 [2025-03-03 13:15:40,263 INFO L349 Elim1Store]: treesize reduction 36, result has 50.7 percent of original size [2025-03-03 13:15:40,263 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 3 case distinctions, treesize of input 31 treesize of output 49 [2025-03-03 13:15:40,299 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:15:40,307 INFO L349 Elim1Store]: treesize reduction 45, result has 2.2 percent of original size [2025-03-03 13:15:40,307 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 2 case distinctions, treesize of input 35 treesize of output 24 [2025-03-03 13:15:40,322 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 66 treesize of output 38 [2025-03-03 13:15:40,332 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:15:40,333 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 19 treesize of output 23 [2025-03-03 13:15:45,944 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:15:45,945 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:15:46,367 WARN L851 $PredicateComparison]: unable to prove that (let ((.cse5 (+ |c_ULTIMATE.start_foo_~me~0#1.offset| 8)) (.cse2 (select |c_#memory_$Pointer$#1.base| |c_~#drvlist~0.base|))) (and (forall ((v_ArrVal_186 (Array Int Int)) (v_ldv_list_add_~head.offset_16 Int) (v_ArrVal_187 (Array Int Int))) (let ((.cse0 (store (store |c_#memory_$Pointer$#1.base| (select .cse2 v_ldv_list_add_~head.offset_16) v_ArrVal_186) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_187))) (let ((.cse1 (store (select .cse0 |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 |c_ULTIMATE.start_foo_~me~0#1.base|))) (or (= |c_~#mutexes~0.base| (select (select (store .cse0 |c_~#drvlist~0.base| .cse1) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|)) (= |c_~#drvlist~0.base| (select .cse1 |c_~#drvlist~0.offset|)))))) (forall ((v_ArrVal_189 Int) (v_ldv_list_add_~head.offset_16 Int) (v___ldv_list_add_~next.offset_24 Int) (v_ArrVal_188 (Array Int Int))) (let ((.cse3 (select .cse2 v_ldv_list_add_~head.offset_16))) (or (forall ((v_ArrVal_186 (Array Int Int)) (v_ArrVal_187 (Array Int Int))) (= |c_~#drvlist~0.base| (select (store (select (store (store |c_#memory_$Pointer$#1.base| .cse3 v_ArrVal_186) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_187) |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 |c_ULTIMATE.start_foo_~me~0#1.base|) |c_~#drvlist~0.offset|))) (= (select (select (let ((.cse4 (store (store |c_#memory_$Pointer$#1.offset| .cse3 (store (select |c_#memory_$Pointer$#1.offset| .cse3) (+ v___ldv_list_add_~next.offset_24 4) .cse5)) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_188))) (store .cse4 |c_~#drvlist~0.base| (store (select .cse4 |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 v_ArrVal_189))) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|)))) (forall ((v_ArrVal_189 Int) (v_ldv_list_add_~head.offset_16 Int) (v___ldv_list_add_~next.offset_24 Int) (v_ArrVal_188 (Array Int Int))) (let ((.cse7 (store (let ((.cse8 (select .cse2 v_ldv_list_add_~head.offset_16))) (store |c_#memory_$Pointer$#1.offset| .cse8 (store (select |c_#memory_$Pointer$#1.offset| .cse8) (+ v___ldv_list_add_~next.offset_24 4) .cse5))) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_188))) (let ((.cse6 (store (select .cse7 |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 v_ArrVal_189))) (or (= (select .cse6 |c_~#drvlist~0.offset|) |c_~#drvlist~0.offset|) (= (select (select (store .cse7 |c_~#drvlist~0.base| .cse6) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|) |c_~#mutexes~0.offset|))))) (forall ((v_ArrVal_186 (Array Int Int)) (v_ldv_list_add_~head.offset_16 Int) (v_ArrVal_187 (Array Int Int))) (let ((.cse9 (select .cse2 v_ldv_list_add_~head.offset_16))) (or (forall ((v_ArrVal_189 Int) (v___ldv_list_add_~next.offset_24 Int) (v_ArrVal_188 (Array Int Int))) (= (select (store (select (store (store |c_#memory_$Pointer$#1.offset| .cse9 (store (select |c_#memory_$Pointer$#1.offset| .cse9) (+ v___ldv_list_add_~next.offset_24 4) .cse5)) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_188) |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 v_ArrVal_189) |c_~#drvlist~0.offset|) |c_~#drvlist~0.offset|)) (= |c_~#mutexes~0.base| (select (select (let ((.cse10 (store (store |c_#memory_$Pointer$#1.base| .cse9 v_ArrVal_186) |c_ULTIMATE.start_foo_~me~0#1.base| v_ArrVal_187))) (store .cse10 |c_~#drvlist~0.base| (store (select .cse10 |c_~#drvlist~0.base|) v_ldv_list_add_~head.offset_16 |c_ULTIMATE.start_foo_~me~0#1.base|))) |c_~#mutexes~0.base|) |c_~#mutexes~0.offset|))))))) is different from false [2025-03-03 13:15:46,370 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [489052273] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:15:46,370 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:15:46,371 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [16, 16] total 31 [2025-03-03 13:15:46,371 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [108244708] [2025-03-03 13:15:46,371 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:15:46,371 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 31 states [2025-03-03 13:15:46,371 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-03-03 13:15:46,372 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 31 interpolants. [2025-03-03 13:15:46,372 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=153, Invalid=1035, Unknown=6, NotChecked=66, Total=1260 [2025-03-03 13:15:46,372 INFO L87 Difference]: Start difference. First operand 124 states and 156 transitions. Second operand has 31 states, 26 states have (on average 1.7307692307692308) internal successors, (45), 24 states have internal predecessors, (45), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:15:50,480 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 4.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2025-03-03 13:16:10,456 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:10,456 INFO L93 Difference]: Finished difference Result 339 states and 450 transitions. [2025-03-03 13:16:10,457 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 29 states. [2025-03-03 13:16:10,458 INFO L78 Accepts]: Start accepts. Automaton has has 31 states, 26 states have (on average 1.7307692307692308) internal successors, (45), 24 states have internal predecessors, (45), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 32 [2025-03-03 13:16:10,458 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:10,459 INFO L225 Difference]: With dead ends: 339 [2025-03-03 13:16:10,459 INFO L226 Difference]: Without dead ends: 231 [2025-03-03 13:16:10,461 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 31 SyntacticMatches, 0 SemanticMatches, 60 ConstructedPredicates, 1 IntricatePredicates, 0 DeprecatedPredicates, 877 ImplicationChecksByTransitivity, 23.5s TimeCoverageRelationStatistics Valid=489, Invalid=3162, Unknown=13, NotChecked=118, Total=3782 [2025-03-03 13:16:10,463 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 336 mSDsluCounter, 586 mSDsCounter, 0 mSdLazyCounter, 1228 mSolverCounterSat, 142 mSolverCounterUnsat, 31 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 5.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 336 SdHoareTripleChecker+Valid, 624 SdHoareTripleChecker+Invalid, 1401 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 142 IncrementalHoareTripleChecker+Valid, 1228 IncrementalHoareTripleChecker+Invalid, 31 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.9s IncrementalHoareTripleChecker+Time [2025-03-03 13:16:10,463 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [336 Valid, 624 Invalid, 1401 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [142 Valid, 1228 Invalid, 31 Unknown, 0 Unchecked, 5.9s Time] [2025-03-03 13:16:10,464 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 231 states. [2025-03-03 13:16:10,498 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 231 to 175. [2025-03-03 13:16:10,498 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 175 states, 135 states have (on average 1.2592592592592593) internal successors, (170), 141 states have internal predecessors, (170), 22 states have call successors, (22), 12 states have call predecessors, (22), 15 states have return successors, (29), 21 states have call predecessors, (29), 22 states have call successors, (29) [2025-03-03 13:16:10,499 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 175 states to 175 states and 221 transitions. [2025-03-03 13:16:10,500 INFO L78 Accepts]: Start accepts. Automaton has 175 states and 221 transitions. Word has length 32 [2025-03-03 13:16:10,500 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:10,500 INFO L471 AbstractCegarLoop]: Abstraction has 175 states and 221 transitions. [2025-03-03 13:16:10,500 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 31 states, 26 states have (on average 1.7307692307692308) internal successors, (45), 24 states have internal predecessors, (45), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:16:10,500 INFO L276 IsEmpty]: Start isEmpty. Operand 175 states and 221 transitions. [2025-03-03 13:16:10,501 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 51 [2025-03-03 13:16:10,501 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:10,501 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:16:10,509 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 13:16:10,701 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:10,702 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:10,702 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:10,702 INFO L85 PathProgramCache]: Analyzing trace with hash 1907832900, now seen corresponding path program 2 times [2025-03-03 13:16:10,702 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-03-03 13:16:10,702 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1628155307] [2025-03-03 13:16:10,702 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:16:10,702 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-03-03 13:16:10,715 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 13:16:10,733 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 13:16:10,733 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:16:10,733 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:13,479 INFO L134 CoverageAnalysis]: Checked inductivity of 20 backedges. 0 proven. 17 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-03 13:16:13,479 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-03-03 13:16:13,479 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1628155307] [2025-03-03 13:16:13,479 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1628155307] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:16:13,480 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [613040544] [2025-03-03 13:16:13,480 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:16:13,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:13,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:13,481 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:13,492 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 13:16:13,567 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 50 statements into 2 equivalence classes. [2025-03-03 13:16:13,603 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 50 of 50 statements. [2025-03-03 13:16:13,603 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:16:13,603 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:13,605 INFO L256 TraceCheckSpWp]: Trace formula consists of 392 conjuncts, 126 conjuncts are in the unsatisfiable core [2025-03-03 13:16:13,609 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:13,885 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2025-03-03 13:16:13,885 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 [2025-03-03 13:16:14,554 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 9 treesize of output 12 [2025-03-03 13:16:14,574 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 22 [2025-03-03 13:16:14,797 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 19 treesize of output 22 [2025-03-03 13:16:14,816 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 9 treesize of output 12 [2025-03-03 13:16:15,753 INFO L349 Elim1Store]: treesize reduction 461, result has 14.9 percent of original size [2025-03-03 13:16:15,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 6 stores, 4 select indices, 4 select index equivalence classes, 2 disjoint index pairs (out of 6 index pairs), introduced 10 new quantified variables, introduced 22 case distinctions, treesize of input 258 treesize of output 554 [2025-03-03 13:16:15,995 INFO L349 Elim1Store]: treesize reduction 160, result has 22.0 percent of original size [2025-03-03 13:16:15,996 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 4 new quantified variables, introduced 6 case distinctions, treesize of input 234 treesize of output 316 [2025-03-03 13:16:16,196 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:16,203 INFO L224 Elim1Store]: Index analysis took 117 ms [2025-03-03 13:16:16,225 INFO L349 Elim1Store]: treesize reduction 199, result has 0.5 percent of original size [2025-03-03 13:16:16,225 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 3 new quantified variables, introduced 12 case distinctions, treesize of input 87 treesize of output 51 [2025-03-03 13:16:16,355 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:16,364 INFO L349 Elim1Store]: treesize reduction 59, result has 1.7 percent of original size [2025-03-03 13:16:16,364 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 6 case distinctions, treesize of input 46 treesize of output 29 [2025-03-03 13:16:16,670 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:16,674 INFO L224 Elim1Store]: Index analysis took 163 ms [2025-03-03 13:16:16,722 INFO L349 Elim1Store]: treesize reduction 199, result has 0.5 percent of original size [2025-03-03 13:16:16,722 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 3 new quantified variables, introduced 12 case distinctions, treesize of input 87 treesize of output 51 [2025-03-03 13:16:16,900 INFO L349 Elim1Store]: treesize reduction 43, result has 2.3 percent of original size [2025-03-03 13:16:16,901 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 3 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 11 [2025-03-03 13:16:17,002 INFO L349 Elim1Store]: treesize reduction 63, result has 1.6 percent of original size [2025-03-03 13:16:17,002 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 4 case distinctions, treesize of input 41 treesize of output 11 [2025-03-03 13:16:17,112 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,138 INFO L349 Elim1Store]: treesize reduction 43, result has 2.3 percent of original size [2025-03-03 13:16:17,138 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 41 treesize of output 11 [2025-03-03 13:16:17,290 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,291 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 8 treesize of output 1 [2025-03-03 13:16:17,628 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,634 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:17,647 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:17,652 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:17,659 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,661 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,665 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,669 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,669 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 3 select indices, 3 select index equivalence classes, 10 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 0 case distinctions, treesize of input 206 treesize of output 358 [2025-03-03 13:16:17,767 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,768 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,769 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,779 INFO L349 Elim1Store]: treesize reduction 72, result has 1.4 percent of original size [2025-03-03 13:16:17,780 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 2 select indices, 2 select index equivalence classes, 4 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 83 treesize of output 165 [2025-03-03 13:16:17,861 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:17,894 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,897 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,906 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:17,942 INFO L349 Elim1Store]: treesize reduction 294, result has 3.9 percent of original size [2025-03-03 13:16:17,942 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 3 select indices, 3 select index equivalence classes, 5 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 12 case distinctions, treesize of input 214 treesize of output 351 [2025-03-03 13:16:18,056 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:18,070 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:18,071 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:18,072 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:18,082 INFO L349 Elim1Store]: treesize reduction 72, result has 1.4 percent of original size [2025-03-03 13:16:18,082 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 2 select indices, 2 select index equivalence classes, 5 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 3 case distinctions, treesize of input 83 treesize of output 165 [2025-03-03 13:16:21,521 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-03 13:16:21,525 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-03 13:16:23,662 WARN L320 FreeRefinementEngine]: Global settings require throwing the following exception [2025-03-03 13:16:23,669 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 13:16:23,863 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:23,864 FATAL L? ?]: The Plugin de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction has thrown an exception: java.lang.AssertionError: no need to replace index at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructReplacementForSelectCase(DerPreprocessor.java:331) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructDerEnabler(DerPreprocessor.java:186) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.(DerPreprocessor.java:144) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.ElimStorePlain.applyComplexEliminationRules(ElimStorePlain.java:153) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:190) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne3(DualJunctionSaa.java:172) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne2(DualJunctionSaa.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne1(DualJunctionSaa.java:140) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne0(DualJunctionSaa.java:124) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminateOne(DualJunctionSaa.java:108) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryExhaustivelyToEliminate(DualJunctionSaa.java:93) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.DualJunctionSaa.tryToEliminate(DualJunctionSaa.java:88) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToEliminateOne(QuantifierPusher.java:542) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyNewEliminationTechniquesExhaustively(QuantifierPusher.java:521) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.applyDualJunctionEliminationTechniques(QuantifierPusher.java:514) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:325) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:189) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:100) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:84) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:297) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.pushMinionEliminatees(QuantifierPushUtilsForSubsetPush.java:255) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.sequentialSubsetPush(QuantifierPushUtilsForSubsetPush.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:337) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:189) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:100) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:84) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:297) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.pushMinionEliminatees(QuantifierPushUtilsForSubsetPush.java:255) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushUtilsForSubsetPush.sequentialSubsetPush(QuantifierPushUtilsForSubsetPush.java:151) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher.tryToPushOverDualFiniteConnective(QuantifierPusher.java:337) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:189) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.convert(QuantifierPushTermWalker.java:1) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine$ApplicationTermTask.doStep(TermContextTransformationEngine.java:209) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:100) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.TermContextTransformationEngine.transform(TermContextTransformationEngine.java:84) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:297) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPushTermWalker.eliminate(QuantifierPushTermWalker.java:283) at de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.PartialQuantifierElimination.eliminate(PartialQuantifierElimination.java:51) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer$QuantifierEliminationPostprocessor.postprocess(IterativePredicateTransformer.java:234) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.applyPostprocessors(IterativePredicateTransformer.java:416) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.predicates.IterativePredicateTransformer.computeStrongestPostconditionSequence(IterativePredicateTransformer.java:195) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolantsUsingUnsatCore(TraceCheckSpWp.java:291) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.computeInterpolants(TraceCheckSpWp.java:181) at de.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.singletracecheck.TraceCheckSpWp.(TraceCheckSpWp.java:160) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:106) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.tracehandling.IpTcStrategyModuleSpWp.construct(IpTcStrategyModuleSpWp.java:1) 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:317) 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:428) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseProgram(TraceAbstractionStarter.java:314) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.analyseSequentialProgram(TraceAbstractionStarter.java:275) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.runCegarLoops(TraceAbstractionStarter.java:167) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionStarter.(TraceAbstractionStarter.java:140) at de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver.finish(TraceAbstractionObserver.java:132) 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) [2025-03-03 13:16:23,870 INFO L158 Benchmark]: Toolchain (without parser) took 73280.78ms. Allocated memory was 201.3MB in the beginning and 520.1MB in the end (delta: 318.8MB). Free memory was 158.0MB in the beginning and 395.5MB in the end (delta: -237.5MB). Peak memory consumption was 246.0MB. Max. memory is 16.1GB. [2025-03-03 13:16:23,870 INFO L158 Benchmark]: CDTParser took 0.85ms. Allocated memory is still 201.3MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 13:16:23,870 INFO L158 Benchmark]: CACSL2BoogieTranslator took 327.10ms. Allocated memory is still 201.3MB. Free memory was 157.6MB in the beginning and 137.1MB in the end (delta: 20.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-03-03 13:16:23,870 INFO L158 Benchmark]: Boogie Procedure Inliner took 40.50ms. Allocated memory is still 201.3MB. Free memory was 137.1MB in the beginning and 135.1MB in the end (delta: 2.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-03-03 13:16:23,871 INFO L158 Benchmark]: Boogie Preprocessor took 64.11ms. Allocated memory is still 201.3MB. Free memory was 135.1MB in the beginning and 129.5MB in the end (delta: 5.6MB). There was no memory consumed. Max. memory is 16.1GB. [2025-03-03 13:16:23,871 INFO L158 Benchmark]: IcfgBuilder took 442.96ms. Allocated memory is still 201.3MB. Free memory was 129.5MB in the beginning and 105.5MB in the end (delta: 23.9MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. [2025-03-03 13:16:23,872 INFO L158 Benchmark]: TraceAbstraction took 72400.43ms. Allocated memory was 201.3MB in the beginning and 520.1MB in the end (delta: 318.8MB). Free memory was 105.1MB in the beginning and 395.5MB in the end (delta: -290.3MB). Peak memory consumption was 195.6MB. Max. memory is 16.1GB. [2025-03-03 13:16:23,873 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.85ms. Allocated memory is still 201.3MB. Free memory is still 115.6MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 327.10ms. Allocated memory is still 201.3MB. Free memory was 157.6MB in the beginning and 137.1MB in the end (delta: 20.5MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 40.50ms. Allocated memory is still 201.3MB. Free memory was 137.1MB in the beginning and 135.1MB in the end (delta: 2.0MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Preprocessor took 64.11ms. Allocated memory is still 201.3MB. Free memory was 135.1MB in the beginning and 129.5MB in the end (delta: 5.6MB). There was no memory consumed. Max. memory is 16.1GB. * IcfgBuilder took 442.96ms. Allocated memory is still 201.3MB. Free memory was 129.5MB in the beginning and 105.5MB in the end (delta: 23.9MB). Peak memory consumption was 25.2MB. Max. memory is 16.1GB. * TraceAbstraction took 72400.43ms. Allocated memory was 201.3MB in the beginning and 520.1MB in the end (delta: 318.8MB). Free memory was 105.1MB in the beginning and 395.5MB in the end (delta: -290.3MB). Peak memory consumption was 195.6MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - ExceptionOrErrorResult: AssertionError: no need to replace index de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: AssertionError: no need to replace index: de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.arrays.DerPreprocessor.constructReplacementForSelectCase(DerPreprocessor.java:331) RESULT: Ultimate could not prove your program: Toolchain returned no result. [2025-03-03 13:16:24,079 WARN L435 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forcibly destroying the process [2025-03-03 13:16:24,109 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Forceful destruction successful, exit code 137 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: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --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 Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 --- Real Ultimate output --- This is Ultimate 0.3.0-?-798a7b3-m [2025-03-03 13:16:25,611 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-03-03 13:16:25,687 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Bitvector.epf [2025-03-03 13:16:25,695 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-03-03 13:16:25,697 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-03-03 13:16:25,711 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-03-03 13:16:25,712 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-03-03 13:16:25,712 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-03-03 13:16:25,712 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-03-03 13:16:25,712 INFO L153 SettingsManager]: * Use memory slicer=true [2025-03-03 13:16:25,712 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-03-03 13:16:25,712 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-03-03 13:16:25,712 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-03-03 13:16:25,712 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Use SBE=true [2025-03-03 13:16:25,713 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * sizeof long=4 [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Adapt memory model on pointer casts if necessary=true [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Use bitvectors instead of ints=true [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Memory model=HoenickeLindenmann_4ByteResolution [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * sizeof long double=12 [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-03-03 13:16:25,713 INFO L153 SettingsManager]: * Use constant arrays=true [2025-03-03 13:16:25,714 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:16:25,714 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-03-03 13:16:25,714 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Trace refinement strategy=FOX [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Command for external solver=cvc4 --incremental --print-success --lang smt [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-03-03 13:16:25,715 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC 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 -> /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux 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 -> Automizer 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 -> 10aecdd717bb6691571ad1da0b912f030832fb85361f767ea82293acfe046216 [2025-03-03 13:16:25,928 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-03-03 13:16:25,933 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-03-03 13:16:25,935 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-03-03 13:16:25,935 INFO L270 PluginConnector]: Initializing CDTParser... [2025-03-03 13:16:25,935 INFO L274 PluginConnector]: CDTParser initialized [2025-03-03 13:16:25,936 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2025-03-03 13:16:27,101 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e96e4196/4839b0ef7d254f87bb8b70f79b91fae9/FLAG1ec0cf156 [2025-03-03 13:16:27,332 INFO L384 CDTParser]: Found 1 translation units. [2025-03-03 13:16:27,333 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i [2025-03-03 13:16:27,346 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e96e4196/4839b0ef7d254f87bb8b70f79b91fae9/FLAG1ec0cf156 [2025-03-03 13:16:27,661 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/8e96e4196/4839b0ef7d254f87bb8b70f79b91fae9 [2025-03-03 13:16:27,663 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-03-03 13:16:27,664 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-03-03 13:16:27,665 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-03-03 13:16:27,665 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-03-03 13:16:27,668 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-03-03 13:16:27,668 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:16:27" (1/1) ... [2025-03-03 13:16:27,668 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@320ac2a8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:27, skipping insertion in model container [2025-03-03 13:16:27,669 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 03.03 01:16:27" (1/1) ... [2025-03-03 13:16:27,695 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:16:27,884 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-03 13:16:27,900 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2025-03-03 13:16:27,905 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2025-03-03 13:16:27,907 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2025-03-03 13:16:27,914 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:16:27,923 INFO L197 MainTranslator]: Restarting translation with changed settings: SettingsChange [mNewPreferredMemoryModel=HoenickeLindenmann_1ByteResolution] [2025-03-03 13:16:27,928 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-03-03 13:16:27,954 WARN L1100 CHandler]: saw a pointer cast to a type that we could not get a type size for, not adapting memory model [2025-03-03 13:16:27,960 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2025-03-03 13:16:27,961 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2025-03-03 13:16:27,961 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2025-03-03 13:16:27,968 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:16:27,971 INFO L200 MainTranslator]: Completed pre-run [2025-03-03 13:16:28,020 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26271,26284] [2025-03-03 13:16:28,024 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26396,26409] [2025-03-03 13:16:28,024 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/ldv-sets/test_mutex_unbounded-1.i[26511,26524] [2025-03-03 13:16:28,030 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-03-03 13:16:28,059 INFO L204 MainTranslator]: Completed translation [2025-03-03 13:16:28,060 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28 WrapperNode [2025-03-03 13:16:28,061 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-03-03 13:16:28,062 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-03-03 13:16:28,062 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-03-03 13:16:28,062 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-03-03 13:16:28,066 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,077 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,094 INFO L138 Inliner]: procedures = 143, calls = 62, calls flagged for inlining = 15, calls inlined = 14, statements flattened = 169 [2025-03-03 13:16:28,094 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-03-03 13:16:28,094 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-03-03 13:16:28,094 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-03-03 13:16:28,094 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-03-03 13:16:28,100 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,100 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,103 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,133 INFO L175 MemorySlicer]: Split 28 memory accesses to 2 slices as follows [2, 26]. 93 percent of accesses are in the largest equivalence class. The 6 initializations are split as follows [2, 4]. The 7 writes are split as follows [0, 7]. [2025-03-03 13:16:28,134 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,134 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,146 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,150 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,151 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,152 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,154 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-03-03 13:16:28,155 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2025-03-03 13:16:28,155 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2025-03-03 13:16:28,155 INFO L274 PluginConnector]: IcfgBuilder initialized [2025-03-03 13:16:28,155 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (1/1) ... [2025-03-03 13:16:28,159 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-03-03 13:16:28,168 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:28,178 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-03-03 13:16:28,180 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-03-03 13:16:28,195 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2025-03-03 13:16:28,195 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2025-03-03 13:16:28,195 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_list_add [2025-03-03 13:16:28,195 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_list_add [2025-03-03 13:16:28,195 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2025-03-03 13:16:28,195 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2025-03-03 13:16:28,196 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#0 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~intINTTYPE1#1 [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2025-03-03 13:16:28,196 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2025-03-03 13:16:28,196 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-03-03 13:16:28,196 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-03-03 13:16:28,303 INFO L256 CfgBuilder]: Building ICFG [2025-03-03 13:16:28,304 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2025-03-03 13:16:28,540 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L667: havoc ldv_set_empty_#t~ret31#1; [2025-03-03 13:16:28,541 INFO L1325 $ProcedureCfgBuilder]: dead code at ProgramPoint L624: havoc ldv_list_empty_#t~mem10#1.base, ldv_list_empty_#t~mem10#1.offset; [2025-03-03 13:16:28,576 INFO L? ?]: Removed 73 outVars from TransFormulas that were not future-live. [2025-03-03 13:16:28,576 INFO L307 CfgBuilder]: Performing block encoding [2025-03-03 13:16:28,583 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-03-03 13:16:28,584 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2025-03-03 13:16:28,584 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:16:28 BoogieIcfgContainer [2025-03-03 13:16:28,584 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2025-03-03 13:16:28,585 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-03-03 13:16:28,586 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-03-03 13:16:28,590 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-03-03 13:16:28,590 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 03.03 01:16:27" (1/3) ... [2025-03-03 13:16:28,591 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c2707d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:16:28, skipping insertion in model container [2025-03-03 13:16:28,591 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 03.03 01:16:28" (2/3) ... [2025-03-03 13:16:28,591 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@5c2707d4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 03.03 01:16:28, skipping insertion in model container [2025-03-03 13:16:28,591 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 03.03 01:16:28" (3/3) ... [2025-03-03 13:16:28,592 INFO L128 eAbstractionObserver]: Analyzing ICFG test_mutex_unbounded-1.i [2025-03-03 13:16:28,601 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-03-03 13:16:28,602 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG test_mutex_unbounded-1.i that has 5 procedures, 63 locations, 1 initial locations, 5 loop locations, and 3 error locations. [2025-03-03 13:16:28,631 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-03-03 13:16:28,639 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=PETRI_NET, 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;@f8b117, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-03-03 13:16:28,639 INFO L334 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2025-03-03 13:16:28,642 INFO L276 IsEmpty]: Start isEmpty. Operand has 63 states, 47 states have (on average 1.3191489361702127) internal successors, (62), 50 states have internal predecessors, (62), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:16:28,645 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 11 [2025-03-03 13:16:28,645 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:28,645 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:16:28,646 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:28,648 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:28,649 INFO L85 PathProgramCache]: Analyzing trace with hash -1743513595, now seen corresponding path program 1 times [2025-03-03 13:16:28,654 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:28,655 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [863756701] [2025-03-03 13:16:28,655 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:28,655 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:28,655 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:28,657 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:28,658 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-03-03 13:16:28,725 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 10 statements into 1 equivalence classes. [2025-03-03 13:16:28,736 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 10 of 10 statements. [2025-03-03 13:16:28,736 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:28,736 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:28,738 INFO L256 TraceCheckSpWp]: Trace formula consists of 51 conjuncts, 14 conjuncts are in the unsatisfiable core [2025-03-03 13:16:28,743 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:28,872 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:28,874 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:16:28,876 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:28,876 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [863756701] [2025-03-03 13:16:28,877 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [863756701] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:16:28,877 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:16:28,877 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-03-03 13:16:28,878 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2104470674] [2025-03-03 13:16:28,879 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:16:28,881 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2025-03-03 13:16:28,881 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:28,893 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2025-03-03 13:16:28,893 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2025-03-03 13:16:28,895 INFO L87 Difference]: Start difference. First operand has 63 states, 47 states have (on average 1.3191489361702127) internal successors, (62), 50 states have internal predecessors, (62), 8 states have call successors, (8), 4 states have call predecessors, (8), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) Second operand has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 13:16:29,328 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:29,329 INFO L93 Difference]: Finished difference Result 171 states and 221 transitions. [2025-03-03 13:16:29,330 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2025-03-03 13:16:29,331 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 10 [2025-03-03 13:16:29,331 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:29,335 INFO L225 Difference]: With dead ends: 171 [2025-03-03 13:16:29,335 INFO L226 Difference]: Without dead ends: 98 [2025-03-03 13:16:29,337 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 3 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=21, Invalid=51, Unknown=0, NotChecked=0, Total=72 [2025-03-03 13:16:29,339 INFO L435 NwaCegarLoop]: 53 mSDtfsCounter, 53 mSDsluCounter, 202 mSDsCounter, 0 mSdLazyCounter, 112 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 255 SdHoareTripleChecker+Invalid, 112 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 112 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-03 13:16:29,339 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 255 Invalid, 112 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 112 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-03 13:16:29,362 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 98 states. [2025-03-03 13:16:29,375 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 98 to 81. [2025-03-03 13:16:29,376 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 81 states, 62 states have (on average 1.3064516129032258) internal successors, (81), 64 states have internal predecessors, (81), 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) [2025-03-03 13:16:29,378 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 81 states to 81 states and 103 transitions. [2025-03-03 13:16:29,380 INFO L78 Accepts]: Start accepts. Automaton has 81 states and 103 transitions. Word has length 10 [2025-03-03 13:16:29,380 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:29,380 INFO L471 AbstractCegarLoop]: Abstraction has 81 states and 103 transitions. [2025-03-03 13:16:29,380 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 5 states have internal predecessors, (10), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-03-03 13:16:29,380 INFO L276 IsEmpty]: Start isEmpty. Operand 81 states and 103 transitions. [2025-03-03 13:16:29,382 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 13 [2025-03-03 13:16:29,382 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:29,382 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:16:29,387 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-03-03 13:16:29,582 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:29,583 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:29,583 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:29,583 INFO L85 PathProgramCache]: Analyzing trace with hash -1903122020, now seen corresponding path program 1 times [2025-03-03 13:16:29,583 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:29,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1489947354] [2025-03-03 13:16:29,584 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:29,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:29,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:29,585 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:29,586 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-03-03 13:16:29,637 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 12 statements into 1 equivalence classes. [2025-03-03 13:16:29,645 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 12 of 12 statements. [2025-03-03 13:16:29,645 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:29,645 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:29,647 INFO L256 TraceCheckSpWp]: Trace formula consists of 56 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-03 13:16:29,648 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:29,665 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:29,666 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:16:29,666 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:29,666 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1489947354] [2025-03-03 13:16:29,666 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1489947354] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:16:29,666 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:16:29,666 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:16:29,666 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1338614192] [2025-03-03 13:16:29,666 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:16:29,667 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:16:29,667 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:29,668 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:16:29,668 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:16:29,668 INFO L87 Difference]: Start difference. First operand 81 states and 103 transitions. Second operand has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:16:29,690 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:29,691 INFO L93 Difference]: Finished difference Result 89 states and 116 transitions. [2025-03-03 13:16:29,691 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:16:29,692 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 12 [2025-03-03 13:16:29,692 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:29,693 INFO L225 Difference]: With dead ends: 89 [2025-03-03 13:16:29,694 INFO L226 Difference]: Without dead ends: 87 [2025-03-03 13:16:29,694 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 11 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:16:29,695 INFO L435 NwaCegarLoop]: 68 mSDtfsCounter, 0 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 199 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 [2025-03-03 13:16:29,695 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 199 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:16:29,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 87 states. [2025-03-03 13:16:29,706 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 87 to 87. [2025-03-03 13:16:29,707 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 87 states, 66 states have (on average 1.2878787878787878) internal successors, (85), 68 states have internal predecessors, (85), 11 states have call successors, (11), 5 states have call predecessors, (11), 7 states have return successors, (17), 13 states have call predecessors, (17), 11 states have call successors, (17) [2025-03-03 13:16:29,708 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 87 states to 87 states and 113 transitions. [2025-03-03 13:16:29,708 INFO L78 Accepts]: Start accepts. Automaton has 87 states and 113 transitions. Word has length 12 [2025-03-03 13:16:29,708 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:29,708 INFO L471 AbstractCegarLoop]: Abstraction has 87 states and 113 transitions. [2025-03-03 13:16:29,708 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.5) internal successors, (10), 3 states have internal predecessors, (10), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:16:29,708 INFO L276 IsEmpty]: Start isEmpty. Operand 87 states and 113 transitions. [2025-03-03 13:16:29,708 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 14 [2025-03-03 13:16:29,709 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:29,709 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-03-03 13:16:29,714 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2025-03-03 13:16:29,912 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:29,912 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:29,912 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:29,913 INFO L85 PathProgramCache]: Analyzing trace with hash 1270961980, now seen corresponding path program 1 times [2025-03-03 13:16:29,913 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:29,913 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [594989476] [2025-03-03 13:16:29,913 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:29,913 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:29,913 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:29,915 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:29,916 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-03-03 13:16:29,969 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 13 statements into 1 equivalence classes. [2025-03-03 13:16:29,980 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 13 of 13 statements. [2025-03-03 13:16:29,980 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:29,980 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:29,982 INFO L256 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 6 conjuncts are in the unsatisfiable core [2025-03-03 13:16:29,983 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:30,038 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 15 treesize of output 7 [2025-03-03 13:16:30,045 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 [2025-03-03 13:16:30,061 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:30,063 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:16:30,063 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:30,063 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [594989476] [2025-03-03 13:16:30,063 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [594989476] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:16:30,063 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:16:30,063 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2025-03-03 13:16:30,063 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1232707504] [2025-03-03 13:16:30,063 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:16:30,064 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:16:30,064 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:30,065 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:16:30,065 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:16:30,065 INFO L87 Difference]: Start difference. First operand 87 states and 113 transitions. Second operand has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:16:30,478 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:30,479 INFO L93 Difference]: Finished difference Result 153 states and 192 transitions. [2025-03-03 13:16:30,479 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:16:30,479 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Word has length 13 [2025-03-03 13:16:30,479 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:30,480 INFO L225 Difference]: With dead ends: 153 [2025-03-03 13:16:30,480 INFO L226 Difference]: Without dead ends: 73 [2025-03-03 13:16:30,480 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 10 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2025-03-03 13:16:30,481 INFO L435 NwaCegarLoop]: 65 mSDtfsCounter, 13 mSDsluCounter, 98 mSDsCounter, 0 mSdLazyCounter, 41 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.4s Time, 0 mProtectedPredicate, 0 mProtectedAction, 13 SdHoareTripleChecker+Valid, 163 SdHoareTripleChecker+Invalid, 43 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 41 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.4s IncrementalHoareTripleChecker+Time [2025-03-03 13:16:30,481 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [13 Valid, 163 Invalid, 43 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 41 Invalid, 0 Unknown, 0 Unchecked, 0.4s Time] [2025-03-03 13:16:30,481 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 73 states. [2025-03-03 13:16:30,489 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 73 to 68. [2025-03-03 13:16:30,492 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 68 states, 50 states have (on average 1.2) internal successors, (60), 53 states have internal predecessors, (60), 9 states have call successors, (9), 5 states have call predecessors, (9), 6 states have return successors, (12), 9 states have call predecessors, (12), 9 states have call successors, (12) [2025-03-03 13:16:30,493 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 68 states to 68 states and 81 transitions. [2025-03-03 13:16:30,493 INFO L78 Accepts]: Start accepts. Automaton has 68 states and 81 transitions. Word has length 13 [2025-03-03 13:16:30,494 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:30,494 INFO L471 AbstractCegarLoop]: Abstraction has 68 states and 81 transitions. [2025-03-03 13:16:30,494 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.75) internal successors, (11), 3 states have internal predecessors, (11), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2025-03-03 13:16:30,494 INFO L276 IsEmpty]: Start isEmpty. Operand 68 states and 81 transitions. [2025-03-03 13:16:30,494 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 29 [2025-03-03 13:16:30,495 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:30,495 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:16:30,501 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-03-03 13:16:30,699 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:30,699 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:30,699 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:30,700 INFO L85 PathProgramCache]: Analyzing trace with hash 1900906071, now seen corresponding path program 1 times [2025-03-03 13:16:30,700 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:30,700 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [422757521] [2025-03-03 13:16:30,700 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:30,700 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:30,700 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:30,702 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:30,703 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-03-03 13:16:30,762 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 28 statements into 1 equivalence classes. [2025-03-03 13:16:30,787 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 28 of 28 statements. [2025-03-03 13:16:30,788 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:30,788 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:30,794 INFO L256 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 24 conjuncts are in the unsatisfiable core [2025-03-03 13:16:30,797 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:30,890 INFO L349 Elim1Store]: treesize reduction 6, result has 40.0 percent of original size [2025-03-03 13:16:30,891 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 13 treesize of output 13 [2025-03-03 13:16:30,984 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:30,989 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 16 treesize of output 8 [2025-03-03 13:16:30,992 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 8 treesize of output 7 [2025-03-03 13:16:31,005 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 4 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 [2025-03-03 13:16:31,022 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 1 new quantified variables, introduced 0 case distinctions, treesize of input 65 treesize of output 57 [2025-03-03 13:16:31,036 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 31 treesize of output 39 [2025-03-03 13:16:31,041 WARN L214 Elim1Store]: Array PQE input equivalent to false [2025-03-03 13:16:31,050 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 32 [2025-03-03 13:16:31,052 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:31,054 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 0 case distinctions, treesize of input 27 treesize of output 17 [2025-03-03 13:16:31,059 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 [2025-03-03 13:16:31,069 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 [2025-03-03 13:16:31,073 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:31,078 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 [2025-03-03 13:16:31,083 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 8 treesize of output 1 [2025-03-03 13:16:31,181 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 16 treesize of output 8 [2025-03-03 13:16:31,200 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:31,201 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:16:31,619 INFO L349 Elim1Store]: treesize reduction 17, result has 64.6 percent of original size [2025-03-03 13:16:31,620 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 2 new quantified variables, introduced 2 case distinctions, treesize of input 394 treesize of output 337 [2025-03-03 13:16:31,659 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2025-03-03 13:16:31,659 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 3 case distinctions, treesize of input 243 treesize of output 255 [2025-03-03 13:16:31,676 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 248 treesize of output 236 [2025-03-03 13:16:31,698 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 196 treesize of output 194 [2025-03-03 13:16:31,940 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 8 treesize of output 4 [2025-03-03 13:16:32,056 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 6 treesize of output 4 [2025-03-03 13:16:32,060 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 20 treesize of output 18 [2025-03-03 13:16:32,158 INFO L173 IndexEqualityManager]: detected equality via solver [2025-03-03 13:16:32,159 INFO L190 IndexEqualityManager]: detected not equals via solver [2025-03-03 13:16:32,167 INFO L349 Elim1Store]: treesize reduction 9, result has 10.0 percent of original size [2025-03-03 13:16:32,167 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 1 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 24 treesize of output 1 [2025-03-03 13:16:32,305 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:32,305 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:32,305 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [422757521] [2025-03-03 13:16:32,305 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [422757521] provided 0 perfect and 2 imperfect interpolant sequences [2025-03-03 13:16:32,305 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:16:32,306 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 13] total 25 [2025-03-03 13:16:32,306 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1939406528] [2025-03-03 13:16:32,306 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:16:32,306 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2025-03-03 13:16:32,306 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:32,307 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2025-03-03 13:16:32,307 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=75, Invalid=525, Unknown=0, NotChecked=0, Total=600 [2025-03-03 13:16:32,307 INFO L87 Difference]: Start difference. First operand 68 states and 81 transitions. Second operand has 25 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 13:16:34,071 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:34,071 INFO L93 Difference]: Finished difference Result 201 states and 249 transitions. [2025-03-03 13:16:34,072 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2025-03-03 13:16:34,072 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Word has length 28 [2025-03-03 13:16:34,072 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:34,073 INFO L225 Difference]: With dead ends: 201 [2025-03-03 13:16:34,073 INFO L226 Difference]: Without dead ends: 176 [2025-03-03 13:16:34,074 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 73 GetRequests, 33 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 241 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=265, Invalid=1457, Unknown=0, NotChecked=0, Total=1722 [2025-03-03 13:16:34,074 INFO L435 NwaCegarLoop]: 38 mSDtfsCounter, 443 mSDsluCounter, 427 mSDsCounter, 0 mSdLazyCounter, 763 mSolverCounterSat, 132 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 448 SdHoareTripleChecker+Valid, 465 SdHoareTripleChecker+Invalid, 895 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 132 IncrementalHoareTripleChecker+Valid, 763 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2025-03-03 13:16:34,075 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [448 Valid, 465 Invalid, 895 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [132 Valid, 763 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2025-03-03 13:16:34,077 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 176 states. [2025-03-03 13:16:34,097 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 176 to 115. [2025-03-03 13:16:34,098 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 115 states, 88 states have (on average 1.2840909090909092) internal successors, (113), 92 states have internal predecessors, (113), 14 states have call successors, (14), 8 states have call predecessors, (14), 10 states have return successors, (20), 14 states have call predecessors, (20), 14 states have call successors, (20) [2025-03-03 13:16:34,100 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 115 states to 115 states and 147 transitions. [2025-03-03 13:16:34,102 INFO L78 Accepts]: Start accepts. Automaton has 115 states and 147 transitions. Word has length 28 [2025-03-03 13:16:34,102 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:34,102 INFO L471 AbstractCegarLoop]: Abstraction has 115 states and 147 transitions. [2025-03-03 13:16:34,102 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 21 states have (on average 1.8571428571428572) internal successors, (39), 19 states have internal predecessors, (39), 6 states have call successors, (6), 4 states have call predecessors, (6), 6 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2025-03-03 13:16:34,102 INFO L276 IsEmpty]: Start isEmpty. Operand 115 states and 147 transitions. [2025-03-03 13:16:34,102 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2025-03-03 13:16:34,102 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:34,103 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:16:34,110 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-03-03 13:16:34,303 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:34,303 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:34,304 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:34,304 INFO L85 PathProgramCache]: Analyzing trace with hash -301043798, now seen corresponding path program 1 times [2025-03-03 13:16:34,304 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:34,304 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [758456734] [2025-03-03 13:16:34,304 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:34,304 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:34,304 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:34,307 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:34,308 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2025-03-03 13:16:34,363 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 13:16:34,382 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 13:16:34,382 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:34,382 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:34,384 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 43 conjuncts are in the unsatisfiable core [2025-03-03 13:16:34,387 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:34,639 INFO L349 Elim1Store]: treesize reduction 6, result has 40.0 percent of original size [2025-03-03 13:16:34,639 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 13 treesize of output 13 [2025-03-03 13:16:34,717 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 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 15 treesize of output 7 [2025-03-03 13:16:35,060 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2025-03-03 13:16:35,060 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 16 [2025-03-03 13:16:35,068 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2025-03-03 13:16:35,069 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 1 case distinctions, treesize of input 21 treesize of output 11 [2025-03-03 13:16:35,251 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:35,251 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:16:35,680 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:35,680 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [758456734] [2025-03-03 13:16:35,681 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [758456734] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:16:35,681 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleCvc4 [357411272] [2025-03-03 13:16:35,681 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:35,681 INFO L173 SolverBuilder]: Constructing external solver with command: cvc4 --incremental --print-success --lang smt [2025-03-03 13:16:35,681 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 [2025-03-03 13:16:35,683 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (exit command is (exit), workingDir is null) [2025-03-03 13:16:35,683 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Waiting until timeout for monitored process [2025-03-03 13:16:35,759 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 31 statements into 1 equivalence classes. [2025-03-03 13:16:35,832 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 31 of 31 statements. [2025-03-03 13:16:35,832 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:35,832 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:35,834 INFO L256 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 47 conjuncts are in the unsatisfiable core [2025-03-03 13:16:35,839 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:36,246 INFO L349 Elim1Store]: treesize reduction 6, result has 40.0 percent of original size [2025-03-03 13:16:36,246 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 13 treesize of output 13 [2025-03-03 13:16:36,817 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2025-03-03 13:16:36,817 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 28 treesize of output 16 [2025-03-03 13:16:36,823 INFO L349 Elim1Store]: treesize reduction 11, result has 8.3 percent of original size [2025-03-03 13:16:36,823 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 35 treesize of output 21 [2025-03-03 13:16:37,052 INFO L134 CoverageAnalysis]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-03-03 13:16:37,052 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-03-03 13:16:37,386 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleCvc4 [357411272] provided 0 perfect and 1 imperfect interpolant sequences [2025-03-03 13:16:37,387 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-03-03 13:16:37,387 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 14] total 27 [2025-03-03 13:16:37,387 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [167592095] [2025-03-03 13:16:37,387 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-03-03 13:16:37,387 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 28 states [2025-03-03 13:16:37,387 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:37,388 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 28 interpolants. [2025-03-03 13:16:37,388 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=144, Invalid=896, Unknown=16, NotChecked=0, Total=1056 [2025-03-03 13:16:37,388 INFO L87 Difference]: Start difference. First operand 115 states and 147 transitions. Second operand has 28 states, 24 states have (on average 1.8333333333333333) internal successors, (44), 21 states have internal predecessors, (44), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:16:39,152 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:39,153 INFO L93 Difference]: Finished difference Result 278 states and 359 transitions. [2025-03-03 13:16:39,157 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 15 states. [2025-03-03 13:16:39,157 INFO L78 Accepts]: Start accepts. Automaton has has 28 states, 24 states have (on average 1.8333333333333333) internal successors, (44), 21 states have internal predecessors, (44), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) Word has length 31 [2025-03-03 13:16:39,157 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:39,158 INFO L225 Difference]: With dead ends: 278 [2025-03-03 13:16:39,158 INFO L226 Difference]: Without dead ends: 179 [2025-03-03 13:16:39,159 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 53 SyntacticMatches, 0 SemanticMatches, 38 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 366 ImplicationChecksByTransitivity, 1.5s TimeCoverageRelationStatistics Valid=238, Invalid=1306, Unknown=16, NotChecked=0, Total=1560 [2025-03-03 13:16:39,162 INFO L435 NwaCegarLoop]: 43 mSDtfsCounter, 82 mSDsluCounter, 551 mSDsCounter, 0 mSdLazyCounter, 781 mSolverCounterSat, 18 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 1.3s Time, 0 mProtectedPredicate, 0 mProtectedAction, 82 SdHoareTripleChecker+Valid, 594 SdHoareTripleChecker+Invalid, 799 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 781 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 1.4s IncrementalHoareTripleChecker+Time [2025-03-03 13:16:39,162 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [82 Valid, 594 Invalid, 799 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 781 Invalid, 0 Unknown, 0 Unchecked, 1.4s Time] [2025-03-03 13:16:39,162 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 179 states. [2025-03-03 13:16:39,183 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 179 to 154. [2025-03-03 13:16:39,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 154 states, 118 states have (on average 1.2966101694915255) internal successors, (153), 122 states have internal predecessors, (153), 19 states have call successors, (19), 11 states have call predecessors, (19), 14 states have return successors, (26), 20 states have call predecessors, (26), 19 states have call successors, (26) [2025-03-03 13:16:39,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 154 states to 154 states and 198 transitions. [2025-03-03 13:16:39,184 INFO L78 Accepts]: Start accepts. Automaton has 154 states and 198 transitions. Word has length 31 [2025-03-03 13:16:39,184 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:39,184 INFO L471 AbstractCegarLoop]: Abstraction has 154 states and 198 transitions. [2025-03-03 13:16:39,184 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 28 states, 24 states have (on average 1.8333333333333333) internal successors, (44), 21 states have internal predecessors, (44), 8 states have call successors, (8), 6 states have call predecessors, (8), 8 states have return successors, (8), 7 states have call predecessors, (8), 8 states have call successors, (8) [2025-03-03 13:16:39,184 INFO L276 IsEmpty]: Start isEmpty. Operand 154 states and 198 transitions. [2025-03-03 13:16:39,185 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 48 [2025-03-03 13:16:39,185 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:39,185 INFO L218 NwaCegarLoop]: trace histogram [3, 3, 3, 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, 1, 1, 1, 1, 1, 1] [2025-03-03 13:16:39,191 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2025-03-03 13:16:39,389 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt (7)] Ended with exit code 0 [2025-03-03 13:16:39,586 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/cvc4 --incremental --print-success --lang smt [2025-03-03 13:16:39,586 INFO L396 AbstractCegarLoop]: === Iteration 6 === Targeting ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:39,586 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:39,587 INFO L85 PathProgramCache]: Analyzing trace with hash -285671670, now seen corresponding path program 1 times [2025-03-03 13:16:39,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:39,587 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [915212177] [2025-03-03 13:16:39,587 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-03-03 13:16:39,587 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:39,587 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:39,592 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:39,593 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2025-03-03 13:16:39,657 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 47 statements into 1 equivalence classes. [2025-03-03 13:16:39,677 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 47 of 47 statements. [2025-03-03 13:16:39,677 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-03-03 13:16:39,677 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:39,680 INFO L256 TraceCheckSpWp]: Trace formula consists of 205 conjuncts, 3 conjuncts are in the unsatisfiable core [2025-03-03 13:16:39,681 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:39,691 INFO L134 CoverageAnalysis]: Checked inductivity of 14 backedges. 11 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2025-03-03 13:16:39,692 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-03-03 13:16:39,692 INFO L136 FreeRefinementEngine]: Strategy FOX found an infeasible trace [2025-03-03 13:16:39,692 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [915212177] [2025-03-03 13:16:39,692 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [915212177] provided 1 perfect and 0 imperfect interpolant sequences [2025-03-03 13:16:39,692 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-03-03 13:16:39,692 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2025-03-03 13:16:39,692 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [229742443] [2025-03-03 13:16:39,692 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-03-03 13:16:39,692 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2025-03-03 13:16:39,692 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy FOX [2025-03-03 13:16:39,693 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2025-03-03 13:16:39,693 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:16:39,693 INFO L87 Difference]: Start difference. First operand 154 states and 198 transitions. Second operand has 4 states, 4 states have (on average 8.5) internal successors, (34), 3 states have internal predecessors, (34), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 13:16:39,711 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-03-03 13:16:39,711 INFO L93 Difference]: Finished difference Result 286 states and 373 transitions. [2025-03-03 13:16:39,712 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2025-03-03 13:16:39,712 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 8.5) internal successors, (34), 3 states have internal predecessors, (34), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) Word has length 47 [2025-03-03 13:16:39,712 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-03-03 13:16:39,713 INFO L225 Difference]: With dead ends: 286 [2025-03-03 13:16:39,713 INFO L226 Difference]: Without dead ends: 161 [2025-03-03 13:16:39,713 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 46 GetRequests, 44 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2025-03-03 13:16:39,714 INFO L435 NwaCegarLoop]: 68 mSDtfsCounter, 0 mSDsluCounter, 131 mSDsCounter, 0 mSdLazyCounter, 7 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 199 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 [2025-03-03 13:16:39,714 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 199 Invalid, 7 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 7 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-03-03 13:16:39,714 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 161 states. [2025-03-03 13:16:39,726 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 161 to 158. [2025-03-03 13:16:39,727 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 158 states, 121 states have (on average 1.2892561983471074) internal successors, (156), 124 states have internal predecessors, (156), 19 states have call successors, (19), 11 states have call predecessors, (19), 15 states have return successors, (27), 22 states have call predecessors, (27), 19 states have call successors, (27) [2025-03-03 13:16:39,728 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 158 states to 158 states and 202 transitions. [2025-03-03 13:16:39,728 INFO L78 Accepts]: Start accepts. Automaton has 158 states and 202 transitions. Word has length 47 [2025-03-03 13:16:39,728 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-03-03 13:16:39,728 INFO L471 AbstractCegarLoop]: Abstraction has 158 states and 202 transitions. [2025-03-03 13:16:39,728 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 8.5) internal successors, (34), 3 states have internal predecessors, (34), 2 states have call successors, (6), 2 states have call predecessors, (6), 3 states have return successors, (6), 3 states have call predecessors, (6), 2 states have call successors, (6) [2025-03-03 13:16:39,728 INFO L276 IsEmpty]: Start isEmpty. Operand 158 states and 202 transitions. [2025-03-03 13:16:39,729 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 50 [2025-03-03 13:16:39,729 INFO L210 NwaCegarLoop]: Found error trace [2025-03-03 13:16:39,729 INFO L218 NwaCegarLoop]: trace histogram [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] [2025-03-03 13:16:39,736 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2025-03-03 13:16:39,930 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:39,930 INFO L396 AbstractCegarLoop]: === Iteration 7 === Targeting ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION === [ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr1ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr2ASSERT_VIOLATIONERROR_FUNCTION] === [2025-03-03 13:16:39,930 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-03-03 13:16:39,930 INFO L85 PathProgramCache]: Analyzing trace with hash -813987688, now seen corresponding path program 2 times [2025-03-03 13:16:39,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy FOX [2025-03-03 13:16:39,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [268129880] [2025-03-03 13:16:39,931 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-03-03 13:16:39,931 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-03-03 13:16:39,931 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2025-03-03 13:16:39,933 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-03-03 13:16:39,933 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2025-03-03 13:16:39,999 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 49 statements into 2 equivalence classes. [2025-03-03 13:16:40,032 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 49 of 49 statements. [2025-03-03 13:16:40,032 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-03-03 13:16:40,032 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-03-03 13:16:40,035 INFO L256 TraceCheckSpWp]: Trace formula consists of 245 conjuncts, 78 conjuncts are in the unsatisfiable core [2025-03-03 13:16:40,049 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-03-03 13:16:40,278 INFO L349 Elim1Store]: treesize reduction 22, result has 35.3 percent of original size [2025-03-03 13:16:40,278 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 27 [2025-03-03 13:16:40,392 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 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 15 treesize of output 7 [2025-03-03 13:16:41,166 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 9 treesize of output 12 [2025-03-03 13:16:41,174 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 14 treesize of output 17 [2025-03-03 13:16:41,947 INFO L349 Elim1Store]: treesize reduction 29, result has 3.3 percent of original size [2025-03-03 13:16:41,947 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 2 select indices, 2 select index equivalence classes, 2 disjoint index pairs (out of 1 index pairs), introduced 5 new quantified variables, introduced 1 case distinctions, treesize of input 76 treesize of output 118 [2025-03-03 13:16:41,973 INFO L349 Elim1Store]: treesize reduction 19, result has 5.0 percent of original size [2025-03-03 13:16:41,974 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 1 case distinctions, treesize of input 29 treesize of output 11 [2025-03-03 13:16:41,989 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 0 case distinctions, treesize of input 37 treesize of output 36 [2025-03-03 13:16:42,013 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 45 treesize of output 29 [2025-03-03 13:16:42,091 INFO L349 Elim1Store]: treesize reduction 19, result has 5.0 percent of original size [2025-03-03 13:16:42,091 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 2 new quantified variables, introduced 1 case distinctions, treesize of input 58 treesize of output 42