./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 c7c6ca5d 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-?-c7c6ca5-m [2024-11-09 15:28:29,152 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-09 15:28:29,218 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-64bit-Automizer_Default.epf [2024-11-09 15:28:29,225 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-09 15:28:29,225 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-09 15:28:29,254 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-09 15:28:29,256 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-09 15:28:29,257 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-09 15:28:29,257 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-09 15:28:29,258 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-09 15:28:29,260 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-09 15:28:29,260 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-09 15:28:29,260 INFO L153 SettingsManager]: * Use SBE=true [2024-11-09 15:28:29,261 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-09 15:28:29,261 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-09 15:28:29,263 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-09 15:28:29,263 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-09 15:28:29,263 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-09 15:28:29,263 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-09 15:28:29,264 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-09 15:28:29,264 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-09 15:28:29,267 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-09 15:28:29,267 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-09 15:28:29,267 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-09 15:28:29,268 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-09 15:28:29,268 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-09 15:28:29,268 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-09 15:28:29,268 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-09 15:28:29,269 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-09 15:28:29,269 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-09 15:28:29,269 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-09 15:28:29,269 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-09 15:28:29,269 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-09 15:28:29,270 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-09 15:28:29,270 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-09 15:28:29,271 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-09 15:28:29,271 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-09 15:28:29,522 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-09 15:28:29,546 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-09 15:28:29,548 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-09 15:28:29,549 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-09 15:28:29,550 INFO L274 PluginConnector]: CDTParser initialized [2024-11-09 15:28:29,551 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-09 15:28:31,020 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-09 15:28:31,211 INFO L384 CDTParser]: Found 1 translation units. [2024-11-09 15:28:31,212 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/termination-recursive-malloc/rec_malloc_ex3.i [2024-11-09 15:28:31,221 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bcc0c6089/cb68294845ec4d58a67253d750659f45/FLAGeb82a471d [2024-11-09 15:28:31,578 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/bcc0c6089/cb68294845ec4d58a67253d750659f45 [2024-11-09 15:28:31,580 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-09 15:28:31,581 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-09 15:28:31,583 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-09 15:28:31,583 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-09 15:28:31,588 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-09 15:28:31,588 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,589 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@5ca3c2d2 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31, skipping insertion in model container [2024-11-09 15:28:31,589 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,604 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-09 15:28:31,782 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:28:31,796 INFO L200 MainTranslator]: Completed pre-run [2024-11-09 15:28:31,810 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-09 15:28:31,824 INFO L204 MainTranslator]: Completed translation [2024-11-09 15:28:31,824 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31 WrapperNode [2024-11-09 15:28:31,824 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-09 15:28:31,825 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-09 15:28:31,825 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-09 15:28:31,825 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-09 15:28:31,832 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,838 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,851 INFO L138 Inliner]: procedures = 11, calls = 11, calls flagged for inlining = 2, calls inlined = 2, statements flattened = 21 [2024-11-09 15:28:31,851 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-09 15:28:31,852 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-09 15:28:31,852 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-09 15:28:31,852 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-09 15:28:31,861 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,862 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,863 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,875 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-09 15:28:31,876 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,876 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,879 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,882 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,883 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,884 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,885 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-09 15:28:31,886 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-09 15:28:31,886 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-09 15:28:31,886 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-09 15:28:31,887 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (1/1) ... [2024-11-09 15:28:31,893 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:31,904 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:31,918 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-09 15:28:31,922 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-09 15:28:31,967 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-09 15:28:31,967 INFO L130 BoogieDeclarations]: Found specification of procedure rec [2024-11-09 15:28:31,967 INFO L138 BoogieDeclarations]: Found implementation of procedure rec [2024-11-09 15:28:31,967 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnHeap [2024-11-09 15:28:31,967 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-09 15:28:31,968 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-09 15:28:31,968 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-09 15:28:31,968 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-09 15:28:32,041 INFO L238 CfgBuilder]: Building ICFG [2024-11-09 15:28:32,053 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-09 15:28:32,148 INFO L? ?]: Removed 6 outVars from TransFormulas that were not future-live. [2024-11-09 15:28:32,148 INFO L287 CfgBuilder]: Performing block encoding [2024-11-09 15:28:32,157 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-09 15:28:32,157 INFO L316 CfgBuilder]: Removed 1 assume(true) statements. [2024-11-09 15:28:32,158 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:28:32 BoogieIcfgContainer [2024-11-09 15:28:32,158 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-09 15:28:32,159 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-09 15:28:32,159 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-09 15:28:32,163 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-09 15:28:32,163 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:28:32,164 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 09.11 03:28:31" (1/3) ... [2024-11-09 15:28:32,164 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6e4ee1ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:28:32, skipping insertion in model container [2024-11-09 15:28:32,165 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:28:32,165 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.11 03:28:31" (2/3) ... [2024-11-09 15:28:32,165 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@6e4ee1ff and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 09.11 03:28:32, skipping insertion in model container [2024-11-09 15:28:32,165 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-09 15:28:32,166 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:28:32" (3/3) ... [2024-11-09 15:28:32,167 INFO L332 chiAutomizerObserver]: Analyzing ICFG rec_malloc_ex3.i [2024-11-09 15:28:32,223 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-09 15:28:32,223 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-09 15:28:32,223 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-09 15:28:32,224 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-09 15:28:32,224 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-09 15:28:32,224 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-09 15:28:32,224 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-09 15:28:32,224 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-09 15:28:32,229 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 10 states have (on average 1.3) internal successors, (13), 10 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-09 15:28:32,247 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 6 [2024-11-09 15:28:32,247 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:32,248 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:32,252 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2024-11-09 15:28:32,252 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:32,252 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-09 15:28:32,252 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 14 states, 10 states have (on average 1.3) internal successors, (13), 10 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-09 15:28:32,253 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 6 [2024-11-09 15:28:32,253 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:32,253 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:32,254 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1] [2024-11-09 15:28:32,254 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:32,259 INFO L745 eck$LassoCheckResult]: Stem: 9#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 4#L-1true 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; 8#L20-2true [2024-11-09 15:28:32,260 INFO L747 eck$LassoCheckResult]: Loop: 8#L20-2true 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; 10#L23true call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 11#$Ultimate##0true ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 7#L9true 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; 13#recFINALtrue assume true; 12#recEXITtrue >#30#return; 5#L23-1true 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; 8#L20-2true [2024-11-09 15:28:32,264 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:32,264 INFO L85 PathProgramCache]: Analyzing trace with hash 1219, now seen corresponding path program 1 times [2024-11-09 15:28:32,274 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:32,274 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2107399383] [2024-11-09 15:28:32,274 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:32,275 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:32,348 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,348 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:32,355 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,375 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:32,378 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:32,378 INFO L85 PathProgramCache]: Analyzing trace with hash -2039113776, now seen corresponding path program 1 times [2024-11-09 15:28:32,378 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:32,379 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [874398051] [2024-11-09 15:28:32,379 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:32,379 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:32,420 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,420 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:32,436 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,440 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:32,442 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:32,442 INFO L85 PathProgramCache]: Analyzing trace with hash -1009969970, now seen corresponding path program 1 times [2024-11-09 15:28:32,443 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:32,443 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1040440610] [2024-11-09 15:28:32,443 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:32,443 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:32,466 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,466 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:32,479 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:32,483 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:33,012 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:33,013 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:33,014 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:33,014 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:33,014 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:33,014 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,014 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:33,014 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:33,015 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration1_Lasso [2024-11-09 15:28:33,015 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:33,015 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:33,032 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,041 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,044 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,047 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,050 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,055 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,102 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,109 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,111 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:33,193 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:33,197 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:33,198 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,199 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,201 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-09 15:28:33,203 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-09 15:28:33,204 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-09 15:28:33,217 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,217 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,218 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,218 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,218 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,220 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,221 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,228 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,242 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-09 15:28:33,244 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,244 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,247 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-09 15:28:33,248 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-09 15:28:33,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-09 15:28:33,263 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,264 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,264 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,264 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,264 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,265 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,265 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,266 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,277 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (3)] Ended with exit code 0 [2024-11-09 15:28:33,278 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,278 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,279 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-09 15:28:33,280 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-09 15:28:33,281 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-09 15:28:33,290 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,291 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,291 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,291 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,291 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,292 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,292 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,295 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,310 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (4)] Forceful destruction successful, exit code 0 [2024-11-09 15:28:33,311 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,311 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,313 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-09 15:28:33,315 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-09 15:28:33,316 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-09 15:28:33,329 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,330 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,330 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,330 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,330 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,332 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,333 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,336 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,351 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (5)] Ended with exit code 0 [2024-11-09 15:28:33,351 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,351 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,353 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-09 15:28:33,355 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-09 15:28:33,356 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-09 15:28:33,368 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,369 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,369 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,369 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,369 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,370 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,371 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,374 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,389 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-09 15:28:33,389 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,389 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,391 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-09 15:28:33,393 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-09 15:28:33,394 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-09 15:28:33,406 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,406 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,406 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-09 15:28:33,406 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,414 INFO L401 nArgumentSynthesizer]: We have 16 Motzkin's Theorem applications. [2024-11-09 15:28:33,414 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-09 15:28:33,426 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:33,442 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-09 15:28:33,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,442 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,444 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-09 15:28:33,446 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-09 15:28:33,447 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-09 15:28:33,459 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:33,460 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:33,460 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:33,460 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:33,460 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:33,461 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:33,461 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:33,467 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:33,474 INFO L443 ModelExtractionUtils]: Simplification made 3 calls to the SMT solver. [2024-11-09 15:28:33,474 INFO L444 ModelExtractionUtils]: 0 out of 3 variables were initially zero. Simplification set additionally 1 variables to zero. [2024-11-09 15:28:33,476 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:33,476 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:33,484 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-09 15:28:33,494 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:33,494 INFO L438 nArgumentSynthesizer]: Removed 0 redundant supporting invariants from a total of 0. [2024-11-09 15:28:33,494 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:33,495 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-09 15:28:33,499 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-09 15:28:33,510 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-09 15:28:33,512 INFO L156 tatePredicateManager]: 0 out of 0 supporting invariants were superfluous and have been removed [2024-11-09 15:28:33,537 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:33,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:33,547 INFO L255 TraceCheckSpWp]: Trace formula consists of 6 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-09 15:28:33,548 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:33,588 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:33,589 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 15:28:33,590 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:33,678 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-09 15:28:33,726 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-09 15:28:33,781 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-09 15:28:33,782 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (9)] Ended with exit code 0 [2024-11-09 15:28:33,783 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand has 14 states, 10 states have (on average 1.3) internal successors, (13), 10 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) Second operand has 7 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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-09 15:28:33,912 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand has 14 states, 10 states have (on average 1.3) internal successors, (13), 10 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). Second operand has 7 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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 58 states and 72 transitions. Complement of second has 20 states. [2024-11-09 15:28:33,915 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 1 stem states 5 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:33,919 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 6 states have (on average 1.1666666666666667) internal successors, (7), 5 states have internal predecessors, (7), 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-09 15:28:33,920 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 19 transitions. [2024-11-09 15:28:33,921 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 19 transitions. Stem has 2 letters. Loop has 7 letters. [2024-11-09 15:28:33,922 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:33,922 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 19 transitions. Stem has 9 letters. Loop has 7 letters. [2024-11-09 15:28:33,923 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:33,923 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 19 transitions. Stem has 2 letters. Loop has 14 letters. [2024-11-09 15:28:33,923 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:33,924 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 58 states and 72 transitions. [2024-11-09 15:28:33,928 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 9 [2024-11-09 15:28:33,938 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 58 states to 35 states and 42 transitions. [2024-11-09 15:28:33,939 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 27 [2024-11-09 15:28:33,940 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 28 [2024-11-09 15:28:33,940 INFO L73 IsDeterministic]: Start isDeterministic. Operand 35 states and 42 transitions. [2024-11-09 15:28:33,940 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:28:33,940 INFO L218 hiAutomatonCegarLoop]: Abstraction has 35 states and 42 transitions. [2024-11-09 15:28:33,954 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states and 42 transitions. [2024-11-09 15:28:33,962 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 32. [2024-11-09 15:28:33,962 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 22 states have internal predecessors, (26), 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-09 15:28:33,963 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2024-11-09 15:28:33,964 INFO L240 hiAutomatonCegarLoop]: Abstraction has 32 states and 38 transitions. [2024-11-09 15:28:33,964 INFO L425 stractBuchiCegarLoop]: Abstraction has 32 states and 38 transitions. [2024-11-09 15:28:33,964 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-09 15:28:33,964 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 32 states and 38 transitions. [2024-11-09 15:28:33,965 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 9 [2024-11-09 15:28:33,965 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:33,966 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:33,966 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:33,966 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:28:33,966 INFO L745 eck$LassoCheckResult]: Stem: 158#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 159#L-1 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; 168#L20-2 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; 146#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 156#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 145#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 147#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 160#$Ultimate##0 [2024-11-09 15:28:33,966 INFO L747 eck$LassoCheckResult]: Loop: 160#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 162#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 161#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 160#$Ultimate##0 [2024-11-09 15:28:33,967 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:33,967 INFO L85 PathProgramCache]: Analyzing trace with hash 557607690, now seen corresponding path program 1 times [2024-11-09 15:28:33,968 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:33,968 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2126805730] [2024-11-09 15:28:33,968 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:33,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:33,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:33,988 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:33,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:34,002 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:34,003 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:34,003 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 1 times [2024-11-09 15:28:34,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:34,003 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [777238225] [2024-11-09 15:28:34,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:34,004 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:34,019 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:34,020 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:34,030 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:34,034 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:34,036 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:34,036 INFO L85 PathProgramCache]: Analyzing trace with hash -1242807987, now seen corresponding path program 2 times [2024-11-09 15:28:34,037 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:34,037 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [388576726] [2024-11-09 15:28:34,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:34,037 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:34,073 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:34,073 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:34,096 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:34,105 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:34,809 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:34,810 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:34,810 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:34,810 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:34,810 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:34,810 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:34,810 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:34,810 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:34,810 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration2_Lasso [2024-11-09 15:28:34,810 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:34,810 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:34,813 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:34,820 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:34,822 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:34,825 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,128 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,131 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,133 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,135 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,139 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,141 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,143 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,145 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,147 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,149 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,151 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,153 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,155 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,157 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:35,395 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:35,395 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:35,395 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,396 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,397 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-09 15:28:35,401 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-09 15:28:35,402 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-09 15:28:35,413 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,413 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:35,414 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:35,414 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,414 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,414 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:35,414 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:35,415 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:35,425 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (10)] Ended with exit code 0 [2024-11-09 15:28:35,425 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,425 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,426 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-09 15:28:35,427 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-09 15:28:35,428 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-09 15:28:35,437 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,438 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:35,438 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:35,438 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,438 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,438 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:35,438 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:35,439 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:35,449 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-09 15:28:35,450 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,450 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,451 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-09 15:28:35,452 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-09 15:28:35,452 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-09 15:28:35,462 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,462 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:35,462 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,462 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,465 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:35,465 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:35,469 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:35,483 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-09 15:28:35,483 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,483 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,485 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-09 15:28:35,486 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-09 15:28:35,487 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-09 15:28:35,499 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,500 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:35,500 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,500 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,503 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:35,503 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:35,506 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:35,521 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-09 15:28:35,522 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,522 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,524 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-09 15:28:35,525 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-09 15:28:35,526 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-09 15:28:35,539 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,539 INFO L203 nArgumentSynthesizer]: 2 stem disjuncts [2024-11-09 15:28:35,539 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,540 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,543 INFO L401 nArgumentSynthesizer]: We have 8 Motzkin's Theorem applications. [2024-11-09 15:28:35,543 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:35,550 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:35,565 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-09 15:28:35,565 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,565 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,567 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-09 15:28:35,568 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-09 15:28:35,569 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-09 15:28:35,582 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:35,582 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:35,582 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:35,582 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:35,588 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:35,588 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:35,598 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:35,623 INFO L443 ModelExtractionUtils]: Simplification made 12 calls to the SMT solver. [2024-11-09 15:28:35,624 INFO L444 ModelExtractionUtils]: 2 out of 16 variables were initially zero. Simplification set additionally 11 variables to zero. [2024-11-09 15:28:35,624 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:35,624 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:35,626 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-09 15:28:35,628 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-09 15:28:35,629 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:35,643 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-09 15:28:35,643 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:35,643 INFO L476 LassoAnalysis]: Termination argument consisting of: Ranking function f(v_rep(select (select #memory_int#0 rec_#in~p.base) 0)_1) = 2*v_rep(select (select #memory_int#0 rec_#in~p.base) 0)_1 + 1 Supporting invariants [] [2024-11-09 15:28:35,658 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (15)] Ended with exit code 0 [2024-11-09 15:28:35,671 INFO L156 tatePredicateManager]: 1 out of 2 supporting invariants were superfluous and have been removed [2024-11-09 15:28:35,676 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#0 [2024-11-09 15:28:35,677 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#0,GLOBAL] [2024-11-09 15:28:35,677 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#0,GLOBAL],[IdentifierExpression[#in~p!base,]]] [2024-11-09 15:28:35,698 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:35,721 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:35,722 INFO L255 TraceCheckSpWp]: Trace formula consists of 122 conjuncts, 14 conjuncts are in the unsatisfiable core [2024-11-09 15:28:35,723 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:35,783 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:35,783 INFO L255 TraceCheckSpWp]: Trace formula consists of 61 conjuncts, 21 conjuncts are in the unsatisfiable core [2024-11-09 15:28:35,784 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:35,820 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-09 15:28:35,840 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-09 15:28:35,840 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.4 stem predicates 3 loop predicates [2024-11-09 15:28:35,840 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 32 states and 38 transitions. cyclomatic complexity: 10 Second operand has 7 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 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-09 15:28:35,975 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 32 states and 38 transitions. cyclomatic complexity: 10. Second operand has 7 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 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 47 states and 56 transitions. Complement of second has 19 states. [2024-11-09 15:28:35,976 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 4 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:35,977 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 7 states, 5 states have (on average 1.4) internal successors, (7), 5 states have internal predecessors, (7), 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-09 15:28:35,977 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 16 transitions. [2024-11-09 15:28:35,977 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 7 letters. Loop has 3 letters. [2024-11-09 15:28:35,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:35,978 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 10 letters. Loop has 3 letters. [2024-11-09 15:28:35,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:35,978 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 16 transitions. Stem has 7 letters. Loop has 6 letters. [2024-11-09 15:28:35,978 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:35,978 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 47 states and 56 transitions. [2024-11-09 15:28:35,980 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 6 [2024-11-09 15:28:35,982 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 47 states to 41 states and 50 transitions. [2024-11-09 15:28:35,982 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 27 [2024-11-09 15:28:35,982 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 29 [2024-11-09 15:28:35,982 INFO L73 IsDeterministic]: Start isDeterministic. Operand 41 states and 50 transitions. [2024-11-09 15:28:35,982 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:28:35,982 INFO L218 hiAutomatonCegarLoop]: Abstraction has 41 states and 50 transitions. [2024-11-09 15:28:35,983 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states and 50 transitions. [2024-11-09 15:28:35,985 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 39. [2024-11-09 15:28:35,986 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 39 states, 27 states have (on average 1.1851851851851851) internal successors, (32), 28 states have internal predecessors, (32), 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-09 15:28:35,987 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 39 states to 39 states and 46 transitions. [2024-11-09 15:28:35,987 INFO L240 hiAutomatonCegarLoop]: Abstraction has 39 states and 46 transitions. [2024-11-09 15:28:35,987 INFO L425 stractBuchiCegarLoop]: Abstraction has 39 states and 46 transitions. [2024-11-09 15:28:35,987 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-09 15:28:35,987 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 39 states and 46 transitions. [2024-11-09 15:28:35,988 INFO L131 ngComponentsAnalysis]: Automaton has 2 accepting balls. 6 [2024-11-09 15:28:35,988 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:35,988 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:35,989 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:35,989 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:35,989 INFO L745 eck$LassoCheckResult]: Stem: 324#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 325#L-1 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; 336#L20-2 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; 320#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 346#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 345#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 316#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 328#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 329#L9 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; 350#recFINAL assume true; 331#recEXIT >#28#return; 332#L15-1 #res := #t~ret5;havoc #t~ret5; 344#recFINAL assume true; 340#recEXIT >#30#return; 335#L23-1 [2024-11-09 15:28:35,989 INFO L747 eck$LassoCheckResult]: Loop: 335#L23-1 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; 317#L20-2 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; 318#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 326#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 341#L9 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; 343#recFINAL assume true; 348#recEXIT >#30#return; 335#L23-1 [2024-11-09 15:28:35,990 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:35,990 INFO L85 PathProgramCache]: Analyzing trace with hash 1969157627, now seen corresponding path program 1 times [2024-11-09 15:28:35,990 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:35,990 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [564202607] [2024-11-09 15:28:35,990 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:35,991 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:36,005 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,005 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:36,015 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,019 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:36,019 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:36,019 INFO L85 PathProgramCache]: Analyzing trace with hash -523709736, now seen corresponding path program 2 times [2024-11-09 15:28:36,019 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:36,020 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1016609146] [2024-11-09 15:28:36,020 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:36,020 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:36,028 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,029 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:36,035 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,037 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:36,037 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:36,037 INFO L85 PathProgramCache]: Analyzing trace with hash 931270558, now seen corresponding path program 1 times [2024-11-09 15:28:36,038 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:36,038 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [608330233] [2024-11-09 15:28:36,038 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:36,038 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:36,055 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,056 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:36,069 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:36,073 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:36,308 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (16)] Ended with exit code 0 [2024-11-09 15:28:36,822 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:36,822 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:36,822 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:36,822 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:36,822 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:36,822 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:36,822 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:36,822 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:36,822 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration3_Lasso [2024-11-09 15:28:36,822 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:36,822 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:36,823 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:36,942 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:36,944 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:36,946 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:36,948 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:36,949 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:37,098 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:37,098 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:37,099 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:37,099 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:37,100 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-09 15:28:37,101 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-09 15:28:37,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-09 15:28:37,112 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:37,112 INFO L203 nArgumentSynthesizer]: 2 stem disjuncts [2024-11-09 15:28:37,112 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-09 15:28:37,112 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:37,117 INFO L401 nArgumentSynthesizer]: We have 20 Motzkin's Theorem applications. [2024-11-09 15:28:37,117 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-09 15:28:37,129 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:37,143 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-09 15:28:37,144 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:37,144 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:37,145 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-09 15:28:37,146 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-09 15:28:37,147 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-09 15:28:37,157 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:37,157 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:37,157 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:37,157 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:37,159 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:37,159 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:37,162 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:37,176 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-09 15:28:37,176 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:37,176 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:37,177 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-09 15:28:37,178 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-09 15:28:37,179 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-09 15:28:37,188 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:37,189 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:37,189 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:37,189 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:37,190 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:37,190 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:37,193 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:37,203 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (19)] Forceful destruction successful, exit code 0 [2024-11-09 15:28:37,204 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:37,204 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:37,205 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-09 15:28:37,206 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-09 15:28:37,207 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-09 15:28:37,216 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:37,217 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:37,217 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:37,217 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:37,220 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:37,220 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:37,227 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:37,234 INFO L443 ModelExtractionUtils]: Simplification made 5 calls to the SMT solver. [2024-11-09 15:28:37,235 INFO L444 ModelExtractionUtils]: 2 out of 16 variables were initially zero. Simplification set additionally 11 variables to zero. [2024-11-09 15:28:37,235 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:37,235 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:37,236 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-09 15:28:37,237 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-09 15:28:37,237 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:37,248 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-09 15:28:37,248 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:37,248 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-09 15:28:37,258 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (20)] Forceful destruction successful, exit code 0 [2024-11-09 15:28:37,263 INFO L156 tatePredicateManager]: 2 out of 2 supporting invariants were superfluous and have been removed [2024-11-09 15:28:37,264 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret9 [2024-11-09 15:28:37,276 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:37,306 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:37,307 INFO L255 TraceCheckSpWp]: Trace formula consists of 152 conjuncts, 6 conjuncts are in the unsatisfiable core [2024-11-09 15:28:37,308 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:37,453 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (21)] Ended with exit code 0 [2024-11-09 15:28:37,470 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:37,471 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 15:28:37,472 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:37,539 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-09 15:28:37,560 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-09 15:28:37,561 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-09 15:28:37,561 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 39 states and 46 transitions. cyclomatic complexity: 11 Second operand has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-09 15:28:37,653 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 39 states and 46 transitions. cyclomatic complexity: 11. Second operand has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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 130 states and 152 transitions. Complement of second has 21 states. [2024-11-09 15:28:37,654 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-09 15:28:37,655 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 1.8571428571428572) internal successors, (13), 6 states have internal predecessors, (13), 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-09 15:28:37,656 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 26 transitions. [2024-11-09 15:28:37,656 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 26 transitions. Stem has 14 letters. Loop has 7 letters. [2024-11-09 15:28:37,656 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:37,656 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 26 transitions. Stem has 21 letters. Loop has 7 letters. [2024-11-09 15:28:37,657 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:37,657 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 26 transitions. Stem has 14 letters. Loop has 14 letters. [2024-11-09 15:28:37,657 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:37,657 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 130 states and 152 transitions. [2024-11-09 15:28:37,661 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 9 [2024-11-09 15:28:37,664 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 130 states to 90 states and 105 transitions. [2024-11-09 15:28:37,664 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 63 [2024-11-09 15:28:37,665 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 65 [2024-11-09 15:28:37,665 INFO L73 IsDeterministic]: Start isDeterministic. Operand 90 states and 105 transitions. [2024-11-09 15:28:37,665 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:28:37,665 INFO L218 hiAutomatonCegarLoop]: Abstraction has 90 states and 105 transitions. [2024-11-09 15:28:37,665 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 90 states and 105 transitions. [2024-11-09 15:28:37,678 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 90 to 82. [2024-11-09 15:28:37,678 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 56 states have (on average 1.1785714285714286) internal successors, (66), 59 states have internal predecessors, (66), 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-09 15:28:37,680 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 96 transitions. [2024-11-09 15:28:37,680 INFO L240 hiAutomatonCegarLoop]: Abstraction has 82 states and 96 transitions. [2024-11-09 15:28:37,680 INFO L425 stractBuchiCegarLoop]: Abstraction has 82 states and 96 transitions. [2024-11-09 15:28:37,680 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-09 15:28:37,680 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 82 states and 96 transitions. [2024-11-09 15:28:37,685 INFO L131 ngComponentsAnalysis]: Automaton has 3 accepting balls. 9 [2024-11-09 15:28:37,685 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:37,686 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:37,686 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:37,686 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1] [2024-11-09 15:28:37,686 INFO L745 eck$LassoCheckResult]: Stem: 616#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 617#L-1 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; 628#L20-2 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; 634#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 635#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 641#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 639#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 640#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 648#L9 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; 659#recFINAL assume true; 638#recEXIT >#28#return; 637#L15-1 #res := #t~ret5;havoc #t~ret5; 636#recFINAL assume true; 633#recEXIT >#30#return; 632#L23-1 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; 627#L20-2 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; 612#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 613#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 680#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 610#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 618#$Ultimate##0 [2024-11-09 15:28:37,686 INFO L747 eck$LassoCheckResult]: Loop: 618#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 619#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 609#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 618#$Ultimate##0 [2024-11-09 15:28:37,687 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:37,687 INFO L85 PathProgramCache]: Analyzing trace with hash -801242957, now seen corresponding path program 2 times [2024-11-09 15:28:37,687 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:37,687 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [461728958] [2024-11-09 15:28:37,687 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:37,687 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:37,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,728 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:37,757 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,766 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:37,769 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:37,770 INFO L85 PathProgramCache]: Analyzing trace with hash 29942, now seen corresponding path program 2 times [2024-11-09 15:28:37,770 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:37,770 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1497038119] [2024-11-09 15:28:37,770 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:37,770 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:37,776 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,776 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:37,778 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,779 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:37,780 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:37,780 INFO L85 PathProgramCache]: Analyzing trace with hash 1599299332, now seen corresponding path program 3 times [2024-11-09 15:28:37,780 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:37,780 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1755296434] [2024-11-09 15:28:37,780 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:37,780 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:37,800 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,800 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:37,824 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:37,831 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:38,971 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:38,971 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:38,971 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:38,971 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:38,971 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:38,971 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:38,971 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:38,971 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:38,971 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration4_Lasso [2024-11-09 15:28:38,971 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:38,971 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:38,973 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,977 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,978 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,980 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,981 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,983 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:38,986 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,121 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,123 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,127 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,129 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,132 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,134 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,135 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,137 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,139 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,141 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,143 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,146 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:39,328 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:39,329 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:39,329 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,329 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,331 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-09 15:28:39,332 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-09 15:28:39,333 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-09 15:28:39,343 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,343 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,343 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,343 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,343 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,343 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,343 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,344 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,354 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (22)] Forceful destruction successful, exit code 0 [2024-11-09 15:28:39,354 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,355 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,356 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-09 15:28:39,357 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-09 15:28:39,358 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-09 15:28:39,367 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,367 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,367 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,367 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,368 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,368 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,368 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,369 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,379 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-09 15:28:39,379 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,379 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,381 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-09 15:28:39,383 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-09 15:28:39,384 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-09 15:28:39,394 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,394 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,395 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,395 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,395 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,395 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,395 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,396 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,406 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-09 15:28:39,407 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,407 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,408 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-09 15:28:39,409 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-09 15:28:39,409 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-09 15:28:39,419 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,419 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,419 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,419 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,419 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,420 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,420 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,421 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,431 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-09 15:28:39,431 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,432 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,433 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-09 15:28:39,434 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-09 15:28:39,434 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-09 15:28:39,444 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,444 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,444 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,444 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,444 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,444 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,445 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,446 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,460 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-09 15:28:39,460 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,461 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,462 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-09 15:28:39,464 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-09 15:28:39,465 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-09 15:28:39,477 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,477 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:39,477 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,477 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,477 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,478 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:39,478 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:39,479 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,490 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-09 15:28:39,490 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,491 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-09 15:28:39,492 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-09 15:28:39,493 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-09 15:28:39,502 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,502 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,503 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,503 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,505 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:39,505 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,508 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,518 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-09 15:28:39,518 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,518 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,519 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-09 15:28:39,520 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-09 15:28:39,521 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-09 15:28:39,530 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,530 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,531 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,531 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,533 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:39,533 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,536 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,546 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-09 15:28:39,547 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,547 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,548 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-09 15:28:39,550 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-09 15:28:39,550 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-09 15:28:39,560 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,560 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,560 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,560 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,562 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:39,562 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,565 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,576 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-09 15:28:39,576 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,577 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,578 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-09 15:28:39,581 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-09 15:28:39,582 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-09 15:28:39,594 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,594 INFO L203 nArgumentSynthesizer]: 4 stem disjuncts [2024-11-09 15:28:39,594 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,594 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,597 INFO L401 nArgumentSynthesizer]: We have 12 Motzkin's Theorem applications. [2024-11-09 15:28:39,597 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,603 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,614 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-09 15:28:39,614 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,614 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,616 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-09 15:28:39,617 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-09 15:28:39,618 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-09 15:28:39,627 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,628 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,628 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,628 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,631 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:39,631 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,636 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:39,647 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (32)] Ended with exit code 0 [2024-11-09 15:28:39,647 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,647 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,648 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-09 15:28:39,649 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-09 15:28:39,650 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-09 15:28:39,661 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:39,661 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:39,661 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:39,661 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:39,663 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:39,663 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:39,667 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:39,677 INFO L443 ModelExtractionUtils]: Simplification made 7 calls to the SMT solver. [2024-11-09 15:28:39,677 INFO L444 ModelExtractionUtils]: 0 out of 10 variables were initially zero. Simplification set additionally 7 variables to zero. [2024-11-09 15:28:39,678 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:39,678 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:39,680 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-09 15:28:39,681 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-09 15:28:39,681 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:39,699 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-09 15:28:39,699 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:39,699 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-09 15:28:39,710 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-09 15:28:39,713 INFO L156 tatePredicateManager]: 1 out of 1 supporting invariants were superfluous and have been removed [2024-11-09 15:28:39,714 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #memory_int#0 [2024-11-09 15:28:39,715 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array IdentifierExpression[#memory_int#0,GLOBAL] [2024-11-09 15:28:39,715 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Cannot backtranslate array access to array ArrayAccessExpression[IdentifierExpression[#memory_int#0,GLOBAL],[IdentifierExpression[#in~p!base,]]] [2024-11-09 15:28:39,726 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:39,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:39,766 INFO L255 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 15:28:39,768 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:39,891 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:39,892 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 15:28:39,892 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:39,914 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-09 15:28:39,928 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-09 15:28:39,929 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 15:28:39,929 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,027 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 106 states and 124 transitions. Complement of second has 17 states. [2024-11-09 15:28:40,031 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:40,032 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,033 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 16 transitions. [2024-11-09 15:28:40,033 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 16 transitions. Stem has 20 letters. Loop has 3 letters. [2024-11-09 15:28:40,033 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:40,033 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:28:40,046 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:40,087 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:40,088 INFO L255 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 15:28:40,089 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:40,186 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (34)] Ended with exit code 0 [2024-11-09 15:28:40,212 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:40,212 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 15:28:40,213 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:40,232 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-09 15:28:40,243 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-09 15:28:40,243 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and with honda bouncer for loop.2 stem predicates 3 loop predicates [2024-11-09 15:28:40,243 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,311 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 106 states and 124 transitions. Complement of second has 17 states. [2024-11-09 15:28:40,312 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:40,312 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,313 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 16 transitions. [2024-11-09 15:28:40,313 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 16 transitions. Stem has 20 letters. Loop has 3 letters. [2024-11-09 15:28:40,313 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:40,313 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:28:40,323 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:40,360 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:40,361 INFO L255 TraceCheckSpWp]: Trace formula consists of 270 conjuncts, 10 conjuncts are in the unsatisfiable core [2024-11-09 15:28:40,362 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:40,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:40,465 INFO L255 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 18 conjuncts are in the unsatisfiable core [2024-11-09 15:28:40,466 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:40,489 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-09 15:28:40,501 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-09 15:28:40,502 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 3 loop predicates [2024-11-09 15:28:40,502 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21 Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,566 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 82 states and 96 transitions. cyclomatic complexity: 21. Second operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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 154 states and 179 transitions. Complement of second has 19 states. [2024-11-09 15:28:40,567 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 6 states 2 stem states 3 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:40,567 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 5 states, 4 states have (on average 3.25) internal successors, (13), 4 states have internal predecessors, (13), 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-09 15:28:40,568 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 6 states to 6 states and 19 transitions. [2024-11-09 15:28:40,568 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 20 letters. Loop has 3 letters. [2024-11-09 15:28:40,568 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:40,568 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 23 letters. Loop has 3 letters. [2024-11-09 15:28:40,568 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:40,568 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 6 states and 19 transitions. Stem has 20 letters. Loop has 6 letters. [2024-11-09 15:28:40,569 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:40,569 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 154 states and 179 transitions. [2024-11-09 15:28:40,573 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-09 15:28:40,575 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 154 states to 110 states and 135 transitions. [2024-11-09 15:28:40,575 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 68 [2024-11-09 15:28:40,576 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 76 [2024-11-09 15:28:40,576 INFO L73 IsDeterministic]: Start isDeterministic. Operand 110 states and 135 transitions. [2024-11-09 15:28:40,576 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:28:40,576 INFO L218 hiAutomatonCegarLoop]: Abstraction has 110 states and 135 transitions. [2024-11-09 15:28:40,576 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 110 states and 135 transitions. [2024-11-09 15:28:40,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 110 to 74. [2024-11-09 15:28:40,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 74 states, 51 states have (on average 1.196078431372549) internal successors, (61), 54 states have internal predecessors, (61), 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-09 15:28:40,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 74 states to 74 states and 87 transitions. [2024-11-09 15:28:40,583 INFO L240 hiAutomatonCegarLoop]: Abstraction has 74 states and 87 transitions. [2024-11-09 15:28:40,583 INFO L425 stractBuchiCegarLoop]: Abstraction has 74 states and 87 transitions. [2024-11-09 15:28:40,583 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-09 15:28:40,583 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 74 states and 87 transitions. [2024-11-09 15:28:40,585 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 3 [2024-11-09 15:28:40,585 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:40,585 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:40,586 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:40,586 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:40,586 INFO L745 eck$LassoCheckResult]: Stem: 1363#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 1364#L-1 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; 1373#L20-2 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; 1360#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1362#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1390#L9 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; 1374#recFINAL assume true; 1366#recEXIT >#30#return; 1367#L23-1 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; 1357#L20-2 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; 1358#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1361#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1398#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 1354#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 1368#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1369#L9 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; 1423#recFINAL assume true; 1421#recEXIT >#28#return; 1404#L15-1 #res := #t~ret5;havoc #t~ret5; 1399#recFINAL assume true; 1379#recEXIT >#30#return; 1371#L23-1 [2024-11-09 15:28:40,586 INFO L747 eck$LassoCheckResult]: Loop: 1371#L23-1 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; 1372#L20-2 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; 1401#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 1405#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 1400#L9 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; 1402#recFINAL assume true; 1406#recEXIT >#30#return; 1371#L23-1 [2024-11-09 15:28:40,587 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:40,587 INFO L85 PathProgramCache]: Analyzing trace with hash 1572162950, now seen corresponding path program 4 times [2024-11-09 15:28:40,587 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:40,587 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1351173040] [2024-11-09 15:28:40,587 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:40,587 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:40,602 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,602 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:40,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,620 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:40,620 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:40,620 INFO L85 PathProgramCache]: Analyzing trace with hash -523709736, now seen corresponding path program 3 times [2024-11-09 15:28:40,621 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:40,621 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1536331747] [2024-11-09 15:28:40,621 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:40,621 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:40,631 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,631 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:40,634 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,638 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:40,638 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:40,638 INFO L85 PathProgramCache]: Analyzing trace with hash 1341076915, now seen corresponding path program 5 times [2024-11-09 15:28:40,638 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:40,638 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1929577112] [2024-11-09 15:28:40,638 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:40,639 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:40,664 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,665 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:40,680 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:40,684 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:41,773 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:41,773 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:41,773 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:41,773 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:41,773 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:41,773 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:41,773 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:41,773 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:41,773 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration5_Lasso [2024-11-09 15:28:41,773 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:41,773 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:41,777 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:41,779 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:41,977 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:41,979 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:41,981 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:41,983 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:42,248 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:42,248 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:42,248 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:42,248 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:42,250 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-09 15:28:42,252 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-09 15:28:42,253 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-09 15:28:42,263 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:42,263 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:42,263 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:42,263 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:42,263 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:42,264 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:42,264 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:42,265 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:42,275 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-09 15:28:42,276 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:42,276 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:42,277 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-09 15:28:42,278 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-09 15:28:42,279 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-09 15:28:42,288 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:42,289 INFO L203 nArgumentSynthesizer]: 6 stem disjuncts [2024-11-09 15:28:42,289 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-09 15:28:42,289 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:42,302 INFO L401 nArgumentSynthesizer]: We have 36 Motzkin's Theorem applications. [2024-11-09 15:28:42,302 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-09 15:28:42,323 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:42,333 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-09 15:28:42,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:42,333 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:42,334 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-09 15:28:42,336 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-09 15:28:42,336 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-09 15:28:42,346 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:42,346 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:42,346 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:42,346 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:42,350 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:42,350 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:42,357 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:42,365 INFO L443 ModelExtractionUtils]: Simplification made 6 calls to the SMT solver. [2024-11-09 15:28:42,365 INFO L444 ModelExtractionUtils]: 2 out of 16 variables were initially zero. Simplification set additionally 11 variables to zero. [2024-11-09 15:28:42,366 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:42,366 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:42,367 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-09 15:28:42,367 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-09 15:28:42,368 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:42,378 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-09 15:28:42,378 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:42,378 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-09 15:28:42,389 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-09 15:28:42,391 INFO L156 tatePredicateManager]: 2 out of 2 supporting invariants were superfluous and have been removed [2024-11-09 15:28:42,392 WARN L976 BoogieBacktranslator]: Unfinished Backtranslation: Unknown variable: #t~ret9 [2024-11-09 15:28:42,400 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:42,431 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:42,432 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 15:28:42,433 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:42,556 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:42,559 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 15:28:42,560 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:42,607 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-09 15:28:42,625 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-09 15:28:42,626 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-09 15:28:42,626 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:42,713 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 118 states and 139 transitions. Complement of second has 21 states. [2024-11-09 15:28:42,716 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-09 15:28:42,717 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:42,717 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 26 transitions. [2024-11-09 15:28:42,718 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 26 transitions. Stem has 21 letters. Loop has 7 letters. [2024-11-09 15:28:42,718 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:42,718 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:28:42,728 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:42,763 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:42,764 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 15:28:42,765 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:42,883 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:42,884 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 15:28:42,885 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:42,937 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-09 15:28:42,958 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-09 15:28:42,959 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-09 15:28:42,959 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:43,041 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 118 states and 139 transitions. Complement of second has 21 states. [2024-11-09 15:28:43,043 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-09 15:28:43,043 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:43,044 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 26 transitions. [2024-11-09 15:28:43,044 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 26 transitions. Stem has 21 letters. Loop has 7 letters. [2024-11-09 15:28:43,044 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:43,044 INFO L682 stractBuchiCegarLoop]: Bad chosen interpolant automaton: word not accepted [2024-11-09 15:28:43,057 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:43,093 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:43,093 INFO L255 TraceCheckSpWp]: Trace formula consists of 238 conjuncts, 8 conjuncts are in the unsatisfiable core [2024-11-09 15:28:43,094 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:43,217 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:43,217 INFO L255 TraceCheckSpWp]: Trace formula consists of 88 conjuncts, 11 conjuncts are in the unsatisfiable core [2024-11-09 15:28:43,218 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:43,264 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-09 15:28:43,283 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-09 15:28:43,284 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-09 15:28:43,284 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18 Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:43,361 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 74 states and 87 transitions. cyclomatic complexity: 18. Second operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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 143 states and 169 transitions. Complement of second has 22 states. [2024-11-09 15:28:43,363 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-09 15:28:43,364 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 2.0) internal successors, (14), 6 states have internal predecessors, (14), 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-09 15:28:43,364 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 28 transitions. [2024-11-09 15:28:43,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 28 transitions. Stem has 21 letters. Loop has 7 letters. [2024-11-09 15:28:43,364 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:43,364 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 28 transitions. Stem has 28 letters. Loop has 7 letters. [2024-11-09 15:28:43,365 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:43,365 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 28 transitions. Stem has 21 letters. Loop has 14 letters. [2024-11-09 15:28:43,366 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:43,366 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 143 states and 169 transitions. [2024-11-09 15:28:43,370 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 6 [2024-11-09 15:28:43,374 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 143 states to 94 states and 109 transitions. [2024-11-09 15:28:43,375 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 57 [2024-11-09 15:28:43,375 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 59 [2024-11-09 15:28:43,375 INFO L73 IsDeterministic]: Start isDeterministic. Operand 94 states and 109 transitions. [2024-11-09 15:28:43,376 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is not deterministic. [2024-11-09 15:28:43,376 INFO L218 hiAutomatonCegarLoop]: Abstraction has 94 states and 109 transitions. [2024-11-09 15:28:43,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 94 states and 109 transitions. [2024-11-09 15:28:43,379 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 94 to 32. [2024-11-09 15:28:43,379 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 23 states have (on average 1.2173913043478262) internal successors, (28), 23 states have internal predecessors, (28), 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-09 15:28:43,380 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 38 transitions. [2024-11-09 15:28:43,380 INFO L240 hiAutomatonCegarLoop]: Abstraction has 32 states and 38 transitions. [2024-11-09 15:28:43,380 INFO L425 stractBuchiCegarLoop]: Abstraction has 32 states and 38 transitions. [2024-11-09 15:28:43,380 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-09 15:28:43,380 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 32 states and 38 transitions. [2024-11-09 15:28:43,383 INFO L131 ngComponentsAnalysis]: Automaton has 1 accepting balls. 6 [2024-11-09 15:28:43,384 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-09 15:28:43,384 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-09 15:28:43,384 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-09 15:28:43,384 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-09 15:28:43,384 INFO L745 eck$LassoCheckResult]: Stem: 2189#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier; 2190#L-1 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; 2198#L20-2 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; 2185#L23 [2024-11-09 15:28:43,384 INFO L747 eck$LassoCheckResult]: Loop: 2185#L23 call main_#t~ret9#1 := rec(main_~op~0#1.base, main_~op~0#1.offset);< 2187#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 2201#L9 assume !(#t~mem1 < 0);havoc #t~mem1;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; 2182#L15 call #t~ret5 := rec(~p.base, ~p.offset);< 2191#$Ultimate##0 ~p.base, ~p.offset := #in~p.base, #in~p.offset;call #t~mem1 := read~int#0(~p.base, ~p.offset, 4); 2193#L9 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; 2206#recFINAL assume true; 2204#recEXIT >#28#return; 2203#L15-1 #res := #t~ret5;havoc #t~ret5; 2202#recFINAL assume true; 2200#recEXIT >#30#return; 2197#L23-1 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; 2184#L20-2 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; 2185#L23 [2024-11-09 15:28:43,385 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:43,385 INFO L85 PathProgramCache]: Analyzing trace with hash 37808, now seen corresponding path program 1 times [2024-11-09 15:28:43,385 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:43,385 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [191390715] [2024-11-09 15:28:43,385 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:43,385 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:43,390 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,391 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:43,393 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,395 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:43,396 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:43,396 INFO L85 PathProgramCache]: Analyzing trace with hash -669629144, now seen corresponding path program 1 times [2024-11-09 15:28:43,396 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:43,396 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [527548849] [2024-11-09 15:28:43,396 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:43,396 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:43,427 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,428 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:43,432 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,436 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:43,437 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:43,437 INFO L85 PathProgramCache]: Analyzing trace with hash -1720097319, now seen corresponding path program 6 times [2024-11-09 15:28:43,437 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-09 15:28:43,437 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [402578050] [2024-11-09 15:28:43,437 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-09 15:28:43,438 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-09 15:28:43,439 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (38)] Ended with exit code 0 [2024-11-09 15:28:43,450 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,451 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-09 15:28:43,457 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-09 15:28:43,459 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-09 15:28:43,984 INFO L204 LassoAnalysis]: Preferences: [2024-11-09 15:28:43,984 INFO L125 ssoRankerPreferences]: Compute integeral hull: false [2024-11-09 15:28:43,984 INFO L126 ssoRankerPreferences]: Enable LassoPartitioneer: true [2024-11-09 15:28:43,985 INFO L127 ssoRankerPreferences]: Term annotations enabled: false [2024-11-09 15:28:43,985 INFO L128 ssoRankerPreferences]: Use exernal solver: false [2024-11-09 15:28:43,985 INFO L129 ssoRankerPreferences]: SMT solver command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:43,985 INFO L130 ssoRankerPreferences]: Dump SMT script to file: false [2024-11-09 15:28:43,985 INFO L131 ssoRankerPreferences]: Path of dumped script: [2024-11-09 15:28:43,985 INFO L132 ssoRankerPreferences]: Filename of dumped script: rec_malloc_ex3.i_Iteration6_Lasso [2024-11-09 15:28:43,985 INFO L133 ssoRankerPreferences]: MapElimAlgo: Frank [2024-11-09 15:28:43,985 INFO L241 LassoAnalysis]: Starting lasso preprocessing... [2024-11-09 15:28:43,986 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,064 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,066 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,068 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,078 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,080 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,082 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,083 INFO L118 MapEliminator]: Using MapEliminator with SimplificationTechnique=SIMPLIFY_DDA AddInequalities=false OnlyTrivialImplicationsArrayWrite=true OnlyTrivialImplicationsForModifiedArguments=true OnlyArgumentsInFormula=true [2024-11-09 15:28:44,199 INFO L259 LassoAnalysis]: Preprocessing complete. [2024-11-09 15:28:44,200 INFO L451 LassoAnalysis]: Using template 'affine'. [2024-11-09 15:28:44,200 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,200 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,202 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-09 15:28:44,202 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-09 15:28:44,203 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-09 15:28:44,212 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,213 INFO L203 nArgumentSynthesizer]: 2 stem disjuncts [2024-11-09 15:28:44,213 INFO L204 nArgumentSynthesizer]: 2 loop disjuncts [2024-11-09 15:28:44,213 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,216 INFO L401 nArgumentSynthesizer]: We have 20 Motzkin's Theorem applications. [2024-11-09 15:28:44,216 INFO L402 nArgumentSynthesizer]: A total of 4 supporting invariants were added. [2024-11-09 15:28:44,227 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,238 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-09 15:28:44,238 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,239 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,239 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-09 15:28:44,241 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-09 15:28:44,241 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-09 15:28:44,251 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,251 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,251 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,251 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,253 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,253 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,259 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,273 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-09 15:28:44,274 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,274 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,275 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-09 15:28:44,277 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-09 15:28:44,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-09 15:28:44,291 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,291 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,291 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,291 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,292 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,292 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,295 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,305 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-09 15:28:44,305 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,305 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,306 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-09 15:28:44,307 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-09 15:28:44,308 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-09 15:28:44,317 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,318 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,318 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,318 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,319 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,319 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,323 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,333 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-09 15:28:44,333 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,334 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,335 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-09 15:28:44,335 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-09 15:28:44,336 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-09 15:28:44,346 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,346 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,346 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,346 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,348 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,348 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,351 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,362 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-09 15:28:44,362 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,363 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-09 15:28:44,364 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-09 15:28:44,365 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-09 15:28:44,375 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,375 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,376 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,376 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,378 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,378 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,381 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,392 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-09 15:28:44,392 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,392 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,394 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-09 15:28:44,395 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-09 15:28:44,396 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-09 15:28:44,405 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,405 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:44,406 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,406 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,406 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,406 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:44,406 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:44,408 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,418 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (45)] Ended with exit code 0 [2024-11-09 15:28:44,418 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,418 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,419 INFO L229 MonitoredProcess]: Starting monitored process 46 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-09 15:28:44,420 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Waiting until timeout for monitored process [2024-11-09 15:28:44,421 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-09 15:28:44,430 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,431 INFO L351 nArgumentSynthesizer]: There is no stem transition; disabling supporting invariant generation. [2024-11-09 15:28:44,431 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,431 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,431 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,431 INFO L401 nArgumentSynthesizer]: We have 2 Motzkin's Theorem applications. [2024-11-09 15:28:44,431 INFO L402 nArgumentSynthesizer]: A total of 0 supporting invariants were added. [2024-11-09 15:28:44,432 INFO L488 LassoAnalysis]: Proving termination failed for this template and these settings. [2024-11-09 15:28:44,442 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (46)] Ended with exit code 0 [2024-11-09 15:28:44,442 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,442 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,443 INFO L229 MonitoredProcess]: Starting monitored process 47 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-09 15:28:44,444 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Waiting until timeout for monitored process [2024-11-09 15:28:44,445 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-09 15:28:44,455 INFO L338 nArgumentSynthesizer]: Template has degree 0. [2024-11-09 15:28:44,456 INFO L203 nArgumentSynthesizer]: 1 stem disjuncts [2024-11-09 15:28:44,456 INFO L204 nArgumentSynthesizer]: 1 loop disjuncts [2024-11-09 15:28:44,456 INFO L205 nArgumentSynthesizer]: 2 template conjuncts. [2024-11-09 15:28:44,457 INFO L401 nArgumentSynthesizer]: We have 6 Motzkin's Theorem applications. [2024-11-09 15:28:44,457 INFO L402 nArgumentSynthesizer]: A total of 2 supporting invariants were added. [2024-11-09 15:28:44,461 INFO L420 nArgumentSynthesizer]: Found a termination argument, trying to simplify. [2024-11-09 15:28:44,464 INFO L443 ModelExtractionUtils]: Simplification made 5 calls to the SMT solver. [2024-11-09 15:28:44,464 INFO L444 ModelExtractionUtils]: 3 out of 7 variables were initially zero. Simplification set additionally 2 variables to zero. [2024-11-09 15:28:44,464 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-09 15:28:44,464 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-09 15:28:44,465 INFO L229 MonitoredProcess]: Starting monitored process 48 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-09 15:28:44,466 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Waiting until timeout for monitored process [2024-11-09 15:28:44,467 INFO L435 nArgumentSynthesizer]: Simplifying supporting invariants... [2024-11-09 15:28:44,477 INFO L438 nArgumentSynthesizer]: Removed 2 redundant supporting invariants from a total of 2. [2024-11-09 15:28:44,478 INFO L474 LassoAnalysis]: Proved termination. [2024-11-09 15:28:44,478 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-09 15:28:44,488 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (47)] Forceful destruction successful, exit code 0 [2024-11-09 15:28:44,491 INFO L156 tatePredicateManager]: 2 out of 2 supporting invariants were superfluous and have been removed [2024-11-09 15:28:44,498 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-09 15:28:44,504 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:44,504 INFO L255 TraceCheckSpWp]: Trace formula consists of 27 conjuncts, 2 conjuncts are in the unsatisfiable core [2024-11-09 15:28:44,504 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:44,528 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-09 15:28:44,529 INFO L255 TraceCheckSpWp]: Trace formula consists of 150 conjuncts, 15 conjuncts are in the unsatisfiable core [2024-11-09 15:28:44,530 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-09 15:28:44,558 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-09 15:28:44,637 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (48)] Ended with exit code 0 [2024-11-09 15:28:44,638 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-09 15:28:44,639 INFO L141 lantAutomatonBouncer]: Defining deterministic Buchi interpolant automaton with honda bouncer for stem and without honda bouncer for loop.1 stem predicates 7 loop predicates [2024-11-09 15:28:44,639 INFO L71 iDifferenceNCSBLazy3]: Start buchiDifferenceNCSBLazy3. First operand 32 states and 38 transitions. cyclomatic complexity: 8 Second operand has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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-09 15:28:44,691 INFO L75 iDifferenceNCSBLazy3]: Finished buchiDifferenceNCSBLazy3. First operand 32 states and 38 transitions. cyclomatic complexity: 8. Second operand has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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 69 states and 86 transitions. Complement of second has 22 states. [2024-11-09 15:28:44,691 INFO L141 InterpolantAutomaton]: Switched to read-only mode: Buchi interpolant automaton has 8 states 1 stem states 6 non-accepting loop states 1 accepting loop states [2024-11-09 15:28:44,692 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 8 states, 7 states have (on average 1.5714285714285714) internal successors, (11), 6 states have internal predecessors, (11), 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-09 15:28:44,692 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 8 states to 8 states and 14 transitions. [2024-11-09 15:28:44,692 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 14 transitions. Stem has 3 letters. Loop has 13 letters. [2024-11-09 15:28:44,692 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:44,693 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 14 transitions. Stem has 16 letters. Loop has 13 letters. [2024-11-09 15:28:44,693 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:44,693 INFO L84 BuchiAccepts]: Start buchiAccepts Operand 8 states and 14 transitions. Stem has 3 letters. Loop has 26 letters. [2024-11-09 15:28:44,693 INFO L116 BuchiAccepts]: Finished buchiAccepts. [2024-11-09 15:28:44,693 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 69 states and 86 transitions. [2024-11-09 15:28:44,695 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:28:44,695 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 69 states to 0 states and 0 transitions. [2024-11-09 15:28:44,695 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 0 [2024-11-09 15:28:44,695 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 0 [2024-11-09 15:28:44,695 INFO L73 IsDeterministic]: Start isDeterministic. Operand 0 states and 0 transitions. [2024-11-09 15:28:44,695 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-09 15:28:44,696 INFO L218 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:28:44,696 INFO L240 hiAutomatonCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:28:44,696 INFO L425 stractBuchiCegarLoop]: Abstraction has 0 states and 0 transitions. [2024-11-09 15:28:44,696 INFO L332 stractBuchiCegarLoop]: ======== Iteration 7 ============ [2024-11-09 15:28:44,696 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 0 states and 0 transitions. [2024-11-09 15:28:44,696 INFO L131 ngComponentsAnalysis]: Automaton has 0 accepting balls. 0 [2024-11-09 15:28:44,696 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is true [2024-11-09 15:28:44,702 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer CFG 09.11 03:28:44 BoogieIcfgContainer [2024-11-09 15:28:44,702 INFO L131 PluginConnector]: ------------------------ END BuchiAutomizer---------------------------- [2024-11-09 15:28:44,703 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2024-11-09 15:28:44,703 INFO L270 PluginConnector]: Initializing Witness Printer... [2024-11-09 15:28:44,703 INFO L274 PluginConnector]: Witness Printer initialized [2024-11-09 15:28:44,703 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.11 03:28:32" (3/4) ... [2024-11-09 15:28:44,705 INFO L145 WitnessPrinter]: No result that supports witness generation found [2024-11-09 15:28:44,706 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2024-11-09 15:28:44,707 INFO L158 Benchmark]: Toolchain (without parser) took 13126.14ms. Allocated memory was 151.0MB in the beginning and 234.9MB in the end (delta: 83.9MB). Free memory was 79.9MB in the beginning and 190.2MB in the end (delta: -110.3MB). There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:28:44,707 INFO L158 Benchmark]: CDTParser took 0.55ms. Allocated memory is still 151.0MB. Free memory is still 102.9MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:28:44,707 INFO L158 Benchmark]: CACSL2BoogieTranslator took 242.09ms. Allocated memory is still 151.0MB. Free memory was 79.5MB in the beginning and 68.0MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. [2024-11-09 15:28:44,708 INFO L158 Benchmark]: Boogie Procedure Inliner took 26.05ms. Allocated memory is still 151.0MB. Free memory was 67.9MB in the beginning and 66.6MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 15:28:44,708 INFO L158 Benchmark]: Boogie Preprocessor took 33.55ms. Allocated memory is still 151.0MB. Free memory was 66.6MB in the beginning and 64.8MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. [2024-11-09 15:28:44,708 INFO L158 Benchmark]: RCFGBuilder took 272.00ms. Allocated memory was 151.0MB in the beginning and 195.0MB in the end (delta: 44.0MB). Free memory was 64.8MB in the beginning and 161.3MB in the end (delta: -96.5MB). Peak memory consumption was 14.1MB. Max. memory is 16.1GB. [2024-11-09 15:28:44,708 INFO L158 Benchmark]: BuchiAutomizer took 12543.52ms. Allocated memory was 195.0MB in the beginning and 234.9MB in the end (delta: 39.8MB). Free memory was 161.3MB in the beginning and 190.2MB in the end (delta: -28.8MB). Peak memory consumption was 10.0MB. Max. memory is 16.1GB. [2024-11-09 15:28:44,709 INFO L158 Benchmark]: Witness Printer took 3.68ms. Allocated memory is still 234.9MB. Free memory is still 190.2MB. There was no memory consumed. Max. memory is 16.1GB. [2024-11-09 15:28:44,710 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.55ms. Allocated memory is still 151.0MB. Free memory is still 102.9MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 242.09ms. Allocated memory is still 151.0MB. Free memory was 79.5MB in the beginning and 68.0MB in the end (delta: 11.4MB). Peak memory consumption was 10.5MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 26.05ms. Allocated memory is still 151.0MB. Free memory was 67.9MB in the beginning and 66.6MB in the end (delta: 1.3MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * Boogie Preprocessor took 33.55ms. Allocated memory is still 151.0MB. Free memory was 66.6MB in the beginning and 64.8MB in the end (delta: 1.8MB). Peak memory consumption was 2.1MB. Max. memory is 16.1GB. * RCFGBuilder took 272.00ms. Allocated memory was 151.0MB in the beginning and 195.0MB in the end (delta: 44.0MB). Free memory was 64.8MB in the beginning and 161.3MB in the end (delta: -96.5MB). Peak memory consumption was 14.1MB. Max. memory is 16.1GB. * BuchiAutomizer took 12543.52ms. Allocated memory was 195.0MB in the beginning and 234.9MB in the end (delta: 39.8MB). Free memory was 161.3MB in the beginning and 190.2MB in the end (delta: -28.8MB). Peak memory consumption was 10.0MB. Max. memory is 16.1GB. * Witness Printer took 3.68ms. Allocated memory is still 234.9MB. Free memory is still 190.2MB. 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 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 - 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 8 locations. One deterministic module has affine ranking function null and consists of 8 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 8 locations. One nondeterministic module has affine ranking function null and consists of 6 locations. One nondeterministic module has affine ranking function null and consists of 8 locations. - StatisticsResult: Timing statistics BüchiAutomizer plugin needed 12.4s and 7 iterations. TraceHistogramMax:3. Analysis of lassos took 9.1s. Construction of modules took 0.3s. Büchi inclusion checks took 2.7s. Highest rank in rank-based complementation 3. Minimization of det autom 1. Minimization of nondet autom 5. Automata minimization 0.0s AutomataMinimizationTime, 5 MinimizatonAttempts, 111 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, 162 SdHoareTripleChecker+Valid, 0.5s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 153 mSDsluCounter, 244 SdHoareTripleChecker+Invalid, 0.4s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 123 mSDsCounter, 118 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 404 IncrementalHoareTripleChecker+Invalid, 522 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 118 mSolverCounterUnsat, 121 mSDtfsCounter, 404 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown LassoAnalysisResults: nont0 unkn0 SFLI0 SFLT0 conc0 concLT0 SILN0 SILU0 SILI0 SILT0 lasso6 LassoPreprocessingBenchmarks: Lassos: inital147 mio100 ax100 hnf100 lsp133 ukn51 mio100 lsp38 div100 bol100 ite100 ukn100 eq162 hnf94 smp100 dnf159 smp88 tf100 neg100 sie114 LassoTerminationAnalysisBenchmarks: ConstraintsSatisfiability: unsat Degree: 0 Time: 46ms 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-09 15:28:44,735 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE