./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/termination-recursive-malloc/rec_malloc_ex3.i --full-output --architecture 64bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 3289d67d Calling Ultimate with: /root/.sdkman/candidates/java/11.0.12-open/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/AutomizerTermination.xml -i ../sv-benchmarks/c/termination-recursive-malloc/rec_malloc_ex3.i -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-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(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 64bit --witnessprinter.graph.data.programhash 33d006375056e7e3c58d58b776bed0fedce081ec4ff9e691f038a741177fe7dd --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.fs.icfgbuilder-eval-3289d67-m [2024-11-17 08:11:01,593 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-17 08:11:01,653 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-17 08:11:01,656 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-17 08:11:01,657 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-17 08:11:01,657 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder.Remove goto edges from RCFG [2024-11-17 08:11:01,679 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-17 08:11:01,679 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-17 08:11:01,679 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-17 08:11:01,680 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-17 08:11:01,680 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-17 08:11:01,680 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-17 08:11:01,681 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-17 08:11:01,681 INFO L153 SettingsManager]: * Use SBE=true [2024-11-17 08:11:01,681 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-17 08:11:01,681 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-17 08:11:01,682 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-17 08:11:01,682 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-17 08:11:01,682 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-17 08:11:01,682 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-17 08:11:01,683 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-17 08:11:01,686 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-17 08:11:01,687 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-17 08:11:01,687 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-17 08:11:01,687 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-17 08:11:01,688 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-17 08:11:01,688 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-17 08:11:01,688 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2024-11-17 08:11:01,688 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-17 08:11:01,688 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-17 08:11:01,689 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-17 08:11:01,689 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-17 08:11:01,692 INFO L153 SettingsManager]: * TransformationType=MODULO_NEIGHBOR 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(F end) ) 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 -> 64bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> 33d006375056e7e3c58d58b776bed0fedce081ec4ff9e691f038a741177fe7dd [2024-11-17 08:11:01,875 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-17 08:11:01,897 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-17 08:11:01,899 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-17 08:11:01,900 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-17 08:11:01,901 INFO L274 PluginConnector]: CDTParser initialized [2024-11-17 08:11:01,902 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/termination-recursive-malloc/rec_malloc_ex3.i [2024-11-17 08:11:03,144 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-17 08:11:03,287 INFO L384 CDTParser]: Found 1 translation units. [2024-11-17 08:11:03,288 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-recursive-malloc/rec_malloc_ex3.i [2024-11-17 08:11:03,293 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3a296a35c/7e7262bb6bd948c79864c244a14ad116/FLAG7f4f2f174 [2024-11-17 08:11:03,712 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/3a296a35c/7e7262bb6bd948c79864c244a14ad116 [2024-11-17 08:11:03,714 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-17 08:11:03,715 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-17 08:11:03,716 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-17 08:11:03,716 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-17 08:11:03,720 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-17 08:11:03,720 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,721 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@58296004 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03, skipping insertion in model container [2024-11-17 08:11:03,721 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,735 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-17 08:11:03,866 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 08:11:03,876 INFO L200 MainTranslator]: Completed pre-run [2024-11-17 08:11:03,888 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-17 08:11:03,900 INFO L204 MainTranslator]: Completed translation [2024-11-17 08:11:03,901 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03 WrapperNode [2024-11-17 08:11:03,901 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-17 08:11:03,902 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-17 08:11:03,902 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-17 08:11:03,902 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-17 08:11:03,907 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,914 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,927 INFO L138 Inliner]: procedures = 11, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 20 [2024-11-17 08:11:03,927 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-17 08:11:03,928 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-17 08:11:03,928 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-17 08:11:03,928 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-17 08:11:03,935 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,936 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,937 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,946 INFO L175 MemorySlicer]: Split 5 memory accesses to 1 slices as follows [5]. 100 percent of accesses are in the largest equivalence class. The 0 initializations are split as follows [0]. The 2 writes are split as follows [2]. [2024-11-17 08:11:03,947 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,947 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,951 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,952 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,953 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,957 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,958 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-17 08:11:03,959 INFO L112 PluginConnector]: ------------------------IcfgBuilder---------------------------- [2024-11-17 08:11:03,960 INFO L270 PluginConnector]: Initializing IcfgBuilder... [2024-11-17 08:11:03,960 INFO L274 PluginConnector]: IcfgBuilder initialized [2024-11-17 08:11:03,960 INFO L184 PluginConnector]: Executing the observer IcfgBuilderObserver from plugin IcfgBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (1/1) ... [2024-11-17 08:11:03,965 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:03,997 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:04,023 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:04,029 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Waiting until timeout for monitored process [2024-11-17 08:11:04,061 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-17 08:11:04,062 INFO L130 BoogieDeclarations]: Found specification of procedure rec [2024-11-17 08:11:04,063 INFO L138 BoogieDeclarations]: Found implementation of procedure rec [2024-11-17 08:11:04,063 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-17 08:11:04,063 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-17 08:11:04,063 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-17 08:11:04,063 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-17 08:11:04,063 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-17 08:11:04,112 INFO L256 CfgBuilder]: Building ICFG [2024-11-17 08:11:04,113 INFO L286 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-17 08:11:04,165 INFO L1250 $ProcedureCfgBuilder]: dead code at ProgramPoint L15: havoc #t~ret5; [2024-11-17 08:11:04,165 INFO L1250 $ProcedureCfgBuilder]: dead code at ProgramPoint L9: havoc ~pv~0; [2024-11-17 08:11:04,188 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-17 08:11:04,188 INFO L307 CfgBuilder]: Performing block encoding [2024-11-17 08:11:04,196 INFO L331 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-17 08:11:04,196 INFO L336 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-17 08:11:04,197 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:11:04 BoogieIcfgContainer [2024-11-17 08:11:04,197 INFO L131 PluginConnector]: ------------------------ END IcfgBuilder---------------------------- [2024-11-17 08:11:04,198 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-17 08:11:04,198 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-17 08:11:04,201 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-17 08:11:04,201 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:11:04,201 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 17.11 08:11:03" (1/3) ... [2024-11-17 08:11:04,202 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6d904662 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.11 08:11:04, skipping insertion in model container [2024-11-17 08:11:04,202 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:11:04,202 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 17.11 08:11:03" (2/3) ... [2024-11-17 08:11:04,202 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6d904662 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 17.11 08:11:04, skipping insertion in model container [2024-11-17 08:11:04,202 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-17 08:11:04,202 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:11:04" (3/3) ... [2024-11-17 08:11:04,203 INFO L332 chiAutomizerObserver]: Analyzing ICFG rec_malloc_ex3.i [2024-11-17 08:11:04,242 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-17 08:11:04,242 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-17 08:11:04,243 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-17 08:11:04,243 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-17 08:11:04,243 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-17 08:11:04,243 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-17 08:11:04,243 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-17 08:11:04,243 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-17 08:11:04,247 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 16 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:04,261 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-17 08:11:04,261 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:04,261 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:04,265 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2024-11-17 08:11:04,265 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:04,266 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-17 08:11:04,266 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 16 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:04,267 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-17 08:11:04,267 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:04,267 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:04,268 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2024-11-17 08:11:04,268 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:04,272 INFO L745 eck$LassoCheckResult]: Stem: 4#ULTIMATE.startENTRYtrue assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 7#ULTIMATE.init_returnLabel#1true assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 15#L20true [2024-11-17 08:11:04,273 INFO L747 eck$LassoCheckResult]: Loop: 15#L20true assume true; 13#L20-1true assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 6#L23-1true call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 11#recENTRYtrue ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 9#L9-1true assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 16#recFINALtrue assume true; 14#recEXITtrue >#24#return; 12#L23true main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 15#L20true [2024-11-17 08:11:04,277 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:04,278 INFO L85 PathProgramCache]: Analyzing trace with hash 1568, now seen corresponding path program 1 times [2024-11-17 08:11:04,284 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:04,284 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [330896341] [2024-11-17 08:11:04,285 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:04,285 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:04,345 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,346 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:04,350 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,364 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:04,367 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:04,368 INFO L85 PathProgramCache]: Analyzing trace with hash 1400452965, now seen corresponding path program 1 times [2024-11-17 08:11:04,368 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:04,368 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [634462455] [2024-11-17 08:11:04,368 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:04,368 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:04,415 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,416 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:04,430 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,436 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:04,438 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:04,438 INFO L85 PathProgramCache]: Analyzing trace with hash -497242492, now seen corresponding path program 1 times [2024-11-17 08:11:04,438 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:04,438 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1989144536] [2024-11-17 08:11:04,438 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:04,439 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:04,467 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,471 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:04,492 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:04,499 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:04,902 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:04,902 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:04,902 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:04,902 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:04,902 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:04,903 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:04,903 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:04,903 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:04,903 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration1_Lasso [2024-11-17 08:11:04,903 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:04,903 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:04,913 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,919 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,921 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,923 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,932 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,935 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,972 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,974 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:04,976 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:05,038 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:05,041 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:05,042 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,042 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,044 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,045 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Waiting until timeout for monitored process [2024-11-17 08:11:05,046 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,057 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,057 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,058 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,058 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,058 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,060 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,060 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,062 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,076 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (2)] Ended with exit code 0 [2024-11-17 08:11:05,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,078 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,080 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Waiting until timeout for monitored process [2024-11-17 08:11:05,085 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,095 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,095 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,095 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,095 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,095 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,096 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,096 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,097 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,108 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:05,108 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,108 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,109 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,110 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Waiting until timeout for monitored process [2024-11-17 08:11:05,111 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,123 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,123 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,124 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,124 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,124 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,124 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,124 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,125 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,137 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Ended with exit code 0 [2024-11-17 08:11:05,138 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,138 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,139 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,140 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Waiting until timeout for monitored process [2024-11-17 08:11:05,141 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,151 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,151 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,152 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,152 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,152 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,152 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,152 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,154 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,164 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:05,164 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,164 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,165 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,166 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Waiting until timeout for monitored process [2024-11-17 08:11:05,167 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,177 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,177 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,177 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,177 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,177 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,178 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,178 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,179 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,189 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (6)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:05,190 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,190 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,191 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,192 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Waiting until timeout for monitored process [2024-11-17 08:11:05,192 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,202 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,202 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,202 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-17 08:11:05,202 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,208 INFO L401 nArgumentSynthesizer]: We have 16 Motzkin's Theorem applications. [2024-11-17 08:11:05,208 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-17 08:11:05,217 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:05,228 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (7)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:05,228 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,229 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,230 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,231 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Waiting until timeout for monitored process [2024-11-17 08:11:05,232 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:05,242 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:05,242 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:05,242 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:05,242 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:05,243 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:05,244 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:05,245 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:05,246 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:05,254 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-17 08:11:05,254 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-17 08:11:05,255 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:05,255 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:05,270 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:05,271 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Waiting until timeout for monitored process [2024-11-17 08:11:05,272 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:05,272 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:11:05,273 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:05,273 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(ULTIMATE.start_main_~i~0#1) = 1*ULTIMATE.start_main_~i~0#1 Supporting invariants [] [2024-11-17 08:11:05,284 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (8)] Ended with exit code 0 [2024-11-17 08:11:05,286 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:11:05,302 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:05,308 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:05,309 INFO L255 TraceCheckSpWp]: Trace formula consists of 6 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-17 08:11:05,310 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:05,332 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:05,333 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 08:11:05,334 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:05,403 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 17 treesize of output 9 [2024-11-17 08:11:05,461 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:05,484 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 6 loop predicates [2024-11-17 08:11:05,485 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 16 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Second operand has 8 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 6 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 08:11:05,584 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:05,610 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 16 states, 12 states have (on average 1.25) internal successors, (15), 12 states have internal predecessors, (15), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2). Second operand has 8 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 6 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) Result 65 states and 78 transitions. Complement of second has 22 states. [2024-11-17 08:11:05,613 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 1 stem states 6 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:05,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 1.1428571428571428) internal successors, (8), 6 states have internal predecessors, (8), 1 states have call successors, (1), 1 states have call predecessors, (1), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-17 08:11:05,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 21 transitions. [2024-11-17 08:11:05,622 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 21 transitions. Stem has 2 letters. Loop has 8 letters. [2024-11-17 08:11:05,623 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:05,623 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 21 transitions. Stem has 10 letters. Loop has 8 letters. [2024-11-17 08:11:05,623 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:05,623 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 21 transitions. Stem has 2 letters. Loop has 16 letters. [2024-11-17 08:11:05,623 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:05,624 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 65 states and 78 transitions. [2024-11-17 08:11:05,629 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 12 [2024-11-17 08:11:05,634 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 65 states to 41 states and 48 transitions. [2024-11-17 08:11:05,634 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 32 [2024-11-17 08:11:05,634 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 33 [2024-11-17 08:11:05,635 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 48 transitions. [2024-11-17 08:11:05,635 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:11:05,635 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 48 transitions. [2024-11-17 08:11:05,650 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 48 transitions. [2024-11-17 08:11:05,659 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 38. [2024-11-17 08:11:05,659 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 28 states have (on average 1.1428571428571428) internal successors, (32), 28 states have internal predecessors, (32), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 5 states have call predecessors, (6), 6 states have call successors, (6) [2024-11-17 08:11:05,662 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2024-11-17 08:11:05,662 INFO L240 hiAutomatonCegarLoop]: Abstraction has 38 states and 44 transitions. [2024-11-17 08:11:05,662 INFO L425 stractBuchiCegarLoop]: Abstraction has 38 states and 44 transitions. [2024-11-17 08:11:05,663 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-17 08:11:05,663 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 38 states and 44 transitions. [2024-11-17 08:11:05,663 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 12 [2024-11-17 08:11:05,664 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:05,664 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:05,664 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:05,664 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:11:05,664 INFO L745 eck$LassoCheckResult]: Stem: 163#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 164#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 170#L20 assume true; 187#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 161#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 167#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 171#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 172#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 160#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 162#recENTRY [2024-11-17 08:11:05,664 INFO L747 eck$LassoCheckResult]: Loop: 162#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 196#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 197#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 183#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 162#recENTRY [2024-11-17 08:11:05,665 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:05,665 INFO L85 PathProgramCache]: Analyzing trace with hash -1401512599, now seen corresponding path program 1 times [2024-11-17 08:11:05,665 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:05,665 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1455636547] [2024-11-17 08:11:05,665 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:05,665 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:05,689 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,689 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:05,702 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,707 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:05,709 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:05,709 INFO L85 PathProgramCache]: Analyzing trace with hash 1137938, now seen corresponding path program 1 times [2024-11-17 08:11:05,710 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:05,710 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [520757209] [2024-11-17 08:11:05,710 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:05,710 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:05,719 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,719 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:05,722 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,723 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:05,724 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:05,724 INFO L85 PathProgramCache]: Analyzing trace with hash 732628602, now seen corresponding path program 2 times [2024-11-17 08:11:05,724 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:05,724 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1004185546] [2024-11-17 08:11:05,724 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:05,724 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:05,742 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,742 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:05,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:05,763 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:06,321 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:06,322 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:06,322 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:06,322 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:06,322 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:06,322 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,322 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:06,322 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:06,322 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration2_Lasso [2024-11-17 08:11:06,322 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:06,322 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:06,324 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,330 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,332 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,333 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,334 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,516 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,518 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,520 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,521 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,523 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,525 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,526 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,528 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,530 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,531 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,533 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,535 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,536 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,538 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:06,726 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:06,727 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:06,727 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,727 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,728 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,730 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Waiting until timeout for monitored process [2024-11-17 08:11:06,730 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,741 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,741 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:06,741 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,741 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,741 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,742 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:06,742 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:06,743 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,753 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:06,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,754 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,755 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,756 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Waiting until timeout for monitored process [2024-11-17 08:11:06,757 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,767 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,767 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:06,767 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,768 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,768 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,768 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:06,768 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:06,769 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,780 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (11)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:06,780 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,780 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,782 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,783 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Waiting until timeout for monitored process [2024-11-17 08:11:06,784 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,794 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,794 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:06,794 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,794 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,794 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,795 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:06,795 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:06,796 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,806 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (12)] Ended with exit code 0 [2024-11-17 08:11:06,807 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,807 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,808 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,809 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Waiting until timeout for monitored process [2024-11-17 08:11:06,810 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,820 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,820 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,821 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,821 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,823 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:06,823 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:06,826 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,836 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (13)] Ended with exit code 0 [2024-11-17 08:11:06,837 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,837 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,838 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,839 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Waiting until timeout for monitored process [2024-11-17 08:11:06,840 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,850 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,850 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,850 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,850 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,852 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:06,852 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:06,855 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,866 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (14)] Ended with exit code 0 [2024-11-17 08:11:06,866 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,866 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,867 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,868 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Waiting until timeout for monitored process [2024-11-17 08:11:06,870 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,880 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,880 INFO L203 nArgumentSynthesizer]: 2 stem disjuncts [2024-11-17 08:11:06,880 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,880 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,883 INFO L401 nArgumentSynthesizer]: We have 8 Motzkin's Theorem applications. [2024-11-17 08:11:06,883 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:06,889 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:06,899 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:06,900 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,900 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,901 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,901 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Waiting until timeout for monitored process [2024-11-17 08:11:06,903 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:06,913 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:06,913 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:06,913 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:06,913 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:06,918 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:06,918 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:06,925 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:06,948 INFO L443 ModelExtractionUtils]: Simplification made 18 calls to the SMT solver. [2024-11-17 08:11:06,948 INFO L444 ModelExtractionUtils]: 2 out of 16 variables were initially zero. Simplification set additionally 7 variables to zero. [2024-11-17 08:11:06,949 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:06,949 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:06,950 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:06,951 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Waiting until timeout for monitored process [2024-11-17 08:11:06,952 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:06,964 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 2. [2024-11-17 08:11:06,964 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:06,964 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(v_rep(select (select old(#memory_int#0) rec_#in~p.base) rec_#in~p.offset)_1) = 2*v_rep(select (select old(#memory_int#0) rec_#in~p.base) rec_#in~p.offset)_1 + 3 Supporting invariants [1*v_rep(select (select old(#memory_int#0) rec_#in~p.base) rec_#in~p.offset)_1 + 1 >= 0, -1*v_rep(select (select #memory_int#0 rec_#in~p.base) 0)_1 + 1*v_rep(select (select old(#memory_int#0) rec_#in~p.base) rec_#in~p.offset)_1 >= 0] [2024-11-17 08:11:06,975 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:06,986 INFO L156 tatePredicateManager]: 2 out of 4 supporting invariants were superfluous and have been removed [2024-11-17 08:11:06,992 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#0 [2024-11-17 08:11:06,993 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array UnaryExpression[OLD,IdentifierExpression[#memory_int#0,GLOBAL]] [2024-11-17 08:11:06,993 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[UnaryExpression[OLD,IdentifierExpression[#memory_int#0,GLOBAL]],[IdentifierExpression[#in~p!base,]]] [2024-11-17 08:11:07,011 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:07,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:07,029 INFO L255 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 13 conjuncts are in the unsatisfiable core [2024-11-17 08:11:07,030 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:07,091 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:07,092 INFO L255 TraceCheckSpWp]: Trace formula consists of 62 conjuncts, 20 conjuncts are in the unsatisfiable core [2024-11-17 08:11:07,094 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:07,103 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 23 treesize of output 15 [2024-11-17 08:11:07,152 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 36 treesize of output 20 [2024-11-17 08:11:07,170 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:07,170 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.4 stem predicates 4 loop predicates [2024-11-17 08:11:07,171 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 38 states and 44 transitions. cyclomatic complexity: 10 Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 08:11:07,324 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 38 states and 44 transitions. cyclomatic complexity: 10. Second operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Result 56 states and 65 transitions. Complement of second has 23 states. [2024-11-17 08:11:07,325 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 4 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:07,325 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 6 states have (on average 1.6666666666666667) internal successors, (10), 6 states have internal predecessors, (10), 3 states have call successors, (3), 2 states have call predecessors, (3), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2024-11-17 08:11:07,326 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 19 transitions. [2024-11-17 08:11:07,326 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 19 transitions. Stem has 9 letters. Loop has 4 letters. [2024-11-17 08:11:07,327 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:07,327 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 19 transitions. Stem has 13 letters. Loop has 4 letters. [2024-11-17 08:11:07,327 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:07,327 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 19 transitions. Stem has 9 letters. Loop has 8 letters. [2024-11-17 08:11:07,328 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:07,328 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 56 states and 65 transitions. [2024-11-17 08:11:07,330 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-17 08:11:07,332 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 56 states to 48 states and 57 transitions. [2024-11-17 08:11:07,334 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 31 [2024-11-17 08:11:07,334 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 33 [2024-11-17 08:11:07,334 INFO L73 IsDeterministic]: Start isDeterministic. Operand 48 states and 57 transitions. [2024-11-17 08:11:07,334 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:11:07,334 INFO L218 hiAutomatonCegarLoop]: Abstraction has 48 states and 57 transitions. [2024-11-17 08:11:07,334 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 48 states and 57 transitions. [2024-11-17 08:11:07,337 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 48 to 45. [2024-11-17 08:11:07,338 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 33 states have (on average 1.1515151515151516) internal successors, (38), 34 states have internal predecessors, (38), 6 states have call successors, (6), 5 states have call predecessors, (6), 6 states have return successors, (8), 5 states have call predecessors, (8), 6 states have call successors, (8) [2024-11-17 08:11:07,339 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 52 transitions. [2024-11-17 08:11:07,339 INFO L240 hiAutomatonCegarLoop]: Abstraction has 45 states and 52 transitions. [2024-11-17 08:11:07,339 INFO L425 stractBuchiCegarLoop]: Abstraction has 45 states and 52 transitions. [2024-11-17 08:11:07,339 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-17 08:11:07,339 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 45 states and 52 transitions. [2024-11-17 08:11:07,340 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 8 [2024-11-17 08:11:07,340 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:07,340 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:07,341 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:07,341 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:07,341 INFO L745 eck$LassoCheckResult]: Stem: 372#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 373#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 384#L20 assume true; 392#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 368#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 405#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 404#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 403#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 367#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 369#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 387#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 411#recFINAL assume true; 409#recEXIT >#22#return; 408#L15-1 #res := #t~ret5;havoc #t~ret5; 401#recFINAL assume true; 402#recEXIT >#24#return; 388#L23 [2024-11-17 08:11:07,341 INFO L747 eck$LassoCheckResult]: Loop: 388#L23 main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 389#L20 assume true; 397#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 376#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 377#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 406#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 407#recFINAL assume true; 399#recEXIT >#24#return; 388#L23 [2024-11-17 08:11:07,343 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:07,343 INFO L85 PathProgramCache]: Analyzing trace with hash -1309096612, now seen corresponding path program 1 times [2024-11-17 08:11:07,343 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:07,343 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1077479465] [2024-11-17 08:11:07,343 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:07,343 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:07,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,360 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:07,367 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,369 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:07,369 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:07,370 INFO L85 PathProgramCache]: Analyzing trace with hash 206828573, now seen corresponding path program 2 times [2024-11-17 08:11:07,370 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:07,370 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [555408304] [2024-11-17 08:11:07,370 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:07,370 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:07,381 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,381 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:07,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,391 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:07,391 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:07,391 INFO L85 PathProgramCache]: Analyzing trace with hash -1542771080, now seen corresponding path program 1 times [2024-11-17 08:11:07,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:07,391 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2001085660] [2024-11-17 08:11:07,391 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:07,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:07,409 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,411 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:07,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:07,430 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:07,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (17)] Ended with exit code 0 [2024-11-17 08:11:08,020 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:08,020 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:08,020 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:08,020 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:08,020 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:08,020 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,020 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:08,020 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:08,020 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration3_Lasso [2024-11-17 08:11:08,020 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:08,020 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:08,021 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,112 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,114 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,116 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,117 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,119 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:08,232 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:08,232 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:08,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:08,234 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:08,235 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Waiting until timeout for monitored process [2024-11-17 08:11:08,236 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:08,245 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:08,245 INFO L203 nArgumentSynthesizer]: 2 stem disjuncts [2024-11-17 08:11:08,245 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-17 08:11:08,245 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:08,249 INFO L401 nArgumentSynthesizer]: We have 20 Motzkin's Theorem applications. [2024-11-17 08:11:08,249 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-17 08:11:08,257 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:08,267 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (18)] Ended with exit code 0 [2024-11-17 08:11:08,268 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,268 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:08,269 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:08,270 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Waiting until timeout for monitored process [2024-11-17 08:11:08,271 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:08,280 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:08,280 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:08,280 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:08,280 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:08,282 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:08,282 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:08,285 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:08,295 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Ended with exit code 0 [2024-11-17 08:11:08,295 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,295 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:08,296 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:08,298 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Waiting until timeout for monitored process [2024-11-17 08:11:08,298 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:08,307 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:08,308 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:08,308 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:08,308 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:08,309 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:08,309 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:08,312 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:08,322 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Ended with exit code 0 [2024-11-17 08:11:08,323 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,323 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:08,324 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:08,325 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Waiting until timeout for monitored process [2024-11-17 08:11:08,325 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:08,334 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:08,335 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:08,335 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:08,335 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:08,338 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:08,338 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:08,348 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:08,359 INFO L443 ModelExtractionUtils]: Simplification made 8 calls to the SMT solver. [2024-11-17 08:11:08,359 INFO L444 ModelExtractionUtils]: 8 out of 16 variables were initially zero. Simplification set additionally 5 variables to zero. [2024-11-17 08:11:08,359 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:08,359 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:08,361 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:08,362 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Waiting until timeout for monitored process [2024-11-17 08:11:08,365 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:08,376 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-17 08:11:08,376 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:08,376 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(ULTIMATE.start_main_~i~0#1, ULTIMATE.start_main_#t~ret9#1) = 1*ULTIMATE.start_main_~i~0#1 + 1*ULTIMATE.start_main_#t~ret9#1 Supporting invariants [] [2024-11-17 08:11:08,387 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:08,390 INFO L156 tatePredicateManager]: 2 out of 2 supporting invariants were superfluous and have been removed [2024-11-17 08:11:08,391 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret9 [2024-11-17 08:11:08,397 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:08,423 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:08,423 INFO L255 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-17 08:11:08,424 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:08,548 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:08,549 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 08:11:08,549 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:08,596 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 17 treesize of output 9 [2024-11-17 08:11:08,610 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:08,610 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-17 08:11:08,610 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 45 states and 52 transitions. cyclomatic complexity: 11 Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 08:11:08,696 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 45 states and 52 transitions. cyclomatic complexity: 11. Second operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) Result 150 states and 172 transitions. Complement of second has 21 states. [2024-11-17 08:11:08,696 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:08,697 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.2857142857142856) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (3), 2 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-17 08:11:08,697 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 30 transitions. [2024-11-17 08:11:08,697 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 30 transitions. Stem has 16 letters. Loop has 8 letters. [2024-11-17 08:11:08,698 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:08,698 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 30 transitions. Stem has 24 letters. Loop has 8 letters. [2024-11-17 08:11:08,698 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:08,698 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 30 transitions. Stem has 16 letters. Loop has 16 letters. [2024-11-17 08:11:08,698 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:08,698 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 150 states and 172 transitions. [2024-11-17 08:11:08,701 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 12 [2024-11-17 08:11:08,702 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 150 states to 104 states and 119 transitions. [2024-11-17 08:11:08,702 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 72 [2024-11-17 08:11:08,703 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 74 [2024-11-17 08:11:08,703 INFO L73 IsDeterministic]: Start isDeterministic. Operand 104 states and 119 transitions. [2024-11-17 08:11:08,703 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:11:08,703 INFO L218 hiAutomatonCegarLoop]: Abstraction has 104 states and 119 transitions. [2024-11-17 08:11:08,703 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 104 states and 119 transitions. [2024-11-17 08:11:08,708 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 104 to 95. [2024-11-17 08:11:08,709 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 95 states, 69 states have (on average 1.144927536231884) internal successors, (79), 72 states have internal predecessors, (79), 13 states have call successors, (13), 11 states have call predecessors, (13), 13 states have return successors, (17), 11 states have call predecessors, (17), 13 states have call successors, (17) [2024-11-17 08:11:08,709 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 95 states to 95 states and 109 transitions. [2024-11-17 08:11:08,710 INFO L240 hiAutomatonCegarLoop]: Abstraction has 95 states and 109 transitions. [2024-11-17 08:11:08,710 INFO L425 stractBuchiCegarLoop]: Abstraction has 95 states and 109 transitions. [2024-11-17 08:11:08,710 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-17 08:11:08,710 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 95 states and 109 transitions. [2024-11-17 08:11:08,711 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 12 [2024-11-17 08:11:08,711 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:08,711 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:08,711 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:08,711 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1] [2024-11-17 08:11:08,711 INFO L745 eck$LassoCheckResult]: Stem: 695#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 696#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 708#L20 assume true; 738#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 735#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 736#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 743#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 742#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 731#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 741#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 751#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 774#recFINAL assume true; 740#recEXIT >#22#return; 739#L15-1 #res := #t~ret5;havoc #t~ret5; 737#recFINAL assume true; 734#recEXIT >#24#return; 733#L23 main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 718#L20 assume true; 719#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 699#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 700#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 703#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 704#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 710#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 778#recENTRY [2024-11-17 08:11:08,711 INFO L747 eck$LassoCheckResult]: Loop: 778#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 779#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 709#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 711#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 778#recENTRY [2024-11-17 08:11:08,712 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:08,712 INFO L85 PathProgramCache]: Analyzing trace with hash -1542770277, now seen corresponding path program 2 times [2024-11-17 08:11:08,712 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:08,712 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [327165586] [2024-11-17 08:11:08,712 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:08,714 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:08,745 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,745 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:08,756 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,764 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:08,765 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:08,765 INFO L85 PathProgramCache]: Analyzing trace with hash 1137938, now seen corresponding path program 2 times [2024-11-17 08:11:08,765 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:08,765 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [23945723] [2024-11-17 08:11:08,765 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:08,765 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:08,767 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Ended with exit code 0 [2024-11-17 08:11:08,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,772 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:08,773 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,774 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:08,774 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:08,775 INFO L85 PathProgramCache]: Analyzing trace with hash 1637233068, now seen corresponding path program 3 times [2024-11-17 08:11:08,775 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:08,775 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2065549293] [2024-11-17 08:11:08,775 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:08,775 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:08,792 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,796 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:08,804 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:08,809 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:09,690 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:09,690 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:09,690 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:09,690 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:09,690 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:09,690 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:09,690 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:09,690 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:09,690 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration4_Lasso [2024-11-17 08:11:09,690 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:09,690 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:09,691 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,694 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,699 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,700 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,701 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,703 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,704 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,705 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,808 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,810 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,811 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,813 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,814 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,816 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,817 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,818 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,820 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,821 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:09,824 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:10,003 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:10,003 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:10,003 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,003 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,005 INFO L229 MonitoredProcess]: Starting monitored process 23 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,006 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Waiting until timeout for monitored process [2024-11-17 08:11:10,006 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,016 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,016 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,016 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,016 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,017 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,017 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,017 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,018 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,029 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (23)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,029 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,029 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,030 INFO L229 MonitoredProcess]: Starting monitored process 24 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,031 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Waiting until timeout for monitored process [2024-11-17 08:11:10,032 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,042 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,042 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,042 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,042 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,042 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,043 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,043 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,044 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,054 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (24)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,054 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,054 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,055 INFO L229 MonitoredProcess]: Starting monitored process 25 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,056 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Waiting until timeout for monitored process [2024-11-17 08:11:10,056 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,066 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,066 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,066 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,066 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,066 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,066 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,066 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,067 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,077 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (25)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,077 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,077 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,078 INFO L229 MonitoredProcess]: Starting monitored process 26 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,079 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Waiting until timeout for monitored process [2024-11-17 08:11:10,079 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,089 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,089 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,089 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,089 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,089 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,089 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,089 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,090 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,100 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (26)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,100 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,100 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,101 INFO L229 MonitoredProcess]: Starting monitored process 27 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,101 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Waiting until timeout for monitored process [2024-11-17 08:11:10,102 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,112 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,112 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,112 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,112 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,112 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,112 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,112 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,113 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,122 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (27)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,123 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,123 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,124 INFO L229 MonitoredProcess]: Starting monitored process 28 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,125 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Waiting until timeout for monitored process [2024-11-17 08:11:10,125 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,134 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,135 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,135 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,135 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,135 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,135 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,135 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,136 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,146 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (28)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,146 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,146 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,147 INFO L229 MonitoredProcess]: Starting monitored process 29 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,148 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Waiting until timeout for monitored process [2024-11-17 08:11:10,148 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,158 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,158 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:10,158 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,158 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,158 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,158 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:10,158 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:10,159 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,168 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (29)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,169 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,169 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,170 INFO L229 MonitoredProcess]: Starting monitored process 30 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,170 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Waiting until timeout for monitored process [2024-11-17 08:11:10,171 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,180 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,181 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,181 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,181 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,182 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:10,182 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,185 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,195 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (30)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,195 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,195 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,196 INFO L229 MonitoredProcess]: Starting monitored process 31 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,196 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Waiting until timeout for monitored process [2024-11-17 08:11:10,197 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,206 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,206 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,206 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,206 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,208 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:10,208 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,211 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,221 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (31)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,222 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,222 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,223 INFO L229 MonitoredProcess]: Starting monitored process 32 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,224 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Waiting until timeout for monitored process [2024-11-17 08:11:10,224 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,233 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,234 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,234 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,234 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,234 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:10,234 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,237 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,246 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,246 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,246 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,248 INFO L229 MonitoredProcess]: Starting monitored process 33 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,249 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Waiting until timeout for monitored process [2024-11-17 08:11:10,249 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,258 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,258 INFO L203 nArgumentSynthesizer]: 4 stem disjuncts [2024-11-17 08:11:10,259 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,259 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,261 INFO L401 nArgumentSynthesizer]: We have 12 Motzkin's Theorem applications. [2024-11-17 08:11:10,261 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,265 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,275 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (33)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,275 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,275 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,277 INFO L229 MonitoredProcess]: Starting monitored process 34 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,277 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Waiting until timeout for monitored process [2024-11-17 08:11:10,278 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,287 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,288 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,288 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,288 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,289 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:10,289 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,293 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:10,303 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,307 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,307 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,309 INFO L229 MonitoredProcess]: Starting monitored process 35 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,310 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Waiting until timeout for monitored process [2024-11-17 08:11:10,311 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:10,321 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:10,321 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:10,321 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:10,321 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:10,324 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:10,324 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:10,328 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:10,334 INFO L443 ModelExtractionUtils]: Simplification made 4 calls to the SMT solver. [2024-11-17 08:11:10,334 INFO L444 ModelExtractionUtils]: 5 out of 10 variables were initially zero. Simplification set additionally 2 variables to zero. [2024-11-17 08:11:10,336 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:10,336 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:10,337 INFO L229 MonitoredProcess]: Starting monitored process 36 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:10,338 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Waiting until timeout for monitored process [2024-11-17 08:11:10,339 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:10,349 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-17 08:11:10,349 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:10,349 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(v_rep(select (select #memory_int#0 rec_#in~p.base) rec_#in~p.offset)_2) = 2*v_rep(select (select #memory_int#0 rec_#in~p.base) rec_#in~p.offset)_2 + 1 Supporting invariants [] [2024-11-17 08:11:10,360 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (35)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,362 INFO L156 tatePredicateManager]: 1 out of 1 supporting invariants were superfluous and have been removed [2024-11-17 08:11:10,363 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#0 [2024-11-17 08:11:10,363 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#0,GLOBAL] [2024-11-17 08:11:10,363 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#0,GLOBAL],[IdentifierExpression[#in~p!base,]]] [2024-11-17 08:11:10,373 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:10,405 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:10,406 INFO L255 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-17 08:11:10,407 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:10,498 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:10,499 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-17 08:11:10,499 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:10,526 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 36 treesize of output 20 [2024-11-17 08:11:10,538 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:10,538 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-17 08:11:10,539 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21 Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:10,613 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Result 125 states and 143 transitions. Complement of second has 21 states. [2024-11-17 08:11:10,614 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:10,615 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:10,615 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 19 transitions. [2024-11-17 08:11:10,615 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 19 transitions. Stem has 24 letters. Loop has 4 letters. [2024-11-17 08:11:10,615 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:10,615 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:11:10,622 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:10,656 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:10,657 INFO L255 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-17 08:11:10,658 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:10,734 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (36)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:10,772 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:10,774 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-17 08:11:10,774 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:10,801 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 36 treesize of output 20 [2024-11-17 08:11:10,814 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:10,815 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-17 08:11:10,815 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21 Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:10,905 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Result 125 states and 143 transitions. Complement of second has 21 states. [2024-11-17 08:11:10,905 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:10,906 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:10,906 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 19 transitions. [2024-11-17 08:11:10,906 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 19 transitions. Stem has 24 letters. Loop has 4 letters. [2024-11-17 08:11:10,906 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:10,906 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:11:10,918 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:10,953 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:10,957 INFO L255 TraceCheckSpWp]: Trace formula consists of 272 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-17 08:11:10,958 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:11,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:11,054 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-17 08:11:11,055 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:11,083 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 36 treesize of output 20 [2024-11-17 08:11:11,096 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:11,096 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 4 loop predicates [2024-11-17 08:11:11,096 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21 Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:11,179 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 95 states and 109 transitions. cyclomatic complexity: 21. Second operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Result 184 states and 209 transitions. Complement of second has 24 states. [2024-11-17 08:11:11,182 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 7 states 2 stem states 4 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:11,183 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 6 states, 5 states have (on average 3.4) internal successors, (17), 5 states have internal predecessors, (17), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:11,183 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 7 states to 7 states and 22 transitions. [2024-11-17 08:11:11,183 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 22 transitions. Stem has 24 letters. Loop has 4 letters. [2024-11-17 08:11:11,183 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:11,183 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 22 transitions. Stem has 28 letters. Loop has 4 letters. [2024-11-17 08:11:11,184 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:11,184 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 7 states and 22 transitions. Stem has 24 letters. Loop has 8 letters. [2024-11-17 08:11:11,184 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:11,184 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 184 states and 209 transitions. [2024-11-17 08:11:11,187 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-17 08:11:11,189 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 184 states to 128 states and 153 transitions. [2024-11-17 08:11:11,189 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 76 [2024-11-17 08:11:11,190 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 84 [2024-11-17 08:11:11,190 INFO L73 IsDeterministic]: Start isDeterministic. Operand 128 states and 153 transitions. [2024-11-17 08:11:11,190 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:11:11,190 INFO L218 hiAutomatonCegarLoop]: Abstraction has 128 states and 153 transitions. [2024-11-17 08:11:11,190 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 128 states and 153 transitions. [2024-11-17 08:11:11,195 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 128 to 84. [2024-11-17 08:11:11,195 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 84 states, 61 states have (on average 1.1639344262295082) internal successors, (71), 64 states have internal predecessors, (71), 10 states have call successors, (10), 10 states have call predecessors, (10), 13 states have return successors, (16), 9 states have call predecessors, (16), 10 states have call successors, (16) [2024-11-17 08:11:11,196 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 84 states to 84 states and 97 transitions. [2024-11-17 08:11:11,196 INFO L240 hiAutomatonCegarLoop]: Abstraction has 84 states and 97 transitions. [2024-11-17 08:11:11,196 INFO L425 stractBuchiCegarLoop]: Abstraction has 84 states and 97 transitions. [2024-11-17 08:11:11,196 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-17 08:11:11,196 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 84 states and 97 transitions. [2024-11-17 08:11:11,201 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 4 [2024-11-17 08:11:11,201 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:11,201 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:11,202 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:11,202 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:11,202 INFO L745 eck$LassoCheckResult]: Stem: 1593#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 1594#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 1604#L20 assume true; 1613#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 1598#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1599#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1619#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 1617#recFINAL assume true; 1615#recEXIT >#24#return; 1609#L23 main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 1611#L20 assume true; 1612#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 1589#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1597#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1647#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 1605#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 1588#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 1590#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1600#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 1601#recFINAL assume true; 1616#recEXIT >#22#return; 1648#L15-1 #res := #t~ret5;havoc #t~ret5; 1645#recFINAL assume true; 1646#recEXIT >#24#return; 1607#L23 [2024-11-17 08:11:11,202 INFO L747 eck$LassoCheckResult]: Loop: 1607#L23 main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 1608#L20 assume true; 1653#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 1643#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1652#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1649#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 1650#recFINAL assume true; 1642#recEXIT >#24#return; 1607#L23 [2024-11-17 08:11:11,202 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:11,202 INFO L85 PathProgramCache]: Analyzing trace with hash 1522855616, now seen corresponding path program 4 times [2024-11-17 08:11:11,202 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:11,202 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1361008892] [2024-11-17 08:11:11,202 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:11,202 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:11,224 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,224 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:11,232 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,238 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:11,238 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:11,238 INFO L85 PathProgramCache]: Analyzing trace with hash 206828573, now seen corresponding path program 3 times [2024-11-17 08:11:11,238 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:11,238 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1042785183] [2024-11-17 08:11:11,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:11,239 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:11,252 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,252 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:11,257 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,258 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:11,258 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:11,258 INFO L85 PathProgramCache]: Analyzing trace with hash -1587956772, now seen corresponding path program 5 times [2024-11-17 08:11:11,258 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:11,258 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [633029728] [2024-11-17 08:11:11,259 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:11,259 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:11,274 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,274 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:11,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:11,300 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:12,156 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:12,157 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:12,157 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:12,157 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:12,157 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:12,157 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:12,157 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:12,157 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:12,157 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration5_Lasso [2024-11-17 08:11:12,157 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:12,157 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:12,159 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,161 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,297 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,299 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,300 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,301 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:12,479 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:12,479 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:12,480 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:12,480 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:12,481 INFO L229 MonitoredProcess]: Starting monitored process 37 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:12,481 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Waiting until timeout for monitored process [2024-11-17 08:11:12,482 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:12,491 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:12,491 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:12,491 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:12,491 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:12,491 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:12,492 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:12,492 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:12,493 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:12,502 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (37)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:12,502 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:12,503 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:12,504 INFO L229 MonitoredProcess]: Starting monitored process 38 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:12,504 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Waiting until timeout for monitored process [2024-11-17 08:11:12,505 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:12,515 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:12,515 INFO L203 nArgumentSynthesizer]: 6 stem disjuncts [2024-11-17 08:11:12,515 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-17 08:11:12,515 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:12,528 INFO L401 nArgumentSynthesizer]: We have 36 Motzkin's Theorem applications. [2024-11-17 08:11:12,528 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-17 08:11:12,545 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:12,556 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:12,557 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:12,557 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:12,558 INFO L229 MonitoredProcess]: Starting monitored process 39 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:12,559 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Waiting until timeout for monitored process [2024-11-17 08:11:12,560 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:12,570 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:12,570 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:12,570 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:12,570 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:12,573 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-17 08:11:12,573 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-17 08:11:12,580 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:12,596 INFO L443 ModelExtractionUtils]: Simplification made 10 calls to the SMT solver. [2024-11-17 08:11:12,596 INFO L444 ModelExtractionUtils]: 2 out of 16 variables were initially zero. Simplification set additionally 11 variables to zero. [2024-11-17 08:11:12,597 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:12,597 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:12,598 INFO L229 MonitoredProcess]: Starting monitored process 40 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:12,599 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:12,605 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Waiting until timeout for monitored process [2024-11-17 08:11:12,610 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-17 08:11:12,610 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:12,610 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(ULTIMATE.start_main_#t~ret9#1, ULTIMATE.start_main_~i~0#1) = 1*ULTIMATE.start_main_#t~ret9#1 + 1*ULTIMATE.start_main_~i~0#1 Supporting invariants [] [2024-11-17 08:11:12,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (39)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:12,627 INFO L156 tatePredicateManager]: 2 out of 2 supporting invariants were superfluous and have been removed [2024-11-17 08:11:12,627 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret9 [2024-11-17 08:11:12,635 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:12,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:12,665 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-17 08:11:12,665 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:12,775 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (40)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:12,779 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:12,780 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 08:11:12,780 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:12,815 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 17 treesize of output 9 [2024-11-17 08:11:12,827 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:12,828 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-17 08:11:12,828 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:12,893 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 134 states and 155 transitions. Complement of second has 21 states. [2024-11-17 08:11:12,893 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:12,893 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:12,894 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 30 transitions. [2024-11-17 08:11:12,894 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 30 transitions. Stem has 24 letters. Loop has 8 letters. [2024-11-17 08:11:12,894 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:12,894 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:11:12,902 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:12,934 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:12,935 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-17 08:11:12,936 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:13,034 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:13,034 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 08:11:13,035 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:13,077 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 17 treesize of output 9 [2024-11-17 08:11:13,090 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:13,090 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-17 08:11:13,090 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:13,155 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 134 states and 155 transitions. Complement of second has 21 states. [2024-11-17 08:11:13,155 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:13,156 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:13,156 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 30 transitions. [2024-11-17 08:11:13,156 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 30 transitions. Stem has 24 letters. Loop has 8 letters. [2024-11-17 08:11:13,156 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:13,156 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-17 08:11:13,165 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:13,191 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:13,192 INFO L255 TraceCheckSpWp]: Trace formula consists of 240 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-17 08:11:13,193 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:13,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:13,291 INFO L255 TraceCheckSpWp]: Trace formula consists of 89 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-17 08:11:13,293 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:13,337 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 17 treesize of output 9 [2024-11-17 08:11:13,349 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-17 08:11:13,350 INFO L141 lantAutomatonBouncer]: Defining Buchi interpolant automaton with scrooge nondeterminism in stemwith honda bouncer for stem and without honda bouncer for loop.2 stem predicates 6 loop predicates [2024-11-17 08:11:13,350 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:13,423 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 84 states and 97 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) Result 162 states and 188 transitions. Complement of second has 22 states. [2024-11-17 08:11:13,425 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 2 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:13,425 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.4285714285714284) internal successors, (17), 6 states have internal predecessors, (17), 3 states have call successors, (3), 2 states have call predecessors, (3), 2 states have return successors, (4), 3 states have call predecessors, (4), 3 states have call successors, (4) [2024-11-17 08:11:13,425 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 32 transitions. [2024-11-17 08:11:13,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 32 transitions. Stem has 24 letters. Loop has 8 letters. [2024-11-17 08:11:13,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:13,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 32 transitions. Stem has 32 letters. Loop has 8 letters. [2024-11-17 08:11:13,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:13,426 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 32 transitions. Stem has 24 letters. Loop has 16 letters. [2024-11-17 08:11:13,426 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:13,426 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 162 states and 188 transitions. [2024-11-17 08:11:13,428 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 8 [2024-11-17 08:11:13,429 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 162 states to 107 states and 122 transitions. [2024-11-17 08:11:13,429 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 63 [2024-11-17 08:11:13,429 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 65 [2024-11-17 08:11:13,429 INFO L73 IsDeterministic]: Start isDeterministic. Operand 107 states and 122 transitions. [2024-11-17 08:11:13,429 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-17 08:11:13,429 INFO L218 hiAutomatonCegarLoop]: Abstraction has 107 states and 122 transitions. [2024-11-17 08:11:13,430 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 107 states and 122 transitions. [2024-11-17 08:11:13,432 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 107 to 36. [2024-11-17 08:11:13,432 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 36 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 27 states have internal predecessors, (32), 4 states have call successors, (4), 4 states have call predecessors, (4), 5 states have return successors, (6), 4 states have call predecessors, (6), 4 states have call successors, (6) [2024-11-17 08:11:13,432 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 36 states to 36 states and 42 transitions. [2024-11-17 08:11:13,432 INFO L240 hiAutomatonCegarLoop]: Abstraction has 36 states and 42 transitions. [2024-11-17 08:11:13,432 INFO L425 stractBuchiCegarLoop]: Abstraction has 36 states and 42 transitions. [2024-11-17 08:11:13,432 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-17 08:11:13,432 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 36 states and 42 transitions. [2024-11-17 08:11:13,432 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 8 [2024-11-17 08:11:13,432 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-17 08:11:13,433 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-17 08:11:13,433 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-17 08:11:13,433 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-17 08:11:13,433 INFO L745 eck$LassoCheckResult]: Stem: 2515#ULTIMATE.startENTRY assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 2516#ULTIMATE.init_returnLabel#1 assume true;assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_#t~nondet6#1, main_#t~malloc7#1.base, main_#t~malloc7#1.offset, main_#t~nondet8#1, main_#t~ret9#1, main_~op~0#1.base, main_~op~0#1.offset, main_~i~0#1;havoc main_#t~nondet6#1;main_~i~0#1 := main_#t~nondet6#1;havoc main_#t~nondet6#1; 2522#L20 assume true; 2534#L20-1 [2024-11-17 08:11:13,433 INFO L747 eck$LassoCheckResult]: Loop: 2534#L20-1 assume !!(main_~i~0#1 > 0);call main_#t~malloc7#1.base, main_#t~malloc7#1.offset := #Ultimate.allocOnHeap(4);main_~op~0#1.base, main_~op~0#1.offset := main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~malloc7#1.base, main_#t~malloc7#1.offset;havoc main_#t~nondet8#1;call write~int#0(main_#t~nondet8#1, main_~op~0#1.base, main_~op~0#1.offset, 4);havoc main_#t~nondet8#1; 2511#L23-1 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 2519#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 2529#L9-1 assume !(#t~mem1 < 0);havoc #t~mem1; 2527#L14 call #t~mem3 := read~int#0(~p.base, ~p.offset, 4);#t~post4 := #t~mem3;call write~int#0(#t~post4 - 1, ~p.base, ~p.offset, 4);havoc #t~mem3;havoc #t~post4; 2510#L15-2 call #t~ret5 := rec(~p.base, ~p.offset);< 2512#recENTRY ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 2523#L9-1 assume #t~mem1 < 0;havoc #t~mem1;call #t~mem2 := read~int#0(~p.base, ~p.offset, 4);~pv~0 := #t~mem2;havoc #t~mem2;call ULTIMATE.dealloc(~p.base, ~p.offset);#res := ~pv~0; 2524#recFINAL assume true; 2538#recEXIT >#22#return; 2543#L15-1 #res := #t~ret5;havoc #t~ret5; 2541#recFINAL assume true; 2539#recEXIT >#24#return; 2530#L23 main_~i~0#1 := main_~i~0#1 + main_#t~ret9#1;havoc main_~op~0#1.base, main_~op~0#1.offset;havoc main_#t~ret9#1; 2532#L20 assume true; 2534#L20-1 [2024-11-17 08:11:13,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:13,433 INFO L85 PathProgramCache]: Analyzing trace with hash 48624, now seen corresponding path program 1 times [2024-11-17 08:11:13,433 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:13,433 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1947661181] [2024-11-17 08:11:13,433 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:13,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:13,435 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,435 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:13,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,436 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:13,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:13,437 INFO L85 PathProgramCache]: Analyzing trace with hash -824108687, now seen corresponding path program 1 times [2024-11-17 08:11:13,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:13,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1823440071] [2024-11-17 08:11:13,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:13,437 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:13,446 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,446 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:13,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,451 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:13,452 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:13,452 INFO L85 PathProgramCache]: Analyzing trace with hash 383573922, now seen corresponding path program 6 times [2024-11-17 08:11:13,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-17 08:11:13,452 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1264931711] [2024-11-17 08:11:13,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-17 08:11:13,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-17 08:11:13,460 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,460 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-17 08:11:13,463 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-17 08:11:13,465 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-17 08:11:13,809 INFO L204 LassoAnalysis]: Preferences: [2024-11-17 08:11:13,809 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-17 08:11:13,809 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-17 08:11:13,809 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-17 08:11:13,809 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-17 08:11:13,809 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:13,809 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-17 08:11:13,809 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-17 08:11:13,809 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration6_Lasso [2024-11-17 08:11:13,809 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-17 08:11:13,809 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-17 08:11:13,812 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,814 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,815 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,816 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,822 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,824 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,826 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,828 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,829 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,847 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-17 08:11:13,919 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-17 08:11:13,919 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-17 08:11:13,919 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:13,919 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:13,920 INFO L229 MonitoredProcess]: Starting monitored process 41 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:13,922 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Waiting until timeout for monitored process [2024-11-17 08:11:13,922 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:13,932 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:13,932 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:13,932 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:13,932 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:13,933 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:13,933 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:13,933 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:13,934 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:13,945 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (41)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:13,945 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:13,945 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:13,947 INFO L229 MonitoredProcess]: Starting monitored process 42 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:13,947 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Waiting until timeout for monitored process [2024-11-17 08:11:13,948 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:13,958 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:13,958 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:13,958 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:13,959 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:13,959 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:13,959 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:13,959 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:13,960 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:13,970 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (42)] Ended with exit code 0 [2024-11-17 08:11:13,970 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:13,971 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:13,972 INFO L229 MonitoredProcess]: Starting monitored process 43 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:13,972 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Waiting until timeout for monitored process [2024-11-17 08:11:13,973 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:13,983 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:13,983 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:13,983 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:13,983 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:13,983 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:13,984 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:13,984 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:13,985 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-17 08:11:13,994 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (43)] Ended with exit code 0 [2024-11-17 08:11:13,994 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:13,994 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:13,995 INFO L229 MonitoredProcess]: Starting monitored process 44 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:13,996 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Waiting until timeout for monitored process [2024-11-17 08:11:13,998 INFO L120 nArgumentSynthesizer]: Termination Analysis Settings: Termination analysis: LINEAR_WITH_GUESSESNumber of strict supporting invariants: 0Number of non-strict supporting invariants: 1Consider only non-deceasing supporting invariants: trueSimplify termination arguments: trueSimplify supporting invariants: trueOverapproximate stem: false [2024-11-17 08:11:14,007 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-17 08:11:14,008 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-17 08:11:14,008 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-17 08:11:14,008 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-17 08:11:14,008 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-17 08:11:14,008 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-17 08:11:14,008 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-17 08:11:14,010 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-17 08:11:14,011 INFO L443 ModelExtractionUtils]: Simplification made 2 calls to the SMT solver. [2024-11-17 08:11:14,011 INFO L444 ModelExtractionUtils]: 1 out of 3 variables were initially zero. Simplification set additionally 0 variables to zero. [2024-11-17 08:11:14,011 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-17 08:11:14,011 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-17 08:11:14,012 INFO L229 MonitoredProcess]: Starting monitored process 45 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) [2024-11-17 08:11:14,013 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Waiting until timeout for monitored process [2024-11-17 08:11:14,013 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-17 08:11:14,013 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-17 08:11:14,013 INFO L474 LassoAnalysis]: Proved termination. [2024-11-17 08:11:14,013 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(ULTIMATE.start_main_~i~0#1) = 1*ULTIMATE.start_main_~i~0#1 Supporting invariants [] [2024-11-17 08:11:14,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (44)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:14,023 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-17 08:11:14,030 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-17 08:11:14,032 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:14,032 INFO L255 TraceCheckSpWp]: Trace formula consists of 7 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-17 08:11:14,032 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:14,049 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-17 08:11:14,050 INFO L255 TraceCheckSpWp]: Trace formula consists of 151 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-17 08:11:14,051 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-17 08:11:14,080 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 17 treesize of output 9 [2024-11-17 08:11:14,125 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-17 08:11:14,125 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 8 loop predicates [2024-11-17 08:11:14,125 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 36 states and 42 transitions. cyclomatic complexity: 8 Second operand has 9 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:14,174 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 36 states and 42 transitions. cyclomatic complexity: 8. Second operand has 9 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) Result 80 states and 95 transitions. Complement of second has 24 states. [2024-11-17 08:11:14,175 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 9 states 1 stem states 7 non-accepting loop states 1 accepting loop states [2024-11-17 08:11:14,175 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 9 states, 8 states have (on average 1.625) internal successors, (13), 7 states have internal predecessors, (13), 2 states have call successors, (2), 1 states have call predecessors, (2), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2024-11-17 08:11:14,176 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 9 states to 9 states and 17 transitions. [2024-11-17 08:11:14,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 17 transitions. Stem has 3 letters. Loop has 15 letters. [2024-11-17 08:11:14,176 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:14,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 17 transitions. Stem has 18 letters. Loop has 15 letters. [2024-11-17 08:11:14,176 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:14,176 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 9 states and 17 transitions. Stem has 3 letters. Loop has 30 letters. [2024-11-17 08:11:14,177 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-17 08:11:14,177 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 80 states and 95 transitions. [2024-11-17 08:11:14,177 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-17 08:11:14,177 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 80 states to 0 states and 0 transitions. [2024-11-17 08:11:14,177 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-17 08:11:14,177 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-17 08:11:14,178 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-17 08:11:14,178 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-17 08:11:14,178 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:11:14,178 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:11:14,178 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-17 08:11:14,178 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-17 08:11:14,178 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-17 08:11:14,178 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-17 08:11:14,178 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-17 08:11:14,182 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 17.11 08:11:14 BoogieIcfgContainer [2024-11-17 08:11:14,183 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-17 08:11:14,183 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-17 08:11:14,183 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-17 08:11:14,183 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-17 08:11:14,183 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.icfgbuilder CFG 17.11 08:11:04" (3/4) ... [2024-11-17 08:11:14,185 INFO L146 WitnessPrinter]: No result that supports witness generation found [2024-11-17 08:11:14,185 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-17 08:11:14,186 INFO L158 Benchmark]: Toolchain (without parser) took 10470.97ms. Allocated memory was 184.5MB in the beginning and 283.1MB in the end (delta: 98.6MB). Free memory was 113.4MB in the beginning and 211.4MB in the end (delta: -98.0MB). Peak memory consumption was 2.0MB. Max. memory is 16.1GB. [2024-11-17 08:11:14,186 INFO L158 Benchmark]: CDTParser took 0.10ms. Allocated memory is still 184.5MB. Free memory is still 145.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:11:14,186 INFO L158 Benchmark]: CACSL2BoogieTranslator took 185.85ms. Allocated memory is still 184.5MB. Free memory was 113.2MB in the beginning and 101.5MB in the end (delta: 11.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. [2024-11-17 08:11:14,186 INFO L158 Benchmark]: Boogie Procedure Inliner took 25.35ms. Allocated memory is still 184.5MB. Free memory was 101.5MB in the beginning and 100.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:11:14,186 INFO L158 Benchmark]: Boogie Preprocessor took 30.45ms. Allocated memory is still 184.5MB. Free memory was 100.1MB in the beginning and 98.5MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-17 08:11:14,186 INFO L158 Benchmark]: IcfgBuilder took 237.94ms. Allocated memory is still 184.5MB. Free memory was 98.3MB in the beginning and 144.6MB in the end (delta: -46.3MB). Peak memory consumption was 4.9MB. Max. memory is 16.1GB. [2024-11-17 08:11:14,187 INFO L158 Benchmark]: BuchiAutomizer took 9984.77ms. Allocated memory was 184.5MB in the beginning and 283.1MB in the end (delta: 98.6MB). Free memory was 144.6MB in the beginning and 212.4MB in the end (delta: -67.8MB). Peak memory consumption was 32.8MB. Max. memory is 16.1GB. [2024-11-17 08:11:14,187 INFO L158 Benchmark]: Witness Printer took 2.55ms. Allocated memory is still 283.1MB. Free memory is still 211.4MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-17 08:11:14,188 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.10ms. Allocated memory is still 184.5MB. Free memory is still 145.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 185.85ms. Allocated memory is still 184.5MB. Free memory was 113.2MB in the beginning and 101.5MB in the end (delta: 11.7MB). Peak memory consumption was 12.6MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 25.35ms. Allocated memory is still 184.5MB. Free memory was 101.5MB in the beginning and 100.1MB in the end (delta: 1.3MB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 30.45ms. Allocated memory is still 184.5MB. Free memory was 100.1MB in the beginning and 98.5MB in the end (delta: 1.6MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * IcfgBuilder took 237.94ms. Allocated memory is still 184.5MB. Free memory was 98.3MB in the beginning and 144.6MB in the end (delta: -46.3MB). Peak memory consumption was 4.9MB. Max. memory is 16.1GB. * BuchiAutomizer took 9984.77ms. Allocated memory was 184.5MB in the beginning and 283.1MB in the end (delta: 98.6MB). Free memory was 144.6MB in the beginning and 212.4MB in the end (delta: -67.8MB). Peak memory consumption was 32.8MB. Max. memory is 16.1GB. * Witness Printer took 2.55ms. Allocated memory is still 283.1MB. Free memory is still 211.4MB. There was no memory consumed. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#0 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array UnaryExpression[OLD,IdentifierExpression[#memory_int#0,GLOBAL]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[UnaryExpression[OLD,IdentifierExpression[#memory_int#0,GLOBAL]],[IdentifierExpression[#in~p!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret9 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #memory_int#0 - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#0,GLOBAL] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#0,GLOBAL],[IdentifierExpression[#in~p!base,]]] - GenericResult: Unfinished Backtranslation Unfinished Backtranslation: Unknown variable: #t~ret9 * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: Constructed decomposition of program Your program was decomposed into 6 terminating modules (0 trivial, 4 deterministic, 2 nondeterministic). One deterministic module has affine ranking function i and consists of 9 locations. One deterministic module has affine ranking function null and consists of 9 locations. One deterministic module has affine ranking function null and consists of 8 locations. One deterministic module has affine ranking function i and consists of 9 locations. One nondeterministic module has affine ranking function null and consists of 7 locations. One nondeterministic module has affine ranking function null and consists of 8 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 9.9s and 7 iterations. TraceHistogramMax:3. Analysis of lassos took 7.0s. Construction of modules took 0.3s. Büchi inclusion checks took 2.4s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 5. Automata minimization 0.0s AutomataMinimizationTime, 5 MinimizatonAttempts, 130 StatesRemovedByMinimization, 5 NontrivialMinimizations. Non-live state removal took 0.0s Buchi closure took 0.0s. Biggest automaton had -1 states and ocurred in iteration -1. Nontrivial modules had stage [4, 0, 2, 0, 0]. InterpolantCoveringCapabilityFinite: 0/0 InterpolantCoveringCapabilityBuchi: 4/4 HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 206 SdHoareTripleChecker+Valid, 0.4s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 197 mSDsluCounter, 352 SdHoareTripleChecker+Invalid, 0.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 203 mSDsCounter, 121 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 469 IncrementalHoareTripleChecker+Invalid, 590 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 121 mSolverCounterUnsat, 149 mSDtfsCounter, 469 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT0 conc0 concLT0 SILN0 SILU0 SILI0 SILT0 lasso6 LassoPreprocessingBenchmarks: Lassos: inital132 mio100 ax100 hnf100 lsp132 ukn49 mio100 lsp42 div100 bol100 ite100 ukn100 eq162 hnf94 smp100 dnf157 smp91 tf100 neg100 sie113 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 42ms VariablesStem: 5 VariablesLoop: 4 DisjunctsStem: 6 DisjunctsLoop: 2 SupportingInvariants: 4 MotzkinApplications: 36 LassoTerminationAnalysisBenchmarks: LassoNonterminationAnalysisSatFixpoint: 0 LassoNonterminationAnalysisSatUnbounded: 0 LassoNonterminationAnalysisUnsat: 0 LassoNonterminationAnalysisUnknown: 0 LassoNonterminationAnalysisTime: 0.0s InitialAbstractionConstructionTime: 0.0s - TerminationAnalysisResult: Termination proven Buchi Automizer proved that your program is terminating RESULT: Ultimate proved your program to be correct! [2024-11-17 08:11:14,200 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Forceful destruction successful, exit code 0 [2024-11-17 08:11:14,407 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Forceful destruction successful, exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE