/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data -s ../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf -tc ../../../trunk/examples/toolchains/AutomizerC.xml --sifa.abstract.domain OctagonDomain -i ../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound100.c -------------------------------------------------------------------------------- This is Ultimate 0.2.3-dev-f954360 [2023-04-02 22:54:55,329 INFO L177 SettingsManager]: Resetting all preferences to default values... [2023-04-02 22:54:55,331 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2023-04-02 22:54:55,369 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2023-04-02 22:54:55,369 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2023-04-02 22:54:55,372 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2023-04-02 22:54:55,375 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2023-04-02 22:54:55,377 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2023-04-02 22:54:55,378 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2023-04-02 22:54:55,379 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2023-04-02 22:54:55,380 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2023-04-02 22:54:55,382 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2023-04-02 22:54:55,382 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2023-04-02 22:54:55,386 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2023-04-02 22:54:55,387 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2023-04-02 22:54:55,388 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2023-04-02 22:54:55,389 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2023-04-02 22:54:55,390 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2023-04-02 22:54:55,392 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2023-04-02 22:54:55,396 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2023-04-02 22:54:55,397 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2023-04-02 22:54:55,399 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2023-04-02 22:54:55,400 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2023-04-02 22:54:55,401 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2023-04-02 22:54:55,407 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2023-04-02 22:54:55,408 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2023-04-02 22:54:55,408 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2023-04-02 22:54:55,410 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2023-04-02 22:54:55,410 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2023-04-02 22:54:55,411 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2023-04-02 22:54:55,411 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2023-04-02 22:54:55,412 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2023-04-02 22:54:55,413 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2023-04-02 22:54:55,414 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2023-04-02 22:54:55,415 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2023-04-02 22:54:55,415 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2023-04-02 22:54:55,415 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2023-04-02 22:54:55,415 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2023-04-02 22:54:55,416 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2023-04-02 22:54:55,416 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2023-04-02 22:54:55,417 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2023-04-02 22:54:55,418 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/default/taipan/svcomp-Reach-32bit-Taipan_Default.epf [2023-04-02 22:54:55,447 INFO L113 SettingsManager]: Loading preferences was successful [2023-04-02 22:54:55,447 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2023-04-02 22:54:55,448 INFO L136 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2023-04-02 22:54:55,448 INFO L138 SettingsManager]: * Log level for class=de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=ERROR; [2023-04-02 22:54:55,449 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2023-04-02 22:54:55,449 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2023-04-02 22:54:55,449 INFO L138 SettingsManager]: * User list type=DISABLED [2023-04-02 22:54:55,449 INFO L136 SettingsManager]: Preferences of Abstract Interpretation differ from their defaults: [2023-04-02 22:54:55,449 INFO L138 SettingsManager]: * Explicit value domain=true [2023-04-02 22:54:55,449 INFO L138 SettingsManager]: * Abstract domain for RCFG-of-the-future=PoormanAbstractDomain [2023-04-02 22:54:55,450 INFO L138 SettingsManager]: * Octagon Domain=false [2023-04-02 22:54:55,450 INFO L138 SettingsManager]: * Abstract domain=CompoundDomain [2023-04-02 22:54:55,450 INFO L138 SettingsManager]: * Check feasibility of abstract posts with an SMT solver=true [2023-04-02 22:54:55,450 INFO L138 SettingsManager]: * Use the RCFG-of-the-future interface=true [2023-04-02 22:54:55,450 INFO L138 SettingsManager]: * Interval Domain=false [2023-04-02 22:54:55,451 INFO L136 SettingsManager]: Preferences of Sifa differ from their defaults: [2023-04-02 22:54:55,451 INFO L138 SettingsManager]: * Call Summarizer=TopInputCallSummarizer [2023-04-02 22:54:55,451 INFO L138 SettingsManager]: * Simplification Technique=POLY_PAC [2023-04-02 22:54:55,451 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2023-04-02 22:54:55,451 INFO L138 SettingsManager]: * sizeof long=4 [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * sizeof POINTER=4 [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2023-04-02 22:54:55,452 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * sizeof long double=12 [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * Use constant arrays=true [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2023-04-02 22:54:55,453 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2023-04-02 22:54:55,453 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-02 22:54:55,454 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Abstract interpretation Mode=USE_PREDICATES [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Trace refinement strategy=SIFA_TAIPAN [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2023-04-02 22:54:55,454 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2023-04-02 22:54:55,455 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode 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.sifa: Abstract Domain -> OctagonDomain [2023-04-02 22:54:55,695 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2023-04-02 22:54:55,720 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2023-04-02 22:54:55,722 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2023-04-02 22:54:55,723 INFO L271 PluginConnector]: Initializing CDTParser... [2023-04-02 22:54:55,724 INFO L275 PluginConnector]: CDTParser initialized [2023-04-02 22:54:55,725 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound100.c [2023-04-02 22:54:56,910 INFO L500 CDTParser]: Created temporary CDT project at NULL [2023-04-02 22:54:57,055 INFO L351 CDTParser]: Found 1 translation units. [2023-04-02 22:54:57,056 INFO L172 CDTParser]: Scanning /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound100.c [2023-04-02 22:54:57,061 INFO L394 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f9b3017d3/b8f8a00acf5c4837948cf80c0da13520/FLAG29ab0e176 [2023-04-02 22:54:57,080 INFO L402 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/f9b3017d3/b8f8a00acf5c4837948cf80c0da13520 [2023-04-02 22:54:57,082 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2023-04-02 22:54:57,083 INFO L131 ToolchainWalker]: Walking toolchain with 4 elements. [2023-04-02 22:54:57,086 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2023-04-02 22:54:57,086 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2023-04-02 22:54:57,089 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2023-04-02 22:54:57,090 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,091 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@6f2a39d8 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57, skipping insertion in model container [2023-04-02 22:54:57,091 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,097 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2023-04-02 22:54:57,113 INFO L178 MainTranslator]: Built tables and reachable declarations [2023-04-02 22:54:57,239 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound100.c[490,503] [2023-04-02 22:54:57,271 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-02 22:54:57,282 INFO L203 MainTranslator]: Completed pre-run [2023-04-02 22:54:57,293 WARN L247 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/releaseScripts/default/sv-benchmarks/c/nla-digbench-scaling/egcd3-ll_unwindbound100.c[490,503] [2023-04-02 22:54:57,315 INFO L209 PostProcessor]: Analyzing one entry point: main [2023-04-02 22:54:57,326 INFO L208 MainTranslator]: Completed translation [2023-04-02 22:54:57,326 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57 WrapperNode [2023-04-02 22:54:57,326 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2023-04-02 22:54:57,327 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2023-04-02 22:54:57,327 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2023-04-02 22:54:57,327 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2023-04-02 22:54:57,337 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,337 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,344 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,345 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,351 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,354 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,355 INFO L185 PluginConnector]: Executing the observer LTLStepAnnotator from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,356 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,357 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2023-04-02 22:54:57,358 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2023-04-02 22:54:57,358 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2023-04-02 22:54:57,358 INFO L275 PluginConnector]: RCFGBuilder initialized [2023-04-02 22:54:57,359 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (1/1) ... [2023-04-02 22:54:57,365 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2023-04-02 22:54:57,374 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:57,386 INFO L229 MonitoredProcess]: Starting monitored process 1 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2023-04-02 22:54:57,414 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Waiting until timeout for monitored process [2023-04-02 22:54:57,430 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2023-04-02 22:54:57,430 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2023-04-02 22:54:57,430 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2023-04-02 22:54:57,432 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2023-04-02 22:54:57,432 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2023-04-02 22:54:57,432 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2023-04-02 22:54:57,432 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2023-04-02 22:54:57,432 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2023-04-02 22:54:57,432 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2023-04-02 22:54:57,432 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2023-04-02 22:54:57,432 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure main [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2023-04-02 22:54:57,433 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2023-04-02 22:54:57,434 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2023-04-02 22:54:57,434 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2023-04-02 22:54:57,434 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2023-04-02 22:54:57,520 INFO L236 CfgBuilder]: Building ICFG [2023-04-02 22:54:57,522 INFO L262 CfgBuilder]: Building CFG for each procedure with an implementation [2023-04-02 22:54:57,737 INFO L277 CfgBuilder]: Performing block encoding [2023-04-02 22:54:57,759 INFO L297 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2023-04-02 22:54:57,759 INFO L302 CfgBuilder]: Removed 3 assume(true) statements. [2023-04-02 22:54:57,761 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.04 10:54:57 BoogieIcfgContainer [2023-04-02 22:54:57,761 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2023-04-02 22:54:57,782 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2023-04-02 22:54:57,782 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2023-04-02 22:54:57,784 INFO L275 PluginConnector]: TraceAbstraction initialized [2023-04-02 22:54:57,784 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 02.04 10:54:57" (1/3) ... [2023-04-02 22:54:57,785 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63ae83ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.04 10:54:57, skipping insertion in model container [2023-04-02 22:54:57,785 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 02.04 10:54:57" (2/3) ... [2023-04-02 22:54:57,785 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@63ae83ac and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 02.04 10:54:57, skipping insertion in model container [2023-04-02 22:54:57,786 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 02.04 10:54:57" (3/3) ... [2023-04-02 22:54:57,787 INFO L112 eAbstractionObserver]: Analyzing ICFG egcd3-ll_unwindbound100.c [2023-04-02 22:54:57,802 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2023-04-02 22:54:57,802 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2023-04-02 22:54:57,859 INFO L356 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2023-04-02 22:54:57,864 INFO L357 AbstractCegarLoop]: Settings: SEPARATE_VIOLATION_CHECK=true, mInterprocedural=true, mMaxIterations=1000000, mWatchIteration=1000000, mArtifact=RCFG, mInterpolation=FPandBP, mInterpolantAutomaton=STRAIGHT_LINE, mDumpAutomata=false, mAutomataFormat=ATS_NUMERATE, mDumpPath=., mDeterminiation=PREDICATE_ABSTRACTION, mMinimize=MINIMIZE_SEVPA, mHoare=true, mAutomataTypeConcurrency=FINITE_AUTOMATA, mHoareTripleChecks=INCREMENTAL, mHoareAnnotationPositions=LoopsAndPotentialCycles, 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;@12d880fa, mLbeIndependenceSettings=[IndependenceType=SEMANTIC, AbstractionType=NONE, UseConditional=false, UseSemiCommutativity=true, Solver=Z3, SolverTimeout=1000ms] [2023-04-02 22:54:57,864 INFO L358 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2023-04-02 22:54:57,867 INFO L276 IsEmpty]: Start isEmpty. Operand has 36 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 22 states have internal predecessors, (32), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2023-04-02 22:54:57,872 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2023-04-02 22:54:57,872 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:54:57,872 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:54:57,873 INFO L420 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:54:57,877 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:54:57,877 INFO L85 PathProgramCache]: Analyzing trace with hash 1884191244, now seen corresponding path program 1 times [2023-04-02 22:54:57,883 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:54:57,883 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1349675788] [2023-04-02 22:54:57,884 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:57,884 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:54:57,995 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:58,055 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:54:58,055 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1349675788] [2023-04-02 22:54:58,055 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: Unsupported non-linear arithmetic [2023-04-02 22:54:58,056 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [758522099] [2023-04-02 22:54:58,056 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:58,056 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:58,056 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:58,061 INFO L229 MonitoredProcess]: Starting monitored process 2 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:54:58,062 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2023-04-02 22:54:58,156 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:58,158 INFO L262 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 1 conjunts are in the unsatisfiable core [2023-04-02 22:54:58,162 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:54:58,188 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:54:58,189 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:54:58,190 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [758522099] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:54:58,190 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:54:58,190 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [2] imperfect sequences [] total 2 [2023-04-02 22:54:58,192 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1380819303] [2023-04-02 22:54:58,193 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:54:58,197 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 2 states [2023-04-02 22:54:58,197 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:54:58,229 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 2 interpolants. [2023-04-02 22:54:58,230 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-02 22:54:58,231 INFO L87 Difference]: Start difference. First operand has 36 states, 21 states have (on average 1.5238095238095237) internal successors, (32), 22 states have internal predecessors, (32), 9 states have call successors, (9), 4 states have call predecessors, (9), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) Second operand has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:54:58,274 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:54:58,274 INFO L93 Difference]: Finished difference Result 62 states and 94 transitions. [2023-04-02 22:54:58,276 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 2 states. [2023-04-02 22:54:58,277 INFO L78 Accepts]: Start accepts. Automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 17 [2023-04-02 22:54:58,278 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:54:58,283 INFO L225 Difference]: With dead ends: 62 [2023-04-02 22:54:58,284 INFO L226 Difference]: Without dead ends: 32 [2023-04-02 22:54:58,287 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 16 GetRequests, 16 SyntacticMatches, 0 SemanticMatches, 0 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=1, Invalid=1, Unknown=0, NotChecked=0, Total=2 [2023-04-02 22:54:58,292 INFO L413 NwaCegarLoop]: 43 mSDtfsCounter, 0 mSDsluCounter, 0 mSDsCounter, 0 mSdLazyCounter, 3 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 43 SdHoareTripleChecker+Invalid, 3 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 3 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:54:58,293 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 43 Invalid, 3 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 3 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:54:58,308 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 32 states. [2023-04-02 22:54:58,328 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 32 to 32. [2023-04-02 22:54:58,330 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 32 states, 19 states have (on average 1.368421052631579) internal successors, (26), 20 states have internal predecessors, (26), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-04-02 22:54:58,333 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 32 states to 32 states and 42 transitions. [2023-04-02 22:54:58,334 INFO L78 Accepts]: Start accepts. Automaton has 32 states and 42 transitions. Word has length 17 [2023-04-02 22:54:58,337 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:54:58,337 INFO L495 AbstractCegarLoop]: Abstraction has 32 states and 42 transitions. [2023-04-02 22:54:58,338 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 2 states, 2 states have (on average 4.0) internal successors, (8), 2 states have internal predecessors, (8), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:54:58,338 INFO L276 IsEmpty]: Start isEmpty. Operand 32 states and 42 transitions. [2023-04-02 22:54:58,339 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 19 [2023-04-02 22:54:58,339 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:54:58,339 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:54:58,348 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2023-04-02 22:54:58,544 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable0 [2023-04-02 22:54:58,545 INFO L420 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:54:58,546 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:54:58,546 INFO L85 PathProgramCache]: Analyzing trace with hash 952486133, now seen corresponding path program 1 times [2023-04-02 22:54:58,546 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:54:58,547 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [795873005] [2023-04-02 22:54:58,547 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:58,547 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:54:58,572 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:54:58,572 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [887523226] [2023-04-02 22:54:58,572 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:58,573 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:58,573 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:58,576 INFO L229 MonitoredProcess]: Starting monitored process 3 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:54:58,578 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2023-04-02 22:54:58,636 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:58,637 INFO L262 TraceCheckSpWp]: Trace formula consists of 94 conjuncts, 5 conjunts are in the unsatisfiable core [2023-04-02 22:54:58,640 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:54:58,722 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:54:58,722 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:54:58,722 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:54:58,723 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [795873005] [2023-04-02 22:54:58,723 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:54:58,724 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [887523226] [2023-04-02 22:54:58,724 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [887523226] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:54:58,724 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:54:58,724 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [4] imperfect sequences [] total 4 [2023-04-02 22:54:58,725 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1339253939] [2023-04-02 22:54:58,725 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:54:58,726 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 4 states [2023-04-02 22:54:58,726 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:54:58,726 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 4 interpolants. [2023-04-02 22:54:58,727 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-04-02 22:54:58,727 INFO L87 Difference]: Start difference. First operand 32 states and 42 transitions. Second operand has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:54:58,750 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:54:58,750 INFO L93 Difference]: Finished difference Result 41 states and 51 transitions. [2023-04-02 22:54:58,750 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2023-04-02 22:54:58,750 INFO L78 Accepts]: Start accepts. Automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 18 [2023-04-02 22:54:58,751 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:54:58,751 INFO L225 Difference]: With dead ends: 41 [2023-04-02 22:54:58,751 INFO L226 Difference]: Without dead ends: 34 [2023-04-02 22:54:58,752 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 17 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 2 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=5, Invalid=7, Unknown=0, NotChecked=0, Total=12 [2023-04-02 22:54:58,753 INFO L413 NwaCegarLoop]: 38 mSDtfsCounter, 0 mSDsluCounter, 65 mSDsCounter, 0 mSdLazyCounter, 13 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 103 SdHoareTripleChecker+Invalid, 13 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 13 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:54:58,753 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 103 Invalid, 13 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 13 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:54:58,754 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 34 states. [2023-04-02 22:54:58,759 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 34 to 34. [2023-04-02 22:54:58,759 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 21 states have (on average 1.3333333333333333) internal successors, (28), 22 states have internal predecessors, (28), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-04-02 22:54:58,760 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 44 transitions. [2023-04-02 22:54:58,760 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 44 transitions. Word has length 18 [2023-04-02 22:54:58,761 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:54:58,761 INFO L495 AbstractCegarLoop]: Abstraction has 34 states and 44 transitions. [2023-04-02 22:54:58,761 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 4 states, 4 states have (on average 2.25) internal successors, (9), 3 states have internal predecessors, (9), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:54:58,761 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 44 transitions. [2023-04-02 22:54:58,762 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 20 [2023-04-02 22:54:58,762 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:54:58,762 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:54:58,772 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2023-04-02 22:54:58,967 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable1 [2023-04-02 22:54:58,968 INFO L420 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:54:58,969 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:54:58,969 INFO L85 PathProgramCache]: Analyzing trace with hash -552718471, now seen corresponding path program 1 times [2023-04-02 22:54:58,969 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:54:58,969 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1065536895] [2023-04-02 22:54:58,969 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:58,970 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:54:58,984 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:54:58,984 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2093070694] [2023-04-02 22:54:58,984 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:58,984 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:58,985 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:58,992 INFO L229 MonitoredProcess]: Starting monitored process 4 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:54:58,993 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2023-04-02 22:54:59,054 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:59,055 INFO L262 TraceCheckSpWp]: Trace formula consists of 96 conjuncts, 7 conjunts are in the unsatisfiable core [2023-04-02 22:54:59,057 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:54:59,096 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-04-02 22:54:59,097 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:54:59,097 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:54:59,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1065536895] [2023-04-02 22:54:59,097 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:54:59,097 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2093070694] [2023-04-02 22:54:59,097 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2093070694] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:54:59,098 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:54:59,099 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-04-02 22:54:59,099 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1387490017] [2023-04-02 22:54:59,099 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:54:59,099 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:54:59,100 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:54:59,102 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:54:59,102 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:54:59,102 INFO L87 Difference]: Start difference. First operand 34 states and 44 transitions. Second operand has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:54:59,211 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:54:59,212 INFO L93 Difference]: Finished difference Result 54 states and 72 transitions. [2023-04-02 22:54:59,213 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-04-02 22:54:59,213 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) Word has length 19 [2023-04-02 22:54:59,213 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:54:59,214 INFO L225 Difference]: With dead ends: 54 [2023-04-02 22:54:59,214 INFO L226 Difference]: Without dead ends: 47 [2023-04-02 22:54:59,215 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 19 GetRequests, 15 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2023-04-02 22:54:59,216 INFO L413 NwaCegarLoop]: 33 mSDtfsCounter, 45 mSDsluCounter, 61 mSDsCounter, 0 mSdLazyCounter, 49 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 49 SdHoareTripleChecker+Valid, 94 SdHoareTripleChecker+Invalid, 57 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 49 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:54:59,217 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [49 Valid, 94 Invalid, 57 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 49 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:54:59,217 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2023-04-02 22:54:59,224 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 35. [2023-04-02 22:54:59,224 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 22 states have (on average 1.3181818181818181) internal successors, (29), 23 states have internal predecessors, (29), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-04-02 22:54:59,225 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 45 transitions. [2023-04-02 22:54:59,225 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 45 transitions. Word has length 19 [2023-04-02 22:54:59,226 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:54:59,226 INFO L495 AbstractCegarLoop]: Abstraction has 35 states and 45 transitions. [2023-04-02 22:54:59,226 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 4 states have (on average 2.75) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:54:59,226 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 45 transitions. [2023-04-02 22:54:59,227 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-04-02 22:54:59,227 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:54:59,227 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:54:59,241 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2023-04-02 22:54:59,432 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:59,433 INFO L420 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:54:59,433 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:54:59,434 INFO L85 PathProgramCache]: Analyzing trace with hash 1491876193, now seen corresponding path program 1 times [2023-04-02 22:54:59,434 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:54:59,434 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [892182223] [2023-04-02 22:54:59,434 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:59,434 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:54:59,451 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:54:59,451 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [534320927] [2023-04-02 22:54:59,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:59,452 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:59,452 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:59,457 INFO L229 MonitoredProcess]: Starting monitored process 5 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:54:59,458 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2023-04-02 22:54:59,506 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:59,507 INFO L262 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 7 conjunts are in the unsatisfiable core [2023-04-02 22:54:59,509 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:54:59,548 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:54:59,548 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:54:59,548 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:54:59,549 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [892182223] [2023-04-02 22:54:59,549 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:54:59,549 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [534320927] [2023-04-02 22:54:59,549 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [534320927] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:54:59,549 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:54:59,549 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-04-02 22:54:59,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1302522768] [2023-04-02 22:54:59,550 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:54:59,550 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:54:59,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:54:59,551 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:54:59,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:54:59,551 INFO L87 Difference]: Start difference. First operand 35 states and 45 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:54:59,573 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:54:59,573 INFO L93 Difference]: Finished difference Result 59 states and 79 transitions. [2023-04-02 22:54:59,573 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2023-04-02 22:54:59,574 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2023-04-02 22:54:59,574 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:54:59,575 INFO L225 Difference]: With dead ends: 59 [2023-04-02 22:54:59,575 INFO L226 Difference]: Without dead ends: 37 [2023-04-02 22:54:59,575 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 23 GetRequests, 20 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:54:59,576 INFO L413 NwaCegarLoop]: 37 mSDtfsCounter, 0 mSDsluCounter, 92 mSDsCounter, 0 mSdLazyCounter, 19 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 0 SdHoareTripleChecker+Valid, 129 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 19 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:54:59,576 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [0 Valid, 129 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 19 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:54:59,577 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 37 states. [2023-04-02 22:54:59,582 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 37 to 37. [2023-04-02 22:54:59,582 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 37 states, 24 states have (on average 1.2916666666666667) internal successors, (31), 25 states have internal predecessors, (31), 9 states have call successors, (9), 4 states have call predecessors, (9), 3 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2023-04-02 22:54:59,583 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 37 states to 37 states and 47 transitions. [2023-04-02 22:54:59,583 INFO L78 Accepts]: Start accepts. Automaton has 37 states and 47 transitions. Word has length 24 [2023-04-02 22:54:59,584 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:54:59,584 INFO L495 AbstractCegarLoop]: Abstraction has 37 states and 47 transitions. [2023-04-02 22:54:59,584 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 3 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:54:59,584 INFO L276 IsEmpty]: Start isEmpty. Operand 37 states and 47 transitions. [2023-04-02 22:54:59,585 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 25 [2023-04-02 22:54:59,585 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:54:59,585 INFO L195 NwaCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:54:59,595 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2023-04-02 22:54:59,790 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:59,791 INFO L420 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:54:59,791 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:54:59,791 INFO L85 PathProgramCache]: Analyzing trace with hash -917044466, now seen corresponding path program 1 times [2023-04-02 22:54:59,791 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:54:59,791 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2038318673] [2023-04-02 22:54:59,792 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:59,792 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:54:59,813 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:54:59,814 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [997711157] [2023-04-02 22:54:59,814 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:54:59,814 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:54:59,814 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:54:59,817 INFO L229 MonitoredProcess]: Starting monitored process 6 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:54:59,821 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2023-04-02 22:54:59,866 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:54:59,867 INFO L262 TraceCheckSpWp]: Trace formula consists of 114 conjuncts, 18 conjunts are in the unsatisfiable core [2023-04-02 22:54:59,871 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:00,077 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 1 proven. 0 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-04-02 22:55:00,077 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:55:00,077 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:00,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2038318673] [2023-04-02 22:55:00,078 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:00,078 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [997711157] [2023-04-02 22:55:00,078 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [997711157] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:55:00,078 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:55:00,078 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [8] imperfect sequences [] total 8 [2023-04-02 22:55:00,078 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1514541782] [2023-04-02 22:55:00,079 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:55:00,079 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 8 states [2023-04-02 22:55:00,079 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:00,080 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 8 interpolants. [2023-04-02 22:55:00,080 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=16, Invalid=40, Unknown=0, NotChecked=0, Total=56 [2023-04-02 22:55:00,080 INFO L87 Difference]: Start difference. First operand 37 states and 47 transitions. Second operand has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:55:00,178 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:00,179 INFO L93 Difference]: Finished difference Result 55 states and 72 transitions. [2023-04-02 22:55:00,179 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2023-04-02 22:55:00,179 INFO L78 Accepts]: Start accepts. Automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) Word has length 24 [2023-04-02 22:55:00,180 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:00,180 INFO L225 Difference]: With dead ends: 55 [2023-04-02 22:55:00,180 INFO L226 Difference]: Without dead ends: 53 [2023-04-02 22:55:00,181 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 17 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=20, Invalid=52, Unknown=0, NotChecked=0, Total=72 [2023-04-02 22:55:00,181 INFO L413 NwaCegarLoop]: 32 mSDtfsCounter, 29 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 95 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 95 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 95 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:00,182 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [37 Valid, 149 Invalid, 95 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 95 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:00,182 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 53 states. [2023-04-02 22:55:00,190 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 53 to 52. [2023-04-02 22:55:00,190 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 34 states have (on average 1.3235294117647058) internal successors, (45), 35 states have internal predecessors, (45), 13 states have call successors, (13), 5 states have call predecessors, (13), 4 states have return successors, (11), 11 states have call predecessors, (11), 11 states have call successors, (11) [2023-04-02 22:55:00,191 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 69 transitions. [2023-04-02 22:55:00,191 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 69 transitions. Word has length 24 [2023-04-02 22:55:00,191 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:00,191 INFO L495 AbstractCegarLoop]: Abstraction has 52 states and 69 transitions. [2023-04-02 22:55:00,192 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 8 states, 6 states have (on average 2.6666666666666665) internal successors, (16), 6 states have internal predecessors, (16), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 3 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:55:00,192 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 69 transitions. [2023-04-02 22:55:00,192 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 26 [2023-04-02 22:55:00,192 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:00,192 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:55:00,201 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:00,398 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:00,398 INFO L420 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:00,399 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:00,399 INFO L85 PathProgramCache]: Analyzing trace with hash -575541792, now seen corresponding path program 1 times [2023-04-02 22:55:00,399 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:00,399 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1767350732] [2023-04-02 22:55:00,399 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:00,399 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:00,411 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:00,412 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1719264785] [2023-04-02 22:55:00,412 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:00,412 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:00,412 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:00,417 INFO L229 MonitoredProcess]: Starting monitored process 7 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:00,420 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2023-04-02 22:55:00,464 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:00,465 INFO L262 TraceCheckSpWp]: Trace formula consists of 124 conjuncts, 9 conjunts are in the unsatisfiable core [2023-04-02 22:55:00,467 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:00,530 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:00,530 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:00,608 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 2 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:00,609 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:00,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1767350732] [2023-04-02 22:55:00,609 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:00,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1719264785] [2023-04-02 22:55:00,609 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1719264785] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:55:00,609 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [513644799] [2023-04-02 22:55:00,628 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:55:00,629 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:00,633 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:00,637 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:00,638 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:00,705 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:03,992 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 123 for LOIs [2023-04-02 22:55:04,106 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:04,108 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:04,113 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:09,817 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1190#(and (<= 101 ~counter~0) (<= 1 |#StackHeapBarrier|) (<= ~counter~0 101) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:55:09,818 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:55:09,818 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:55:09,818 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 10 [2023-04-02 22:55:09,818 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [333528272] [2023-04-02 22:55:09,818 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:55:09,822 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2023-04-02 22:55:09,822 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:09,823 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2023-04-02 22:55:09,824 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=129, Invalid=683, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:55:09,824 INFO L87 Difference]: Start difference. First operand 52 states and 69 transitions. Second operand has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:55:10,002 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:10,003 INFO L93 Difference]: Finished difference Result 148 states and 194 transitions. [2023-04-02 22:55:10,005 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2023-04-02 22:55:10,006 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) Word has length 25 [2023-04-02 22:55:10,011 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:10,017 INFO L225 Difference]: With dead ends: 148 [2023-04-02 22:55:10,017 INFO L226 Difference]: Without dead ends: 141 [2023-04-02 22:55:10,018 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 77 GetRequests, 47 SyntacticMatches, 0 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 300 ImplicationChecksByTransitivity, 5.8s TimeCoverageRelationStatistics Valid=152, Invalid=840, Unknown=0, NotChecked=0, Total=992 [2023-04-02 22:55:10,020 INFO L413 NwaCegarLoop]: 36 mSDtfsCounter, 83 mSDsluCounter, 182 mSDsCounter, 0 mSdLazyCounter, 89 mSolverCounterSat, 16 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 83 SdHoareTripleChecker+Valid, 218 SdHoareTripleChecker+Invalid, 105 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 16 IncrementalHoareTripleChecker+Valid, 89 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:10,021 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [83 Valid, 218 Invalid, 105 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [16 Valid, 89 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:10,021 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 141 states. [2023-04-02 22:55:10,034 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 141 to 98. [2023-04-02 22:55:10,034 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 98 states, 67 states have (on average 1.3432835820895523) internal successors, (90), 69 states have internal predecessors, (90), 22 states have call successors, (22), 9 states have call predecessors, (22), 8 states have return successors, (19), 19 states have call predecessors, (19), 19 states have call successors, (19) [2023-04-02 22:55:10,035 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 98 states to 98 states and 131 transitions. [2023-04-02 22:55:10,035 INFO L78 Accepts]: Start accepts. Automaton has 98 states and 131 transitions. Word has length 25 [2023-04-02 22:55:10,035 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:10,035 INFO L495 AbstractCegarLoop]: Abstraction has 98 states and 131 transitions. [2023-04-02 22:55:10,035 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 2.9) internal successors, (29), 10 states have internal predecessors, (29), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:55:10,035 INFO L276 IsEmpty]: Start isEmpty. Operand 98 states and 131 transitions. [2023-04-02 22:55:10,036 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 27 [2023-04-02 22:55:10,036 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:10,036 INFO L195 NwaCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:55:10,041 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:10,236 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:10,237 INFO L420 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:10,237 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:10,237 INFO L85 PathProgramCache]: Analyzing trace with hash -676943890, now seen corresponding path program 1 times [2023-04-02 22:55:10,237 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:10,237 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [501235003] [2023-04-02 22:55:10,238 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:10,238 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:10,252 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:10,252 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1444364750] [2023-04-02 22:55:10,252 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:10,253 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:10,253 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:10,255 INFO L229 MonitoredProcess]: Starting monitored process 8 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:10,256 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2023-04-02 22:55:10,294 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:10,295 INFO L262 TraceCheckSpWp]: Trace formula consists of 126 conjuncts, 9 conjunts are in the unsatisfiable core [2023-04-02 22:55:10,297 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:10,332 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-04-02 22:55:10,333 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:10,387 INFO L134 CoverageAnalysis]: Checked inductivity of 5 backedges. 0 proven. 4 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-04-02 22:55:10,388 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:10,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [501235003] [2023-04-02 22:55:10,388 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:10,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1444364750] [2023-04-02 22:55:10,388 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1444364750] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:55:10,388 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1966385527] [2023-04-02 22:55:10,393 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:55:10,393 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:10,393 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:10,394 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:10,394 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:10,416 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:12,283 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 6 for LOIs [2023-04-02 22:55:12,290 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:12,291 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:12,296 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:16,799 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '1730#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:55:16,800 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:55:16,800 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:55:16,800 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 7 [2023-04-02 22:55:16,800 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [412846500] [2023-04-02 22:55:16,800 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:55:16,801 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2023-04-02 22:55:16,801 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:16,801 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2023-04-02 22:55:16,801 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=93, Invalid=557, Unknown=0, NotChecked=0, Total=650 [2023-04-02 22:55:16,801 INFO L87 Difference]: Start difference. First operand 98 states and 131 transitions. Second operand has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:55:17,061 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:17,062 INFO L93 Difference]: Finished difference Result 184 states and 262 transitions. [2023-04-02 22:55:17,062 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:55:17,062 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 26 [2023-04-02 22:55:17,062 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:17,063 INFO L225 Difference]: With dead ends: 184 [2023-04-02 22:55:17,063 INFO L226 Difference]: Without dead ends: 172 [2023-04-02 22:55:17,064 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 49 SyntacticMatches, 4 SemanticMatches, 30 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 175 ImplicationChecksByTransitivity, 4.6s TimeCoverageRelationStatistics Valid=164, Invalid=828, Unknown=0, NotChecked=0, Total=992 [2023-04-02 22:55:17,065 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 120 mSDsluCounter, 146 mSDsCounter, 0 mSdLazyCounter, 133 mSolverCounterSat, 39 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 195 SdHoareTripleChecker+Invalid, 172 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 39 IncrementalHoareTripleChecker+Valid, 133 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:17,065 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 195 Invalid, 172 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [39 Valid, 133 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:17,066 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 172 states. [2023-04-02 22:55:17,081 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 172 to 129. [2023-04-02 22:55:17,081 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 95 states have (on average 1.3578947368421053) internal successors, (129), 96 states have internal predecessors, (129), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2023-04-02 22:55:17,082 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 177 transitions. [2023-04-02 22:55:17,082 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 177 transitions. Word has length 26 [2023-04-02 22:55:17,083 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:17,083 INFO L495 AbstractCegarLoop]: Abstraction has 129 states and 177 transitions. [2023-04-02 22:55:17,083 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 6 states have (on average 3.0) internal successors, (18), 6 states have internal predecessors, (18), 3 states have call successors, (5), 2 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2023-04-02 22:55:17,083 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 177 transitions. [2023-04-02 22:55:17,084 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 30 [2023-04-02 22:55:17,084 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:17,084 INFO L195 NwaCegarLoop]: trace histogram [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] [2023-04-02 22:55:17,091 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Ended with exit code 0 [2023-04-02 22:55:17,288 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:17,289 INFO L420 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:17,289 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:17,289 INFO L85 PathProgramCache]: Analyzing trace with hash -1039050843, now seen corresponding path program 1 times [2023-04-02 22:55:17,289 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:17,289 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1585158160] [2023-04-02 22:55:17,289 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:17,290 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:17,305 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:17,305 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [800731553] [2023-04-02 22:55:17,305 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:17,306 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:17,306 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:17,313 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:17,315 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2023-04-02 22:55:17,356 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:17,357 INFO L262 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 17 conjunts are in the unsatisfiable core [2023-04-02 22:55:17,358 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:17,427 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 1 proven. 1 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:17,428 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:17,492 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:17,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1585158160] [2023-04-02 22:55:17,492 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:17,492 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [800731553] [2023-04-02 22:55:17,493 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [800731553] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:55:17,493 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1692174110] [2023-04-02 22:55:17,496 INFO L159 IcfgInterpreter]: Started Sifa with 26 locations of interest [2023-04-02 22:55:17,497 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:17,498 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:17,498 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:17,498 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:17,526 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:17,754 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 14 for LOIs [2023-04-02 22:55:17,757 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:17,759 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:17,765 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:18,454 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleSifa [1692174110] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:55:18,454 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:55:18,454 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [20] imperfect sequences [7] total 26 [2023-04-02 22:55:18,455 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1876812971] [2023-04-02 22:55:18,455 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:55:18,455 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 21 states [2023-04-02 22:55:18,455 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:18,456 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 21 interpolants. [2023-04-02 22:55:18,456 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=117, Invalid=695, Unknown=0, NotChecked=0, Total=812 [2023-04-02 22:55:18,456 INFO L87 Difference]: Start difference. First operand 129 states and 177 transitions. Second operand has 21 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 14 states have internal predecessors, (17), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-04-02 22:55:19,142 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:19,143 INFO L93 Difference]: Finished difference Result 174 states and 240 transitions. [2023-04-02 22:55:19,143 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-04-02 22:55:19,143 INFO L78 Accepts]: Start accepts. Automaton has has 21 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 14 states have internal predecessors, (17), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) Word has length 29 [2023-04-02 22:55:19,144 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:19,145 INFO L225 Difference]: With dead ends: 174 [2023-04-02 22:55:19,146 INFO L226 Difference]: Without dead ends: 130 [2023-04-02 22:55:19,149 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 34 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 365 ImplicationChecksByTransitivity, 1.1s TimeCoverageRelationStatistics Valid=195, Invalid=1137, Unknown=0, NotChecked=0, Total=1332 [2023-04-02 22:55:19,151 INFO L413 NwaCegarLoop]: 13 mSDtfsCounter, 19 mSDsluCounter, 33 mSDsCounter, 0 mSdLazyCounter, 388 mSolverCounterSat, 23 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 22 SdHoareTripleChecker+Valid, 46 SdHoareTripleChecker+Invalid, 411 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 23 IncrementalHoareTripleChecker+Valid, 388 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.3s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:19,151 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [22 Valid, 46 Invalid, 411 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [23 Valid, 388 Invalid, 0 Unknown, 0 Unchecked, 0.3s Time] [2023-04-02 22:55:19,151 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 130 states. [2023-04-02 22:55:19,181 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 130 to 129. [2023-04-02 22:55:19,181 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 129 states, 95 states have (on average 1.3368421052631578) internal successors, (127), 96 states have internal predecessors, (127), 25 states have call successors, (25), 9 states have call predecessors, (25), 8 states have return successors, (23), 23 states have call predecessors, (23), 23 states have call successors, (23) [2023-04-02 22:55:19,184 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 129 states to 129 states and 175 transitions. [2023-04-02 22:55:19,185 INFO L78 Accepts]: Start accepts. Automaton has 129 states and 175 transitions. Word has length 29 [2023-04-02 22:55:19,185 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:19,185 INFO L495 AbstractCegarLoop]: Abstraction has 129 states and 175 transitions. [2023-04-02 22:55:19,185 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 21 states, 15 states have (on average 1.1333333333333333) internal successors, (17), 14 states have internal predecessors, (17), 5 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2023-04-02 22:55:19,185 INFO L276 IsEmpty]: Start isEmpty. Operand 129 states and 175 transitions. [2023-04-02 22:55:19,188 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 32 [2023-04-02 22:55:19,188 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:19,188 INFO L195 NwaCegarLoop]: trace 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] [2023-04-02 22:55:19,197 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:19,393 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable7 [2023-04-02 22:55:19,394 INFO L420 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:19,394 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:19,394 INFO L85 PathProgramCache]: Analyzing trace with hash -51344455, now seen corresponding path program 1 times [2023-04-02 22:55:19,394 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:19,394 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [145259886] [2023-04-02 22:55:19,394 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:19,394 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:19,403 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:19,403 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1999461399] [2023-04-02 22:55:19,404 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:19,404 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:19,404 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:19,417 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:19,419 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2023-04-02 22:55:19,458 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:19,459 INFO L262 TraceCheckSpWp]: Trace formula consists of 144 conjuncts, 31 conjunts are in the unsatisfiable core [2023-04-02 22:55:19,461 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:19,616 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 7 refuted. 0 times theorem prover too weak. 1 trivial. 0 not checked. [2023-04-02 22:55:19,616 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:19,711 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 0 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:19,711 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:19,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [145259886] [2023-04-02 22:55:19,711 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:19,711 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1999461399] [2023-04-02 22:55:19,712 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1999461399] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:55:19,712 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1181424432] [2023-04-02 22:55:19,713 INFO L159 IcfgInterpreter]: Started Sifa with 24 locations of interest [2023-04-02 22:55:19,714 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:19,714 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:19,714 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:19,714 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:19,739 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:21,488 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 118 for LOIs [2023-04-02 22:55:21,558 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:21,560 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:21,562 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:29,070 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '2984#(and (<= 1 |#StackHeapBarrier|) (< ~counter~0 101) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (<= 3 ~counter~0) (= |#NULL.base| 0))' at error location [2023-04-02 22:55:29,070 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:55:29,070 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:55:29,070 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 6] total 13 [2023-04-02 22:55:29,071 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [852783226] [2023-04-02 22:55:29,071 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:55:29,071 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 13 states [2023-04-02 22:55:29,071 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:29,072 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 13 interpolants. [2023-04-02 22:55:29,072 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=105, Invalid=1017, Unknown=0, NotChecked=0, Total=1122 [2023-04-02 22:55:29,072 INFO L87 Difference]: Start difference. First operand 129 states and 175 transitions. Second operand has 13 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 10 states have internal predecessors, (41), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-04-02 22:55:30,899 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:30,899 INFO L93 Difference]: Finished difference Result 180 states and 248 transitions. [2023-04-02 22:55:30,899 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2023-04-02 22:55:30,900 INFO L78 Accepts]: Start accepts. Automaton has has 13 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 10 states have internal predecessors, (41), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 31 [2023-04-02 22:55:30,900 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:30,901 INFO L225 Difference]: With dead ends: 180 [2023-04-02 22:55:30,901 INFO L226 Difference]: Without dead ends: 178 [2023-04-02 22:55:30,902 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 95 GetRequests, 60 SyntacticMatches, 0 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 276 ImplicationChecksByTransitivity, 8.5s TimeCoverageRelationStatistics Valid=125, Invalid=1207, Unknown=0, NotChecked=0, Total=1332 [2023-04-02 22:55:30,903 INFO L413 NwaCegarLoop]: 49 mSDtfsCounter, 85 mSDsluCounter, 248 mSDsCounter, 0 mSdLazyCounter, 253 mSolverCounterSat, 37 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.9s Time, 0 mProtectedPredicate, 0 mProtectedAction, 93 SdHoareTripleChecker+Valid, 297 SdHoareTripleChecker+Invalid, 290 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 37 IncrementalHoareTripleChecker+Valid, 253 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.9s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:30,903 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [93 Valid, 297 Invalid, 290 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [37 Valid, 253 Invalid, 0 Unknown, 0 Unchecked, 0.9s Time] [2023-04-02 22:55:30,903 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 178 states. [2023-04-02 22:55:30,921 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 178 to 167. [2023-04-02 22:55:30,922 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 167 states, 122 states have (on average 1.3442622950819672) internal successors, (164), 123 states have internal predecessors, (164), 33 states have call successors, (33), 12 states have call predecessors, (33), 11 states have return successors, (31), 31 states have call predecessors, (31), 31 states have call successors, (31) [2023-04-02 22:55:30,923 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 167 states to 167 states and 228 transitions. [2023-04-02 22:55:30,923 INFO L78 Accepts]: Start accepts. Automaton has 167 states and 228 transitions. Word has length 31 [2023-04-02 22:55:30,923 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:30,924 INFO L495 AbstractCegarLoop]: Abstraction has 167 states and 228 transitions. [2023-04-02 22:55:30,924 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 13 states, 12 states have (on average 3.4166666666666665) internal successors, (41), 10 states have internal predecessors, (41), 4 states have call successors, (7), 3 states have call predecessors, (7), 2 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2023-04-02 22:55:30,924 INFO L276 IsEmpty]: Start isEmpty. Operand 167 states and 228 transitions. [2023-04-02 22:55:30,924 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 37 [2023-04-02 22:55:30,925 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:30,925 INFO L195 NwaCegarLoop]: trace histogram [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] [2023-04-02 22:55:30,932 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:31,130 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:31,130 INFO L420 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:31,130 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:31,130 INFO L85 PathProgramCache]: Analyzing trace with hash 486113754, now seen corresponding path program 1 times [2023-04-02 22:55:31,130 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:31,131 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1220230420] [2023-04-02 22:55:31,131 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:31,131 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:31,150 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:31,150 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2033238689] [2023-04-02 22:55:31,150 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:31,150 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:31,150 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:31,152 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:31,165 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2023-04-02 22:55:31,231 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:31,233 INFO L262 TraceCheckSpWp]: Trace formula consists of 153 conjuncts, 33 conjunts are in the unsatisfiable core [2023-04-02 22:55:31,234 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:31,380 INFO L134 CoverageAnalysis]: Checked inductivity of 10 backedges. 1 proven. 7 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:31,380 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:31,436 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:31,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1220230420] [2023-04-02 22:55:31,436 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:31,436 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2033238689] [2023-04-02 22:55:31,436 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2033238689] provided 0 perfect and 1 imperfect interpolant sequences [2023-04-02 22:55:31,437 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1704337975] [2023-04-02 22:55:31,438 INFO L159 IcfgInterpreter]: Started Sifa with 27 locations of interest [2023-04-02 22:55:31,438 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:31,439 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:31,439 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:31,439 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:31,454 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:33,785 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 17 for LOIs [2023-04-02 22:55:33,788 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:33,789 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:33,793 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:41,112 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '3638#(and (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (<= ~counter~0 100) (= |#NULL.offset| 0) (<= 3 ~counter~0) (= |#NULL.base| 0))' at error location [2023-04-02 22:55:41,112 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:55:41,112 INFO L185 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:55:41,112 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2023-04-02 22:55:41,112 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [336039700] [2023-04-02 22:55:41,112 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2023-04-02 22:55:41,113 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2023-04-02 22:55:41,113 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:41,113 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2023-04-02 22:55:41,114 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=97, Invalid=1025, Unknown=0, NotChecked=0, Total=1122 [2023-04-02 22:55:41,114 INFO L87 Difference]: Start difference. First operand 167 states and 228 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-04-02 22:55:41,335 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:41,335 INFO L93 Difference]: Finished difference Result 190 states and 255 transitions. [2023-04-02 22:55:41,336 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2023-04-02 22:55:41,336 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 36 [2023-04-02 22:55:41,336 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:41,337 INFO L225 Difference]: With dead ends: 190 [2023-04-02 22:55:41,337 INFO L226 Difference]: Without dead ends: 188 [2023-04-02 22:55:41,338 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 79 GetRequests, 43 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 287 ImplicationChecksByTransitivity, 7.4s TimeCoverageRelationStatistics Valid=115, Invalid=1217, Unknown=0, NotChecked=0, Total=1332 [2023-04-02 22:55:41,341 INFO L413 NwaCegarLoop]: 41 mSDtfsCounter, 46 mSDsluCounter, 165 mSDsCounter, 0 mSdLazyCounter, 207 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 53 SdHoareTripleChecker+Valid, 206 SdHoareTripleChecker+Invalid, 221 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 207 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:41,341 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [53 Valid, 206 Invalid, 221 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 207 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:41,342 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 188 states. [2023-04-02 22:55:41,361 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 188 to 186. [2023-04-02 22:55:41,362 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 186 states, 134 states have (on average 1.328358208955224) internal successors, (178), 135 states have internal predecessors, (178), 37 states have call successors, (37), 15 states have call predecessors, (37), 14 states have return successors, (35), 35 states have call predecessors, (35), 35 states have call successors, (35) [2023-04-02 22:55:41,363 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 186 states to 186 states and 250 transitions. [2023-04-02 22:55:41,363 INFO L78 Accepts]: Start accepts. Automaton has 186 states and 250 transitions. Word has length 36 [2023-04-02 22:55:41,363 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:41,363 INFO L495 AbstractCegarLoop]: Abstraction has 186 states and 250 transitions. [2023-04-02 22:55:41,363 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 2 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2023-04-02 22:55:41,363 INFO L276 IsEmpty]: Start isEmpty. Operand 186 states and 250 transitions. [2023-04-02 22:55:41,364 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 38 [2023-04-02 22:55:41,364 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:41,364 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:55:41,377 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:41,569 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable9 [2023-04-02 22:55:41,570 INFO L420 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:41,570 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:41,570 INFO L85 PathProgramCache]: Analyzing trace with hash 1371325752, now seen corresponding path program 1 times [2023-04-02 22:55:41,570 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:41,570 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1459060323] [2023-04-02 22:55:41,571 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:41,571 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:41,584 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:41,584 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1649129615] [2023-04-02 22:55:41,584 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:41,584 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:41,584 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:41,586 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:41,588 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2023-04-02 22:55:41,633 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:41,634 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 11 conjunts are in the unsatisfiable core [2023-04-02 22:55:41,635 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:41,675 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-04-02 22:55:41,675 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:41,730 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 16 proven. 5 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2023-04-02 22:55:41,731 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:41,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1459060323] [2023-04-02 22:55:41,731 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:41,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1649129615] [2023-04-02 22:55:41,731 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1649129615] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:55:41,731 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [765678832] [2023-04-02 22:55:41,733 INFO L159 IcfgInterpreter]: Started Sifa with 22 locations of interest [2023-04-02 22:55:41,733 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:41,733 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:41,733 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:41,733 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:41,751 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:55:45,560 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 119 for LOIs [2023-04-02 22:55:45,637 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:55:45,639 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:55:45,642 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:55:53,737 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '4431#(and (<= 101 ~counter~0) (<= 1 |#StackHeapBarrier|) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0) (= |#NULL.offset| 0) (= |#NULL.base| 0))' at error location [2023-04-02 22:55:53,737 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:55:53,737 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:55:53,737 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2023-04-02 22:55:53,737 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [295996733] [2023-04-02 22:55:53,737 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:55:53,738 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2023-04-02 22:55:53,738 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:53,738 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2023-04-02 22:55:53,738 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=164, Invalid=766, Unknown=0, NotChecked=0, Total=930 [2023-04-02 22:55:53,739 INFO L87 Difference]: Start difference. First operand 186 states and 250 transitions. Second operand has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:55:53,965 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:53,966 INFO L93 Difference]: Finished difference Result 478 states and 661 transitions. [2023-04-02 22:55:53,966 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2023-04-02 22:55:53,966 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) Word has length 37 [2023-04-02 22:55:53,966 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:53,969 INFO L225 Difference]: With dead ends: 478 [2023-04-02 22:55:53,969 INFO L226 Difference]: Without dead ends: 402 [2023-04-02 22:55:53,970 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 115 GetRequests, 81 SyntacticMatches, 0 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 424 ImplicationChecksByTransitivity, 8.2s TimeCoverageRelationStatistics Valid=207, Invalid=1053, Unknown=0, NotChecked=0, Total=1260 [2023-04-02 22:55:53,970 INFO L413 NwaCegarLoop]: 44 mSDtfsCounter, 124 mSDsluCounter, 239 mSDsCounter, 0 mSdLazyCounter, 124 mSolverCounterSat, 20 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 124 SdHoareTripleChecker+Valid, 283 SdHoareTripleChecker+Invalid, 144 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 20 IncrementalHoareTripleChecker+Valid, 124 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:53,970 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [124 Valid, 283 Invalid, 144 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [20 Valid, 124 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:53,971 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 402 states. [2023-04-02 22:55:54,013 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 402 to 372. [2023-04-02 22:55:54,013 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 372 states, 261 states have (on average 1.3103448275862069) internal successors, (342), 265 states have internal predecessors, (342), 84 states have call successors, (84), 27 states have call predecessors, (84), 26 states have return successors, (79), 79 states have call predecessors, (79), 79 states have call successors, (79) [2023-04-02 22:55:54,016 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 372 states to 372 states and 505 transitions. [2023-04-02 22:55:54,016 INFO L78 Accepts]: Start accepts. Automaton has 372 states and 505 transitions. Word has length 37 [2023-04-02 22:55:54,016 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:54,016 INFO L495 AbstractCegarLoop]: Abstraction has 372 states and 505 transitions. [2023-04-02 22:55:54,016 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.5) internal successors, (42), 12 states have internal predecessors, (42), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:55:54,016 INFO L276 IsEmpty]: Start isEmpty. Operand 372 states and 505 transitions. [2023-04-02 22:55:54,017 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-04-02 22:55:54,017 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:54,017 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:55:54,023 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:54,223 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2023-04-02 22:55:54,223 INFO L420 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:54,223 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:54,223 INFO L85 PathProgramCache]: Analyzing trace with hash 1047985326, now seen corresponding path program 2 times [2023-04-02 22:55:54,223 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:54,224 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [130311389] [2023-04-02 22:55:54,224 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:54,224 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:54,231 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:54,232 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [531073004] [2023-04-02 22:55:54,232 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:55:54,232 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:54,232 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:54,234 INFO L229 MonitoredProcess]: Starting monitored process 13 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:54,237 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Waiting until timeout for monitored process [2023-04-02 22:55:54,286 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2023-04-02 22:55:54,287 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:55:54,287 INFO L262 TraceCheckSpWp]: Trace formula consists of 174 conjuncts, 5 conjunts are in the unsatisfiable core [2023-04-02 22:55:54,289 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:54,308 INFO L134 CoverageAnalysis]: Checked inductivity of 21 backedges. 19 proven. 0 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:54,308 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:55:54,309 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:54,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [130311389] [2023-04-02 22:55:54,309 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:54,309 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [531073004] [2023-04-02 22:55:54,309 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [531073004] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:55:54,309 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:55:54,309 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-04-02 22:55:54,309 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [562025462] [2023-04-02 22:55:54,309 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:55:54,310 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:55:54,310 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:55:54,310 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:55:54,310 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:55:54,311 INFO L87 Difference]: Start difference. First operand 372 states and 505 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:55:54,435 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:55:54,436 INFO L93 Difference]: Finished difference Result 539 states and 766 transitions. [2023-04-02 22:55:54,436 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-04-02 22:55:54,436 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 38 [2023-04-02 22:55:54,436 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:55:54,439 INFO L225 Difference]: With dead ends: 539 [2023-04-02 22:55:54,439 INFO L226 Difference]: Without dead ends: 454 [2023-04-02 22:55:54,439 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 40 GetRequests, 35 SyntacticMatches, 0 SemanticMatches, 5 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=15, Invalid=27, Unknown=0, NotChecked=0, Total=42 [2023-04-02 22:55:54,440 INFO L413 NwaCegarLoop]: 52 mSDtfsCounter, 30 mSDsluCounter, 93 mSDsCounter, 0 mSdLazyCounter, 90 mSolverCounterSat, 8 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 34 SdHoareTripleChecker+Valid, 145 SdHoareTripleChecker+Invalid, 98 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 8 IncrementalHoareTripleChecker+Valid, 90 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2023-04-02 22:55:54,440 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [34 Valid, 145 Invalid, 98 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [8 Valid, 90 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2023-04-02 22:55:54,441 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 454 states. [2023-04-02 22:55:54,484 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 454 to 372. [2023-04-02 22:55:54,485 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 372 states, 265 states have (on average 1.3169811320754716) internal successors, (349), 269 states have internal predecessors, (349), 80 states have call successors, (80), 27 states have call predecessors, (80), 26 states have return successors, (75), 75 states have call predecessors, (75), 75 states have call successors, (75) [2023-04-02 22:55:54,487 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 372 states to 372 states and 504 transitions. [2023-04-02 22:55:54,487 INFO L78 Accepts]: Start accepts. Automaton has 372 states and 504 transitions. Word has length 38 [2023-04-02 22:55:54,487 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:55:54,487 INFO L495 AbstractCegarLoop]: Abstraction has 372 states and 504 transitions. [2023-04-02 22:55:54,487 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2023-04-02 22:55:54,487 INFO L276 IsEmpty]: Start isEmpty. Operand 372 states and 504 transitions. [2023-04-02 22:55:54,488 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 39 [2023-04-02 22:55:54,488 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:55:54,488 INFO L195 NwaCegarLoop]: trace histogram [3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:55:54,494 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (13)] Forceful destruction successful, exit code 0 [2023-04-02 22:55:54,693 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 13 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable11 [2023-04-02 22:55:54,694 INFO L420 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:55:54,694 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:55:54,694 INFO L85 PathProgramCache]: Analyzing trace with hash -989802546, now seen corresponding path program 1 times [2023-04-02 22:55:54,694 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:55:54,694 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2145122215] [2023-04-02 22:55:54,694 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:54,695 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:55:54,711 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:55:54,711 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [979768281] [2023-04-02 22:55:54,711 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:55:54,711 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:55:54,711 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:55:54,712 INFO L229 MonitoredProcess]: Starting monitored process 14 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:55:54,715 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Waiting until timeout for monitored process [2023-04-02 22:55:54,760 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:55:54,760 INFO L262 TraceCheckSpWp]: Trace formula consists of 173 conjuncts, 13 conjunts are in the unsatisfiable core [2023-04-02 22:55:54,763 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:55:54,808 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:54,808 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:55:54,882 INFO L134 CoverageAnalysis]: Checked inductivity of 19 backedges. 11 proven. 6 refuted. 0 times theorem prover too weak. 2 trivial. 0 not checked. [2023-04-02 22:55:54,882 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:55:54,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2145122215] [2023-04-02 22:55:54,882 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:55:54,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [979768281] [2023-04-02 22:55:54,882 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [979768281] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:55:54,882 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [638778594] [2023-04-02 22:55:54,884 INFO L159 IcfgInterpreter]: Started Sifa with 25 locations of interest [2023-04-02 22:55:54,884 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:55:54,884 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:55:54,884 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:55:54,884 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:55:54,905 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:56:03,141 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 11 for LOIs [2023-04-02 22:56:03,145 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:56:03,146 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:56:03,151 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:56:03,548 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '7358#(and (<= 101 ~counter~0) (<= ~counter~0 101) (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:56:03,549 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:56:03,549 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:56:03,549 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2023-04-02 22:56:03,549 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1163429892] [2023-04-02 22:56:03,549 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:56:03,550 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2023-04-02 22:56:03,550 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:03,550 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2023-04-02 22:56:03,551 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=219, Invalid=971, Unknown=0, NotChecked=0, Total=1190 [2023-04-02 22:56:03,551 INFO L87 Difference]: Start difference. First operand 372 states and 504 transitions. Second operand has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:56:03,862 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:56:03,862 INFO L93 Difference]: Finished difference Result 785 states and 1067 transitions. [2023-04-02 22:56:03,862 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 20 states. [2023-04-02 22:56:03,863 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) Word has length 38 [2023-04-02 22:56:03,863 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:56:03,865 INFO L225 Difference]: With dead ends: 785 [2023-04-02 22:56:03,866 INFO L226 Difference]: Without dead ends: 570 [2023-04-02 22:56:03,867 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 120 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 40 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 549 ImplicationChecksByTransitivity, 0.5s TimeCoverageRelationStatistics Valid=299, Invalid=1423, Unknown=0, NotChecked=0, Total=1722 [2023-04-02 22:56:03,868 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 186 mSDsluCounter, 251 mSDsCounter, 0 mSdLazyCounter, 132 mSolverCounterSat, 42 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 186 SdHoareTripleChecker+Valid, 290 SdHoareTripleChecker+Invalid, 174 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 42 IncrementalHoareTripleChecker+Valid, 132 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:56:03,868 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [186 Valid, 290 Invalid, 174 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [42 Valid, 132 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:56:03,869 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 570 states. [2023-04-02 22:56:03,937 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 570 to 533. [2023-04-02 22:56:03,938 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 533 states, 380 states have (on average 1.2815789473684212) internal successors, (487), 386 states have internal predecessors, (487), 118 states have call successors, (118), 35 states have call predecessors, (118), 34 states have return successors, (111), 111 states have call predecessors, (111), 111 states have call successors, (111) [2023-04-02 22:56:03,941 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 533 states to 533 states and 716 transitions. [2023-04-02 22:56:03,941 INFO L78 Accepts]: Start accepts. Automaton has 533 states and 716 transitions. Word has length 38 [2023-04-02 22:56:03,941 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:56:03,941 INFO L495 AbstractCegarLoop]: Abstraction has 533 states and 716 transitions. [2023-04-02 22:56:03,941 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.4285714285714284) internal successors, (48), 14 states have internal predecessors, (48), 4 states have call successors, (8), 4 states have call predecessors, (8), 3 states have return successors, (6), 2 states have call predecessors, (6), 3 states have call successors, (6) [2023-04-02 22:56:03,942 INFO L276 IsEmpty]: Start isEmpty. Operand 533 states and 716 transitions. [2023-04-02 22:56:03,942 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 42 [2023-04-02 22:56:03,942 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:56:03,942 INFO L195 NwaCegarLoop]: trace histogram [3, 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] [2023-04-02 22:56:03,949 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (14)] Forceful destruction successful, exit code 0 [2023-04-02 22:56:04,148 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 14 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2023-04-02 22:56:04,148 INFO L420 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:56:04,149 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:56:04,149 INFO L85 PathProgramCache]: Analyzing trace with hash -1031319527, now seen corresponding path program 1 times [2023-04-02 22:56:04,149 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:56:04,149 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [356989763] [2023-04-02 22:56:04,149 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:04,149 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:56:04,155 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:56:04,156 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1478405295] [2023-04-02 22:56:04,156 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:04,156 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:04,156 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:56:04,157 INFO L229 MonitoredProcess]: Starting monitored process 15 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:56:04,159 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Waiting until timeout for monitored process [2023-04-02 22:56:04,196 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:56:04,197 INFO L262 TraceCheckSpWp]: Trace formula consists of 162 conjuncts, 15 conjunts are in the unsatisfiable core [2023-04-02 22:56:04,198 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:56:04,245 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 6 trivial. 0 not checked. [2023-04-02 22:56:04,245 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:56:04,319 INFO L134 CoverageAnalysis]: Checked inductivity of 16 backedges. 7 proven. 0 refuted. 0 times theorem prover too weak. 9 trivial. 0 not checked. [2023-04-02 22:56:04,319 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:56:04,319 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [356989763] [2023-04-02 22:56:04,319 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:56:04,319 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1478405295] [2023-04-02 22:56:04,319 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1478405295] provided 1 perfect and 1 imperfect interpolant sequences [2023-04-02 22:56:04,319 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:56:04,319 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [7] total 9 [2023-04-02 22:56:04,320 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [32639683] [2023-04-02 22:56:04,320 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:56:04,320 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2023-04-02 22:56:04,320 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:04,321 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2023-04-02 22:56:04,321 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=18, Invalid=54, Unknown=0, NotChecked=0, Total=72 [2023-04-02 22:56:04,321 INFO L87 Difference]: Start difference. First operand 533 states and 716 transitions. Second operand has 6 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2023-04-02 22:56:04,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:56:04,451 INFO L93 Difference]: Finished difference Result 667 states and 893 transitions. [2023-04-02 22:56:04,451 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-04-02 22:56:04,451 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) Word has length 41 [2023-04-02 22:56:04,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:56:04,454 INFO L225 Difference]: With dead ends: 667 [2023-04-02 22:56:04,454 INFO L226 Difference]: Without dead ends: 665 [2023-04-02 22:56:04,455 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 82 GetRequests, 72 SyntacticMatches, 2 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=22, Invalid=68, Unknown=0, NotChecked=0, Total=90 [2023-04-02 22:56:04,455 INFO L413 NwaCegarLoop]: 34 mSDtfsCounter, 14 mSDsluCounter, 80 mSDsCounter, 0 mSdLazyCounter, 57 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 17 SdHoareTripleChecker+Valid, 114 SdHoareTripleChecker+Invalid, 60 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 57 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:56:04,456 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [17 Valid, 114 Invalid, 60 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 57 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:56:04,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 665 states. [2023-04-02 22:56:04,542 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 665 to 650. [2023-04-02 22:56:04,543 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 650 states, 453 states have (on average 1.2759381898454747) internal successors, (578), 459 states have internal predecessors, (578), 150 states have call successors, (150), 47 states have call predecessors, (150), 46 states have return successors, (143), 143 states have call predecessors, (143), 143 states have call successors, (143) [2023-04-02 22:56:04,546 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 650 states to 650 states and 871 transitions. [2023-04-02 22:56:04,546 INFO L78 Accepts]: Start accepts. Automaton has 650 states and 871 transitions. Word has length 41 [2023-04-02 22:56:04,546 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:56:04,546 INFO L495 AbstractCegarLoop]: Abstraction has 650 states and 871 transitions. [2023-04-02 22:56:04,547 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 4.6) internal successors, (23), 4 states have internal predecessors, (23), 3 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 3 states have call predecessors, (5), 2 states have call successors, (5) [2023-04-02 22:56:04,547 INFO L276 IsEmpty]: Start isEmpty. Operand 650 states and 871 transitions. [2023-04-02 22:56:04,547 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 47 [2023-04-02 22:56:04,547 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:56:04,547 INFO L195 NwaCegarLoop]: trace histogram [4, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:56:04,557 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (15)] Forceful destruction successful, exit code 0 [2023-04-02 22:56:04,753 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable13,15 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:04,753 INFO L420 AbstractCegarLoop]: === Iteration 15 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:56:04,753 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:56:04,753 INFO L85 PathProgramCache]: Analyzing trace with hash 2131273978, now seen corresponding path program 1 times [2023-04-02 22:56:04,753 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:56:04,754 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1695565710] [2023-04-02 22:56:04,754 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:04,754 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:56:04,763 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:56:04,763 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2047722900] [2023-04-02 22:56:04,763 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:04,763 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:04,764 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:56:04,764 INFO L229 MonitoredProcess]: Starting monitored process 16 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:56:04,765 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Waiting until timeout for monitored process [2023-04-02 22:56:04,806 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:56:04,807 INFO L262 TraceCheckSpWp]: Trace formula consists of 171 conjuncts, 24 conjunts are in the unsatisfiable core [2023-04-02 22:56:04,809 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:56:05,114 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 8 proven. 11 refuted. 0 times theorem prover too weak. 7 trivial. 0 not checked. [2023-04-02 22:56:05,114 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:56:06,713 INFO L134 CoverageAnalysis]: Checked inductivity of 26 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 20 trivial. 0 not checked. [2023-04-02 22:56:06,714 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:56:06,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1695565710] [2023-04-02 22:56:06,714 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:56:06,714 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2047722900] [2023-04-02 22:56:06,714 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2047722900] provided 1 perfect and 1 imperfect interpolant sequences [2023-04-02 22:56:06,714 INFO L185 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2023-04-02 22:56:06,714 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [13] total 15 [2023-04-02 22:56:06,714 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [807005371] [2023-04-02 22:56:06,714 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:56:06,715 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:56:06,715 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:06,715 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:56:06,715 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=37, Invalid=173, Unknown=0, NotChecked=0, Total=210 [2023-04-02 22:56:06,715 INFO L87 Difference]: Start difference. First operand 650 states and 871 transitions. Second operand has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-04-02 22:56:06,840 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:56:06,841 INFO L93 Difference]: Finished difference Result 680 states and 900 transitions. [2023-04-02 22:56:06,841 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-04-02 22:56:06,841 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) Word has length 46 [2023-04-02 22:56:06,841 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:56:06,844 INFO L225 Difference]: With dead ends: 680 [2023-04-02 22:56:06,844 INFO L226 Difference]: Without dead ends: 678 [2023-04-02 22:56:06,845 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 77 SyntacticMatches, 1 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 45 ImplicationChecksByTransitivity, 1.7s TimeCoverageRelationStatistics Valid=41, Invalid=199, Unknown=0, NotChecked=0, Total=240 [2023-04-02 22:56:06,845 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 11 mSDsluCounter, 86 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 2 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 126 SdHoareTripleChecker+Invalid, 55 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 2 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:56:06,846 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 126 Invalid, 55 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [2 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:56:06,846 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 678 states. [2023-04-02 22:56:06,929 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 678 to 674. [2023-04-02 22:56:06,930 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 674 states, 471 states have (on average 1.2632696390658174) internal successors, (595), 477 states have internal predecessors, (595), 150 states have call successors, (150), 53 states have call predecessors, (150), 52 states have return successors, (143), 143 states have call predecessors, (143), 143 states have call successors, (143) [2023-04-02 22:56:06,932 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 674 states to 674 states and 888 transitions. [2023-04-02 22:56:06,933 INFO L78 Accepts]: Start accepts. Automaton has 674 states and 888 transitions. Word has length 46 [2023-04-02 22:56:06,933 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:56:06,933 INFO L495 AbstractCegarLoop]: Abstraction has 674 states and 888 transitions. [2023-04-02 22:56:06,933 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.0) internal successors, (20), 4 states have internal predecessors, (20), 2 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (6), 2 states have call predecessors, (6), 2 states have call successors, (6) [2023-04-02 22:56:06,933 INFO L276 IsEmpty]: Start isEmpty. Operand 674 states and 888 transitions. [2023-04-02 22:56:06,933 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 54 [2023-04-02 22:56:06,934 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:56:06,934 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 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] [2023-04-02 22:56:06,943 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (16)] Forceful destruction successful, exit code 0 [2023-04-02 22:56:07,143 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 16 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable14 [2023-04-02 22:56:07,144 INFO L420 AbstractCegarLoop]: === Iteration 16 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:56:07,144 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:56:07,144 INFO L85 PathProgramCache]: Analyzing trace with hash 724937013, now seen corresponding path program 1 times [2023-04-02 22:56:07,144 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:56:07,145 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1271949868] [2023-04-02 22:56:07,145 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:07,145 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:56:07,164 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:56:07,165 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [454555837] [2023-04-02 22:56:07,165 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:07,165 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:07,165 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:56:07,169 INFO L229 MonitoredProcess]: Starting monitored process 17 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:56:07,171 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Waiting until timeout for monitored process [2023-04-02 22:56:07,220 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:56:07,221 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 60 conjunts are in the unsatisfiable core [2023-04-02 22:56:07,223 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:56:07,854 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 14 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-04-02 22:56:07,854 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:56:08,483 INFO L134 CoverageAnalysis]: Checked inductivity of 40 backedges. 10 proven. 13 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2023-04-02 22:56:08,483 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:56:08,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1271949868] [2023-04-02 22:56:08,483 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:56:08,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [454555837] [2023-04-02 22:56:08,483 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [454555837] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:56:08,483 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [858386497] [2023-04-02 22:56:08,485 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2023-04-02 22:56:08,485 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:56:08,485 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:56:08,486 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:56:08,486 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:56:08,500 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:56:21,125 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-04-02 22:56:21,139 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:56:21,140 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:56:21,143 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:56:25,402 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '14021#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:56:25,402 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:56:25,402 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:56:25,402 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 25 [2023-04-02 22:56:25,402 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1343620287] [2023-04-02 22:56:25,403 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:56:25,403 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2023-04-02 22:56:25,403 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:25,404 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2023-04-02 22:56:25,404 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=174, Invalid=1896, Unknown=0, NotChecked=0, Total=2070 [2023-04-02 22:56:25,404 INFO L87 Difference]: Start difference. First operand 674 states and 888 transitions. Second operand has 25 states, 22 states have (on average 2.409090909090909) internal successors, (53), 22 states have internal predecessors, (53), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2023-04-02 22:56:33,401 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:56:33,401 INFO L93 Difference]: Finished difference Result 1248 states and 1667 transitions. [2023-04-02 22:56:33,402 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 36 states. [2023-04-02 22:56:33,402 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 22 states have (on average 2.409090909090909) internal successors, (53), 22 states have internal predecessors, (53), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 53 [2023-04-02 22:56:33,402 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:56:33,408 INFO L225 Difference]: With dead ends: 1248 [2023-04-02 22:56:33,408 INFO L226 Difference]: Without dead ends: 969 [2023-04-02 22:56:33,411 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 186 GetRequests, 110 SyntacticMatches, 5 SemanticMatches, 71 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1605 ImplicationChecksByTransitivity, 10.3s TimeCoverageRelationStatistics Valid=596, Invalid=4660, Unknown=0, NotChecked=0, Total=5256 [2023-04-02 22:56:33,411 INFO L413 NwaCegarLoop]: 46 mSDtfsCounter, 274 mSDsluCounter, 418 mSDsCounter, 0 mSdLazyCounter, 610 mSolverCounterSat, 193 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 2.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 280 SdHoareTripleChecker+Valid, 464 SdHoareTripleChecker+Invalid, 803 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 193 IncrementalHoareTripleChecker+Valid, 610 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 2.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:56:33,411 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [280 Valid, 464 Invalid, 803 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [193 Valid, 610 Invalid, 0 Unknown, 0 Unchecked, 2.2s Time] [2023-04-02 22:56:33,413 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 969 states. [2023-04-02 22:56:33,641 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 969 to 825. [2023-04-02 22:56:33,642 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 825 states, 591 states have (on average 1.260575296108291) internal successors, (745), 595 states have internal predecessors, (745), 172 states have call successors, (172), 62 states have call predecessors, (172), 61 states have return successors, (167), 167 states have call predecessors, (167), 167 states have call successors, (167) [2023-04-02 22:56:33,646 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 825 states to 825 states and 1084 transitions. [2023-04-02 22:56:33,646 INFO L78 Accepts]: Start accepts. Automaton has 825 states and 1084 transitions. Word has length 53 [2023-04-02 22:56:33,647 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:56:33,647 INFO L495 AbstractCegarLoop]: Abstraction has 825 states and 1084 transitions. [2023-04-02 22:56:33,647 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 22 states have (on average 2.409090909090909) internal successors, (53), 22 states have internal predecessors, (53), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2023-04-02 22:56:33,647 INFO L276 IsEmpty]: Start isEmpty. Operand 825 states and 1084 transitions. [2023-04-02 22:56:33,648 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 60 [2023-04-02 22:56:33,648 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:56:33,648 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 3, 3, 3, 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] [2023-04-02 22:56:33,659 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (17)] Forceful destruction successful, exit code 0 [2023-04-02 22:56:33,853 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 17 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable15 [2023-04-02 22:56:33,853 INFO L420 AbstractCegarLoop]: === Iteration 17 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:56:33,853 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:56:33,853 INFO L85 PathProgramCache]: Analyzing trace with hash 1191530980, now seen corresponding path program 1 times [2023-04-02 22:56:33,854 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:56:33,854 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [121925527] [2023-04-02 22:56:33,854 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:33,854 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:56:33,861 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:56:33,861 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1258004974] [2023-04-02 22:56:33,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:33,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:33,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:56:33,862 INFO L229 MonitoredProcess]: Starting monitored process 18 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:56:33,863 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Waiting until timeout for monitored process [2023-04-02 22:56:33,908 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:56:33,909 INFO L262 TraceCheckSpWp]: Trace formula consists of 210 conjuncts, 17 conjunts are in the unsatisfiable core [2023-04-02 22:56:33,910 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:56:33,989 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-04-02 22:56:33,990 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:56:34,104 INFO L134 CoverageAnalysis]: Checked inductivity of 51 backedges. 8 proven. 17 refuted. 0 times theorem prover too weak. 26 trivial. 0 not checked. [2023-04-02 22:56:34,105 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:56:34,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [121925527] [2023-04-02 22:56:34,105 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:56:34,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1258004974] [2023-04-02 22:56:34,105 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1258004974] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:56:34,105 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1199649461] [2023-04-02 22:56:34,106 INFO L159 IcfgInterpreter]: Started Sifa with 32 locations of interest [2023-04-02 22:56:34,107 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:56:34,107 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:56:34,107 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:56:34,107 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:56:34,121 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:56:41,691 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-04-02 22:56:41,693 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:56:41,694 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:56:41,696 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:56:44,803 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '17456#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:56:44,803 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:56:44,804 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:56:44,804 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 18 [2023-04-02 22:56:44,804 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [166720953] [2023-04-02 22:56:44,804 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:56:44,804 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 18 states [2023-04-02 22:56:44,804 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:44,805 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 18 interpolants. [2023-04-02 22:56:44,805 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=297, Invalid=1425, Unknown=0, NotChecked=0, Total=1722 [2023-04-02 22:56:44,805 INFO L87 Difference]: Start difference. First operand 825 states and 1084 transitions. Second operand has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 6 states have call successors, (16), 5 states have call predecessors, (16), 4 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) [2023-04-02 22:56:45,785 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:56:45,786 INFO L93 Difference]: Finished difference Result 1840 states and 2543 transitions. [2023-04-02 22:56:45,786 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 28 states. [2023-04-02 22:56:45,786 INFO L78 Accepts]: Start accepts. Automaton has has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 6 states have call successors, (16), 5 states have call predecessors, (16), 4 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) Word has length 59 [2023-04-02 22:56:45,786 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:56:45,794 INFO L225 Difference]: With dead ends: 1840 [2023-04-02 22:56:45,794 INFO L226 Difference]: Without dead ends: 1818 [2023-04-02 22:56:45,796 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 187 GetRequests, 136 SyntacticMatches, 0 SemanticMatches, 51 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 923 ImplicationChecksByTransitivity, 3.5s TimeCoverageRelationStatistics Valid=459, Invalid=2297, Unknown=0, NotChecked=0, Total=2756 [2023-04-02 22:56:45,797 INFO L413 NwaCegarLoop]: 40 mSDtfsCounter, 303 mSDsluCounter, 266 mSDsCounter, 0 mSdLazyCounter, 185 mSolverCounterSat, 74 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 303 SdHoareTripleChecker+Valid, 306 SdHoareTripleChecker+Invalid, 259 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 74 IncrementalHoareTripleChecker+Valid, 185 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2023-04-02 22:56:45,797 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [303 Valid, 306 Invalid, 259 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [74 Valid, 185 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2023-04-02 22:56:45,799 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 1818 states. [2023-04-02 22:56:46,272 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 1818 to 1719. [2023-04-02 22:56:46,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1719 states, 1254 states have (on average 1.2878787878787878) internal successors, (1615), 1274 states have internal predecessors, (1615), 367 states have call successors, (367), 98 states have call predecessors, (367), 97 states have return successors, (359), 346 states have call predecessors, (359), 359 states have call successors, (359) [2023-04-02 22:56:46,282 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1719 states to 1719 states and 2341 transitions. [2023-04-02 22:56:46,282 INFO L78 Accepts]: Start accepts. Automaton has 1719 states and 2341 transitions. Word has length 59 [2023-04-02 22:56:46,283 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:56:46,283 INFO L495 AbstractCegarLoop]: Abstraction has 1719 states and 2341 transitions. [2023-04-02 22:56:46,283 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 18 states, 18 states have (on average 3.5) internal successors, (63), 18 states have internal predecessors, (63), 6 states have call successors, (16), 5 states have call predecessors, (16), 4 states have return successors, (14), 4 states have call predecessors, (14), 5 states have call successors, (14) [2023-04-02 22:56:46,283 INFO L276 IsEmpty]: Start isEmpty. Operand 1719 states and 2341 transitions. [2023-04-02 22:56:46,284 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 66 [2023-04-02 22:56:46,284 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:56:46,284 INFO L195 NwaCegarLoop]: trace histogram [5, 4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:56:46,293 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (18)] Forceful destruction successful, exit code 0 [2023-04-02 22:56:46,490 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 18 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable16 [2023-04-02 22:56:46,490 INFO L420 AbstractCegarLoop]: === Iteration 18 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:56:46,490 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:56:46,490 INFO L85 PathProgramCache]: Analyzing trace with hash -1631462211, now seen corresponding path program 1 times [2023-04-02 22:56:46,490 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:56:46,490 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1298636943] [2023-04-02 22:56:46,491 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:46,491 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:56:46,497 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:56:46,497 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1816309349] [2023-04-02 22:56:46,497 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:56:46,497 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:56:46,497 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:56:46,498 INFO L229 MonitoredProcess]: Starting monitored process 19 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:56:46,501 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Waiting until timeout for monitored process [2023-04-02 22:56:46,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:56:46,552 INFO L262 TraceCheckSpWp]: Trace formula consists of 230 conjuncts, 33 conjunts are in the unsatisfiable core [2023-04-02 22:56:46,554 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:56:47,355 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 10 proven. 39 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2023-04-02 22:56:47,355 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:56:47,763 INFO L134 CoverageAnalysis]: Checked inductivity of 65 backedges. 32 proven. 10 refuted. 0 times theorem prover too weak. 23 trivial. 0 not checked. [2023-04-02 22:56:47,764 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:56:47,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1298636943] [2023-04-02 22:56:47,764 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:56:47,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1816309349] [2023-04-02 22:56:47,764 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1816309349] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:56:47,764 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [1049231119] [2023-04-02 22:56:47,765 INFO L159 IcfgInterpreter]: Started Sifa with 31 locations of interest [2023-04-02 22:56:47,765 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:56:47,766 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:56:47,766 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:56:47,766 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:56:47,780 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:56:55,807 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-04-02 22:56:55,809 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:56:55,810 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:56:55,812 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:56:59,726 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '23017#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:56:59,726 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:56:59,726 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:56:59,726 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 8] total 22 [2023-04-02 22:56:59,726 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1062043128] [2023-04-02 22:56:59,727 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:56:59,728 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2023-04-02 22:56:59,728 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:56:59,729 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2023-04-02 22:56:59,734 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=140, Invalid=1752, Unknown=0, NotChecked=0, Total=1892 [2023-04-02 22:56:59,734 INFO L87 Difference]: Start difference. First operand 1719 states and 2341 transitions. Second operand has 22 states, 21 states have (on average 3.4285714285714284) internal successors, (72), 18 states have internal predecessors, (72), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2023-04-02 22:58:22,240 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:58:23,784 WARN L539 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.54s for a HTC check with result INVALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2023-04-02 22:58:25,012 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:58:25,013 INFO L93 Difference]: Finished difference Result 2621 states and 3683 transitions. [2023-04-02 22:58:25,013 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 54 states. [2023-04-02 22:58:25,013 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 21 states have (on average 3.4285714285714284) internal successors, (72), 18 states have internal predecessors, (72), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) Word has length 65 [2023-04-02 22:58:25,014 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:58:25,025 INFO L225 Difference]: With dead ends: 2621 [2023-04-02 22:58:25,025 INFO L226 Difference]: Without dead ends: 2619 [2023-04-02 22:58:25,028 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 267 GetRequests, 178 SyntacticMatches, 1 SemanticMatches, 88 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2160 ImplicationChecksByTransitivity, 67.6s TimeCoverageRelationStatistics Valid=944, Invalid=7066, Unknown=0, NotChecked=0, Total=8010 [2023-04-02 22:58:25,029 INFO L413 NwaCegarLoop]: 81 mSDtfsCounter, 337 mSDsluCounter, 560 mSDsCounter, 0 mSdLazyCounter, 1079 mSolverCounterSat, 136 mSolverCounterUnsat, 1 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 21.6s Time, 0 mProtectedPredicate, 0 mProtectedAction, 340 SdHoareTripleChecker+Valid, 641 SdHoareTripleChecker+Invalid, 1216 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 136 IncrementalHoareTripleChecker+Valid, 1079 IncrementalHoareTripleChecker+Invalid, 1 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 21.7s IncrementalHoareTripleChecker+Time [2023-04-02 22:58:25,029 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [340 Valid, 641 Invalid, 1216 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [136 Valid, 1079 Invalid, 1 Unknown, 0 Unchecked, 21.7s Time] [2023-04-02 22:58:25,031 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2619 states. [2023-04-02 22:58:25,606 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2619 to 1934. [2023-04-02 22:58:25,609 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 1934 states, 1435 states have (on average 1.2989547038327527) internal successors, (1864), 1471 states have internal predecessors, (1864), 395 states have call successors, (395), 104 states have call predecessors, (395), 103 states have return successors, (387), 358 states have call predecessors, (387), 387 states have call successors, (387) [2023-04-02 22:58:25,616 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 1934 states to 1934 states and 2646 transitions. [2023-04-02 22:58:25,616 INFO L78 Accepts]: Start accepts. Automaton has 1934 states and 2646 transitions. Word has length 65 [2023-04-02 22:58:25,616 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:58:25,616 INFO L495 AbstractCegarLoop]: Abstraction has 1934 states and 2646 transitions. [2023-04-02 22:58:25,616 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 21 states have (on average 3.4285714285714284) internal successors, (72), 18 states have internal predecessors, (72), 7 states have call successors, (15), 3 states have call predecessors, (15), 3 states have return successors, (13), 5 states have call predecessors, (13), 5 states have call successors, (13) [2023-04-02 22:58:25,616 INFO L276 IsEmpty]: Start isEmpty. Operand 1934 states and 2646 transitions. [2023-04-02 22:58:25,618 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 69 [2023-04-02 22:58:25,618 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:58:25,618 INFO L195 NwaCegarLoop]: trace histogram [7, 6, 6, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:58:25,623 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (19)] Forceful destruction successful, exit code 0 [2023-04-02 22:58:25,823 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 19 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable17 [2023-04-02 22:58:25,824 INFO L420 AbstractCegarLoop]: === Iteration 19 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:58:25,824 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:58:25,824 INFO L85 PathProgramCache]: Analyzing trace with hash 1809269162, now seen corresponding path program 2 times [2023-04-02 22:58:25,824 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:58:25,824 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [373174609] [2023-04-02 22:58:25,824 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:58:25,824 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:58:25,834 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:58:25,834 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [476458225] [2023-04-02 22:58:25,834 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2023-04-02 22:58:25,834 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:58:25,834 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:58:25,835 INFO L229 MonitoredProcess]: Starting monitored process 20 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:58:25,838 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Waiting until timeout for monitored process [2023-04-02 22:58:25,882 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2023-04-02 22:58:25,882 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:58:25,883 INFO L262 TraceCheckSpWp]: Trace formula consists of 182 conjuncts, 4 conjunts are in the unsatisfiable core [2023-04-02 22:58:25,884 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:58:25,908 INFO L134 CoverageAnalysis]: Checked inductivity of 91 backedges. 51 proven. 0 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2023-04-02 22:58:25,908 INFO L323 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2023-04-02 22:58:25,909 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:58:25,909 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [373174609] [2023-04-02 22:58:25,909 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:58:25,909 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [476458225] [2023-04-02 22:58:25,909 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [476458225] provided 1 perfect and 0 imperfect interpolant sequences [2023-04-02 22:58:25,909 INFO L185 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2023-04-02 22:58:25,909 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2023-04-02 22:58:25,909 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1940698806] [2023-04-02 22:58:25,909 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2023-04-02 22:58:25,910 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2023-04-02 22:58:25,910 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:58:25,910 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2023-04-02 22:58:25,910 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=8, Invalid=12, Unknown=0, NotChecked=0, Total=20 [2023-04-02 22:58:25,910 INFO L87 Difference]: Start difference. First operand 1934 states and 2646 transitions. Second operand has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-04-02 22:58:26,450 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:58:26,450 INFO L93 Difference]: Finished difference Result 3417 states and 4749 transitions. [2023-04-02 22:58:26,450 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2023-04-02 22:58:26,451 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) Word has length 68 [2023-04-02 22:58:26,451 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:58:26,460 INFO L225 Difference]: With dead ends: 3417 [2023-04-02 22:58:26,460 INFO L226 Difference]: Without dead ends: 2313 [2023-04-02 22:58:26,463 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 69 GetRequests, 65 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=12, Invalid=18, Unknown=0, NotChecked=0, Total=30 [2023-04-02 22:58:26,464 INFO L413 NwaCegarLoop]: 39 mSDtfsCounter, 12 mSDsluCounter, 59 mSDsCounter, 0 mSdLazyCounter, 53 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 98 SdHoareTripleChecker+Invalid, 54 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 53 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2023-04-02 22:58:26,464 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [12 Valid, 98 Invalid, 54 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 53 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2023-04-02 22:58:26,466 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 2313 states. [2023-04-02 22:58:27,128 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 2313 to 2152. [2023-04-02 22:58:27,132 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2152 states, 1559 states have (on average 1.2995509942270687) internal successors, (2026), 1595 states have internal predecessors, (2026), 489 states have call successors, (489), 104 states have call predecessors, (489), 103 states have return successors, (481), 452 states have call predecessors, (481), 481 states have call successors, (481) [2023-04-02 22:58:27,146 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2152 states to 2152 states and 2996 transitions. [2023-04-02 22:58:27,147 INFO L78 Accepts]: Start accepts. Automaton has 2152 states and 2996 transitions. Word has length 68 [2023-04-02 22:58:27,148 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:58:27,148 INFO L495 AbstractCegarLoop]: Abstraction has 2152 states and 2996 transitions. [2023-04-02 22:58:27,148 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 5.8) internal successors, (29), 5 states have internal predecessors, (29), 3 states have call successors, (11), 2 states have call predecessors, (11), 2 states have return successors, (9), 3 states have call predecessors, (9), 3 states have call successors, (9) [2023-04-02 22:58:27,149 INFO L276 IsEmpty]: Start isEmpty. Operand 2152 states and 2996 transitions. [2023-04-02 22:58:27,149 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 71 [2023-04-02 22:58:27,149 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:58:27,149 INFO L195 NwaCegarLoop]: trace histogram [6, 5, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:58:27,155 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (20)] Ended with exit code 0 [2023-04-02 22:58:27,354 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable18,20 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:58:27,355 INFO L420 AbstractCegarLoop]: === Iteration 20 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:58:27,355 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:58:27,355 INFO L85 PathProgramCache]: Analyzing trace with hash 891695958, now seen corresponding path program 3 times [2023-04-02 22:58:27,355 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:58:27,355 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1726367195] [2023-04-02 22:58:27,355 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:58:27,355 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:58:27,361 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:58:27,361 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [823041409] [2023-04-02 22:58:27,361 INFO L93 rtionOrderModulation]: Changing assertion order to TERMS_WITH_SMALL_CONSTANTS_FIRST [2023-04-02 22:58:27,361 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:58:27,362 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:58:27,363 INFO L229 MonitoredProcess]: Starting monitored process 21 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:58:27,365 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Waiting until timeout for monitored process [2023-04-02 22:58:27,414 INFO L228 tOrderPrioritization]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2023-04-02 22:58:27,414 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2023-04-02 22:58:27,415 INFO L262 TraceCheckSpWp]: Trace formula consists of 199 conjuncts, 63 conjunts are in the unsatisfiable core [2023-04-02 22:58:27,417 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:58:28,001 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 10 proven. 33 refuted. 0 times theorem prover too weak. 41 trivial. 0 not checked. [2023-04-02 22:58:28,001 INFO L327 TraceCheckSpWp]: Computing backward predicates... [2023-04-02 22:58:28,897 INFO L134 CoverageAnalysis]: Checked inductivity of 84 backedges. 16 proven. 26 refuted. 0 times theorem prover too weak. 42 trivial. 0 not checked. [2023-04-02 22:58:28,897 INFO L136 FreeRefinementEngine]: Strategy SIFA_TAIPAN found an infeasible trace [2023-04-02 22:58:28,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1726367195] [2023-04-02 22:58:28,897 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2023-04-02 22:58:28,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [823041409] [2023-04-02 22:58:28,897 INFO L158 FreeRefinementEngine]: IpTcStrategyModuleZ3 [823041409] provided 0 perfect and 2 imperfect interpolant sequences [2023-04-02 22:58:28,897 INFO L334 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSifa [160966295] [2023-04-02 22:58:28,899 INFO L159 IcfgInterpreter]: Started Sifa with 31 locations of interest [2023-04-02 22:58:28,899 INFO L166 IcfgInterpreter]: Building call graph [2023-04-02 22:58:28,899 INFO L171 IcfgInterpreter]: Initial procedures are [ULTIMATE.start] [2023-04-02 22:58:28,899 INFO L176 IcfgInterpreter]: Starting interpretation [2023-04-02 22:58:28,899 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.start with input of size 1 for LOIs [2023-04-02 22:58:28,914 INFO L197 IcfgInterpreter]: Interpreting procedure main with input of size 13 for LOIs [2023-04-02 22:58:36,693 INFO L197 IcfgInterpreter]: Interpreting procedure __VERIFIER_assert with input of size 1 for LOIs [2023-04-02 22:58:36,695 INFO L197 IcfgInterpreter]: Interpreting procedure assume_abort_if_not with input of size 11 for LOIs [2023-04-02 22:58:36,697 INFO L197 IcfgInterpreter]: Interpreting procedure ULTIMATE.init with input of size 10 for LOIs [2023-04-02 22:58:36,699 INFO L180 IcfgInterpreter]: Interpretation finished [2023-04-02 22:58:41,412 INFO L133 SifaRunner]: Sifa could not show that error location is unreachable, found '38337#(and (= |__VERIFIER_assert_#in~cond| 0) (= __VERIFIER_assert_~cond 0))' at error location [2023-04-02 22:58:41,412 WARN L311 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: ALGORITHM_FAILED [2023-04-02 22:58:41,412 INFO L185 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2023-04-02 22:58:41,412 INFO L198 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [15, 13] total 26 [2023-04-02 22:58:41,412 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1853283005] [2023-04-02 22:58:41,412 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2023-04-02 22:58:41,413 INFO L571 AbstractCegarLoop]: INTERPOLANT automaton has 26 states [2023-04-02 22:58:41,413 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy SIFA_TAIPAN [2023-04-02 22:58:41,414 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 26 interpolants. [2023-04-02 22:58:41,414 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=182, Invalid=2170, Unknown=0, NotChecked=0, Total=2352 [2023-04-02 22:58:41,415 INFO L87 Difference]: Start difference. First operand 2152 states and 2996 transitions. Second operand has 26 states, 25 states have (on average 2.88) internal successors, (72), 23 states have internal predecessors, (72), 6 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2023-04-02 22:59:02,976 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2023-04-02 22:59:02,977 INFO L93 Difference]: Finished difference Result 3014 states and 4161 transitions. [2023-04-02 22:59:02,977 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 45 states. [2023-04-02 22:59:02,977 INFO L78 Accepts]: Start accepts. Automaton has has 26 states, 25 states have (on average 2.88) internal successors, (72), 23 states have internal predecessors, (72), 6 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) Word has length 70 [2023-04-02 22:59:02,977 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2023-04-02 22:59:02,987 INFO L225 Difference]: With dead ends: 3014 [2023-04-02 22:59:02,988 INFO L226 Difference]: Without dead ends: 3008 [2023-04-02 22:59:02,991 INFO L412 NwaCegarLoop]: 0 DeclaredPredicates, 247 GetRequests, 162 SyntacticMatches, 0 SemanticMatches, 85 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 2134 ImplicationChecksByTransitivity, 18.5s TimeCoverageRelationStatistics Valid=968, Invalid=6514, Unknown=0, NotChecked=0, Total=7482 [2023-04-02 22:59:02,991 INFO L413 NwaCegarLoop]: 62 mSDtfsCounter, 434 mSDsluCounter, 628 mSDsCounter, 0 mSdLazyCounter, 937 mSolverCounterSat, 266 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 7.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 434 SdHoareTripleChecker+Valid, 690 SdHoareTripleChecker+Invalid, 1203 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 266 IncrementalHoareTripleChecker+Valid, 937 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 7.6s IncrementalHoareTripleChecker+Time [2023-04-02 22:59:02,991 INFO L414 NwaCegarLoop]: SdHoareTripleChecker [434 Valid, 690 Invalid, 1203 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [266 Valid, 937 Invalid, 0 Unknown, 0 Unchecked, 7.6s Time] [2023-04-02 22:59:02,994 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 3008 states. [2023-04-02 22:59:03,787 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 3008 to 2610. [2023-04-02 22:59:03,791 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 2610 states, 1946 states have (on average 1.289311408016444) internal successors, (2509), 1982 states have internal predecessors, (2509), 521 states have call successors, (521), 144 states have call predecessors, (521), 142 states have return successors, (514), 483 states have call predecessors, (514), 514 states have call successors, (514) [2023-04-02 22:59:03,799 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 2610 states to 2610 states and 3544 transitions. [2023-04-02 22:59:03,799 INFO L78 Accepts]: Start accepts. Automaton has 2610 states and 3544 transitions. Word has length 70 [2023-04-02 22:59:03,799 INFO L84 Accepts]: Finished accepts. word is rejected. [2023-04-02 22:59:03,799 INFO L495 AbstractCegarLoop]: Abstraction has 2610 states and 3544 transitions. [2023-04-02 22:59:03,800 INFO L496 AbstractCegarLoop]: INTERPOLANT automaton has has 26 states, 25 states have (on average 2.88) internal successors, (72), 23 states have internal predecessors, (72), 6 states have call successors, (17), 3 states have call predecessors, (17), 2 states have return successors, (15), 6 states have call predecessors, (15), 6 states have call successors, (15) [2023-04-02 22:59:03,800 INFO L276 IsEmpty]: Start isEmpty. Operand 2610 states and 3544 transitions. [2023-04-02 22:59:03,801 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 84 [2023-04-02 22:59:03,801 INFO L187 NwaCegarLoop]: Found error trace [2023-04-02 22:59:03,801 INFO L195 NwaCegarLoop]: trace histogram [9, 8, 8, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2023-04-02 22:59:03,807 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (21)] Forceful destruction successful, exit code 0 [2023-04-02 22:59:04,007 WARN L477 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable19,21 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:59:04,007 INFO L420 AbstractCegarLoop]: === Iteration 21 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2023-04-02 22:59:04,007 INFO L145 PredicateUnifier]: Initialized classic predicate unifier [2023-04-02 22:59:04,007 INFO L85 PathProgramCache]: Analyzing trace with hash 1520975003, now seen corresponding path program 1 times [2023-04-02 22:59:04,007 INFO L118 FreeRefinementEngine]: Executing refinement strategy SIFA_TAIPAN [2023-04-02 22:59:04,008 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [36418619] [2023-04-02 22:59:04,008 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:59:04,008 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2023-04-02 22:59:04,013 ERROR L246 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2023-04-02 22:59:04,014 INFO L334 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [744175537] [2023-04-02 22:59:04,014 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2023-04-02 22:59:04,014 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2023-04-02 22:59:04,014 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2023-04-02 22:59:04,015 INFO L229 MonitoredProcess]: Starting monitored process 22 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2023-04-02 22:59:04,019 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (22)] Waiting until timeout for monitored process [2023-04-02 22:59:04,081 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2023-04-02 22:59:04,082 INFO L262 TraceCheckSpWp]: Trace formula consists of 258 conjuncts, 81 conjunts are in the unsatisfiable core [2023-04-02 22:59:04,084 INFO L285 TraceCheckSpWp]: Computing forward predicates... [2023-04-02 22:59:05,071 INFO L134 CoverageAnalysis]: Checked inductivity of 156 backedges. 30 proven. 34 refuted. 0 times theorem prover too weak. 92 trivial. 0 not checked. [2023-04-02 22:59:05,071 INFO L327 TraceCheckSpWp]: Computing backward predicates...