./Ultimate.py --spec ../../../trunk/examples/svcomp/properties/unreach-call.prp --file ../../../trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version c4f91361 Calling Ultimate with: /root/.sdkman/candidates/java/current/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.5.800.v20200727-1323.jar -data @noDefault -ultimatedata /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../../../trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.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 d82f1b23bea4834b28dfbe602ddf1f3e06a3ee60a847e3002a9403f092f2c830 --- Real Ultimate output --- This is Ultimate 0.2.3-dev-c4f9136-m [2023-11-23 14:26:12,717 INFO L188 SettingsManager]: Resetting all preferences to default values... [2023-11-23 14:26:12,796 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2023-11-23 14:26:12,800 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2023-11-23 14:26:12,801 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2023-11-23 14:26:12,821 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2023-11-23 14:26:12,822 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-11-23 14:26:12,822 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-11-23 14:26:12,823 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2023-11-23 14:26:12,823 INFO L153 SettingsManager]: * Use memory slicer=true [2023-11-23 14:26:12,824 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-11-23 14:26:12,824 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-11-23 14:26:12,825 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2023-11-23 14:26:12,826 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2023-11-23 14:26:12,827 INFO L153 SettingsManager]: * Use SBE=true [2023-11-23 14:26:12,827 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-11-23 14:26:12,828 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-11-23 14:26:12,830 INFO L153 SettingsManager]: * sizeof long=4 [2023-11-23 14:26:12,830 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2023-11-23 14:26:12,830 INFO L153 SettingsManager]: * sizeof POINTER=4 [2023-11-23 14:26:12,830 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2023-11-23 14:26:12,831 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-11-23 14:26:12,831 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-11-23 14:26:12,831 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-11-23 14:26:12,831 INFO L153 SettingsManager]: * sizeof long double=12 [2023-11-23 14:26:12,831 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2023-11-23 14:26:12,832 INFO L153 SettingsManager]: * Use constant arrays=true [2023-11-23 14:26:12,832 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-11-23 14:26:12,832 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2023-11-23 14:26:12,832 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2023-11-23 14:26:12,833 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2023-11-23 14:26:12,833 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 14:26:12,834 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-11-23 14:26:12,834 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-11-23 14:26:12,834 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2023-11-23 14:26:12,834 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2023-11-23 14:26:12,834 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-11-23 14:26:12,834 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2023-11-23 14:26:12,835 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2023-11-23 14:26:12,835 INFO L153 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-11-23 14:26:12,835 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2023-11-23 14:26:12,835 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2023-11-23 14:26:12,835 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC WARNING: An illegal reflective access operation has occurred WARNING: Illegal reflective access by com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 (file:/storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/plugins/com.sun.xml.bind_2.2.0.v201505121915.jar) to method java.lang.ClassLoader.defineClass(java.lang.String,byte[],int,int) WARNING: Please consider reporting this to the maintainers of com.sun.xml.bind.v2.runtime.reflect.opt.Injector$1 WARNING: Use --illegal-access=warn to enable warnings of further illegal reflective access operations WARNING: All illegal access operations will be denied in a future release 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 -> d82f1b23bea4834b28dfbe602ddf1f3e06a3ee60a847e3002a9403f092f2c830 [2023-11-23 14:26:13,021 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-11-23 14:26:13,036 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-11-23 14:26:13,038 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-11-23 14:26:13,038 INFO L270 PluginConnector]: Initializing CDTParser... [2023-11-23 14:26:13,039 INFO L274 PluginConnector]: CDTParser initialized [2023-11-23 14:26:13,040 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i [2023-11-23 14:26:13,965 INFO L533 CDTParser]: Created temporary CDT project at NULL [2023-11-23 14:26:14,162 INFO L384 CDTParser]: Found 1 translation units. [2023-11-23 14:26:14,164 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i [2023-11-23 14:26:14,174 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f31e94600/cacb5e4903c14b7fb2dc32a61807a3b6/FLAG4a270d878 [2023-11-23 14:26:14,182 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f31e94600/cacb5e4903c14b7fb2dc32a61807a3b6 [2023-11-23 14:26:14,184 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-11-23 14:26:14,185 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2023-11-23 14:26:14,187 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-11-23 14:26:14,187 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-11-23 14:26:14,190 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2023-11-23 14:26:14,191 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,191 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5fe4868c and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14, skipping insertion in model container [2023-11-23 14:26:14,193 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,221 INFO L177 MainTranslator]: Built tables and reachable declarations [2023-11-23 14:26:14,500 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[25842,25855] [2023-11-23 14:26:14,505 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[25967,25980] [2023-11-23 14:26:14,506 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[26082,26095] [2023-11-23 14:26:14,515 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 14:26:14,524 INFO L202 MainTranslator]: Completed pre-run [2023-11-23 14:26:14,563 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[25842,25855] [2023-11-23 14:26:14,566 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[25967,25980] [2023-11-23 14:26:14,567 WARN L240 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/ldv-sets/test_mutex_double_unlock.i[26082,26095] [2023-11-23 14:26:14,572 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-11-23 14:26:14,599 INFO L206 MainTranslator]: Completed translation [2023-11-23 14:26:14,600 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14 WrapperNode [2023-11-23 14:26:14,600 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-11-23 14:26:14,601 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2023-11-23 14:26:14,602 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2023-11-23 14:26:14,602 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2023-11-23 14:26:14,607 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,632 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,659 INFO L138 Inliner]: procedures = 139, calls = 57, calls flagged for inlining = 14, calls inlined = 13, statements flattened = 138 [2023-11-23 14:26:14,659 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2023-11-23 14:26:14,660 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-11-23 14:26:14,660 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2023-11-23 14:26:14,660 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2023-11-23 14:26:14,668 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,668 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,670 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,690 INFO L175 MemorySlicer]: Split 22 memory accesses to 2 slices as follows [2, 20]. 91 percent of accesses are in the largest equivalence class. The 4 initializations are split as follows [2, 2]. The 7 writes are split as follows [0, 7]. [2023-11-23 14:26:14,690 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,691 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,696 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,698 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,699 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,700 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,703 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-11-23 14:26:14,703 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-11-23 14:26:14,704 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2023-11-23 14:26:14,704 INFO L274 PluginConnector]: RCFGBuilder initialized [2023-11-23 14:26:14,704 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (1/1) ... [2023-11-23 14:26:14,713 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-11-23 14:26:14,723 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:26:14,746 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-11-23 14:26:14,760 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-11-23 14:26:14,794 INFO L130 BoogieDeclarations]: Found specification of procedure __ldv_list_add [2023-11-23 14:26:14,794 INFO L138 BoogieDeclarations]: Found implementation of procedure __ldv_list_add [2023-11-23 14:26:14,795 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_unlock [2023-11-23 14:26:14,796 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_unlock [2023-11-23 14:26:14,796 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2023-11-23 14:26:14,796 INFO L130 BoogieDeclarations]: Found specification of procedure mutex_lock [2023-11-23 14:26:14,796 INFO L138 BoogieDeclarations]: Found implementation of procedure mutex_lock [2023-11-23 14:26:14,796 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-11-23 14:26:14,796 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#0 [2023-11-23 14:26:14,796 INFO L130 BoogieDeclarations]: Found specification of procedure write~$Pointer$#1 [2023-11-23 14:26:14,797 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_is_in_set [2023-11-23 14:26:14,797 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_is_in_set [2023-11-23 14:26:14,797 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#0 [2023-11-23 14:26:14,797 INFO L130 BoogieDeclarations]: Found specification of procedure read~$Pointer$#1 [2023-11-23 14:26:14,797 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-11-23 14:26:14,797 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#0 [2023-11-23 14:26:14,798 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~$Pointer$#1 [2023-11-23 14:26:14,798 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2023-11-23 14:26:14,798 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2023-11-23 14:26:14,798 INFO L130 BoogieDeclarations]: Found specification of procedure ldv_successful_malloc [2023-11-23 14:26:14,798 INFO L138 BoogieDeclarations]: Found implementation of procedure ldv_successful_malloc [2023-11-23 14:26:14,799 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-11-23 14:26:14,799 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-11-23 14:26:14,929 INFO L241 CfgBuilder]: Building ICFG [2023-11-23 14:26:14,931 INFO L267 CfgBuilder]: Building CFG for each procedure with an implementation [2023-11-23 14:26:15,086 INFO L282 CfgBuilder]: Performing block encoding [2023-11-23 14:26:15,123 INFO L304 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-11-23 14:26:15,123 INFO L309 CfgBuilder]: Removed 2 assume(true) statements. [2023-11-23 14:26:15,124 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 02:26:15 BoogieIcfgContainer [2023-11-23 14:26:15,124 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-11-23 14:26:15,126 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-11-23 14:26:15,126 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2023-11-23 14:26:15,128 INFO L274 PluginConnector]: TraceAbstraction initialized [2023-11-23 14:26:15,128 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.11 02:26:14" (1/3) ... [2023-11-23 14:26:15,129 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46b4ba13 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 02:26:15, skipping insertion in model container [2023-11-23 14:26:15,129 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.11 02:26:14" (2/3) ... [2023-11-23 14:26:15,129 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@46b4ba13 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.11 02:26:15, skipping insertion in model container [2023-11-23 14:26:15,129 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.11 02:26:15" (3/3) ... [2023-11-23 14:26:15,130 INFO L112 eAbstractionObserver]: Analyzing ICFG test_mutex_double_unlock.i [2023-11-23 14:26:15,148 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-11-23 14:26:15,149 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 3 error locations. [2023-11-23 14:26:15,179 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-11-23 14:26:15,184 INFO L357 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, mHoare=true, 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;@6fb04f78, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-11-23 14:26:15,185 INFO L358 AbstractCegarLoop]: Starting to check reachability of 3 error locations. [2023-11-23 14:26:15,187 INFO L276 IsEmpty]: Start isEmpty. Operand has 55 states, 35 states have (on average 1.4) internal successors, (49), 38 states have internal predecessors, (49), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-11-23 14:26:15,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-23 14:26:15,193 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:15,193 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:15,194 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:15,197 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:15,197 INFO L85 PathProgramCache]: Analyzing trace with hash 771595544, now seen corresponding path program 1 times [2023-11-23 14:26:15,203 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:15,204 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1556465271] [2023-11-23 14:26:15,204 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:15,204 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:15,296 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,366 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:15,371 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,381 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:15,386 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,397 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2023-11-23 14:26:15,400 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,408 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-23 14:26:15,409 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:15,409 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1556465271] [2023-11-23 14:26:15,409 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1556465271] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 14:26:15,410 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 14:26:15,410 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2023-11-23 14:26:15,411 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1276917225] [2023-11-23 14:26:15,411 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 14:26:15,414 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2023-11-23 14:26:15,416 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:15,435 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2023-11-23 14:26:15,436 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 14:26:15,438 INFO L87 Difference]: Start difference. First operand has 55 states, 35 states have (on average 1.4) internal successors, (49), 38 states have internal predecessors, (49), 11 states have call successors, (11), 5 states have call predecessors, (11), 5 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) Second operand has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-23 14:26:15,570 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:26:15,570 INFO L93 Difference]: Finished difference Result 115 states and 161 transitions. [2023-11-23 14:26:15,571 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2023-11-23 14:26:15,572 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2023-11-23 14:26:15,572 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:26:15,584 INFO L225 Difference]: With dead ends: 115 [2023-11-23 14:26:15,585 INFO L226 Difference]: Without dead ends: 60 [2023-11-23 14:26:15,587 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2023-11-23 14:26:15,589 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 29 mSDsluCounter, 9 mSDsCounter, 0 mSdLazyCounter, 50 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 32 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 50 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 14:26:15,590 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [32 Valid, 43 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 50 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 14:26:15,601 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states. [2023-11-23 14:26:15,642 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 53. [2023-11-23 14:26:15,644 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 53 states, 34 states have (on average 1.2058823529411764) internal successors, (41), 36 states have internal predecessors, (41), 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) [2023-11-23 14:26:15,648 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 53 states to 53 states and 63 transitions. [2023-11-23 14:26:15,664 INFO L78 Accepts]: Start accepts. Automaton has 53 states and 63 transitions. Word has length 24 [2023-11-23 14:26:15,664 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:26:15,665 INFO L495 AbstractCegarLoop]: Abstraction has 53 states and 63 transitions. [2023-11-23 14:26:15,665 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.666666666666667) internal successors, (14), 2 states have internal predecessors, (14), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-11-23 14:26:15,665 INFO L276 IsEmpty]: Start isEmpty. Operand 53 states and 63 transitions. [2023-11-23 14:26:15,666 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-23 14:26:15,666 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:15,666 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:15,666 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2023-11-23 14:26:15,667 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:15,667 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:15,667 INFO L85 PathProgramCache]: Analyzing trace with hash -85566308, now seen corresponding path program 1 times [2023-11-23 14:26:15,668 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:15,668 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [489207473] [2023-11-23 14:26:15,668 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:15,668 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:15,733 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,826 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:15,829 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,837 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:15,840 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,845 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2023-11-23 14:26:15,847 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:15,873 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-23 14:26:15,873 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:15,873 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [489207473] [2023-11-23 14:26:15,873 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [489207473] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 14:26:15,873 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 14:26:15,873 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-11-23 14:26:15,873 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1199558146] [2023-11-23 14:26:15,874 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 14:26:15,874 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-11-23 14:26:15,874 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:15,875 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-11-23 14:26:15,875 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-11-23 14:26:15,875 INFO L87 Difference]: Start difference. First operand 53 states and 63 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 14:26:16,037 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:26:16,038 INFO L93 Difference]: Finished difference Result 66 states and 82 transitions. [2023-11-23 14:26:16,038 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-11-23 14:26:16,040 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2023-11-23 14:26:16,040 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:26:16,041 INFO L225 Difference]: With dead ends: 66 [2023-11-23 14:26:16,041 INFO L226 Difference]: Without dead ends: 64 [2023-11-23 14:26:16,041 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 12 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-11-23 14:26:16,042 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 32 mSDsluCounter, 63 mSDsCounter, 0 mSdLazyCounter, 120 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 38 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 129 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 120 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 14:26:16,043 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [38 Valid, 94 Invalid, 129 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 120 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 14:26:16,045 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 64 states. [2023-11-23 14:26:16,065 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 64 to 57. [2023-11-23 14:26:16,066 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 37 states have (on average 1.1891891891891893) internal successors, (44), 39 states have internal predecessors, (44), 11 states have call successors, (11), 5 states have call predecessors, (11), 6 states have return successors, (14), 12 states have call predecessors, (14), 11 states have call successors, (14) [2023-11-23 14:26:16,066 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 69 transitions. [2023-11-23 14:26:16,067 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 69 transitions. Word has length 24 [2023-11-23 14:26:16,067 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:26:16,067 INFO L495 AbstractCegarLoop]: Abstraction has 57 states and 69 transitions. [2023-11-23 14:26:16,068 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 1 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 14:26:16,068 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 69 transitions. [2023-11-23 14:26:16,069 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-11-23 14:26:16,069 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:16,069 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:16,069 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2023-11-23 14:26:16,069 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:16,070 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:16,070 INFO L85 PathProgramCache]: Analyzing trace with hash 1489036997, now seen corresponding path program 1 times [2023-11-23 14:26:16,070 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:16,070 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1552828083] [2023-11-23 14:26:16,070 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:16,071 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:16,105 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:16,262 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:16,266 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:16,272 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:16,276 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:16,282 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 15 [2023-11-23 14:26:16,285 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:16,344 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2023-11-23 14:26:16,344 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:16,345 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1552828083] [2023-11-23 14:26:16,345 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1552828083] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 14:26:16,345 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 14:26:16,345 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2023-11-23 14:26:16,346 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1107909211] [2023-11-23 14:26:16,349 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 14:26:16,350 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-11-23 14:26:16,351 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:16,351 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-11-23 14:26:16,352 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2023-11-23 14:26:16,352 INFO L87 Difference]: Start difference. First operand 57 states and 69 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 1 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 14:26:16,845 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:26:16,845 INFO L93 Difference]: Finished difference Result 172 states and 225 transitions. [2023-11-23 14:26:16,846 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2023-11-23 14:26:16,846 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 1 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 24 [2023-11-23 14:26:16,846 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:26:16,852 INFO L225 Difference]: With dead ends: 172 [2023-11-23 14:26:16,852 INFO L226 Difference]: Without dead ends: 121 [2023-11-23 14:26:16,856 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 18 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=54, Invalid=102, Unknown=0, NotChecked=0, Total=156 [2023-11-23 14:26:16,857 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 119 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 261 mSolverCounterSat, 30 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 125 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 291 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 30 IncrementalHoareTripleChecker+Valid, 261 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-11-23 14:26:16,857 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [125 Valid, 103 Invalid, 291 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [30 Valid, 261 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-11-23 14:26:16,858 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 121 states. [2023-11-23 14:26:16,867 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 121 to 102. [2023-11-23 14:26:16,867 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 102 states, 68 states have (on average 1.2352941176470589) internal successors, (84), 74 states have internal predecessors, (84), 18 states have call successors, (18), 9 states have call predecessors, (18), 13 states have return successors, (29), 18 states have call predecessors, (29), 18 states have call successors, (29) [2023-11-23 14:26:16,868 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 102 states to 102 states and 131 transitions. [2023-11-23 14:26:16,869 INFO L78 Accepts]: Start accepts. Automaton has 102 states and 131 transitions. Word has length 24 [2023-11-23 14:26:16,871 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:26:16,871 INFO L495 AbstractCegarLoop]: Abstraction has 102 states and 131 transitions. [2023-11-23 14:26:16,872 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 5 states have internal predecessors, (14), 1 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-11-23 14:26:16,872 INFO L276 IsEmpty]: Start isEmpty. Operand 102 states and 131 transitions. [2023-11-23 14:26:16,873 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 56 [2023-11-23 14:26:16,873 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:16,873 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:16,874 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2023-11-23 14:26:16,874 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:16,874 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:16,874 INFO L85 PathProgramCache]: Analyzing trace with hash -97933331, now seen corresponding path program 1 times [2023-11-23 14:26:16,875 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:16,875 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1062380847] [2023-11-23 14:26:16,875 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:16,875 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:16,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:18,349 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:18,353 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:18,411 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:18,414 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:18,481 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:26:18,500 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,014 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:19,017 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,075 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:26:19,077 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,098 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 14:26:19,102 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,175 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2023-11-23 14:26:19,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,323 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2023-11-23 14:26:19,326 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,476 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 8 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-23 14:26:19,477 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:19,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1062380847] [2023-11-23 14:26:19,477 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1062380847] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:26:19,477 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [368820320] [2023-11-23 14:26:19,477 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:19,478 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:26:19,478 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:26:19,481 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) [2023-11-23 14:26:19,482 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-11-23 14:26:19,610 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:19,634 INFO L262 TraceCheckSpWp]: Trace formula consists of 412 conjuncts, 156 conjunts are in the unsatisfiable core [2023-11-23 14:26:19,643 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 14:26:19,879 INFO L349 Elim1Store]: treesize reduction 18, result has 35.7 percent of original size [2023-11-23 14:26:19,880 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 17 treesize of output 21 [2023-11-23 14:26:20,121 INFO L349 Elim1Store]: treesize reduction 40, result has 32.2 percent of original size [2023-11-23 14:26:20,122 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 24 treesize of output 28 [2023-11-23 14:26:20,926 INFO L349 Elim1Store]: treesize reduction 117, result has 35.4 percent of original size [2023-11-23 14:26:20,928 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 92 treesize of output 184 [2023-11-23 14:26:20,946 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 [2023-11-23 14:26:20,971 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 [2023-11-23 14:26:20,997 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 [2023-11-23 14:26:21,006 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 [2023-11-23 14:26:21,045 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,049 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,059 INFO L349 Elim1Store]: treesize reduction 25, result has 24.2 percent of original size [2023-11-23 14:26:21,059 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 6 case distinctions, treesize of input 114 treesize of output 94 [2023-11-23 14:26:21,087 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:26:21,100 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:26:21,187 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,190 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,193 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 114 treesize of output 86 [2023-11-23 14:26:21,205 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:26:21,242 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,243 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 0 case distinctions, treesize of input 36 treesize of output 12 [2023-11-23 14:26:21,359 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,359 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:21,360 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 26 treesize of output 5 [2023-11-23 14:26:21,362 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:26:22,421 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:22,425 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:22,431 INFO L349 Elim1Store]: treesize reduction 203, result has 0.5 percent of original size [2023-11-23 14:26:22,432 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 2 select indices, 2 select index equivalence classes, 1 disjoint index pairs (out of 1 index pairs), introduced 7 new quantified variables, introduced 2 case distinctions, treesize of input 834 treesize of output 728 [2023-11-23 14:26:22,440 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:22,445 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 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 226 treesize of output 200 [2023-11-23 14:26:22,486 INFO L349 Elim1Store]: treesize reduction 44, result has 38.0 percent of original size [2023-11-23 14:26:22,486 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 53 treesize of output 129 [2023-11-23 14:26:22,528 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:22,535 INFO L349 Elim1Store]: treesize reduction 4, result has 86.7 percent of original size [2023-11-23 14:26:22,535 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 3 select indices, 3 select index equivalence classes, 4 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 38 treesize of output 36 [2023-11-23 14:26:22,541 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 4 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 40 treesize of output 1 [2023-11-23 14:26:25,023 INFO L134 CoverageAnalysis]: Checked inductivity of 29 backedges. 10 proven. 13 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-23 14:26:25,023 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 14:26:26,055 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [368820320] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:26:26,055 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 14:26:26,055 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [31, 30] total 60 [2023-11-23 14:26:26,055 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [964962144] [2023-11-23 14:26:26,056 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 14:26:26,056 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 60 states [2023-11-23 14:26:26,057 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:26,058 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 60 interpolants. [2023-11-23 14:26:26,059 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=239, Invalid=4306, Unknown=11, NotChecked=0, Total=4556 [2023-11-23 14:26:26,059 INFO L87 Difference]: Start difference. First operand 102 states and 131 transitions. Second operand has 60 states, 39 states have (on average 1.7692307692307692) internal successors, (69), 42 states have internal predecessors, (69), 16 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) [2023-11-23 14:26:29,352 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.34s for a HTC check with result INVALID. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2023-11-23 14:26:35,688 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:26:35,688 INFO L93 Difference]: Finished difference Result 222 states and 278 transitions. [2023-11-23 14:26:35,689 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 50 states. [2023-11-23 14:26:35,689 INFO L78 Accepts]: Start accepts. Automaton has has 60 states, 39 states have (on average 1.7692307692307692) internal successors, (69), 42 states have internal predecessors, (69), 16 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) Word has length 55 [2023-11-23 14:26:35,689 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:26:35,690 INFO L225 Difference]: With dead ends: 222 [2023-11-23 14:26:35,690 INFO L226 Difference]: Without dead ends: 160 [2023-11-23 14:26:35,693 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 42 SyntacticMatches, 0 SemanticMatches, 109 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2485 ImplicationChecksByTransitivity, 8.0s TimeCoverageRelationStatistics Valid=888, Invalid=11298, Unknown=24, NotChecked=0, Total=12210 [2023-11-23 14:26:35,694 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 573 mSDsluCounter, 731 mSDsCounter, 0 mSdLazyCounter, 4213 mSolverCounterSat, 181 mSolverCounterUnsat, 65 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 577 SdHoareTripleChecker+Valid, 768 SdHoareTripleChecker+Invalid, 4459 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 181 IncrementalHoareTripleChecker+Valid, 4213 IncrementalHoareTripleChecker+Invalid, 65 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 5.3s IncrementalHoareTripleChecker+Time [2023-11-23 14:26:35,694 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [577 Valid, 768 Invalid, 4459 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [181 Valid, 4213 Invalid, 65 Unknown, 0 Unchecked, 5.3s Time] [2023-11-23 14:26:35,695 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 160 states. [2023-11-23 14:26:35,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 160 to 116. [2023-11-23 14:26:35,708 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 116 states, 80 states have (on average 1.2375) internal successors, (99), 86 states have internal predecessors, (99), 18 states have call successors, (18), 10 states have call predecessors, (18), 15 states have return successors, (29), 19 states have call predecessors, (29), 18 states have call successors, (29) [2023-11-23 14:26:35,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 116 states to 116 states and 146 transitions. [2023-11-23 14:26:35,709 INFO L78 Accepts]: Start accepts. Automaton has 116 states and 146 transitions. Word has length 55 [2023-11-23 14:26:35,709 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:26:35,709 INFO L495 AbstractCegarLoop]: Abstraction has 116 states and 146 transitions. [2023-11-23 14:26:35,710 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 60 states, 39 states have (on average 1.7692307692307692) internal successors, (69), 42 states have internal predecessors, (69), 16 states have call successors, (18), 12 states have call predecessors, (18), 15 states have return successors, (16), 15 states have call predecessors, (16), 14 states have call successors, (16) [2023-11-23 14:26:35,710 INFO L276 IsEmpty]: Start isEmpty. Operand 116 states and 146 transitions. [2023-11-23 14:26:35,711 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 67 [2023-11-23 14:26:35,711 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:35,711 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 5, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:35,726 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-11-23 14:26:35,923 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:26:35,924 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:35,924 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:35,924 INFO L85 PathProgramCache]: Analyzing trace with hash -946371460, now seen corresponding path program 1 times [2023-11-23 14:26:35,924 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:35,924 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [663757392] [2023-11-23 14:26:35,924 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:35,925 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:35,936 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:35,956 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:35,958 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:35,959 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:35,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:35,968 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:26:35,972 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:35,994 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:35,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,002 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:26:36,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,014 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 34 [2023-11-23 14:26:36,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,022 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:36,023 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,024 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:26:36,025 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,026 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 57 [2023-11-23 14:26:36,027 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,029 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 2 proven. 10 refuted. 0 times theorem prover too weak. 52 trivial. 0 not checked. [2023-11-23 14:26:36,029 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:36,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [663757392] [2023-11-23 14:26:36,029 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [663757392] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:26:36,029 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1247244304] [2023-11-23 14:26:36,029 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:36,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:26:36,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:26:36,030 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) [2023-11-23 14:26:36,034 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-11-23 14:26:36,153 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:36,154 INFO L262 TraceCheckSpWp]: Trace formula consists of 369 conjuncts, 5 conjunts are in the unsatisfiable core [2023-11-23 14:26:36,158 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 14:26:36,171 INFO L134 CoverageAnalysis]: Checked inductivity of 64 backedges. 40 proven. 0 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-23 14:26:36,171 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-11-23 14:26:36,171 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1247244304] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 14:26:36,171 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-11-23 14:26:36,171 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [6] total 6 [2023-11-23 14:26:36,171 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1175887708] [2023-11-23 14:26:36,171 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 14:26:36,172 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-11-23 14:26:36,172 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:36,172 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-11-23 14:26:36,172 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-23 14:26:36,173 INFO L87 Difference]: Start difference. First operand 116 states and 146 transitions. Second operand has 4 states, 4 states have (on average 8.25) internal successors, (33), 4 states have internal predecessors, (33), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2023-11-23 14:26:36,217 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:26:36,217 INFO L93 Difference]: Finished difference Result 204 states and 259 transitions. [2023-11-23 14:26:36,217 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-11-23 14:26:36,217 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 8.25) internal successors, (33), 4 states have internal predecessors, (33), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) Word has length 66 [2023-11-23 14:26:36,219 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:26:36,222 INFO L225 Difference]: With dead ends: 204 [2023-11-23 14:26:36,222 INFO L226 Difference]: Without dead ends: 124 [2023-11-23 14:26:36,222 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 84 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=20, Unknown=0, NotChecked=0, Total=30 [2023-11-23 14:26:36,223 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 0 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 36 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 152 SdHoareTripleChecker+Invalid, 36 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 36 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-11-23 14:26:36,223 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 152 Invalid, 36 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 36 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-11-23 14:26:36,225 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 124 states. [2023-11-23 14:26:36,247 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 124 to 118. [2023-11-23 14:26:36,250 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 81 states have (on average 1.2222222222222223) internal successors, (99), 87 states have internal predecessors, (99), 18 states have call successors, (18), 10 states have call predecessors, (18), 16 states have return successors, (30), 20 states have call predecessors, (30), 18 states have call successors, (30) [2023-11-23 14:26:36,253 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 147 transitions. [2023-11-23 14:26:36,253 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 147 transitions. Word has length 66 [2023-11-23 14:26:36,253 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:26:36,253 INFO L495 AbstractCegarLoop]: Abstraction has 118 states and 147 transitions. [2023-11-23 14:26:36,254 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 8.25) internal successors, (33), 4 states have internal predecessors, (33), 2 states have call successors, (10), 2 states have call predecessors, (10), 3 states have return successors, (9), 3 states have call predecessors, (9), 2 states have call successors, (9) [2023-11-23 14:26:36,254 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 147 transitions. [2023-11-23 14:26:36,257 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2023-11-23 14:26:36,257 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:26:36,257 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:26:36,274 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-11-23 14:26:36,464 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:26:36,464 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:26:36,464 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:26:36,465 INFO L85 PathProgramCache]: Analyzing trace with hash 49680093, now seen corresponding path program 1 times [2023-11-23 14:26:36,465 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:26:36,465 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1927612450] [2023-11-23 14:26:36,465 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:36,465 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:26:36,491 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:37,356 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:37,359 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:37,394 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:26:37,396 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:37,451 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:26:37,462 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,231 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:26:38,233 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,292 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:26:38,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,300 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 14:26:38,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,380 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2023-11-23 14:26:38,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,566 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 46 [2023-11-23 14:26:38,568 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,665 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 20 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-11-23 14:26:38,666 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:26:38,666 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1927612450] [2023-11-23 14:26:38,666 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1927612450] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:26:38,667 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1798977645] [2023-11-23 14:26:38,667 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:26:38,667 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:26:38,667 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:26:38,668 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) [2023-11-23 14:26:38,669 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-11-23 14:26:38,790 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:26:38,792 INFO L262 TraceCheckSpWp]: Trace formula consists of 422 conjuncts, 133 conjunts are in the unsatisfiable core [2023-11-23 14:26:38,797 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 14:26:38,966 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2023-11-23 14:26:38,967 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 19 treesize of output 16 [2023-11-23 14:26:39,072 INFO L349 Elim1Store]: treesize reduction 20, result has 33.3 percent of original size [2023-11-23 14:26:39,073 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 2 case distinctions, treesize of input 19 treesize of output 16 [2023-11-23 14:26:39,553 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2023-11-23 14:26:39,553 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 2 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 72 treesize of output 71 [2023-11-23 14:26:39,560 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 120 treesize of output 102 [2023-11-23 14:26:39,618 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2023-11-23 14:26:39,619 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 1 case distinctions, treesize of input 67 treesize of output 71 [2023-11-23 14:26:39,626 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 120 treesize of output 102 [2023-11-23 14:26:39,688 INFO L349 Elim1Store]: treesize reduction 29, result has 39.6 percent of original size [2023-11-23 14:26:39,689 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 3 new quantified variables, introduced 2 case distinctions, treesize of input 67 treesize of output 71 [2023-11-23 14:26:39,696 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 120 treesize of output 102 [2023-11-23 14:26:39,924 INFO L349 Elim1Store]: treesize reduction 182, result has 37.9 percent of original size [2023-11-23 14:26:39,924 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 4 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 6 new quantified variables, introduced 11 case distinctions, treesize of input 212 treesize of output 305 [2023-11-23 14:26:40,022 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:40,022 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 [2023-11-23 14:26:40,036 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 [2023-11-23 14:26:40,080 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,124 INFO L349 Elim1Store]: treesize reduction 54, result has 12.9 percent of original size [2023-11-23 14:26:40,125 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 7 case distinctions, treesize of input 198 treesize of output 200 [2023-11-23 14:26:40,195 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,208 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,215 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,217 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,218 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 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 161 treesize of output 157 [2023-11-23 14:26:40,268 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,272 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,286 INFO L349 Elim1Store]: treesize reduction 42, result has 16.0 percent of original size [2023-11-23 14:26:40,287 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 5 case distinctions, treesize of input 123 treesize of output 109 [2023-11-23 14:26:40,354 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,361 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,362 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 113 treesize of output 91 [2023-11-23 14:26:40,393 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 468 treesize of output 380 [2023-11-23 14:26:40,429 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,429 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:26:40,431 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 28 [2023-11-23 14:26:40,437 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:26:40,450 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:40,483 INFO L349 Elim1Store]: treesize reduction 35, result has 32.7 percent of original size [2023-11-23 14:26:40,484 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 1 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 4 case distinctions, treesize of input 1177 treesize of output 1029 [2023-11-23 14:26:40,744 INFO L349 Elim1Store]: treesize reduction 92, result has 32.8 percent of original size [2023-11-23 14:26:40,744 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 3 case distinctions, treesize of input 24 treesize of output 55 [2023-11-23 14:26:41,916 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 95 treesize of output 83 [2023-11-23 14:26:41,937 INFO L349 Elim1Store]: treesize reduction 118, result has 9.9 percent of original size [2023-11-23 14:26:41,938 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 38 [2023-11-23 14:26:41,961 INFO L349 Elim1Store]: treesize reduction 209, result has 0.5 percent of original size [2023-11-23 14:26:41,962 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 37 treesize of output 1 [2023-11-23 14:26:42,003 INFO L349 Elim1Store]: treesize reduction 65, result has 1.5 percent of original size [2023-11-23 14:26:42,004 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 1 case distinctions, treesize of input 23 treesize of output 1 [2023-11-23 14:26:42,017 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 162 treesize of output 148 [2023-11-23 14:26:42,107 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 45 treesize of output 39 [2023-11-23 14:26:42,232 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 84 treesize of output 72 [2023-11-23 14:26:42,334 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 269 treesize of output 245 [2023-11-23 14:26:42,429 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 41 treesize of output 31 [2023-11-23 14:26:42,556 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 41 treesize of output 31 [2023-11-23 14:26:42,639 INFO L349 Elim1Store]: treesize reduction 44, result has 33.3 percent of original size [2023-11-23 14:26:42,640 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 1 case distinctions, treesize of input 23 treesize of output 42 [2023-11-23 14:26:42,644 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 41 treesize of output 31 [2023-11-23 14:26:42,672 INFO L349 Elim1Store]: treesize reduction 197, result has 6.2 percent of original size [2023-11-23 14:26:42,673 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 37 treesize of output 66 [2023-11-23 14:26:42,710 INFO L349 Elim1Store]: treesize reduction 209, result has 0.5 percent of original size [2023-11-23 14:26:42,711 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 2 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 37 treesize of output 1 [2023-11-23 14:26:42,766 INFO L349 Elim1Store]: treesize reduction 130, result has 0.8 percent of original size [2023-11-23 14:26:42,766 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 1 case distinctions, treesize of input 26 treesize of output 1 [2023-11-23 14:26:42,784 INFO L349 Elim1Store]: treesize reduction 65, result has 1.5 percent of original size [2023-11-23 14:26:42,784 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 1 case distinctions, treesize of input 23 treesize of output 1 [2023-11-23 14:26:44,895 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 1983 treesize of output 1855 [2023-11-23 14:26:44,927 INFO L349 Elim1Store]: treesize reduction 4, result has 66.7 percent of original size [2023-11-23 14:26:44,927 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 15 treesize of output 15 [2023-11-23 14:26:44,931 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:26:44,932 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 69 treesize of output 53 [2023-11-23 14:26:46,683 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 12 proven. 15 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-11-23 14:26:46,683 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 14:26:47,691 INFO L349 Elim1Store]: treesize reduction 29, result has 67.0 percent of original size [2023-11-23 14:26:47,691 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 3 new quantified variables, introduced 4 case distinctions, treesize of input 693 treesize of output 624 [2023-11-23 14:26:47,733 INFO L349 Elim1Store]: treesize reduction 143, result has 33.5 percent of original size [2023-11-23 14:26:47,733 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 235 treesize of output 227 [2023-11-23 14:26:47,753 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:26:47,753 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 199 treesize of output 222 [2023-11-23 14:26:47,774 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:26:47,775 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 223 treesize of output 246 [2023-11-23 14:26:47,807 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:26:47,807 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 16 treesize of output 15 [2023-11-23 14:26:47,819 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 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 20 treesize of output 16 [2023-11-23 14:26:47,881 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:26:47,881 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 59 treesize of output 74 [2023-11-23 14:26:47,911 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 15 treesize of output 4 [2023-11-23 14:26:47,917 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 172 treesize of output 161 [2023-11-23 14:26:47,947 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:26:47,948 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 164 treesize of output 173 [2023-11-23 14:26:48,380 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1798977645] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:26:48,380 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-11-23 14:26:48,380 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [27, 20] total 46 [2023-11-23 14:26:48,380 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1617876768] [2023-11-23 14:26:48,381 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-11-23 14:26:48,381 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 46 states [2023-11-23 14:26:48,381 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:26:48,381 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 46 interpolants. [2023-11-23 14:26:48,382 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=199, Invalid=2448, Unknown=5, NotChecked=0, Total=2652 [2023-11-23 14:26:48,382 INFO L87 Difference]: Start difference. First operand 118 states and 147 transitions. Second operand has 46 states, 35 states have (on average 2.057142857142857) internal successors, (72), 38 states have internal predecessors, (72), 12 states have call successors, (18), 10 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 12 states have call successors, (16) [2023-11-23 14:27:04,699 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:27:04,699 INFO L93 Difference]: Finished difference Result 295 states and 373 transitions. [2023-11-23 14:27:04,699 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 55 states. [2023-11-23 14:27:04,699 INFO L78 Accepts]: Start accepts. Automaton has has 46 states, 35 states have (on average 2.057142857142857) internal successors, (72), 38 states have internal predecessors, (72), 12 states have call successors, (18), 10 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 12 states have call successors, (16) Word has length 57 [2023-11-23 14:27:04,699 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:27:04,700 INFO L225 Difference]: With dead ends: 295 [2023-11-23 14:27:04,700 INFO L226 Difference]: Without dead ends: 163 [2023-11-23 14:27:04,702 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 169 GetRequests, 68 SyntacticMatches, 0 SemanticMatches, 101 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2518 ImplicationChecksByTransitivity, 15.0s TimeCoverageRelationStatistics Valid=1117, Invalid=9359, Unknown=30, NotChecked=0, Total=10506 [2023-11-23 14:27:04,703 INFO L413 NwaCegarLoop]: 21 mSDtfsCounter, 709 mSDsluCounter, 287 mSDsCounter, 0 mSdLazyCounter, 2333 mSolverCounterSat, 214 mSolverCounterUnsat, 2 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 6.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 710 SdHoareTripleChecker+Valid, 308 SdHoareTripleChecker+Invalid, 2549 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 214 IncrementalHoareTripleChecker+Valid, 2333 IncrementalHoareTripleChecker+Invalid, 2 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 6.3s IncrementalHoareTripleChecker+Time [2023-11-23 14:27:04,703 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [710 Valid, 308 Invalid, 2549 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [214 Valid, 2333 Invalid, 2 Unknown, 0 Unchecked, 6.3s Time] [2023-11-23 14:27:04,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 163 states. [2023-11-23 14:27:04,714 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 163 to 126. [2023-11-23 14:27:04,715 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 126 states, 89 states have (on average 1.1910112359550562) internal successors, (106), 94 states have internal predecessors, (106), 18 states have call successors, (18), 11 states have call predecessors, (18), 17 states have return successors, (32), 20 states have call predecessors, (32), 18 states have call successors, (32) [2023-11-23 14:27:04,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 126 states to 126 states and 156 transitions. [2023-11-23 14:27:04,718 INFO L78 Accepts]: Start accepts. Automaton has 126 states and 156 transitions. Word has length 57 [2023-11-23 14:27:04,718 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:27:04,718 INFO L495 AbstractCegarLoop]: Abstraction has 126 states and 156 transitions. [2023-11-23 14:27:04,719 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 46 states, 35 states have (on average 2.057142857142857) internal successors, (72), 38 states have internal predecessors, (72), 12 states have call successors, (18), 10 states have call predecessors, (18), 15 states have return successors, (16), 14 states have call predecessors, (16), 12 states have call successors, (16) [2023-11-23 14:27:04,719 INFO L276 IsEmpty]: Start isEmpty. Operand 126 states and 156 transitions. [2023-11-23 14:27:04,721 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-11-23 14:27:04,721 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:27:04,721 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:27:04,738 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2023-11-23 14:27:04,930 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:27:04,930 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:27:04,931 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:27:04,931 INFO L85 PathProgramCache]: Analyzing trace with hash 922279796, now seen corresponding path program 1 times [2023-11-23 14:27:04,931 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:27:04,931 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1296409330] [2023-11-23 14:27:04,931 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:27:04,931 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:27:04,945 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,138 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:05,166 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,169 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:27:05,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,179 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:27:05,187 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,283 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:05,284 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,285 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:27:05,287 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,289 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 14:27:05,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,320 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2023-11-23 14:27:05,325 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,366 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2023-11-23 14:27:05,369 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,389 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:05,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,392 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-11-23 14:27:05,395 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,397 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2023-11-23 14:27:05,399 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,433 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 26 proven. 5 refuted. 0 times theorem prover too weak. 43 trivial. 0 not checked. [2023-11-23 14:27:05,433 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:27:05,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1296409330] [2023-11-23 14:27:05,434 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1296409330] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:27:05,434 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1699217854] [2023-11-23 14:27:05,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:27:05,434 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:27:05,434 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:27:05,436 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) [2023-11-23 14:27:05,437 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-11-23 14:27:05,597 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:05,600 INFO L262 TraceCheckSpWp]: Trace formula consists of 526 conjuncts, 52 conjunts are in the unsatisfiable core [2023-11-23 14:27:05,608 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 14:27:05,907 INFO L349 Elim1Store]: treesize reduction 141, result has 31.2 percent of original size [2023-11-23 14:27:05,907 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 108 treesize of output 196 [2023-11-23 14:27:05,914 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-11-23 14:27:05,922 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:05,922 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 1 [2023-11-23 14:27:05,940 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-11-23 14:27:05,952 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 12 treesize of output 11 [2023-11-23 14:27:06,238 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 9 treesize of output 7 [2023-11-23 14:27:06,243 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 20 treesize of output 9 [2023-11-23 14:27:06,245 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 9 treesize of output 7 [2023-11-23 14:27:06,310 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 [2023-11-23 14:27:06,462 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 31 proven. 5 refuted. 0 times theorem prover too weak. 38 trivial. 0 not checked. [2023-11-23 14:27:06,462 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 14:27:06,895 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:27:06,896 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 2 select indices, 2 select index equivalence classes, 0 disjoint index pairs (out of 1 index pairs), introduced 2 new quantified variables, introduced 1 case distinctions, treesize of input 10966 treesize of output 10558 [2023-11-23 14:27:06,922 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 630 treesize of output 614 [2023-11-23 14:27:06,932 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 710 treesize of output 678 [2023-11-23 14:27:07,126 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 460 treesize of output 452 [2023-11-23 14:27:07,315 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:27:07,317 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 64 treesize of output 62 [2023-11-23 14:27:07,320 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:27:07,322 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:27:07,325 INFO L190 IndexEqualityManager]: detected not equals via solver [2023-11-23 14:27:07,481 INFO L134 CoverageAnalysis]: Checked inductivity of 74 backedges. 27 proven. 5 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-11-23 14:27:07,481 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1699217854] provided 0 perfect and 2 imperfect interpolant sequences [2023-11-23 14:27:07,481 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2023-11-23 14:27:07,481 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 12, 14] total 40 [2023-11-23 14:27:07,481 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1180288052] [2023-11-23 14:27:07,481 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2023-11-23 14:27:07,482 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 40 states [2023-11-23 14:27:07,482 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:27:07,483 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 40 interpolants. [2023-11-23 14:27:07,483 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=177, Invalid=1383, Unknown=0, NotChecked=0, Total=1560 [2023-11-23 14:27:07,483 INFO L87 Difference]: Start difference. First operand 126 states and 156 transitions. Second operand has 40 states, 31 states have (on average 3.4193548387096775) internal successors, (106), 34 states have internal predecessors, (106), 16 states have call successors, (35), 10 states have call predecessors, (35), 17 states have return successors, (32), 19 states have call predecessors, (32), 16 states have call successors, (32) [2023-11-23 14:27:08,601 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:27:08,602 INFO L93 Difference]: Finished difference Result 239 states and 299 transitions. [2023-11-23 14:27:08,602 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2023-11-23 14:27:08,602 INFO L78 Accepts]: Start accepts. Automaton has has 40 states, 31 states have (on average 3.4193548387096775) internal successors, (106), 34 states have internal predecessors, (106), 16 states have call successors, (35), 10 states have call predecessors, (35), 17 states have return successors, (32), 19 states have call predecessors, (32), 16 states have call successors, (32) Word has length 78 [2023-11-23 14:27:08,603 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:27:08,603 INFO L225 Difference]: With dead ends: 239 [2023-11-23 14:27:08,603 INFO L226 Difference]: Without dead ends: 155 [2023-11-23 14:27:08,605 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 210 GetRequests, 152 SyntacticMatches, 0 SemanticMatches, 58 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 767 ImplicationChecksByTransitivity, 0.9s TimeCoverageRelationStatistics Valid=523, Invalid=3017, Unknown=0, NotChecked=0, Total=3540 [2023-11-23 14:27:08,605 INFO L413 NwaCegarLoop]: 31 mSDtfsCounter, 325 mSDsluCounter, 266 mSDsCounter, 0 mSdLazyCounter, 1227 mSolverCounterSat, 110 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 327 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 1337 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 110 IncrementalHoareTripleChecker+Valid, 1227 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.7s IncrementalHoareTripleChecker+Time [2023-11-23 14:27:08,605 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [327 Valid, 297 Invalid, 1337 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [110 Valid, 1227 Invalid, 0 Unknown, 0 Unchecked, 0.7s Time] [2023-11-23 14:27:08,606 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 155 states. [2023-11-23 14:27:08,617 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 155 to 129. [2023-11-23 14:27:08,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 91 states have (on average 1.1868131868131868) internal successors, (108), 94 states have internal predecessors, (108), 20 states have call successors, (20), 13 states have call predecessors, (20), 16 states have return successors, (28), 21 states have call predecessors, (28), 20 states have call successors, (28) [2023-11-23 14:27:08,618 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 156 transitions. [2023-11-23 14:27:08,618 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 156 transitions. Word has length 78 [2023-11-23 14:27:08,619 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:27:08,619 INFO L495 AbstractCegarLoop]: Abstraction has 129 states and 156 transitions. [2023-11-23 14:27:08,619 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 40 states, 31 states have (on average 3.4193548387096775) internal successors, (106), 34 states have internal predecessors, (106), 16 states have call successors, (35), 10 states have call predecessors, (35), 17 states have return successors, (32), 19 states have call predecessors, (32), 16 states have call successors, (32) [2023-11-23 14:27:08,619 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 156 transitions. [2023-11-23 14:27:08,620 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 79 [2023-11-23 14:27:08,620 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:27:08,620 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:27:08,633 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2023-11-23 14:27:08,824 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:27:08,824 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:27:08,824 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:27:08,825 INFO L85 PathProgramCache]: Analyzing trace with hash -1798084195, now seen corresponding path program 2 times [2023-11-23 14:27:08,825 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:27:08,825 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [364960347] [2023-11-23 14:27:08,825 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:27:08,825 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:27:08,838 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,871 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:08,872 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,873 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:27:08,874 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,882 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:27:08,886 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,891 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:08,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,892 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:27:08,892 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,893 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 14:27:08,895 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,900 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2023-11-23 14:27:08,903 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2023-11-23 14:27:08,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,909 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:08,909 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,911 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-11-23 14:27:08,911 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,912 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2023-11-23 14:27:08,913 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:08,943 INFO L134 CoverageAnalysis]: Checked inductivity of 73 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 65 trivial. 0 not checked. [2023-11-23 14:27:08,943 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:27:08,943 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [364960347] [2023-11-23 14:27:08,944 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [364960347] provided 1 perfect and 0 imperfect interpolant sequences [2023-11-23 14:27:08,944 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-11-23 14:27:08,944 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [7] imperfect sequences [] total 7 [2023-11-23 14:27:08,944 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1254393718] [2023-11-23 14:27:08,945 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-11-23 14:27:08,945 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-11-23 14:27:08,946 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2023-11-23 14:27:08,946 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-11-23 14:27:08,946 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2023-11-23 14:27:08,946 INFO L87 Difference]: Start difference. First operand 129 states and 156 transitions. Second operand has 7 states, 7 states have (on average 4.285714285714286) internal successors, (30), 4 states have internal predecessors, (30), 1 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) [2023-11-23 14:27:09,077 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-11-23 14:27:09,078 INFO L93 Difference]: Finished difference Result 141 states and 170 transitions. [2023-11-23 14:27:09,078 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2023-11-23 14:27:09,078 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 4.285714285714286) internal successors, (30), 4 states have internal predecessors, (30), 1 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) Word has length 78 [2023-11-23 14:27:09,078 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-11-23 14:27:09,079 INFO L225 Difference]: With dead ends: 141 [2023-11-23 14:27:09,079 INFO L226 Difference]: Without dead ends: 139 [2023-11-23 14:27:09,079 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 28 GetRequests, 21 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2023-11-23 14:27:09,080 INFO L413 NwaCegarLoop]: 28 mSDtfsCounter, 60 mSDsluCounter, 58 mSDsCounter, 0 mSdLazyCounter, 157 mSolverCounterSat, 22 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 64 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 179 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 22 IncrementalHoareTripleChecker+Valid, 157 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-11-23 14:27:09,080 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [64 Valid, 86 Invalid, 179 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [22 Valid, 157 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-11-23 14:27:09,081 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 139 states. [2023-11-23 14:27:09,096 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 139 to 139. [2023-11-23 14:27:09,097 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 139 states, 99 states have (on average 1.1717171717171717) internal successors, (116), 101 states have internal predecessors, (116), 20 states have call successors, (20), 13 states have call predecessors, (20), 18 states have return successors, (30), 24 states have call predecessors, (30), 20 states have call successors, (30) [2023-11-23 14:27:09,097 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 139 states to 139 states and 166 transitions. [2023-11-23 14:27:09,098 INFO L78 Accepts]: Start accepts. Automaton has 139 states and 166 transitions. Word has length 78 [2023-11-23 14:27:09,098 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-11-23 14:27:09,098 INFO L495 AbstractCegarLoop]: Abstraction has 139 states and 166 transitions. [2023-11-23 14:27:09,098 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 4.285714285714286) internal successors, (30), 4 states have internal predecessors, (30), 1 states have call successors, (10), 4 states have call predecessors, (10), 2 states have return successors, (9), 2 states have call predecessors, (9), 1 states have call successors, (9) [2023-11-23 14:27:09,098 INFO L276 IsEmpty]: Start isEmpty. Operand 139 states and 166 transitions. [2023-11-23 14:27:09,099 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 81 [2023-11-23 14:27:09,099 INFO L187 NwaCegarLoop]: Found error trace [2023-11-23 14:27:09,099 INFO L195 NwaCegarLoop]: trace histogram [5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-11-23 14:27:09,099 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7 [2023-11-23 14:27:09,099 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION === [mutex_unlockErr0ASSERT_VIOLATIONERROR_FUNCTION, mutex_lockErr0ASSERT_VIOLATIONERROR_FUNCTION, ULTIMATE.startErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-11-23 14:27:09,099 INFO L160 PredicateUnifier]: Initialized classic predicate unifier [2023-11-23 14:27:09,100 INFO L85 PathProgramCache]: Analyzing trace with hash 1104153060, now seen corresponding path program 3 times [2023-11-23 14:27:09,100 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2023-11-23 14:27:09,100 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1916781211] [2023-11-23 14:27:09,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-11-23 14:27:09,100 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-11-23 14:27:09,127 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,477 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:09,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,497 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 7 [2023-11-23 14:27:09,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,506 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2023-11-23 14:27:09,523 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,618 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:09,619 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,620 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 10 [2023-11-23 14:27:09,621 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,622 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 18 [2023-11-23 14:27:09,624 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,653 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 24 [2023-11-23 14:27:09,657 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,682 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 44 [2023-11-23 14:27:09,686 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,764 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 1 [2023-11-23 14:27:09,766 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,905 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2023-11-23 14:27:09,906 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,976 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 69 [2023-11-23 14:27:09,977 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-11-23 14:27:09,979 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 29 proven. 19 refuted. 0 times theorem prover too weak. 34 trivial. 0 not checked. [2023-11-23 14:27:09,979 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2023-11-23 14:27:09,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1916781211] [2023-11-23 14:27:09,979 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1916781211] provided 0 perfect and 1 imperfect interpolant sequences [2023-11-23 14:27:09,979 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1447967455] [2023-11-23 14:27:09,979 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-11-23 14:27:09,979 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-11-23 14:27:09,980 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-11-23 14:27:09,980 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) [2023-11-23 14:27:09,982 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-11-23 14:27:10,165 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-11-23 14:27:10,165 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-11-23 14:27:10,169 INFO L262 TraceCheckSpWp]: Trace formula consists of 526 conjuncts, 209 conjunts are in the unsatisfiable core [2023-11-23 14:27:10,174 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-11-23 14:27:10,598 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2023-11-23 14:27:10,674 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,694 INFO L349 Elim1Store]: treesize reduction 14, result has 39.1 percent of original size [2023-11-23 14:27:10,694 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 1 case distinctions, treesize of input 15 treesize of output 18 [2023-11-23 14:27:10,699 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 [2023-11-23 14:27:10,782 INFO L349 Elim1Store]: treesize reduction 177, result has 36.1 percent of original size [2023-11-23 14:27:10,782 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 3 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 4 new quantified variables, introduced 6 case distinctions, treesize of input 258 treesize of output 328 [2023-11-23 14:27:10,790 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 [2023-11-23 14:27:10,800 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 [2023-11-23 14:27:10,807 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 [2023-11-23 14:27:10,837 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 [2023-11-23 14:27:10,875 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,881 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,892 INFO L349 Elim1Store]: treesize reduction 41, result has 22.6 percent of original size [2023-11-23 14:27:10,893 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 2 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 2 new quantified variables, introduced 6 case distinctions, treesize of input 169 treesize of output 133 [2023-11-23 14:27:10,912 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:27:10,940 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,943 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,944 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:10,945 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 2 new quantified variables, introduced 0 case distinctions, treesize of input 120 treesize of output 72 [2023-11-23 14:27:10,949 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:27:11,004 INFO L349 Elim1Store]: treesize reduction 21, result has 36.4 percent of original size [2023-11-23 14:27:11,005 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 2 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 112 treesize of output 82 [2023-11-23 14:27:11,014 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 5 treesize of output 3 [2023-11-23 14:27:11,056 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:11,063 INFO L349 Elim1Store]: treesize reduction 21, result has 36.4 percent of original size [2023-11-23 14:27:11,063 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 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 73 treesize of output 49 [2023-11-23 14:27:11,266 INFO L349 Elim1Store]: treesize reduction 282, result has 22.5 percent of original size [2023-11-23 14:27:11,267 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 1 select indices, 1 select index equivalence classes, 3 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 2 case distinctions, treesize of input 201 treesize of output 96 [2023-11-23 14:27:13,558 INFO L134 CoverageAnalysis]: Checked inductivity of 82 backedges. 37 proven. 21 refuted. 0 times theorem prover too weak. 24 trivial. 0 not checked. [2023-11-23 14:27:13,559 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-11-23 14:27:15,432 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 659 treesize of output 651 [2023-11-23 14:27:15,477 INFO L349 Elim1Store]: treesize reduction 13, result has 69.0 percent of original size [2023-11-23 14:27:15,477 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 4 new quantified variables, introduced 4 case distinctions, treesize of input 1682 treesize of output 1458 [2023-11-23 14:27:15,493 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 286 treesize of output 270 [2023-11-23 14:27:15,541 INFO L349 Elim1Store]: treesize reduction 38, result has 56.8 percent of original size [2023-11-23 14:27:15,541 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 7 case distinctions, treesize of input 450 treesize of output 421 [2023-11-23 14:27:15,580 INFO L349 Elim1Store]: treesize reduction 8, result has 68.0 percent of original size [2023-11-23 14:27:15,581 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 4 new quantified variables, introduced 3 case distinctions, treesize of input 694 treesize of output 596 [2023-11-23 14:27:15,627 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 1 [2023-11-23 14:27:15,707 WARN L214 Elim1Store]: Array PQE input equivalent to true [2023-11-23 14:27:15,863 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 34 treesize of output 22 [2023-11-23 14:27:15,887 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 54 treesize of output 38 [2023-11-23 14:27:15,899 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 [2023-11-23 14:27:15,912 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:15,915 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:15,926 INFO L173 IndexEqualityManager]: detected equality via solver [2023-11-23 14:27:15,930 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 8 treesize of output 4 [2023-11-23 14:27:16,279 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:27:16,280 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 3 select indices, 3 select index equivalence classes, 0 disjoint index pairs (out of 3 index pairs), introduced 3 new quantified variables, introduced 3 case distinctions, treesize of input 2993108 treesize of output 2828936 [2023-11-23 14:27:16,990 INFO L349 Elim1Store]: treesize reduction 73, result has 73.3 percent of original size [2023-11-23 14:27:16,990 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 7 select indices, 7 select index equivalence classes, 0 disjoint index pairs (out of 21 index pairs), introduced 8 new quantified variables, introduced 21 case distinctions, treesize of input 66816 treesize of output 66305 [2023-11-23 14:27:17,561 INFO L349 Elim1Store]: treesize reduction 0, result has 100.0 percent of original size [2023-11-23 14:27:17,561 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 1, 0 stores, 6 select indices, 6 select index equivalence classes, 0 disjoint index pairs (out of 15 index pairs), introduced 7 new quantified variables, introduced 15 case distinctions, treesize of input 73768 treesize of output 72615 Killed by 15