./Ultimate.py --spec ../sv-benchmarks/c/properties/termination.prp --file ../sv-benchmarks/c/recursified_loop-simple/recursified_deep-nested.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for termination Using default analysis Version 3061b6dc 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/recursified_loop-simple/recursified_deep-nested.c -s /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(F end) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash dea78793c7130d873f751539350d9a84f129d659be765f9ed3f85c683976c43a --- Real Ultimate output --- This is Ultimate 0.2.5-tmp.dk.eval-assert-order-craig-3061b6d-m [2024-11-19 15:01:48,797 INFO L188 SettingsManager]: Resetting all preferences to default values... [2024-11-19 15:01:48,834 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/config/svcomp-Termination-32bit-Automizer_Default.epf [2024-11-19 15:01:48,838 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2024-11-19 15:01:48,838 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2024-11-19 15:01:48,861 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2024-11-19 15:01:48,862 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2024-11-19 15:01:48,862 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2024-11-19 15:01:48,863 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2024-11-19 15:01:48,863 INFO L153 SettingsManager]: * Use memory slicer=true [2024-11-19 15:01:48,864 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2024-11-19 15:01:48,864 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2024-11-19 15:01:48,864 INFO L153 SettingsManager]: * Use SBE=true [2024-11-19 15:01:48,865 INFO L151 SettingsManager]: Preferences of BuchiAutomizer differ from their defaults: [2024-11-19 15:01:48,865 INFO L153 SettingsManager]: * NCSB implementation=INTSET_LAZY3 [2024-11-19 15:01:48,865 INFO L153 SettingsManager]: * Use old map elimination=false [2024-11-19 15:01:48,865 INFO L153 SettingsManager]: * Use external solver (rank synthesis)=false [2024-11-19 15:01:48,866 INFO L153 SettingsManager]: * Use only trivial implications for array writes=true [2024-11-19 15:01:48,866 INFO L153 SettingsManager]: * Rank analysis=LINEAR_WITH_GUESSES [2024-11-19 15:01:48,866 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2024-11-19 15:01:48,867 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=ASSUME [2024-11-19 15:01:48,871 INFO L153 SettingsManager]: * sizeof long=4 [2024-11-19 15:01:48,871 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2024-11-19 15:01:48,871 INFO L153 SettingsManager]: * sizeof POINTER=4 [2024-11-19 15:01:48,871 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=ASSUME [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=ASSUME [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=ASSUME [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * Allow undefined functions=false [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * Check unreachability of reach_error function=false [2024-11-19 15:01:48,872 INFO L153 SettingsManager]: * sizeof long double=12 [2024-11-19 15:01:48,873 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2024-11-19 15:01:48,873 INFO L153 SettingsManager]: * Assume nondeterminstic values are in range=false [2024-11-19 15:01:48,873 INFO L153 SettingsManager]: * Use constant arrays=true [2024-11-19 15:01:48,873 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2024-11-19 15:01:48,873 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2024-11-19 15:01:48,873 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2024-11-19 15:01:48,874 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2024-11-19 15:01:48,874 INFO L151 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2024-11-19 15:01:48,874 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 -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> dea78793c7130d873f751539350d9a84f129d659be765f9ed3f85c683976c43a [2024-11-19 15:01:49,138 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2024-11-19 15:01:49,161 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2024-11-19 15:01:49,163 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2024-11-19 15:01:49,164 INFO L270 PluginConnector]: Initializing CDTParser... [2024-11-19 15:01:49,165 INFO L274 PluginConnector]: CDTParser initialized [2024-11-19 15:01:49,166 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/recursified_loop-simple/recursified_deep-nested.c [2024-11-19 15:01:50,435 INFO L533 CDTParser]: Created temporary CDT project at NULL [2024-11-19 15:01:50,609 INFO L384 CDTParser]: Found 1 translation units. [2024-11-19 15:01:50,609 INFO L180 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/recursified_loop-simple/recursified_deep-nested.c [2024-11-19 15:01:50,616 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/292eb537d/ce594ffe1f0f49e3999e7745e97f0324/FLAGd1e457944 [2024-11-19 15:01:51,001 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/292eb537d/ce594ffe1f0f49e3999e7745e97f0324 [2024-11-19 15:01:51,004 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2024-11-19 15:01:51,005 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2024-11-19 15:01:51,006 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2024-11-19 15:01:51,007 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2024-11-19 15:01:51,017 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2024-11-19 15:01:51,018 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,019 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7dadc61e and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51, skipping insertion in model container [2024-11-19 15:01:51,019 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,042 INFO L175 MainTranslator]: Built tables and reachable declarations [2024-11-19 15:01:51,202 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 15:01:51,212 INFO L200 MainTranslator]: Completed pre-run [2024-11-19 15:01:51,232 INFO L210 PostProcessor]: Analyzing one entry point: main [2024-11-19 15:01:51,249 INFO L204 MainTranslator]: Completed translation [2024-11-19 15:01:51,249 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51 WrapperNode [2024-11-19 15:01:51,249 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2024-11-19 15:01:51,250 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2024-11-19 15:01:51,250 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2024-11-19 15:01:51,250 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2024-11-19 15:01:51,256 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,263 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,279 INFO L138 Inliner]: procedures = 16, calls = 72, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 116 [2024-11-19 15:01:51,280 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2024-11-19 15:01:51,280 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2024-11-19 15:01:51,281 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2024-11-19 15:01:51,281 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2024-11-19 15:01:51,290 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,290 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,293 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,315 INFO L175 MemorySlicer]: Split 38 memory accesses to 7 slices as follows [2, 6, 6, 6, 6, 5, 7]. 18 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2, 0, 0, 0, 0, 0, 0]. The 11 writes are split as follows [0, 2, 2, 2, 2, 2, 1]. [2024-11-19 15:01:51,315 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,315 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,321 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,323 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,325 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,326 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,329 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2024-11-19 15:01:51,330 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2024-11-19 15:01:51,330 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2024-11-19 15:01:51,330 INFO L274 PluginConnector]: RCFGBuilder initialized [2024-11-19 15:01:51,331 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (1/1) ... [2024-11-19 15:01:51,341 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2024-11-19 15:01:51,350 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:01:51,371 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-19 15:01:51,374 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-19 15:01:51,425 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_12_to_13_0 [2024-11-19 15:01:51,425 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_12_to_13_0 [2024-11-19 15:01:51,425 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2024-11-19 15:01:51,426 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_13_to_14_0 [2024-11-19 15:01:51,426 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_13_to_14_0 [2024-11-19 15:01:51,426 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_11_to_12_0 [2024-11-19 15:01:51,426 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_11_to_12_0 [2024-11-19 15:01:51,427 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2024-11-19 15:01:51,427 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#1 [2024-11-19 15:01:51,427 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#2 [2024-11-19 15:01:51,427 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#3 [2024-11-19 15:01:51,427 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#4 [2024-11-19 15:01:51,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#5 [2024-11-19 15:01:51,428 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#6 [2024-11-19 15:01:51,429 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_14_to_16_0 [2024-11-19 15:01:51,431 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_14_to_16_0 [2024-11-19 15:01:51,431 INFO L130 BoogieDeclarations]: Found specification of procedure func_to_recursive_line_10_to_11_0 [2024-11-19 15:01:51,431 INFO L138 BoogieDeclarations]: Found implementation of procedure func_to_recursive_line_10_to_11_0 [2024-11-19 15:01:51,431 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocOnStack [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#0 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#1 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#2 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#3 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#4 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#5 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure write~int#6 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2024-11-19 15:01:51,432 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#0 [2024-11-19 15:01:51,432 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#1 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#2 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#3 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#4 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#5 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure read~int#6 [2024-11-19 15:01:51,433 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2024-11-19 15:01:51,554 INFO L238 CfgBuilder]: Building ICFG [2024-11-19 15:01:51,557 INFO L264 CfgBuilder]: Building CFG for each procedure with an implementation [2024-11-19 15:01:51,914 INFO L? ?]: Removed 15 outVars from TransFormulas that were not future-live. [2024-11-19 15:01:51,914 INFO L287 CfgBuilder]: Performing block encoding [2024-11-19 15:01:51,929 INFO L311 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2024-11-19 15:01:51,929 INFO L316 CfgBuilder]: Removed 0 assume(true) statements. [2024-11-19 15:01:51,930 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 03:01:51 BoogieIcfgContainer [2024-11-19 15:01:51,930 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2024-11-19 15:01:51,930 INFO L112 PluginConnector]: ------------------------BuchiAutomizer---------------------------- [2024-11-19 15:01:51,931 INFO L270 PluginConnector]: Initializing BuchiAutomizer... [2024-11-19 15:01:51,934 INFO L274 PluginConnector]: BuchiAutomizer initialized [2024-11-19 15:01:51,935 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:01:51,935 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "CDTParser AST 19.11 03:01:51" (1/3) ... [2024-11-19 15:01:51,936 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5832809 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 03:01:51, skipping insertion in model container [2024-11-19 15:01:51,936 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:01:51,936 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 19.11 03:01:51" (2/3) ... [2024-11-19 15:01:51,937 INFO L204 PluginConnector]: Invalid model from BuchiAutomizer for observer de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer.BuchiAutomizerObserver@5832809 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.buchiautomizer AST 19.11 03:01:51, skipping insertion in model container [2024-11-19 15:01:51,937 INFO L99 BuchiAutomizer]: Safety of program was proven or not checked, starting termination analysis [2024-11-19 15:01:51,937 INFO L184 PluginConnector]: Executing the observer BuchiAutomizerObserver from plugin BuchiAutomizer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 19.11 03:01:51" (3/3) ... [2024-11-19 15:01:51,939 INFO L332 chiAutomizerObserver]: Analyzing ICFG recursified_deep-nested.c [2024-11-19 15:01:51,986 INFO L300 stractBuchiCegarLoop]: Interprodecural is true [2024-11-19 15:01:51,986 INFO L301 stractBuchiCegarLoop]: Hoare is None [2024-11-19 15:01:51,986 INFO L302 stractBuchiCegarLoop]: Compute interpolants for ForwardPredicates [2024-11-19 15:01:51,986 INFO L303 stractBuchiCegarLoop]: Backedges is STRAIGHT_LINE [2024-11-19 15:01:51,987 INFO L304 stractBuchiCegarLoop]: Determinization is PREDICATE_ABSTRACTION [2024-11-19 15:01:51,987 INFO L305 stractBuchiCegarLoop]: Difference is false [2024-11-19 15:01:51,987 INFO L306 stractBuchiCegarLoop]: Minimize is MINIMIZE_SEVPA [2024-11-19 15:01:51,987 INFO L310 stractBuchiCegarLoop]: ======== Iteration 0 == of CEGAR loop == BuchiAutomatonCegarLoop ======== [2024-11-19 15:01:51,990 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 50 states, 34 states have (on average 1.2941176470588236) internal successors, (44), 39 states have internal predecessors, (44), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-19 15:01:52,007 INFO L131 ngComponentsAnalysis]: Automaton has 5 accepting balls. 33 [2024-11-19 15:01:52,007 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:01:52,008 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:01:52,013 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:01:52,013 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:01:52,013 INFO L332 stractBuchiCegarLoop]: ======== Iteration 1 ============ [2024-11-19 15:01:52,014 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand has 50 states, 34 states have (on average 1.2941176470588236) internal successors, (44), 39 states have internal predecessors, (44), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2024-11-19 15:01:52,017 INFO L131 ngComponentsAnalysis]: Automaton has 5 accepting balls. 33 [2024-11-19 15:01:52,017 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:01:52,017 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:01:52,017 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:01:52,017 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:01:52,023 INFO L745 eck$LassoCheckResult]: Stem: 20#$Ultimate##0true assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 33#L-1true assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 19#L139true call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 35#$Ultimate##0true [2024-11-19 15:01:52,024 INFO L747 eck$LassoCheckResult]: Loop: 35#$Ultimate##0true ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 17#L110true assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 42#L116true call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 30#$Ultimate##0true ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 24#L90true assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 22#L90-1true assume true; 25#func_to_recursive_line_11_to_12_0EXITtrue >#112#return; 51#L116-1true call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 18#L121true call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 35#$Ultimate##0true [2024-11-19 15:01:52,028 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:01:52,029 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 1 times [2024-11-19 15:01:52,036 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:01:52,036 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [293190717] [2024-11-19 15:01:52,037 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:01:52,037 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:01:52,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:01:52,182 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:01:52,225 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:01:52,252 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:01:52,254 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:01:52,255 INFO L85 PathProgramCache]: Analyzing trace with hash 376946881, now seen corresponding path program 1 times [2024-11-19 15:01:52,255 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:01:52,255 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1647510111] [2024-11-19 15:01:52,255 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:01:52,256 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:01:52,302 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:01:52,950 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-19 15:01:52,950 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:01:52,951 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1647510111] [2024-11-19 15:01:52,952 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1647510111] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 15:01:52,952 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 15:01:52,952 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2024-11-19 15:01:52,953 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1266549353] [2024-11-19 15:01:52,953 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 15:01:52,957 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:01:52,958 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:01:52,995 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2024-11-19 15:01:52,996 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=11, Invalid=31, Unknown=0, NotChecked=0, Total=42 [2024-11-19 15:01:52,998 INFO L87 Difference]: Start difference. First operand has 50 states, 34 states have (on average 1.2941176470588236) internal successors, (44), 39 states have internal predecessors, (44), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 7 states, 6 states have (on average 1.0) internal successors, (6), 5 states have internal predecessors, (6), 2 states have call successors, (2), 2 states have call predecessors, (2), 1 states have return successors, (1), 1 states have call predecessors, (1), 1 states have call successors, (1) [2024-11-19 15:01:53,385 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:01:53,385 INFO L93 Difference]: Finished difference Result 53 states and 67 transitions. [2024-11-19 15:01:53,386 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 53 states and 67 transitions. [2024-11-19 15:01:53,389 INFO L131 ngComponentsAnalysis]: Automaton has 5 accepting balls. 32 [2024-11-19 15:01:53,394 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 53 states to 45 states and 57 transitions. [2024-11-19 15:01:53,397 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 45 [2024-11-19 15:01:53,397 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 45 [2024-11-19 15:01:53,398 INFO L73 IsDeterministic]: Start isDeterministic. Operand 45 states and 57 transitions. [2024-11-19 15:01:53,399 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:01:53,399 INFO L218 hiAutomatonCegarLoop]: Abstraction has 45 states and 57 transitions. [2024-11-19 15:01:53,412 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states and 57 transitions. [2024-11-19 15:01:53,422 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 45. [2024-11-19 15:01:53,423 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 45 states, 30 states have (on average 1.2666666666666666) internal successors, (38), 34 states have internal predecessors, (38), 10 states have call successors, (10), 5 states have call predecessors, (10), 5 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2024-11-19 15:01:53,424 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 45 states to 45 states and 57 transitions. [2024-11-19 15:01:53,425 INFO L240 hiAutomatonCegarLoop]: Abstraction has 45 states and 57 transitions. [2024-11-19 15:01:53,427 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2024-11-19 15:01:53,430 INFO L425 stractBuchiCegarLoop]: Abstraction has 45 states and 57 transitions. [2024-11-19 15:01:53,430 INFO L332 stractBuchiCegarLoop]: ======== Iteration 2 ============ [2024-11-19 15:01:53,430 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 45 states and 57 transitions. [2024-11-19 15:01:53,431 INFO L131 ngComponentsAnalysis]: Automaton has 5 accepting balls. 32 [2024-11-19 15:01:53,431 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:01:53,431 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:01:53,432 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:01:53,432 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:01:53,432 INFO L745 eck$LassoCheckResult]: Stem: 161#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 138#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 139#L139 call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 143#$Ultimate##0 [2024-11-19 15:01:53,432 INFO L747 eck$LassoCheckResult]: Loop: 143#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 145#L110 assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 130#L116 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 128#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 131#L90 assume #t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296;havoc #t~mem31;havoc #t~mem30;call write~int#4(0, ~c.base, ~c.offset, 4); 150#L96 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 154#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 155#L70 assume !(#t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296);havoc #t~mem27;havoc #t~mem26; 151#L70-1 assume true; 148#func_to_recursive_line_12_to_13_0EXIT >#106#return; 152#L96-1 call #t~mem32 := read~int#3(~b.base, ~b.offset, 4);#t~pre33 := 1 + #t~mem32;call write~int#3(1 + #t~mem32, ~b.base, ~b.offset, 4);havoc #t~mem32;havoc #t~pre33; 129#L101 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 128#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 131#L90 assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 162#L90-1 assume true; 163#func_to_recursive_line_11_to_12_0EXIT >#108#return; 164#L90-1 assume true; 166#func_to_recursive_line_11_to_12_0EXIT >#112#return; 165#L116-1 call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 144#L121 call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 143#$Ultimate##0 [2024-11-19 15:01:53,433 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:01:53,433 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 2 times [2024-11-19 15:01:53,433 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:01:53,433 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1006838824] [2024-11-19 15:01:53,433 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2024-11-19 15:01:53,433 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:01:53,455 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 15:01:53,456 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:01:53,456 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:01:53,468 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:01:53,474 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:01:53,475 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:01:53,475 INFO L85 PathProgramCache]: Analyzing trace with hash 1072601781, now seen corresponding path program 1 times [2024-11-19 15:01:53,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:01:53,476 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1576218927] [2024-11-19 15:01:53,476 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:01:53,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:01:53,507 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:01:53,926 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2024-11-19 15:01:53,927 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:01:53,927 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1576218927] [2024-11-19 15:01:53,927 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1576218927] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:01:53,928 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1114850216] [2024-11-19 15:01:53,928 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:01:53,928 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:01:53,928 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:01:53,931 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:01:53,932 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2024-11-19 15:01:54,046 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:01:54,054 INFO L255 TraceCheckSpWp]: Trace formula consists of 316 conjuncts, 58 conjuncts are in the unsatisfiable core [2024-11-19 15:01:54,064 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:01:54,112 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:01:54,178 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:01:54,234 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 19 treesize of output 15 [2024-11-19 15:01:54,369 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 15:01:54,369 INFO L307 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2024-11-19 15:01:54,370 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1114850216] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 15:01:54,370 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2024-11-19 15:01:54,370 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [9] imperfect sequences [7] total 14 [2024-11-19 15:01:54,370 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1704374084] [2024-11-19 15:01:54,370 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 15:01:54,371 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:01:54,371 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:01:54,371 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2024-11-19 15:01:54,371 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=148, Unknown=0, NotChecked=0, Total=182 [2024-11-19 15:01:54,371 INFO L87 Difference]: Start difference. First operand 45 states and 57 transitions. cyclomatic complexity: 17 Second operand has 9 states, 7 states have (on average 1.7142857142857142) internal successors, (12), 7 states have internal predecessors, (12), 3 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (3), 1 states have call predecessors, (3), 3 states have call successors, (3) [2024-11-19 15:02:06,675 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 12.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-19 15:02:18,768 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 12.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-19 15:02:30,796 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 12.00s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0] [2024-11-19 15:02:30,864 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:02:30,865 INFO L93 Difference]: Finished difference Result 72 states and 92 transitions. [2024-11-19 15:02:30,865 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 72 states and 92 transitions. [2024-11-19 15:02:30,868 INFO L131 ngComponentsAnalysis]: Automaton has 7 accepting balls. 49 [2024-11-19 15:02:30,871 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 72 states to 70 states and 90 transitions. [2024-11-19 15:02:30,872 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 70 [2024-11-19 15:02:30,872 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 70 [2024-11-19 15:02:30,872 INFO L73 IsDeterministic]: Start isDeterministic. Operand 70 states and 90 transitions. [2024-11-19 15:02:30,872 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:02:30,872 INFO L218 hiAutomatonCegarLoop]: Abstraction has 70 states and 90 transitions. [2024-11-19 15:02:30,873 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states and 90 transitions. [2024-11-19 15:02:30,877 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 47. [2024-11-19 15:02:30,878 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 47 states, 32 states have (on average 1.25) internal successors, (40), 35 states have internal predecessors, (40), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (9), 8 states have call predecessors, (9), 8 states have call successors, (9) [2024-11-19 15:02:30,878 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 47 states to 47 states and 59 transitions. [2024-11-19 15:02:30,879 INFO L240 hiAutomatonCegarLoop]: Abstraction has 47 states and 59 transitions. [2024-11-19 15:02:30,880 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2024-11-19 15:02:30,880 INFO L425 stractBuchiCegarLoop]: Abstraction has 47 states and 59 transitions. [2024-11-19 15:02:30,881 INFO L332 stractBuchiCegarLoop]: ======== Iteration 3 ============ [2024-11-19 15:02:30,881 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 47 states and 59 transitions. [2024-11-19 15:02:30,881 INFO L131 ngComponentsAnalysis]: Automaton has 5 accepting balls. 32 [2024-11-19 15:02:30,882 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:02:30,882 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:02:30,884 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:02:30,884 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:02:30,885 INFO L745 eck$LassoCheckResult]: Stem: 364#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 340#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 341#L139 call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 346#$Ultimate##0 [2024-11-19 15:02:30,885 INFO L747 eck$LassoCheckResult]: Loop: 346#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 348#L110 assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 335#L116 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 334#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 337#L90 assume #t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296;havoc #t~mem31;havoc #t~mem30;call write~int#4(0, ~c.base, ~c.offset, 4); 351#L96 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 355#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 356#L70 assume #t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296;havoc #t~mem27;havoc #t~mem26;call write~int#1(0, ~d.base, ~d.offset, 4); 330#L76 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 342#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 363#L50 assume !(#t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296);havoc #t~mem23;havoc #t~mem22; 332#L50-1 assume true; 329#func_to_recursive_line_13_to_14_0EXIT >#98#return; 333#L76-1 call #t~mem28 := read~int#4(~c.base, ~c.offset, 4);#t~pre29 := 1 + #t~mem28;call write~int#4(1 + #t~mem28, ~c.base, ~c.offset, 4);havoc #t~mem28;havoc #t~pre29; 352#L81 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 361#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 362#L70 assume !(#t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296);havoc #t~mem27;havoc #t~mem26; 353#L70-1 assume true; 350#func_to_recursive_line_12_to_13_0EXIT >#100#return; 353#L70-1 assume true; 350#func_to_recursive_line_12_to_13_0EXIT >#106#return; 354#L96-1 call #t~mem32 := read~int#3(~b.base, ~b.offset, 4);#t~pre33 := 1 + #t~mem32;call write~int#3(1 + #t~mem32, ~b.base, ~b.offset, 4);havoc #t~mem32;havoc #t~pre33; 336#L101 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 334#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 337#L90 assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 369#L90-1 assume true; 367#func_to_recursive_line_11_to_12_0EXIT >#108#return; 365#L90-1 assume true; 366#func_to_recursive_line_11_to_12_0EXIT >#112#return; 368#L116-1 call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 347#L121 call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 346#$Ultimate##0 [2024-11-19 15:02:30,885 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:30,888 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 3 times [2024-11-19 15:02:30,888 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:30,889 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [338043720] [2024-11-19 15:02:30,889 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2024-11-19 15:02:30,889 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:30,910 INFO L227 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 1 check-sat command(s) [2024-11-19 15:02:30,910 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:02:30,911 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:02:30,922 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:02:30,927 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:02:30,928 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:30,928 INFO L85 PathProgramCache]: Analyzing trace with hash 2046612426, now seen corresponding path program 1 times [2024-11-19 15:02:30,928 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:30,928 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [498585790] [2024-11-19 15:02:30,929 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:30,929 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:30,960 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:31,474 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 15:02:31,475 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:02:31,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [498585790] [2024-11-19 15:02:31,475 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [498585790] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:02:31,475 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1492551568] [2024-11-19 15:02:31,475 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:31,475 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:02:31,475 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:02:31,478 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:02:31,479 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2024-11-19 15:02:31,601 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:31,604 INFO L255 TraceCheckSpWp]: Trace formula consists of 468 conjuncts, 82 conjuncts are in the unsatisfiable core [2024-11-19 15:02:31,607 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:02:31,632 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:31,812 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:32,460 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 5 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 15:02:32,460 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:02:33,433 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 15:02:33,433 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1492551568] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:02:33,433 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:02:33,433 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 16, 12] total 34 [2024-11-19 15:02:33,434 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1357818500] [2024-11-19 15:02:33,434 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:02:33,434 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:02:33,434 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:02:33,434 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 34 interpolants. [2024-11-19 15:02:33,435 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=137, Invalid=985, Unknown=0, NotChecked=0, Total=1122 [2024-11-19 15:02:33,435 INFO L87 Difference]: Start difference. First operand 47 states and 59 transitions. cyclomatic complexity: 17 Second operand has 34 states, 28 states have (on average 1.7857142857142858) internal successors, (50), 29 states have internal predecessors, (50), 14 states have call successors, (15), 8 states have call predecessors, (15), 10 states have return successors, (14), 7 states have call predecessors, (14), 14 states have call successors, (14) [2024-11-19 15:02:35,453 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:02:35,454 INFO L93 Difference]: Finished difference Result 66 states and 82 transitions. [2024-11-19 15:02:35,454 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 66 states and 82 transitions. [2024-11-19 15:02:35,455 INFO L131 ngComponentsAnalysis]: Automaton has 6 accepting balls. 37 [2024-11-19 15:02:35,458 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 66 states to 60 states and 73 transitions. [2024-11-19 15:02:35,458 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 60 [2024-11-19 15:02:35,458 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 60 [2024-11-19 15:02:35,459 INFO L73 IsDeterministic]: Start isDeterministic. Operand 60 states and 73 transitions. [2024-11-19 15:02:35,459 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:02:35,459 INFO L218 hiAutomatonCegarLoop]: Abstraction has 60 states and 73 transitions. [2024-11-19 15:02:35,459 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 60 states and 73 transitions. [2024-11-19 15:02:35,462 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 60 to 60. [2024-11-19 15:02:35,462 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 60 states, 40 states have (on average 1.2) internal successors, (48), 43 states have internal predecessors, (48), 12 states have call successors, (12), 8 states have call predecessors, (12), 8 states have return successors, (13), 9 states have call predecessors, (13), 9 states have call successors, (13) [2024-11-19 15:02:35,466 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 60 states to 60 states and 73 transitions. [2024-11-19 15:02:35,467 INFO L240 hiAutomatonCegarLoop]: Abstraction has 60 states and 73 transitions. [2024-11-19 15:02:35,467 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2024-11-19 15:02:35,468 INFO L425 stractBuchiCegarLoop]: Abstraction has 60 states and 73 transitions. [2024-11-19 15:02:35,469 INFO L332 stractBuchiCegarLoop]: ======== Iteration 4 ============ [2024-11-19 15:02:35,469 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 60 states and 73 transitions. [2024-11-19 15:02:35,470 INFO L131 ngComponentsAnalysis]: Automaton has 6 accepting balls. 37 [2024-11-19 15:02:35,472 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:02:35,472 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:02:35,473 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:02:35,473 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:02:35,474 INFO L745 eck$LassoCheckResult]: Stem: 741#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 711#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 712#L139 call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 718#$Ultimate##0 [2024-11-19 15:02:35,474 INFO L747 eck$LassoCheckResult]: Loop: 718#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 720#L110 assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 706#L116 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 705#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 708#L90 assume #t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296;havoc #t~mem31;havoc #t~mem30;call write~int#4(0, ~c.base, ~c.offset, 4); 728#L96 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 729#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 738#L70 assume #t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296;havoc #t~mem27;havoc #t~mem26;call write~int#1(0, ~d.base, ~d.offset, 4); 714#L76 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 715#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 753#L50 assume #t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296;havoc #t~mem23;havoc #t~mem22;call write~int#2(0, ~e.base, ~e.offset, 4); 697#L56 call func_to_recursive_line_14_to_16_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 717#$Ultimate##0 ~uint32_max#1.base, ~uint32_max#1.offset := #in~uint32_max#1.base, #in~uint32_max#1.offset;~c#1.base, ~c#1.offset := #in~c#1.base, #in~c#1.offset;~b#1.base, ~b#1.offset := #in~b#1.base, #in~b#1.offset;~a#1.base, ~a#1.offset := #in~a#1.base, #in~a#1.offset;~e#1.base, ~e#1.offset := #in~e#1.base, #in~e#1.offset;~d#1.base, ~d#1.offset := #in~d#1.base, #in~d#1.offset;call #t~mem5#1 := read~int#2(~e#1.base, ~e#1.offset, 4);call #t~mem4#1 := read~int#6(~uint32_max#1.base, ~uint32_max#1.offset, 4); 721#L25 assume !(#t~mem5#1 % 4294967296 < (#t~mem4#1 - 1) % 4294967296);havoc #t~mem5#1;havoc #t~mem4#1; 733#L25-1 assume true; 736#func_to_recursive_line_14_to_16_0EXIT >#102#return; 737#L56-1 call #t~mem24 := read~int#1(~d.base, ~d.offset, 4);#t~pre25 := 1 + #t~mem24;call write~int#1(1 + #t~mem24, ~d.base, ~d.offset, 4);havoc #t~mem24;havoc #t~pre25; 713#L61 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 715#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 753#L50 assume !(#t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296);havoc #t~mem23;havoc #t~mem22; 752#L50-1 assume true; 751#func_to_recursive_line_13_to_14_0EXIT >#104#return; 750#L50-1 assume true; 749#func_to_recursive_line_13_to_14_0EXIT >#98#return; 748#L76-1 call #t~mem28 := read~int#4(~c.base, ~c.offset, 4);#t~pre29 := 1 + #t~mem28;call write~int#4(1 + #t~mem28, ~c.base, ~c.offset, 4);havoc #t~mem28;havoc #t~pre29; 724#L81 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 747#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 755#L70 assume !(#t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296);havoc #t~mem27;havoc #t~mem26; 727#L70-1 assume true; 723#func_to_recursive_line_12_to_13_0EXIT >#100#return; 725#L70-1 assume true; 746#func_to_recursive_line_12_to_13_0EXIT >#106#return; 726#L96-1 call #t~mem32 := read~int#3(~b.base, ~b.offset, 4);#t~pre33 := 1 + #t~mem32;call write~int#3(1 + #t~mem32, ~b.base, ~b.offset, 4);havoc #t~mem32;havoc #t~pre33; 707#L101 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 705#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 708#L90 assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 742#L90-1 assume true; 743#func_to_recursive_line_11_to_12_0EXIT >#108#return; 744#L90-1 assume true; 754#func_to_recursive_line_11_to_12_0EXIT >#112#return; 745#L116-1 call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 719#L121 call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 718#$Ultimate##0 [2024-11-19 15:02:35,475 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:35,475 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 4 times [2024-11-19 15:02:35,475 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:35,475 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2085491915] [2024-11-19 15:02:35,476 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2024-11-19 15:02:35,476 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:35,493 INFO L227 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2024-11-19 15:02:35,494 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:02:35,494 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:02:35,502 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:02:35,505 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:02:35,506 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:35,506 INFO L85 PathProgramCache]: Analyzing trace with hash -1754161005, now seen corresponding path program 1 times [2024-11-19 15:02:35,506 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:35,507 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1898892159] [2024-11-19 15:02:35,507 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:35,507 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:35,555 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:36,099 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 3 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 15:02:36,100 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:02:36,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1898892159] [2024-11-19 15:02:36,100 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1898892159] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:02:36,100 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1796395773] [2024-11-19 15:02:36,100 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:36,101 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:02:36,101 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:02:36,102 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:02:36,104 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2024-11-19 15:02:36,260 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:36,263 INFO L255 TraceCheckSpWp]: Trace formula consists of 616 conjuncts, 93 conjuncts are in the unsatisfiable core [2024-11-19 15:02:36,266 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:02:36,289 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:36,586 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:37,617 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 8 proven. 4 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2024-11-19 15:02:37,617 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:02:39,081 INFO L134 CoverageAnalysis]: Checked inductivity of 12 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 15:02:39,081 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1796395773] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:02:39,081 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:02:39,081 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 20, 16] total 43 [2024-11-19 15:02:39,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [310722595] [2024-11-19 15:02:39,082 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:02:39,082 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:02:39,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:02:39,082 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 43 interpolants. [2024-11-19 15:02:39,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=181, Invalid=1625, Unknown=0, NotChecked=0, Total=1806 [2024-11-19 15:02:39,083 INFO L87 Difference]: Start difference. First operand 60 states and 73 transitions. cyclomatic complexity: 19 Second operand has 43 states, 35 states have (on average 1.8857142857142857) internal successors, (66), 37 states have internal predecessors, (66), 19 states have call successors, (20), 9 states have call predecessors, (20), 12 states have return successors, (19), 10 states have call predecessors, (19), 19 states have call successors, (19) [2024-11-19 15:02:41,519 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:02:41,519 INFO L93 Difference]: Finished difference Result 95 states and 119 transitions. [2024-11-19 15:02:41,519 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 95 states and 119 transitions. [2024-11-19 15:02:41,521 INFO L131 ngComponentsAnalysis]: Automaton has 9 accepting balls. 52 [2024-11-19 15:02:41,522 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 95 states to 91 states and 113 transitions. [2024-11-19 15:02:41,523 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 91 [2024-11-19 15:02:41,523 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 91 [2024-11-19 15:02:41,523 INFO L73 IsDeterministic]: Start isDeterministic. Operand 91 states and 113 transitions. [2024-11-19 15:02:41,524 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:02:41,524 INFO L218 hiAutomatonCegarLoop]: Abstraction has 91 states and 113 transitions. [2024-11-19 15:02:41,524 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 91 states and 113 transitions. [2024-11-19 15:02:41,528 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 91 to 80. [2024-11-19 15:02:41,528 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 80 states, 52 states have (on average 1.1730769230769231) internal successors, (61), 56 states have internal predecessors, (61), 16 states have call successors, (16), 11 states have call predecessors, (16), 12 states have return successors, (22), 12 states have call predecessors, (22), 12 states have call successors, (22) [2024-11-19 15:02:41,529 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 80 states to 80 states and 99 transitions. [2024-11-19 15:02:41,529 INFO L240 hiAutomatonCegarLoop]: Abstraction has 80 states and 99 transitions. [2024-11-19 15:02:41,532 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2024-11-19 15:02:41,532 INFO L425 stractBuchiCegarLoop]: Abstraction has 80 states and 99 transitions. [2024-11-19 15:02:41,533 INFO L332 stractBuchiCegarLoop]: ======== Iteration 5 ============ [2024-11-19 15:02:41,534 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 80 states and 99 transitions. [2024-11-19 15:02:41,535 INFO L131 ngComponentsAnalysis]: Automaton has 8 accepting balls. 47 [2024-11-19 15:02:41,535 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:02:41,535 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:02:41,536 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:02:41,537 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:02:41,538 INFO L745 eck$LassoCheckResult]: Stem: 1250#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 1216#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 1217#L139 call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 1223#$Ultimate##0 [2024-11-19 15:02:41,538 INFO L747 eck$LassoCheckResult]: Loop: 1223#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1225#L110 assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 1212#L116 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1211#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1214#L90 assume #t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296;havoc #t~mem31;havoc #t~mem30;call write~int#4(0, ~c.base, ~c.offset, 4); 1236#L96 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1237#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1268#L70 assume #t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296;havoc #t~mem27;havoc #t~mem26;call write~int#1(0, ~d.base, ~d.offset, 4); 1219#L76 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1263#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1265#L50 assume #t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296;havoc #t~mem23;havoc #t~mem22;call write~int#2(0, ~e.base, ~e.offset, 4); 1201#L56 call func_to_recursive_line_14_to_16_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1229#$Ultimate##0 ~uint32_max#1.base, ~uint32_max#1.offset := #in~uint32_max#1.base, #in~uint32_max#1.offset;~c#1.base, ~c#1.offset := #in~c#1.base, #in~c#1.offset;~b#1.base, ~b#1.offset := #in~b#1.base, #in~b#1.offset;~a#1.base, ~a#1.offset := #in~a#1.base, #in~a#1.offset;~e#1.base, ~e#1.offset := #in~e#1.base, #in~e#1.offset;~d#1.base, ~d#1.offset := #in~d#1.base, #in~d#1.offset;call #t~mem5#1 := read~int#2(~e#1.base, ~e#1.offset, 4);call #t~mem4#1 := read~int#6(~uint32_max#1.base, ~uint32_max#1.offset, 4); 1257#L25 assume #t~mem5#1 % 4294967296 < (#t~mem4#1 - 1) % 4294967296;havoc #t~mem5#1;havoc #t~mem4#1;call #t~mem6#1 := read~int#5(~a#1.base, ~a#1.offset, 4);call #t~mem7#1 := read~int#3(~b#1.base, ~b#1.offset, 4);#t~short10#1 := #t~mem6#1 % 4294967296 == #t~mem7#1 % 4294967296; 1249#L29 assume !#t~short10#1; 1200#L29-2 #t~short13#1 := #t~short10#1; 1203#L29-3 assume #t~short13#1;call #t~mem11#1 := read~int#4(~c#1.base, ~c#1.offset, 4);call #t~mem12#1 := read~int#1(~d#1.base, ~d#1.offset, 4);#t~short13#1 := #t~mem11#1 % 4294967296 == #t~mem12#1 % 4294967296; 1233#L29-5 #t~short16#1 := #t~short13#1; 1204#L29-6 assume !#t~short16#1; 1205#L29-8 #t~short19#1 := #t~short16#1; 1218#L29-9 assume !#t~short19#1; 1222#L29-11 assume !#t~short19#1;havoc #t~mem6#1;havoc #t~mem7#1;havoc #t~mem8#1;havoc #t~mem9#1;havoc #t~short10#1;havoc #t~mem11#1;havoc #t~mem12#1;havoc #t~short13#1;havoc #t~mem14#1;havoc #t~mem15#1;havoc #t~short16#1;havoc #t~mem18#1;havoc #t~mem17#1;havoc #t~short19#1; 1215#L29-13 call #t~mem20#1 := read~int#2(~e#1.base, ~e#1.offset, 4);#t~pre21#1 := 1 + #t~mem20#1;call write~int#2(1 + #t~mem20#1, ~e#1.base, ~e#1.offset, 4);havoc #t~mem20#1;havoc #t~pre21#1; 1202#L41 call func_to_recursive_line_14_to_16_0(~uint32_max#1.base, ~uint32_max#1.offset, ~c#1.base, ~c#1.offset, ~b#1.base, ~b#1.offset, ~a#1.base, ~a#1.offset, ~e#1.base, ~e#1.offset, ~d#1.base, ~d#1.offset);< 1229#$Ultimate##0 ~uint32_max#1.base, ~uint32_max#1.offset := #in~uint32_max#1.base, #in~uint32_max#1.offset;~c#1.base, ~c#1.offset := #in~c#1.base, #in~c#1.offset;~b#1.base, ~b#1.offset := #in~b#1.base, #in~b#1.offset;~a#1.base, ~a#1.offset := #in~a#1.base, #in~a#1.offset;~e#1.base, ~e#1.offset := #in~e#1.base, #in~e#1.offset;~d#1.base, ~d#1.offset := #in~d#1.base, #in~d#1.offset;call #t~mem5#1 := read~int#2(~e#1.base, ~e#1.offset, 4);call #t~mem4#1 := read~int#6(~uint32_max#1.base, ~uint32_max#1.offset, 4); 1257#L25 assume !(#t~mem5#1 % 4294967296 < (#t~mem4#1 - 1) % 4294967296);havoc #t~mem5#1;havoc #t~mem4#1; 1258#L25-1 assume true; 1273#func_to_recursive_line_14_to_16_0EXIT >#110#return; 1271#L25-1 assume true; 1270#func_to_recursive_line_14_to_16_0EXIT >#102#return; 1267#L56-1 call #t~mem24 := read~int#1(~d.base, ~d.offset, 4);#t~pre25 := 1 + #t~mem24;call write~int#1(1 + #t~mem24, ~d.base, ~d.offset, 4);havoc #t~mem24;havoc #t~pre25; 1220#L61 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1263#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1265#L50 assume !(#t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296);havoc #t~mem23;havoc #t~mem22; 1266#L50-1 assume true; 1269#func_to_recursive_line_13_to_14_0EXIT >#104#return; 1262#L50-1 assume true; 1261#func_to_recursive_line_13_to_14_0EXIT >#98#return; 1260#L76-1 call #t~mem28 := read~int#4(~c.base, ~c.offset, 4);#t~pre29 := 1 + #t~mem28;call write~int#4(1 + #t~mem28, ~c.base, ~c.offset, 4);havoc #t~mem28;havoc #t~pre29; 1231#L81 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1259#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1277#L70 assume !(#t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296);havoc #t~mem27;havoc #t~mem26; 1235#L70-1 assume true; 1230#func_to_recursive_line_12_to_13_0EXIT >#100#return; 1232#L70-1 assume true; 1256#func_to_recursive_line_12_to_13_0EXIT >#106#return; 1234#L96-1 call #t~mem32 := read~int#3(~b.base, ~b.offset, 4);#t~pre33 := 1 + #t~mem32;call write~int#3(1 + #t~mem32, ~b.base, ~b.offset, 4);havoc #t~mem32;havoc #t~pre33; 1213#L101 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1211#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1214#L90 assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 1252#L90-1 assume true; 1253#func_to_recursive_line_11_to_12_0EXIT >#108#return; 1254#L90-1 assume true; 1278#func_to_recursive_line_11_to_12_0EXIT >#112#return; 1255#L116-1 call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 1224#L121 call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1223#$Ultimate##0 [2024-11-19 15:02:41,539 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:41,541 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 5 times [2024-11-19 15:02:41,542 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:41,542 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1875818520] [2024-11-19 15:02:41,542 INFO L93 rtionOrderModulation]: Changing assertion order to INSIDE_LOOP_FIRST1 [2024-11-19 15:02:41,542 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:41,555 INFO L227 tOrderPrioritization]: Assert order INSIDE_LOOP_FIRST1 issued 1 check-sat command(s) [2024-11-19 15:02:41,556 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:02:41,556 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:02:41,563 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:02:41,569 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:02:41,571 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:41,572 INFO L85 PathProgramCache]: Analyzing trace with hash 198549804, now seen corresponding path program 1 times [2024-11-19 15:02:41,572 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:41,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1810521146] [2024-11-19 15:02:41,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:41,572 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:41,593 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:41,650 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 8 proven. 0 refuted. 0 times theorem prover too weak. 8 trivial. 0 not checked. [2024-11-19 15:02:41,651 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:02:41,651 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1810521146] [2024-11-19 15:02:41,651 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1810521146] provided 1 perfect and 0 imperfect interpolant sequences [2024-11-19 15:02:41,651 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2024-11-19 15:02:41,651 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2024-11-19 15:02:41,651 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [921240866] [2024-11-19 15:02:41,651 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2024-11-19 15:02:41,652 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:02:41,652 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:02:41,652 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2024-11-19 15:02:41,652 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2024-11-19 15:02:41,652 INFO L87 Difference]: Start difference. First operand 80 states and 99 transitions. cyclomatic complexity: 27 Second operand has 4 states, 4 states have (on average 8.75) internal successors, (35), 4 states have internal predecessors, (35), 2 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (8), 1 states have call predecessors, (8), 2 states have call successors, (8) [2024-11-19 15:02:41,669 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2024-11-19 15:02:41,669 INFO L93 Difference]: Finished difference Result 83 states and 102 transitions. [2024-11-19 15:02:41,669 INFO L82 GeneralOperation]: Start removeNonLiveStates. Operand 83 states and 102 transitions. [2024-11-19 15:02:41,670 INFO L131 ngComponentsAnalysis]: Automaton has 8 accepting balls. 50 [2024-11-19 15:02:41,673 INFO L88 GeneralOperation]: Finished removeNonLiveStates. Reduced from 83 states to 83 states and 102 transitions. [2024-11-19 15:02:41,674 INFO L87 BuchiClosureNwa]: Accepting states before buchiClosure: 83 [2024-11-19 15:02:41,674 INFO L106 BuchiClosureNwa]: Accepting states after buchiClosure: 83 [2024-11-19 15:02:41,674 INFO L73 IsDeterministic]: Start isDeterministic. Operand 83 states and 102 transitions. [2024-11-19 15:02:41,675 INFO L80 IsDeterministic]: Finished isDeterministic. Operand is deterministic. [2024-11-19 15:02:41,675 INFO L218 hiAutomatonCegarLoop]: Abstraction has 83 states and 102 transitions. [2024-11-19 15:02:41,675 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 83 states and 102 transitions. [2024-11-19 15:02:41,681 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 83 to 82. [2024-11-19 15:02:41,681 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 82 states, 54 states have (on average 1.1666666666666667) internal successors, (63), 58 states have internal predecessors, (63), 16 states have call successors, (16), 11 states have call predecessors, (16), 12 states have return successors, (22), 12 states have call predecessors, (22), 12 states have call successors, (22) [2024-11-19 15:02:41,682 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 82 states to 82 states and 101 transitions. [2024-11-19 15:02:41,682 INFO L240 hiAutomatonCegarLoop]: Abstraction has 82 states and 101 transitions. [2024-11-19 15:02:41,685 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2024-11-19 15:02:41,686 INFO L425 stractBuchiCegarLoop]: Abstraction has 82 states and 101 transitions. [2024-11-19 15:02:41,686 INFO L332 stractBuchiCegarLoop]: ======== Iteration 6 ============ [2024-11-19 15:02:41,686 INFO L72 BuchiIsEmpty]: Start buchiIsEmpty. Operand 82 states and 101 transitions. [2024-11-19 15:02:41,687 INFO L131 ngComponentsAnalysis]: Automaton has 8 accepting balls. 49 [2024-11-19 15:02:41,687 INFO L87 BuchiIsEmpty]: Finished buchiIsEmpty Result is false [2024-11-19 15:02:41,687 INFO L119 BuchiIsEmpty]: Starting construction of run [2024-11-19 15:02:41,688 INFO L148 hiAutomatonCegarLoop]: Counterexample stem histogram [1, 1, 1] [2024-11-19 15:02:41,688 INFO L149 hiAutomatonCegarLoop]: Counterexample loop histogram [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2024-11-19 15:02:41,688 INFO L745 eck$LassoCheckResult]: Stem: 1422#$Ultimate##0 assume { :begin_inline_ULTIMATE.init } true;assume 0 == #valid[0];assume 0 < #StackHeapBarrier;call #Ultimate.allocInit(2, 1);call write~init~int#0(48, 1, 0, 1);call write~init~int#0(0, 1, 1, 1);call #Ultimate.allocInit(14, 2);call #Ultimate.allocInit(12, 3); 1384#L-1 assume { :end_inline_ULTIMATE.init } true;assume { :begin_inline_main } true;havoc main_#res#1;havoc main_~#a~0#1.base, main_~#a~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset;call main_~#a~0#1.base, main_~#a~0#1.offset := #Ultimate.allocOnStack(4);call main_~#b~0#1.base, main_~#b~0#1.offset := #Ultimate.allocOnStack(4);call main_~#c~0#1.base, main_~#c~0#1.offset := #Ultimate.allocOnStack(4);call main_~#d~0#1.base, main_~#d~0#1.offset := #Ultimate.allocOnStack(4);call main_~#e~0#1.base, main_~#e~0#1.offset := #Ultimate.allocOnStack(4);call main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset := #Ultimate.allocOnStack(4);call write~int#6(4294967295, main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, 4);call write~int#5(0, main_~#a~0#1.base, main_~#a~0#1.offset, 4); 1385#L139 call func_to_recursive_line_10_to_11_0(main_~#uint32_max~0#1.base, main_~#uint32_max~0#1.offset, main_~#c~0#1.base, main_~#c~0#1.offset, main_~#b~0#1.base, main_~#b~0#1.offset, main_~#a~0#1.base, main_~#a~0#1.offset, main_~#e~0#1.base, main_~#e~0#1.offset, main_~#d~0#1.base, main_~#d~0#1.offset);< 1393#$Ultimate##0 [2024-11-19 15:02:41,690 INFO L747 eck$LassoCheckResult]: Loop: 1393#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem35 := read~int#5(~a.base, ~a.offset, 4);call #t~mem34 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1395#L110 assume #t~mem35 % 4294967296 < (#t~mem34 - 1) % 4294967296;havoc #t~mem35;havoc #t~mem34;call write~int#3(0, ~b.base, ~b.offset, 4); 1378#L116 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1376#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1379#L90 assume #t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296;havoc #t~mem31;havoc #t~mem30;call write~int#4(0, ~c.base, ~c.offset, 4); 1405#L96 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1406#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1436#L70 assume #t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296;havoc #t~mem27;havoc #t~mem26;call write~int#1(0, ~d.base, ~d.offset, 4); 1389#L76 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1435#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1437#L50 assume #t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296;havoc #t~mem23;havoc #t~mem22;call write~int#2(0, ~e.base, ~e.offset, 4); 1371#L56 call func_to_recursive_line_14_to_16_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1399#$Ultimate##0 ~uint32_max#1.base, ~uint32_max#1.offset := #in~uint32_max#1.base, #in~uint32_max#1.offset;~c#1.base, ~c#1.offset := #in~c#1.base, #in~c#1.offset;~b#1.base, ~b#1.offset := #in~b#1.base, #in~b#1.offset;~a#1.base, ~a#1.offset := #in~a#1.base, #in~a#1.offset;~e#1.base, ~e#1.offset := #in~e#1.base, #in~e#1.offset;~d#1.base, ~d#1.offset := #in~d#1.base, #in~d#1.offset;call #t~mem5#1 := read~int#2(~e#1.base, ~e#1.offset, 4);call #t~mem4#1 := read~int#6(~uint32_max#1.base, ~uint32_max#1.offset, 4); 1431#L25 assume #t~mem5#1 % 4294967296 < (#t~mem4#1 - 1) % 4294967296;havoc #t~mem5#1;havoc #t~mem4#1;call #t~mem6#1 := read~int#5(~a#1.base, ~a#1.offset, 4);call #t~mem7#1 := read~int#3(~b#1.base, ~b#1.offset, 4);#t~short10#1 := #t~mem6#1 % 4294967296 == #t~mem7#1 % 4294967296; 1420#L29 assume #t~short10#1;call #t~mem8#1 := read~int#3(~b#1.base, ~b#1.offset, 4);call #t~mem9#1 := read~int#4(~c#1.base, ~c#1.offset, 4);#t~short10#1 := #t~mem8#1 % 4294967296 == #t~mem9#1 % 4294967296; 1370#L29-2 #t~short13#1 := #t~short10#1; 1373#L29-3 assume #t~short13#1;call #t~mem11#1 := read~int#4(~c#1.base, ~c#1.offset, 4);call #t~mem12#1 := read~int#1(~d#1.base, ~d#1.offset, 4);#t~short13#1 := #t~mem11#1 % 4294967296 == #t~mem12#1 % 4294967296; 1400#L29-5 #t~short16#1 := #t~short13#1; 1374#L29-6 assume !#t~short16#1; 1375#L29-8 #t~short19#1 := #t~short16#1; 1386#L29-9 assume !#t~short19#1; 1392#L29-11 assume !#t~short19#1;havoc #t~mem6#1;havoc #t~mem7#1;havoc #t~mem8#1;havoc #t~mem9#1;havoc #t~short10#1;havoc #t~mem11#1;havoc #t~mem12#1;havoc #t~short13#1;havoc #t~mem14#1;havoc #t~mem15#1;havoc #t~short16#1;havoc #t~mem18#1;havoc #t~mem17#1;havoc #t~short19#1; 1383#L29-13 call #t~mem20#1 := read~int#2(~e#1.base, ~e#1.offset, 4);#t~pre21#1 := 1 + #t~mem20#1;call write~int#2(1 + #t~mem20#1, ~e#1.base, ~e#1.offset, 4);havoc #t~mem20#1;havoc #t~pre21#1; 1372#L41 call func_to_recursive_line_14_to_16_0(~uint32_max#1.base, ~uint32_max#1.offset, ~c#1.base, ~c#1.offset, ~b#1.base, ~b#1.offset, ~a#1.base, ~a#1.offset, ~e#1.base, ~e#1.offset, ~d#1.base, ~d#1.offset);< 1399#$Ultimate##0 ~uint32_max#1.base, ~uint32_max#1.offset := #in~uint32_max#1.base, #in~uint32_max#1.offset;~c#1.base, ~c#1.offset := #in~c#1.base, #in~c#1.offset;~b#1.base, ~b#1.offset := #in~b#1.base, #in~b#1.offset;~a#1.base, ~a#1.offset := #in~a#1.base, #in~a#1.offset;~e#1.base, ~e#1.offset := #in~e#1.base, #in~e#1.offset;~d#1.base, ~d#1.offset := #in~d#1.base, #in~d#1.offset;call #t~mem5#1 := read~int#2(~e#1.base, ~e#1.offset, 4);call #t~mem4#1 := read~int#6(~uint32_max#1.base, ~uint32_max#1.offset, 4); 1431#L25 assume !(#t~mem5#1 % 4294967296 < (#t~mem4#1 - 1) % 4294967296);havoc #t~mem5#1;havoc #t~mem4#1; 1432#L25-1 assume true; 1443#func_to_recursive_line_14_to_16_0EXIT >#110#return; 1442#L25-1 assume true; 1441#func_to_recursive_line_14_to_16_0EXIT >#102#return; 1439#L56-1 call #t~mem24 := read~int#1(~d.base, ~d.offset, 4);#t~pre25 := 1 + #t~mem24;call write~int#1(1 + #t~mem24, ~d.base, ~d.offset, 4);havoc #t~mem24;havoc #t~pre25; 1388#L61 call func_to_recursive_line_13_to_14_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1435#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem23 := read~int#1(~d.base, ~d.offset, 4);call #t~mem22 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1437#L50 assume !(#t~mem23 % 4294967296 < (#t~mem22 - 1) % 4294967296);havoc #t~mem23;havoc #t~mem22; 1438#L50-1 assume true; 1440#func_to_recursive_line_13_to_14_0EXIT >#104#return; 1434#L50-1 assume true; 1433#func_to_recursive_line_13_to_14_0EXIT >#98#return; 1430#L76-1 call #t~mem28 := read~int#4(~c.base, ~c.offset, 4);#t~pre29 := 1 + #t~mem28;call write~int#4(1 + #t~mem28, ~c.base, ~c.offset, 4);havoc #t~mem28;havoc #t~pre29; 1402#L81 call func_to_recursive_line_12_to_13_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1429#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem27 := read~int#4(~c.base, ~c.offset, 4);call #t~mem26 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1444#L70 assume !(#t~mem27 % 4294967296 < (#t~mem26 - 1) % 4294967296);havoc #t~mem27;havoc #t~mem26; 1407#L70-1 assume true; 1401#func_to_recursive_line_12_to_13_0EXIT >#100#return; 1403#L70-1 assume true; 1428#func_to_recursive_line_12_to_13_0EXIT >#106#return; 1404#L96-1 call #t~mem32 := read~int#3(~b.base, ~b.offset, 4);#t~pre33 := 1 + #t~mem32;call write~int#3(1 + #t~mem32, ~b.base, ~b.offset, 4);havoc #t~mem32;havoc #t~pre33; 1377#L101 call func_to_recursive_line_11_to_12_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1376#$Ultimate##0 ~uint32_max.base, ~uint32_max.offset := #in~uint32_max.base, #in~uint32_max.offset;~c.base, ~c.offset := #in~c.base, #in~c.offset;~b.base, ~b.offset := #in~b.base, #in~b.offset;~a.base, ~a.offset := #in~a.base, #in~a.offset;~e.base, ~e.offset := #in~e.base, #in~e.offset;~d.base, ~d.offset := #in~d.base, #in~d.offset;call #t~mem31 := read~int#3(~b.base, ~b.offset, 4);call #t~mem30 := read~int#6(~uint32_max.base, ~uint32_max.offset, 4); 1379#L90 assume !(#t~mem31 % 4294967296 < (#t~mem30 - 1) % 4294967296);havoc #t~mem31;havoc #t~mem30; 1423#L90-1 assume true; 1424#func_to_recursive_line_11_to_12_0EXIT >#108#return; 1425#L90-1 assume true; 1427#func_to_recursive_line_11_to_12_0EXIT >#112#return; 1426#L116-1 call #t~mem36 := read~int#5(~a.base, ~a.offset, 4);#t~pre37 := 1 + #t~mem36;call write~int#5(1 + #t~mem36, ~a.base, ~a.offset, 4);havoc #t~mem36;havoc #t~pre37; 1394#L121 call func_to_recursive_line_10_to_11_0(~uint32_max.base, ~uint32_max.offset, ~c.base, ~c.offset, ~b.base, ~b.offset, ~a.base, ~a.offset, ~e.base, ~e.offset, ~d.base, ~d.offset);< 1393#$Ultimate##0 [2024-11-19 15:02:41,690 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:41,691 INFO L85 PathProgramCache]: Analyzing trace with hash 118256, now seen corresponding path program 6 times [2024-11-19 15:02:41,691 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:41,691 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1806780451] [2024-11-19 15:02:41,691 INFO L93 rtionOrderModulation]: Changing assertion order to MIX_INSIDE_OUTSIDE [2024-11-19 15:02:41,691 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:41,704 INFO L227 tOrderPrioritization]: Assert order MIX_INSIDE_OUTSIDE issued 1 check-sat command(s) [2024-11-19 15:02:41,704 INFO L228 tOrderPrioritization]: Conjunction of SSA is sat [2024-11-19 15:02:41,705 INFO L356 TraceCheck]: Trace is feasible, we will do another trace check, this time with branch encoders. [2024-11-19 15:02:41,711 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is sat [2024-11-19 15:02:41,714 INFO L130 FreeRefinementEngine]: Strategy CAMEL found a feasible trace [2024-11-19 15:02:41,714 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2024-11-19 15:02:41,714 INFO L85 PathProgramCache]: Analyzing trace with hash -49596690, now seen corresponding path program 1 times [2024-11-19 15:02:41,714 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2024-11-19 15:02:41,715 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1686792134] [2024-11-19 15:02:41,715 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:41,715 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2024-11-19 15:02:41,765 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:42,626 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 15:02:42,627 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2024-11-19 15:02:42,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1686792134] [2024-11-19 15:02:42,627 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1686792134] provided 0 perfect and 1 imperfect interpolant sequences [2024-11-19 15:02:42,627 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1169515020] [2024-11-19 15:02:42,627 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2024-11-19 15:02:42,627 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2024-11-19 15:02:42,627 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2024-11-19 15:02:42,629 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2024-11-19 15:02:42,631 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2024-11-19 15:02:42,781 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2024-11-19 15:02:42,785 INFO L255 TraceCheckSpWp]: Trace formula consists of 736 conjuncts, 73 conjuncts are in the unsatisfiable core [2024-11-19 15:02:42,815 INFO L278 TraceCheckSpWp]: Computing forward predicates... [2024-11-19 15:02:42,823 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:42,839 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 1 stores, 0 select indices, 0 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 0 new quantified variables, introduced 0 case distinctions, treesize of input 11 treesize of output 7 [2024-11-19 15:02:43,141 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2024-11-19 15:02:43,247 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 5 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2024-11-19 15:02:43,247 INFO L311 TraceCheckSpWp]: Computing backward predicates... [2024-11-19 15:02:44,173 INFO L378 Elim1Store]: Elim1 eliminated variable of array dimension 2, 0 stores, 1 select indices, 1 select index equivalence classes, 0 disjoint index pairs (out of 0 index pairs), introduced 1 new quantified variables, introduced 0 case distinctions, treesize of input 16 treesize of output 12 [2024-11-19 15:03:10,185 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 8 proven. 5 refuted. 0 times theorem prover too weak. 3 trivial. 0 not checked. [2024-11-19 15:03:10,185 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1169515020] provided 0 perfect and 2 imperfect interpolant sequences [2024-11-19 15:03:10,185 INFO L185 FreeRefinementEngine]: Found 0 perfect and 3 imperfect interpolant sequences. [2024-11-19 15:03:10,185 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [18, 17, 14] total 35 [2024-11-19 15:03:10,185 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [151487546] [2024-11-19 15:03:10,185 INFO L85 oduleStraightlineAll]: Using 3 imperfect interpolants to construct interpolant automaton [2024-11-19 15:03:10,186 INFO L762 eck$LassoCheckResult]: loop already infeasible [2024-11-19 15:03:10,186 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2024-11-19 15:03:10,186 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 35 interpolants. [2024-11-19 15:03:10,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=113, Invalid=1074, Unknown=3, NotChecked=0, Total=1190 [2024-11-19 15:03:10,188 INFO L87 Difference]: Start difference. First operand 82 states and 101 transitions. cyclomatic complexity: 27 Second operand has 35 states, 31 states have (on average 2.2903225806451615) internal successors, (71), 29 states have internal predecessors, (71), 16 states have call successors, (19), 7 states have call predecessors, (19), 9 states have return successors, (21), 11 states have call predecessors, (21), 16 states have call successors, (21) [2024-11-19 15:03:22,487 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 12.04s for a HTC check with result UNKNOWN. Formula has sorts [Array, Bool, Int], hasArrays=true, hasNonlinArith=false, quantifiers [0]