./Ultimate.py --spec ../sv-benchmarks/c/properties/unreach-call.prp --file ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c --full-output --architecture 32bit -------------------------------------------------------------------------------- Checking for ERROR reachability Using default analysis Version 551b0097 Calling Ultimate with: /root/.sdkman/candidates/java/21.0.5-tem/bin/java -Dosgi.configuration.area=/storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/config -Xmx15G -Xms4m -jar /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/plugins/org.eclipse.equinox.launcher_1.6.800.v20240513-1750.jar -data @noDefault -ultimatedata /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data -tc /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/AutomizerReach.xml -i ../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c -s /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf --cacsl2boogietranslator.entry.function main --witnessprinter.witness.directory /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux --witnessprinter.witness.filename witness --witnessprinter.write.witness.besides.input.file false --witnessprinter.graph.data.specification CHECK( init(main()), LTL(G ! call(reach_error())) ) --witnessprinter.graph.data.producer Automizer --witnessprinter.graph.data.architecture 32bit --witnessprinter.graph.data.programhash b2a54f54b02d2bb65a6f46eeae11edba1907f4f082d2aaa313102e422e7e6122 --- Real Ultimate output --- This is Ultimate 0.3.0-?-551b009-m [2025-01-09 03:37:10,081 INFO L188 SettingsManager]: Resetting all preferences to default values... [2025-01-09 03:37:10,122 INFO L114 SettingsManager]: Loading settings from /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/config/svcomp-Reach-32bit-Automizer_Default.epf [2025-01-09 03:37:10,130 WARN L101 SettingsManager]: Preference file contains the following unknown settings: [2025-01-09 03:37:10,133 WARN L103 SettingsManager]: * de.uni_freiburg.informatik.ultimate.core.Log level for class [2025-01-09 03:37:10,162 INFO L130 SettingsManager]: Preferences different from defaults after loading the file: [2025-01-09 03:37:10,162 INFO L151 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2025-01-09 03:37:10,162 INFO L153 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2025-01-09 03:37:10,162 INFO L151 SettingsManager]: Preferences of Boogie Preprocessor differ from their defaults: [2025-01-09 03:37:10,162 INFO L153 SettingsManager]: * Use memory slicer=true [2025-01-09 03:37:10,163 INFO L151 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2025-01-09 03:37:10,163 INFO L153 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2025-01-09 03:37:10,163 INFO L151 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2025-01-09 03:37:10,163 INFO L153 SettingsManager]: * Create parallel compositions if possible=false [2025-01-09 03:37:10,163 INFO L153 SettingsManager]: * Use SBE=true [2025-01-09 03:37:10,163 INFO L151 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2025-01-09 03:37:10,163 INFO L153 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2025-01-09 03:37:10,163 INFO L153 SettingsManager]: * sizeof long=4 [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * Overapproximate operations on floating types=true [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * sizeof POINTER=4 [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * Check division by zero=IGNORE [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * sizeof long double=12 [2025-01-09 03:37:10,164 INFO L153 SettingsManager]: * Check if freed pointer was valid=false [2025-01-09 03:37:10,167 INFO L153 SettingsManager]: * Behaviour of calls to undefined functions=OVERAPPROXIMATE_BEHAVIOUR [2025-01-09 03:37:10,167 INFO L153 SettingsManager]: * Use constant arrays=true [2025-01-09 03:37:10,168 INFO L151 SettingsManager]: Preferences of IcfgBuilder differ from their defaults: [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:37:10,168 INFO L151 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Size of a code block=SequenceOfStatements [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Only consider context switches at boundaries of atomic blocks=true [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * SMT solver=External_DefaultMode [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:37:10,168 INFO L151 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Compute procedure contracts=false [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopHeads [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Trace refinement strategy=CAMEL [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Apply one-shot large block encoding in concurrent analysis=false [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Automaton type used in concurrency analysis=PETRI_NET [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Order on configurations for Petri net unfoldings=DBO [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2025-01-09 03:37:10,168 INFO L153 SettingsManager]: * Looper check in Petri net analysis=SEMANTIC Applying setting for plugin de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator: Entry function -> main Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness directory -> /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Witness filename -> witness Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Write witness besides input file -> false Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data specification -> CHECK( init(main()), LTL(G ! call(reach_error())) ) Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data producer -> Automizer Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data architecture -> 32bit Applying setting for plugin de.uni_freiburg.informatik.ultimate.witnessprinter: Graph data programhash -> b2a54f54b02d2bb65a6f46eeae11edba1907f4f082d2aaa313102e422e7e6122 [2025-01-09 03:37:10,428 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2025-01-09 03:37:10,436 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2025-01-09 03:37:10,438 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2025-01-09 03:37:10,439 INFO L270 PluginConnector]: Initializing CDTParser... [2025-01-09 03:37:10,439 INFO L274 PluginConnector]: CDTParser initialized [2025-01-09 03:37:10,440 INFO L431 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c [2025-01-09 03:37:11,560 INFO L533 CDTParser]: Created temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/ed17743fb/3a2e7743aa5543ab97f49ed51385c035/FLAGa51ac4d25 [2025-01-09 03:37:11,832 INFO L384 CDTParser]: Found 1 translation units. [2025-01-09 03:37:11,834 INFO L180 CDTParser]: Scanning /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c [2025-01-09 03:37:11,855 INFO L427 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/ed17743fb/3a2e7743aa5543ab97f49ed51385c035/FLAGa51ac4d25 [2025-01-09 03:37:12,163 INFO L435 CDTParser]: Successfully deleted /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/data/ed17743fb/3a2e7743aa5543ab97f49ed51385c035 [2025-01-09 03:37:12,166 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2025-01-09 03:37:12,167 INFO L133 ToolchainWalker]: Walking toolchain with 6 elements. [2025-01-09 03:37:12,168 INFO L112 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2025-01-09 03:37:12,168 INFO L270 PluginConnector]: Initializing CACSL2BoogieTranslator... [2025-01-09 03:37:12,171 INFO L274 PluginConnector]: CACSL2BoogieTranslator initialized [2025-01-09 03:37:12,172 INFO L184 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,172 INFO L204 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4481a9af and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12, skipping insertion in model container [2025-01-09 03:37:12,173 INFO L184 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,183 INFO L175 MainTranslator]: Built tables and reachable declarations [2025-01-09 03:37:12,286 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c[458,471] [2025-01-09 03:37:12,300 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 03:37:12,307 INFO L200 MainTranslator]: Completed pre-run [2025-01-09 03:37:12,314 WARN L250 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate-jdk21/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/ps4-ll_valuebound5.c[458,471] [2025-01-09 03:37:12,318 INFO L210 PostProcessor]: Analyzing one entry point: main [2025-01-09 03:37:12,329 INFO L204 MainTranslator]: Completed translation [2025-01-09 03:37:12,330 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12 WrapperNode [2025-01-09 03:37:12,330 INFO L131 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2025-01-09 03:37:12,331 INFO L112 PluginConnector]: ------------------------Boogie Procedure Inliner---------------------------- [2025-01-09 03:37:12,331 INFO L270 PluginConnector]: Initializing Boogie Procedure Inliner... [2025-01-09 03:37:12,331 INFO L274 PluginConnector]: Boogie Procedure Inliner initialized [2025-01-09 03:37:12,335 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,339 INFO L184 PluginConnector]: Executing the observer Inliner from plugin Boogie Procedure Inliner for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,349 INFO L138 Inliner]: procedures = 14, calls = 11, calls flagged for inlining = 3, calls inlined = 3, statements flattened = 35 [2025-01-09 03:37:12,350 INFO L131 PluginConnector]: ------------------------ END Boogie Procedure Inliner---------------------------- [2025-01-09 03:37:12,351 INFO L112 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2025-01-09 03:37:12,351 INFO L270 PluginConnector]: Initializing Boogie Preprocessor... [2025-01-09 03:37:12,352 INFO L274 PluginConnector]: Boogie Preprocessor initialized [2025-01-09 03:37:12,356 INFO L184 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,357 INFO L184 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,357 INFO L184 PluginConnector]: Executing the observer MemorySlicer from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,367 INFO L175 MemorySlicer]: Split 2 memory accesses to 1 slices as follows [2]. 100 percent of accesses are in the largest equivalence class. The 2 initializations are split as follows [2]. The 0 writes are split as follows [0]. [2025-01-09 03:37:12,367 INFO L184 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,368 INFO L184 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,371 INFO L184 PluginConnector]: Executing the observer ReplaceArrayAssignments from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,371 INFO L184 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,373 INFO L184 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,374 INFO L184 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,374 INFO L184 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,376 INFO L131 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2025-01-09 03:37:12,377 INFO L112 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2025-01-09 03:37:12,378 INFO L270 PluginConnector]: Initializing RCFGBuilder... [2025-01-09 03:37:12,378 INFO L274 PluginConnector]: RCFGBuilder initialized [2025-01-09 03:37:12,379 INFO L184 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (1/1) ... [2025-01-09 03:37:12,382 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 [2025-01-09 03:37:12,391 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:37:12,405 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (exit command is (exit), workingDir is null) [2025-01-09 03:37:12,408 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Waiting until timeout for monitored process [2025-01-09 03:37:12,424 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2025-01-09 03:37:12,424 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int#0 [2025-01-09 03:37:12,424 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2025-01-09 03:37:12,424 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2025-01-09 03:37:12,424 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2025-01-09 03:37:12,424 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2025-01-09 03:37:12,459 INFO L234 CfgBuilder]: Building ICFG [2025-01-09 03:37:12,460 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2025-01-09 03:37:12,524 INFO L? ?]: Removed 7 outVars from TransFormulas that were not future-live. [2025-01-09 03:37:12,525 INFO L283 CfgBuilder]: Performing block encoding [2025-01-09 03:37:12,530 INFO L307 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2025-01-09 03:37:12,530 INFO L312 CfgBuilder]: Removed 1 assume(true) statements. [2025-01-09 03:37:12,530 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:37:12 BoogieIcfgContainer [2025-01-09 03:37:12,530 INFO L131 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2025-01-09 03:37:12,532 INFO L112 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2025-01-09 03:37:12,532 INFO L270 PluginConnector]: Initializing TraceAbstraction... [2025-01-09 03:37:12,535 INFO L274 PluginConnector]: TraceAbstraction initialized [2025-01-09 03:37:12,535 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 09.01 03:37:12" (1/3) ... [2025-01-09 03:37:12,536 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1db8b4f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 03:37:12, skipping insertion in model container [2025-01-09 03:37:12,537 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 09.01 03:37:12" (2/3) ... [2025-01-09 03:37:12,537 INFO L204 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@1db8b4f4 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 09.01 03:37:12, skipping insertion in model container [2025-01-09 03:37:12,537 INFO L184 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:37:12" (3/3) ... [2025-01-09 03:37:12,538 INFO L128 eAbstractionObserver]: Analyzing ICFG ps4-ll_valuebound5.c [2025-01-09 03:37:12,549 INFO L216 ceAbstractionStarter]: Automizer settings: Hoare:LoopHeads NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2025-01-09 03:37:12,550 INFO L151 ceAbstractionStarter]: Applying trace abstraction to ICFG ps4-ll_valuebound5.c that has 2 procedures, 18 locations, 1 initial locations, 1 loop locations, and 1 error locations. [2025-01-09 03:37:12,584 INFO L332 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2025-01-09 03:37:12,591 INFO L333 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mAutomataTypeConcurrency=PETRI_NET, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopHeads, mDumpOnlyReuseAutomata=false, mLimitTraceHistogram=0, mErrorLocTimeLimit=0, mLimitPathProgramCount=0, mCollectInterpolantStatistics=true, mHeuristicEmptinessCheck=false, mHeuristicEmptinessCheckAStarHeuristic=ZERO, mHeuristicEmptinessCheckAStarHeuristicRandomSeed=1337, mHeuristicEmptinessCheckSmtFeatureScoringMethod=DAGSIZE, mSMTFeatureExtraction=false, mSMTFeatureExtractionDumpPath=., mOverrideInterpolantAutomaton=false, mMcrInterpolantMethod=WP, mPorIndependenceSettings=[Lde.uni_freiburg.informatik.ultimate.lib.tracecheckerutils.partialorder.independence.IndependenceSettings;@1537ea8b, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2025-01-09 03:37:12,591 INFO L334 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2025-01-09 03:37:12,594 INFO L276 IsEmpty]: Start isEmpty. Operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 03:37:12,597 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-01-09 03:37:12,597 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:37:12,598 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:37:12,598 INFO L396 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:37:12,601 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:37:12,601 INFO L85 PathProgramCache]: Analyzing trace with hash 120200094, now seen corresponding path program 1 times [2025-01-09 03:37:12,606 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:37:12,606 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [986533040] [2025-01-09 03:37:12,607 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:12,607 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:37:12,648 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-09 03:37:12,656 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-09 03:37:12,657 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:12,657 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:37:12,683 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 03:37:12,683 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:37:12,683 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [986533040] [2025-01-09 03:37:12,684 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [986533040] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:37:12,684 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:37:12,684 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2025-01-09 03:37:12,685 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1754595766] [2025-01-09 03:37:12,685 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:37:12,687 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2025-01-09 03:37:12,687 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:37:12,698 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2025-01-09 03:37:12,699 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 03:37:12,700 INFO L87 Difference]: Start difference. First operand has 18 states, 13 states have (on average 1.3076923076923077) internal successors, (17), 13 states have internal predecessors, (17), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) Second operand has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 03:37:12,709 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:37:12,709 INFO L93 Difference]: Finished difference Result 33 states and 45 transitions. [2025-01-09 03:37:12,709 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2025-01-09 03:37:12,710 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-01-09 03:37:12,710 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:37:12,714 INFO L225 Difference]: With dead ends: 33 [2025-01-09 03:37:12,714 INFO L226 Difference]: Without dead ends: 14 [2025-01-09 03:37:12,716 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 2 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2025-01-09 03:37:12,717 INFO L435 NwaCegarLoop]: 20 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 0 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 20 SdHoareTripleChecker+Invalid, 0 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 0 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:37:12,718 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 20 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 0 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:37:12,726 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 14 states. [2025-01-09 03:37:12,733 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 14 to 14. [2025-01-09 03:37:12,733 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 14 states, 9 states have (on average 1.2222222222222223) internal successors, (11), 10 states have internal predecessors, (11), 3 states have call successors, (3), 1 states have call predecessors, (3), 1 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 03:37:12,735 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 14 states to 14 states and 16 transitions. [2025-01-09 03:37:12,736 INFO L78 Accepts]: Start accepts. Automaton has 14 states and 16 transitions. Word has length 8 [2025-01-09 03:37:12,736 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:37:12,736 INFO L471 AbstractCegarLoop]: Abstraction has 14 states and 16 transitions. [2025-01-09 03:37:12,737 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 3.5) internal successors, (7), 2 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 03:37:12,737 INFO L276 IsEmpty]: Start isEmpty. Operand 14 states and 16 transitions. [2025-01-09 03:37:12,737 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 9 [2025-01-09 03:37:12,737 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:37:12,737 INFO L218 NwaCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:37:12,738 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2025-01-09 03:37:12,738 INFO L396 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:37:12,738 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:37:12,738 INFO L85 PathProgramCache]: Analyzing trace with hash 177458396, now seen corresponding path program 1 times [2025-01-09 03:37:12,738 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:37:12,739 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1480838416] [2025-01-09 03:37:12,739 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:12,739 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:37:12,744 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-09 03:37:12,752 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-09 03:37:12,753 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:12,753 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:37:12,754 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1693755474] [2025-01-09 03:37:12,754 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:12,754 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:12,755 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:37:12,756 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 03:37:12,759 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2025-01-09 03:37:12,789 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 8 statements into 1 equivalence classes. [2025-01-09 03:37:12,808 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 8 of 8 statements. [2025-01-09 03:37:12,808 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:12,808 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:37:12,815 INFO L256 TraceCheckSpWp]: Trace formula consists of 43 conjuncts, 7 conjuncts are in the unsatisfiable core [2025-01-09 03:37:12,818 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:37:12,887 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 03:37:12,888 INFO L308 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2025-01-09 03:37:12,888 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:37:12,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1480838416] [2025-01-09 03:37:12,888 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:37:12,888 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1693755474] [2025-01-09 03:37:12,889 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1693755474] provided 1 perfect and 0 imperfect interpolant sequences [2025-01-09 03:37:12,889 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2025-01-09 03:37:12,889 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2025-01-09 03:37:12,889 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1650603203] [2025-01-09 03:37:12,889 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:37:12,890 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:37:12,890 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:37:12,890 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:37:12,890 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2025-01-09 03:37:12,891 INFO L87 Difference]: Start difference. First operand 14 states and 16 transitions. Second operand has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 03:37:12,930 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:37:12,930 INFO L93 Difference]: Finished difference Result 24 states and 28 transitions. [2025-01-09 03:37:12,931 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:37:12,931 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) Word has length 8 [2025-01-09 03:37:12,931 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:37:12,931 INFO L225 Difference]: With dead ends: 24 [2025-01-09 03:37:12,931 INFO L226 Difference]: Without dead ends: 20 [2025-01-09 03:37:12,932 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 8 GetRequests, 4 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2025-01-09 03:37:12,932 INFO L435 NwaCegarLoop]: 11 mSDtfsCounter, 4 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 22 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 24 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 22 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:37:12,932 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [6 Valid, 41 Invalid, 24 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 22 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:37:12,933 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 20 states. [2025-01-09 03:37:12,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 20 to 20. [2025-01-09 03:37:12,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 20 states, 13 states have (on average 1.1538461538461537) internal successors, (15), 14 states have internal predecessors, (15), 4 states have call successors, (4), 2 states have call predecessors, (4), 2 states have return successors, (3), 3 states have call predecessors, (3), 3 states have call successors, (3) [2025-01-09 03:37:12,936 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 20 states to 20 states and 22 transitions. [2025-01-09 03:37:12,937 INFO L78 Accepts]: Start accepts. Automaton has 20 states and 22 transitions. Word has length 8 [2025-01-09 03:37:12,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:37:12,937 INFO L471 AbstractCegarLoop]: Abstraction has 20 states and 22 transitions. [2025-01-09 03:37:12,937 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 1.75) internal successors, (7), 4 states have internal predecessors, (7), 1 states have call successors, (1), 1 states have call predecessors, (1), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 03:37:12,937 INFO L276 IsEmpty]: Start isEmpty. Operand 20 states and 22 transitions. [2025-01-09 03:37:12,937 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 15 [2025-01-09 03:37:12,937 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:37:12,937 INFO L218 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:37:12,944 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Ended with exit code 0 [2025-01-09 03:37:13,142 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:13,143 INFO L396 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:37:13,143 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:37:13,143 INFO L85 PathProgramCache]: Analyzing trace with hash -761501731, now seen corresponding path program 1 times [2025-01-09 03:37:13,143 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:37:13,143 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1478861006] [2025-01-09 03:37:13,143 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:13,144 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:37:13,149 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-01-09 03:37:13,159 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-01-09 03:37:13,160 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:13,160 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:37:13,160 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [727144043] [2025-01-09 03:37:13,161 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:13,161 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:13,161 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:37:13,163 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 03:37:13,164 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2025-01-09 03:37:13,184 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 14 statements into 1 equivalence classes. [2025-01-09 03:37:13,194 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 14 of 14 statements. [2025-01-09 03:37:13,194 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:13,195 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:37:13,195 INFO L256 TraceCheckSpWp]: Trace formula consists of 59 conjuncts, 11 conjuncts are in the unsatisfiable core [2025-01-09 03:37:13,197 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:37:13,235 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2025-01-09 03:37:13,235 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:37:13,288 INFO L134 CoverageAnalysis]: Checked inductivity of 3 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2025-01-09 03:37:13,288 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:37:13,288 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1478861006] [2025-01-09 03:37:13,289 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:37:13,290 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [727144043] [2025-01-09 03:37:13,290 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [727144043] provided 1 perfect and 1 imperfect interpolant sequences [2025-01-09 03:37:13,290 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2025-01-09 03:37:13,290 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2025-01-09 03:37:13,290 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1040481299] [2025-01-09 03:37:13,290 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2025-01-09 03:37:13,290 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2025-01-09 03:37:13,291 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:37:13,292 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2025-01-09 03:37:13,292 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2025-01-09 03:37:13,292 INFO L87 Difference]: Start difference. First operand 20 states and 22 transitions. Second operand has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 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) [2025-01-09 03:37:13,338 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:37:13,339 INFO L93 Difference]: Finished difference Result 26 states and 27 transitions. [2025-01-09 03:37:13,339 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2025-01-09 03:37:13,339 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 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) Word has length 14 [2025-01-09 03:37:13,339 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:37:13,340 INFO L225 Difference]: With dead ends: 26 [2025-01-09 03:37:13,340 INFO L226 Difference]: Without dead ends: 21 [2025-01-09 03:37:13,340 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 19 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2025-01-09 03:37:13,341 INFO L435 NwaCegarLoop]: 12 mSDtfsCounter, 4 mSDsluCounter, 29 mSDsCounter, 0 mSdLazyCounter, 16 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 41 SdHoareTripleChecker+Invalid, 17 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 16 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:37:13,342 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 41 Invalid, 17 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 16 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:37:13,343 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 21 states. [2025-01-09 03:37:13,348 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 21 to 21. [2025-01-09 03:37:13,349 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 21 states, 15 states have (on average 1.0666666666666667) internal successors, (16), 15 states have internal predecessors, (16), 3 states have call successors, (3), 3 states have call predecessors, (3), 2 states have return successors, (2), 2 states have call predecessors, (2), 2 states have call successors, (2) [2025-01-09 03:37:13,350 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 21 states to 21 states and 21 transitions. [2025-01-09 03:37:13,351 INFO L78 Accepts]: Start accepts. Automaton has 21 states and 21 transitions. Word has length 14 [2025-01-09 03:37:13,351 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:37:13,351 INFO L471 AbstractCegarLoop]: Abstraction has 21 states and 21 transitions. [2025-01-09 03:37:13,351 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.2) internal successors, (11), 4 states have internal predecessors, (11), 1 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) [2025-01-09 03:37:13,351 INFO L276 IsEmpty]: Start isEmpty. Operand 21 states and 21 transitions. [2025-01-09 03:37:13,351 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 21 [2025-01-09 03:37:13,352 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:37:13,352 INFO L218 NwaCegarLoop]: trace histogram [3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:37:13,357 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2025-01-09 03:37:13,552 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,3 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:13,552 INFO L396 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:37:13,553 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:37:13,553 INFO L85 PathProgramCache]: Analyzing trace with hash 256882650, now seen corresponding path program 1 times [2025-01-09 03:37:13,553 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:37:13,553 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2119861663] [2025-01-09 03:37:13,553 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:13,553 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:37:13,558 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-01-09 03:37:13,568 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-01-09 03:37:13,568 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:13,568 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:37:13,569 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [260025575] [2025-01-09 03:37:13,569 INFO L97 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2025-01-09 03:37:13,569 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:13,569 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:37:13,572 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 03:37:13,576 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2025-01-09 03:37:13,633 INFO L108 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY partitioned 20 statements into 1 equivalence classes. [2025-01-09 03:37:13,642 INFO L111 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) and asserted 20 of 20 statements. [2025-01-09 03:37:13,642 INFO L114 AnnotateAndAsserter]: Assert order NOT_INCREMENTALLY issued 1 check-sat command(s) [2025-01-09 03:37:13,643 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:37:13,643 INFO L256 TraceCheckSpWp]: Trace formula consists of 69 conjuncts, 12 conjuncts are in the unsatisfiable core [2025-01-09 03:37:13,644 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:37:13,704 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 03:37:13,704 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:37:13,778 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 4 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2025-01-09 03:37:13,779 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:37:13,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2119861663] [2025-01-09 03:37:13,779 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:37:13,779 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [260025575] [2025-01-09 03:37:13,779 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [260025575] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 03:37:13,779 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 03:37:13,779 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2025-01-09 03:37:13,779 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [49943372] [2025-01-09 03:37:13,779 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 03:37:13,779 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2025-01-09 03:37:13,780 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:37:13,780 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2025-01-09 03:37:13,780 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2025-01-09 03:37:13,780 INFO L87 Difference]: Start difference. First operand 21 states and 21 transitions. Second operand has 10 states, 8 states have (on average 1.875) internal successors, (15), 9 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-01-09 03:37:13,852 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:37:13,852 INFO L93 Difference]: Finished difference Result 33 states and 38 transitions. [2025-01-09 03:37:13,852 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2025-01-09 03:37:13,852 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 8 states have (on average 1.875) internal successors, (15), 9 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 20 [2025-01-09 03:37:13,853 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:37:13,853 INFO L225 Difference]: With dead ends: 33 [2025-01-09 03:37:13,853 INFO L226 Difference]: Without dead ends: 27 [2025-01-09 03:37:13,853 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 41 GetRequests, 28 SyntacticMatches, 2 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=39, Invalid=117, Unknown=0, NotChecked=0, Total=156 [2025-01-09 03:37:13,854 INFO L435 NwaCegarLoop]: 14 mSDtfsCounter, 1 mSDsluCounter, 72 mSDsCounter, 0 mSdLazyCounter, 46 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 1 SdHoareTripleChecker+Valid, 86 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 46 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2025-01-09 03:37:13,854 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [1 Valid, 86 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 46 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2025-01-09 03:37:13,854 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2025-01-09 03:37:13,858 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2025-01-09 03:37:13,859 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 18 states have (on average 1.0555555555555556) internal successors, (19), 18 states have internal predecessors, (19), 6 states have call successors, (6), 3 states have call predecessors, (6), 2 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2025-01-09 03:37:13,859 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2025-01-09 03:37:13,859 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 20 [2025-01-09 03:37:13,859 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:37:13,859 INFO L471 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2025-01-09 03:37:13,859 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 8 states have (on average 1.875) internal successors, (15), 9 states have internal predecessors, (15), 6 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2025-01-09 03:37:13,859 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2025-01-09 03:37:13,860 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2025-01-09 03:37:13,860 INFO L210 NwaCegarLoop]: Found error trace [2025-01-09 03:37:13,860 INFO L218 NwaCegarLoop]: trace histogram [6, 5, 5, 5, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1] [2025-01-09 03:37:13,866 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2025-01-09 03:37:14,060 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:14,061 INFO L396 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2025-01-09 03:37:14,061 INFO L157 PredicateUnifier]: Initialized classic predicate unifier [2025-01-09 03:37:14,061 INFO L85 PathProgramCache]: Analyzing trace with hash 243596829, now seen corresponding path program 2 times [2025-01-09 03:37:14,061 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2025-01-09 03:37:14,061 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [953960966] [2025-01-09 03:37:14,061 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 03:37:14,061 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2025-01-09 03:37:14,067 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-01-09 03:37:14,088 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 03:37:14,088 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 03:37:14,088 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unknown [2025-01-09 03:37:14,090 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [220451540] [2025-01-09 03:37:14,090 INFO L95 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2025-01-09 03:37:14,090 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:14,090 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 [2025-01-09 03:37:14,093 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2025-01-09 03:37:14,094 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2025-01-09 03:37:14,118 INFO L108 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 partitioned 38 statements into 2 equivalence classes. [2025-01-09 03:37:14,132 INFO L111 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) and asserted 38 of 38 statements. [2025-01-09 03:37:14,132 INFO L114 AnnotateAndAsserter]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2025-01-09 03:37:14,132 INFO L115 AnnotateAndAsserter]: Conjunction of SSA is unsat [2025-01-09 03:37:14,133 INFO L256 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 34 conjuncts are in the unsatisfiable core [2025-01-09 03:37:14,135 INFO L279 TraceCheckSpWp]: Computing forward predicates... [2025-01-09 03:37:14,293 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 9 proven. 33 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 03:37:14,294 INFO L312 TraceCheckSpWp]: Computing backward predicates... [2025-01-09 03:37:14,578 INFO L134 CoverageAnalysis]: Checked inductivity of 70 backedges. 9 proven. 33 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2025-01-09 03:37:14,578 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2025-01-09 03:37:14,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [953960966] [2025-01-09 03:37:14,578 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2025-01-09 03:37:14,578 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [220451540] [2025-01-09 03:37:14,578 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [220451540] provided 0 perfect and 2 imperfect interpolant sequences [2025-01-09 03:37:14,578 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2025-01-09 03:37:14,579 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [13, 12] total 22 [2025-01-09 03:37:14,579 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [241487290] [2025-01-09 03:37:14,579 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2025-01-09 03:37:14,579 INFO L548 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2025-01-09 03:37:14,579 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2025-01-09 03:37:14,580 INFO L144 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2025-01-09 03:37:14,580 INFO L146 InterpolantAutomaton]: CoverageRelationStatistics Valid=81, Invalid=381, Unknown=0, NotChecked=0, Total=462 [2025-01-09 03:37:14,580 INFO L87 Difference]: Start difference. First operand 27 states and 30 transitions. Second operand has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 03:37:14,780 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2025-01-09 03:37:14,780 INFO L93 Difference]: Finished difference Result 30 states and 35 transitions. [2025-01-09 03:37:14,780 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2025-01-09 03:37:14,780 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Word has length 38 [2025-01-09 03:37:14,781 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2025-01-09 03:37:14,781 INFO L225 Difference]: With dead ends: 30 [2025-01-09 03:37:14,781 INFO L226 Difference]: Without dead ends: 0 [2025-01-09 03:37:14,781 INFO L434 NwaCegarLoop]: 0 DeclaredPredicates, 80 GetRequests, 54 SyntacticMatches, 0 SemanticMatches, 26 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 65 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=139, Invalid=617, Unknown=0, NotChecked=0, Total=756 [2025-01-09 03:37:14,782 INFO L435 NwaCegarLoop]: 11 mSDtfsCounter, 4 mSDsluCounter, 99 mSDsCounter, 0 mSdLazyCounter, 163 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 110 SdHoareTripleChecker+Invalid, 172 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 163 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2025-01-09 03:37:14,782 INFO L436 NwaCegarLoop]: SdHoareTripleChecker [5 Valid, 110 Invalid, 172 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 163 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2025-01-09 03:37:14,782 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2025-01-09 03:37:14,782 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2025-01-09 03:37:14,783 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2025-01-09 03:37:14,783 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2025-01-09 03:37:14,783 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 38 [2025-01-09 03:37:14,783 INFO L84 Accepts]: Finished accepts. word is rejected. [2025-01-09 03:37:14,783 INFO L471 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2025-01-09 03:37:14,783 INFO L472 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.5555555555555556) internal successors, (28), 19 states have internal predecessors, (28), 12 states have call successors, (12), 3 states have call predecessors, (12), 2 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2025-01-09 03:37:14,783 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2025-01-09 03:37:14,783 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2025-01-09 03:37:14,785 INFO L782 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2025-01-09 03:37:14,795 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2025-01-09 03:37:14,986 WARN L453 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2025-01-09 03:37:14,988 INFO L422 BasicCegarLoop]: Path program histogram: [2, 1, 1, 1] [2025-01-09 03:37:14,990 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2025-01-09 03:37:15,079 INFO L170 ceAbstractionStarter]: Computing trace abstraction results [2025-01-09 03:37:15,093 INFO L201 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 09.01 03:37:15 BoogieIcfgContainer [2025-01-09 03:37:15,093 INFO L131 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2025-01-09 03:37:15,094 INFO L112 PluginConnector]: ------------------------Witness Printer---------------------------- [2025-01-09 03:37:15,094 INFO L270 PluginConnector]: Initializing Witness Printer... [2025-01-09 03:37:15,094 INFO L274 PluginConnector]: Witness Printer initialized [2025-01-09 03:37:15,094 INFO L184 PluginConnector]: Executing the observer RCFGCatcher from plugin Witness Printer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 09.01 03:37:12" (3/4) ... [2025-01-09 03:37:15,096 INFO L146 WitnessPrinter]: Generating witness for correct program [2025-01-09 03:37:15,107 INFO L362 RCFGBacktranslator]: Ignoring RootEdge to procedure __VERIFIER_assert [2025-01-09 03:37:15,109 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 12 nodes and edges [2025-01-09 03:37:15,109 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 4 nodes and edges [2025-01-09 03:37:15,109 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 3 nodes and edges [2025-01-09 03:37:15,109 INFO L919 BoogieBacktranslator]: Reduced CFG by removing 1 nodes and edges [2025-01-09 03:37:15,158 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.graphml [2025-01-09 03:37:15,158 INFO L149 WitnessManager]: Wrote witness to /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/witness.yml [2025-01-09 03:37:15,158 INFO L131 PluginConnector]: ------------------------ END Witness Printer---------------------------- [2025-01-09 03:37:15,159 INFO L158 Benchmark]: Toolchain (without parser) took 2991.59ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 56.4MB in the end (delta: 48.3MB). Peak memory consumption was 50.3MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,159 INFO L158 Benchmark]: CDTParser took 0.13ms. Allocated memory is still 201.3MB. Free memory is still 126.7MB. There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 03:37:15,159 INFO L158 Benchmark]: CACSL2BoogieTranslator took 162.56ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 94.0MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,159 INFO L158 Benchmark]: Boogie Procedure Inliner took 19.08ms. Allocated memory is still 142.6MB. Free memory was 94.0MB in the beginning and 93.0MB in the end (delta: 987.6kB). There was no memory consumed. Max. memory is 16.1GB. [2025-01-09 03:37:15,159 INFO L158 Benchmark]: Boogie Preprocessor took 26.02ms. Allocated memory is still 142.6MB. Free memory was 93.0MB in the beginning and 91.5MB in the end (delta: 1.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,160 INFO L158 Benchmark]: RCFGBuilder took 153.02ms. Allocated memory is still 142.6MB. Free memory was 91.5MB in the beginning and 81.1MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,160 INFO L158 Benchmark]: TraceAbstraction took 2561.17ms. Allocated memory is still 142.6MB. Free memory was 80.1MB in the beginning and 61.3MB in the end (delta: 18.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,160 INFO L158 Benchmark]: Witness Printer took 64.23ms. Allocated memory is still 142.6MB. Free memory was 61.3MB in the beginning and 56.4MB in the end (delta: 4.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. [2025-01-09 03:37:15,161 INFO L338 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.13ms. Allocated memory is still 201.3MB. Free memory is still 126.7MB. There was no memory consumed. Max. memory is 16.1GB. * CACSL2BoogieTranslator took 162.56ms. Allocated memory is still 142.6MB. Free memory was 104.8MB in the beginning and 94.0MB in the end (delta: 10.8MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Boogie Procedure Inliner took 19.08ms. Allocated memory is still 142.6MB. Free memory was 94.0MB in the beginning and 93.0MB in the end (delta: 987.6kB). There was no memory consumed. Max. memory is 16.1GB. * Boogie Preprocessor took 26.02ms. Allocated memory is still 142.6MB. Free memory was 93.0MB in the beginning and 91.5MB in the end (delta: 1.5MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * RCFGBuilder took 153.02ms. Allocated memory is still 142.6MB. Free memory was 91.5MB in the beginning and 81.1MB in the end (delta: 10.4MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * TraceAbstraction took 2561.17ms. Allocated memory is still 142.6MB. Free memory was 80.1MB in the beginning and 61.3MB in the end (delta: 18.8MB). Peak memory consumption was 16.8MB. Max. memory is 16.1GB. * Witness Printer took 64.23ms. Allocated memory is still 142.6MB. Free memory was 61.3MB in the beginning and 56.4MB in the end (delta: 4.9MB). Peak memory consumption was 8.4MB. Max. memory is 16.1GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 12]: a call to reach_error is unreachable For all program executions holds that a call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 18 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 2.4s, OverallIterations: 5, TraceHistogramMax: 6, PathProgramHistogramMax: 2, EmptinessCheckTime: 0.0s, AutomataDifference: 0.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 0.0s, InitialAbstractionConstructionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 17 SdHoareTripleChecker+Valid, 0.2s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 13 mSDsluCounter, 298 SdHoareTripleChecker+Invalid, 0.2s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 230 mSDsCounter, 14 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 247 IncrementalHoareTripleChecker+Invalid, 261 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 14 mSolverCounterUnsat, 68 mSDtfsCounter, 247 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 158 GetRequests, 107 SyntacticMatches, 4 SemanticMatches, 47 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 70 ImplicationChecksByTransitivity, 0.5s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=27occurred in iteration=4, InterpolantAutomatonStates: 36, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 5 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.1s SatisfiabilityAnalysisTime, 0.8s InterpolantComputationTime, 168 NumberOfCodeBlocks, 168 NumberOfCodeBlocksAsserted, 11 NumberOfCheckSat, 152 ConstructedInterpolants, 0 QuantifiedInterpolants, 589 SizeOfPredicates, 7 NumberOfNonLiveVariables, 288 ConjunctsInSsa, 64 ConjunctsInUnsatCore, 8 InterpolantComputations, 3 PerfectInterpolantSequences, 95/166 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available, ConComCheckerStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 27]: Loop Invariant Derived loop invariant: (((((y + ((__int128) y * y)) == (c + ((__int128) c * y))) && ((((__int128) 2 * c) + ((__int128) c * y)) == (((__int128) 2 * y) + ((__int128) y * y)))) && ((((__int128) k * y) == ((__int128) y * y)) || (c < k))) && (((((((__int128) y * y) * y) * 2) + ((((__int128) y * y) * y) * y)) + ((__int128) y * y)) == ((__int128) x * 4))) RESULT: Ultimate proved your program to be correct! [2025-01-09 03:37:15,173 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate-jdk21/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:4000 (1)] Ended with exit code 0 Received shutdown request... --- End real Ultimate output --- Execution finished normally Writing output log to file Ultimate.log Result: TRUE