/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound1.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-05ce600 [2022-02-23 21:51:23,426 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-02-23 21:51:23,428 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-02-23 21:51:23,469 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-02-23 21:51:23,470 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-02-23 21:51:23,470 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-02-23 21:51:23,471 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-02-23 21:51:23,472 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-02-23 21:51:23,473 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-02-23 21:51:23,479 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-02-23 21:51:23,480 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-02-23 21:51:23,481 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-02-23 21:51:23,481 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-02-23 21:51:23,482 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-02-23 21:51:23,482 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-02-23 21:51:23,483 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-02-23 21:51:23,483 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-02-23 21:51:23,484 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-02-23 21:51:23,485 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-02-23 21:51:23,486 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-02-23 21:51:23,487 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-02-23 21:51:23,492 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-02-23 21:51:23,493 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-02-23 21:51:23,493 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-02-23 21:51:23,495 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-02-23 21:51:23,495 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-02-23 21:51:23,495 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-02-23 21:51:23,496 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-02-23 21:51:23,496 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-02-23 21:51:23,496 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-02-23 21:51:23,497 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-02-23 21:51:23,497 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-02-23 21:51:23,498 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-02-23 21:51:23,498 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-02-23 21:51:23,499 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-02-23 21:51:23,499 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-02-23 21:51:23,499 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-02-23 21:51:23,499 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-02-23 21:51:23,500 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-02-23 21:51:23,500 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-02-23 21:51:23,501 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-02-23 21:51:23,506 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-02-23 21:51:23,536 INFO L113 SettingsManager]: Loading preferences was successful [2022-02-23 21:51:23,536 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-02-23 21:51:23,537 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-02-23 21:51:23,537 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-02-23 21:51:23,538 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-02-23 21:51:23,538 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-02-23 21:51:23,538 INFO L138 SettingsManager]: * Use SBE=true [2022-02-23 21:51:23,538 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-02-23 21:51:23,539 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Use constant arrays=true [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-02-23 21:51:23,540 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 21:51:23,540 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-02-23 21:51:23,540 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-02-23 21:51:23,541 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-02-23 21:51:23,541 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-02-23 21:51:23,541 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-02-23 21:51:23,541 INFO L138 SettingsManager]: * TransformationType=LOOP_ACCELERATION_QVASR 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.core: Log level for class -> de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN; [2022-02-23 21:51:23,734 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-02-23 21:51:23,759 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-02-23 21:51:23,761 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-02-23 21:51:23,762 INFO L271 PluginConnector]: Initializing CDTParser... [2022-02-23 21:51:23,763 INFO L275 PluginConnector]: CDTParser initialized [2022-02-23 21:51:23,764 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound1.c [2022-02-23 21:51:23,803 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/10f167a49/8d0b75b385a84d43847e4d647853ccd7/FLAG75be186b6 [2022-02-23 21:51:24,188 INFO L306 CDTParser]: Found 1 translation units. [2022-02-23 21:51:24,188 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound1.c [2022-02-23 21:51:24,195 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/10f167a49/8d0b75b385a84d43847e4d647853ccd7/FLAG75be186b6 [2022-02-23 21:51:24,208 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/10f167a49/8d0b75b385a84d43847e4d647853ccd7 [2022-02-23 21:51:24,209 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-02-23 21:51:24,211 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-02-23 21:51:24,212 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-02-23 21:51:24,212 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-02-23 21:51:24,214 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-02-23 21:51:24,215 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,215 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@7528bfda and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24, skipping insertion in model container [2022-02-23 21:51:24,215 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,219 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-02-23 21:51:24,230 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-02-23 21:51:24,352 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound1.c[597,610] [2022-02-23 21:51:24,374 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 21:51:24,379 INFO L203 MainTranslator]: Completed pre-run [2022-02-23 21:51:24,389 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound1.c[597,610] [2022-02-23 21:51:24,404 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-02-23 21:51:24,412 INFO L208 MainTranslator]: Completed translation [2022-02-23 21:51:24,412 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24 WrapperNode [2022-02-23 21:51:24,413 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-02-23 21:51:24,413 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-02-23 21:51:24,413 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-02-23 21:51:24,413 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-02-23 21:51:24,421 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,421 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,424 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,425 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,427 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,429 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,429 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,430 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-02-23 21:51:24,455 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-02-23 21:51:24,455 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-02-23 21:51:24,455 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-02-23 21:51:24,456 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,462 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-02-23 21:51:24,468 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:24,495 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) [2022-02-23 21:51:24,504 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 [2022-02-23 21:51:24,520 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-02-23 21:51:24,520 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-02-23 21:51:24,520 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-02-23 21:51:24,520 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-02-23 21:51:24,520 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-02-23 21:51:24,521 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-02-23 21:51:24,521 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-02-23 21:51:24,521 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-02-23 21:51:24,522 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-02-23 21:51:24,523 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-02-23 21:51:24,523 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-02-23 21:51:24,523 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-02-23 21:51:24,524 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-02-23 21:51:24,566 INFO L234 CfgBuilder]: Building ICFG [2022-02-23 21:51:24,567 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-02-23 21:51:24,689 INFO L275 CfgBuilder]: Performing block encoding [2022-02-23 21:51:24,693 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-02-23 21:51:24,693 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-02-23 21:51:24,694 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 09:51:24 BoogieIcfgContainer [2022-02-23 21:51:24,694 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-02-23 21:51:24,695 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-02-23 21:51:24,695 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-02-23 21:51:24,695 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-02-23 21:51:24,697 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 09:51:24" (1/1) ... [2022-02-23 21:51:24,708 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 09:51:24 BasicIcfg [2022-02-23 21:51:24,708 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-02-23 21:51:24,709 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-02-23 21:51:24,709 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-02-23 21:51:24,710 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-02-23 21:51:24,711 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 23.02 09:51:24" (1/4) ... [2022-02-23 21:51:24,716 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@493c0976 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 09:51:24, skipping insertion in model container [2022-02-23 21:51:24,731 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 23.02 09:51:24" (2/4) ... [2022-02-23 21:51:24,732 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@493c0976 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 23.02 09:51:24, skipping insertion in model container [2022-02-23 21:51:24,732 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 23.02 09:51:24" (3/4) ... [2022-02-23 21:51:24,732 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@493c0976 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 09:51:24, skipping insertion in model container [2022-02-23 21:51:24,732 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 23.02 09:51:24" (4/4) ... [2022-02-23 21:51:24,733 INFO L111 eAbstractionObserver]: Analyzing ICFG bresenham-ll_valuebound1.cqvasr [2022-02-23 21:51:24,736 INFO L205 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-02-23 21:51:24,736 INFO L164 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-02-23 21:51:24,774 INFO L338 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-02-23 21:51:24,778 INFO L339 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, mLoopAccelerationTechnique=FAST_UPR [2022-02-23 21:51:24,778 INFO L340 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-02-23 21:51:24,806 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-02-23 21:51:24,809 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-02-23 21:51:24,809 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:24,809 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 21:51:24,810 INFO L402 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:24,813 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:24,813 INFO L85 PathProgramCache]: Analyzing trace with hash -1563578423, now seen corresponding path program 1 times [2022-02-23 21:51:24,838 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:24,838 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [480233166] [2022-02-23 21:51:24,839 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:24,839 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:24,927 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:24,975 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-02-23 21:51:24,987 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:24,995 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-02-23 21:51:24,999 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:25,007 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-02-23 21:51:25,016 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:25,025 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 21:51:25,026 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:25,026 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [480233166] [2022-02-23 21:51:25,026 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [480233166] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 21:51:25,026 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 21:51:25,027 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-02-23 21:51:25,028 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1623660178] [2022-02-23 21:51:25,028 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 21:51:25,031 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-02-23 21:51:25,031 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:25,053 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-02-23 21:51:25,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 21:51:25,056 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-02-23 21:51:25,111 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:25,111 INFO L93 Difference]: Finished difference Result 57 states and 74 transitions. [2022-02-23 21:51:25,114 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-02-23 21:51:25,115 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 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 23 [2022-02-23 21:51:25,116 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:25,126 INFO L225 Difference]: With dead ends: 57 [2022-02-23 21:51:25,126 INFO L226 Difference]: Without dead ends: 27 [2022-02-23 21:51:25,128 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-02-23 21:51:25,131 INFO L933 BasicCegarLoop]: 31 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:25,132 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 34 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 21:51:25,143 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-02-23 21:51:25,167 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-02-23 21:51:25,168 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 6 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) [2022-02-23 21:51:25,169 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2022-02-23 21:51:25,170 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 23 [2022-02-23 21:51:25,170 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:25,170 INFO L470 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2022-02-23 21:51:25,170 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-02-23 21:51:25,171 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2022-02-23 21:51:25,172 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-02-23 21:51:25,172 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:25,172 INFO L514 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 21:51:25,172 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-02-23 21:51:25,172 INFO L402 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:25,174 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:25,174 INFO L85 PathProgramCache]: Analyzing trace with hash -1863481077, now seen corresponding path program 1 times [2022-02-23 21:51:25,175 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:25,175 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [575211359] [2022-02-23 21:51:25,175 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:25,175 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:25,205 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:25,205 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [2093962579] [2022-02-23 21:51:25,205 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:25,205 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:25,206 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:25,208 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) [2022-02-23 21:51:25,209 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Waiting until timeout for monitored process [2022-02-23 21:51:25,246 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:25,247 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 13 conjunts are in the unsatisfiable core [2022-02-23 21:51:25,251 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:25,355 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 21:51:25,355 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-02-23 21:51:25,356 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:25,356 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [575211359] [2022-02-23 21:51:25,356 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:25,356 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [2093962579] [2022-02-23 21:51:25,356 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [2093962579] provided 1 perfect and 0 imperfect interpolant sequences [2022-02-23 21:51:25,356 INFO L191 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-02-23 21:51:25,356 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-02-23 21:51:25,357 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1215932085] [2022-02-23 21:51:25,357 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-02-23 21:51:25,357 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-02-23 21:51:25,358 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:25,358 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-02-23 21:51:25,358 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-02-23 21:51:25,358 INFO L87 Difference]: Start difference. First operand 27 states and 30 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2022-02-23 21:51:25,409 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:25,410 INFO L93 Difference]: Finished difference Result 39 states and 44 transitions. [2022-02-23 21:51:25,410 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-02-23 21:51:25,410 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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 23 [2022-02-23 21:51:25,410 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:25,411 INFO L225 Difference]: With dead ends: 39 [2022-02-23 21:51:25,412 INFO L226 Difference]: Without dead ends: 35 [2022-02-23 21:51:25,412 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-02-23 21:51:25,413 INFO L933 BasicCegarLoop]: 22 mSDtfsCounter, 10 mSDsluCounter, 79 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 101 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:25,413 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 101 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-02-23 21:51:25,414 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-02-23 21:51:25,417 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-02-23 21:51:25,418 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-02-23 21:51:25,418 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2022-02-23 21:51:25,418 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 23 [2022-02-23 21:51:25,419 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:25,419 INFO L470 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2022-02-23 21:51:25,419 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 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) [2022-02-23 21:51:25,419 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2022-02-23 21:51:25,420 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-02-23 21:51:25,420 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:25,420 INFO L514 BasicCegarLoop]: 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, 1] [2022-02-23 21:51:25,439 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (2)] Forceful destruction successful, exit code 0 [2022-02-23 21:51:25,635 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:25,636 INFO L402 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:25,636 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:25,636 INFO L85 PathProgramCache]: Analyzing trace with hash -646008129, now seen corresponding path program 1 times [2022-02-23 21:51:25,636 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:25,637 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [779784632] [2022-02-23 21:51:25,637 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:25,637 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:25,662 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:25,663 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1631138610] [2022-02-23 21:51:25,663 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:25,663 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:25,663 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:25,680 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) [2022-02-23 21:51:25,687 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Waiting until timeout for monitored process [2022-02-23 21:51:25,728 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:25,729 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 24 conjunts are in the unsatisfiable core [2022-02-23 21:51:25,734 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:26,049 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 21:51:26,049 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:26,158 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:26,158 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [779784632] [2022-02-23 21:51:26,158 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:26,158 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1631138610] [2022-02-23 21:51:26,158 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1631138610] provided 0 perfect and 1 imperfect interpolant sequences [2022-02-23 21:51:26,159 INFO L191 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-02-23 21:51:26,159 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11] total 11 [2022-02-23 21:51:26,159 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1818420742] [2022-02-23 21:51:26,159 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:26,159 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-02-23 21:51:26,159 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:26,160 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-02-23 21:51:26,160 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=38, Invalid=144, Unknown=0, NotChecked=0, Total=182 [2022-02-23 21:51:26,160 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand has 11 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-02-23 21:51:26,255 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:26,255 INFO L93 Difference]: Finished difference Result 61 states and 70 transitions. [2022-02-23 21:51:26,255 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-02-23 21:51:26,255 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) Word has length 32 [2022-02-23 21:51:26,256 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:26,256 INFO L225 Difference]: With dead ends: 61 [2022-02-23 21:51:26,256 INFO L226 Difference]: Without dead ends: 35 [2022-02-23 21:51:26,257 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 43 GetRequests, 27 SyntacticMatches, 1 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 39 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=56, Invalid=216, Unknown=0, NotChecked=0, Total=272 [2022-02-23 21:51:26,257 INFO L933 BasicCegarLoop]: 24 mSDtfsCounter, 26 mSDsluCounter, 118 mSDsCounter, 0 mSdLazyCounter, 128 mSolverCounterSat, 13 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 142 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 13 IncrementalHoareTripleChecker+Valid, 128 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:26,258 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [28 Valid, 142 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [13 Valid, 128 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 21:51:26,258 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-02-23 21:51:26,261 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 35. [2022-02-23 21:51:26,262 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 35 states, 23 states have (on average 1.1304347826086956) internal successors, (26), 24 states have internal predecessors, (26), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-02-23 21:51:26,262 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 35 states to 35 states and 38 transitions. [2022-02-23 21:51:26,262 INFO L78 Accepts]: Start accepts. Automaton has 35 states and 38 transitions. Word has length 32 [2022-02-23 21:51:26,262 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:26,263 INFO L470 AbstractCegarLoop]: Abstraction has 35 states and 38 transitions. [2022-02-23 21:51:26,263 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 10 states have (on average 1.9) internal successors, (19), 9 states have internal predecessors, (19), 4 states have call successors, (6), 2 states have call predecessors, (6), 2 states have return successors, (4), 4 states have call predecessors, (4), 3 states have call successors, (4) [2022-02-23 21:51:26,263 INFO L276 IsEmpty]: Start isEmpty. Operand 35 states and 38 transitions. [2022-02-23 21:51:26,263 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-02-23 21:51:26,263 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:26,264 INFO L514 BasicCegarLoop]: 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, 1] [2022-02-23 21:51:26,280 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-02-23 21:51:26,480 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-02-23 21:51:26,480 INFO L402 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:26,480 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:26,481 INFO L85 PathProgramCache]: Analyzing trace with hash 241495552, now seen corresponding path program 1 times [2022-02-23 21:51:26,481 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:26,481 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1646671458] [2022-02-23 21:51:26,481 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:26,481 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:26,489 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:26,489 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1504607093] [2022-02-23 21:51:26,489 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:26,489 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:26,490 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:26,491 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) [2022-02-23 21:51:26,523 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Waiting until timeout for monitored process [2022-02-23 21:51:26,551 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:26,552 INFO L263 TraceCheckSpWp]: Trace formula consists of 105 conjuncts, 31 conjunts are in the unsatisfiable core [2022-02-23 21:51:26,553 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:26,815 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 21:51:26,815 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:26,978 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 3 proven. 1 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-02-23 21:51:26,978 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:26,978 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1646671458] [2022-02-23 21:51:26,978 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:26,978 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1504607093] [2022-02-23 21:51:26,979 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1504607093] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 21:51:26,979 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 21:51:26,979 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [12, 9] total 17 [2022-02-23 21:51:26,979 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1387431373] [2022-02-23 21:51:26,979 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:26,979 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 17 states [2022-02-23 21:51:26,980 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:26,980 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 17 interpolants. [2022-02-23 21:51:26,980 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=51, Invalid=221, Unknown=0, NotChecked=0, Total=272 [2022-02-23 21:51:26,980 INFO L87 Difference]: Start difference. First operand 35 states and 38 transitions. Second operand has 17 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-02-23 21:51:27,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:27,215 INFO L93 Difference]: Finished difference Result 59 states and 67 transitions. [2022-02-23 21:51:27,215 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 16 states. [2022-02-23 21:51:27,216 INFO L78 Accepts]: Start accepts. Automaton has has 17 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) Word has length 32 [2022-02-23 21:51:27,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:27,218 INFO L225 Difference]: With dead ends: 59 [2022-02-23 21:51:27,218 INFO L226 Difference]: Without dead ends: 44 [2022-02-23 21:51:27,218 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 70 GetRequests, 46 SyntacticMatches, 2 SemanticMatches, 22 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 79 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=106, Invalid=446, Unknown=0, NotChecked=0, Total=552 [2022-02-23 21:51:27,220 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 45 mSDsluCounter, 117 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 40 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 46 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 208 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 40 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:27,221 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [46 Valid, 134 Invalid, 208 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [40 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 21:51:27,222 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 44 states. [2022-02-23 21:51:27,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 44 to 42. [2022-02-23 21:51:27,232 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 42 states, 29 states have (on average 1.103448275862069) internal successors, (32), 29 states have internal predecessors, (32), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-02-23 21:51:27,236 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 42 states to 42 states and 46 transitions. [2022-02-23 21:51:27,239 INFO L78 Accepts]: Start accepts. Automaton has 42 states and 46 transitions. Word has length 32 [2022-02-23 21:51:27,239 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:27,239 INFO L470 AbstractCegarLoop]: Abstraction has 42 states and 46 transitions. [2022-02-23 21:51:27,239 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 17 states, 15 states have (on average 1.9333333333333333) internal successors, (29), 15 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 5 states have call predecessors, (7), 4 states have call successors, (7) [2022-02-23 21:51:27,240 INFO L276 IsEmpty]: Start isEmpty. Operand 42 states and 46 transitions. [2022-02-23 21:51:27,240 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-02-23 21:51:27,240 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:27,240 INFO L514 BasicCegarLoop]: 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] [2022-02-23 21:51:27,268 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-02-23 21:51:27,441 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:27,441 INFO L402 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:27,442 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:27,442 INFO L85 PathProgramCache]: Analyzing trace with hash -1661983408, now seen corresponding path program 1 times [2022-02-23 21:51:27,442 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:27,442 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [636208832] [2022-02-23 21:51:27,442 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:27,442 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:27,454 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:27,455 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1830626475] [2022-02-23 21:51:27,455 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:27,455 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:27,455 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:27,462 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) [2022-02-23 21:51:27,503 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Waiting until timeout for monitored process [2022-02-23 21:51:27,545 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:27,546 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 26 conjunts are in the unsatisfiable core [2022-02-23 21:51:27,547 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:27,789 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-02-23 21:51:27,789 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:28,137 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-02-23 21:51:28,137 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:28,137 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [636208832] [2022-02-23 21:51:28,137 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:28,137 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1830626475] [2022-02-23 21:51:28,137 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1830626475] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 21:51:28,137 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 21:51:28,137 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 22 [2022-02-23 21:51:28,137 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1455346970] [2022-02-23 21:51:28,138 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:28,138 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-02-23 21:51:28,138 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:28,138 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-02-23 21:51:28,138 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2022-02-23 21:51:28,139 INFO L87 Difference]: Start difference. First operand 42 states and 46 transitions. Second operand has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-02-23 21:51:28,585 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:28,585 INFO L93 Difference]: Finished difference Result 55 states and 60 transitions. [2022-02-23 21:51:28,585 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 24 states. [2022-02-23 21:51:28,585 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 39 [2022-02-23 21:51:28,585 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:28,586 INFO L225 Difference]: With dead ends: 55 [2022-02-23 21:51:28,586 INFO L226 Difference]: Without dead ends: 47 [2022-02-23 21:51:28,586 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 91 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 33 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 232 ImplicationChecksByTransitivity, 0.6s TimeCoverageRelationStatistics Valid=197, Invalid=993, Unknown=0, NotChecked=0, Total=1190 [2022-02-23 21:51:28,587 INFO L933 BasicCegarLoop]: 20 mSDtfsCounter, 36 mSDsluCounter, 197 mSDsCounter, 0 mSdLazyCounter, 142 mSolverCounterSat, 24 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 37 SdHoareTripleChecker+Valid, 217 SdHoareTripleChecker+Invalid, 232 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 24 IncrementalHoareTripleChecker+Valid, 142 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 66 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:28,587 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [37 Valid, 217 Invalid, 232 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [24 Valid, 142 Invalid, 0 Unknown, 66 Unchecked, 0.1s Time] [2022-02-23 21:51:28,587 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 47 states. [2022-02-23 21:51:28,591 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 47 to 46. [2022-02-23 21:51:28,591 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 46 states, 32 states have (on average 1.0625) internal successors, (34), 32 states have internal predecessors, (34), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 7 states have call predecessors, (7), 7 states have call successors, (7) [2022-02-23 21:51:28,592 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 46 states to 46 states and 50 transitions. [2022-02-23 21:51:28,592 INFO L78 Accepts]: Start accepts. Automaton has 46 states and 50 transitions. Word has length 39 [2022-02-23 21:51:28,592 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:28,592 INFO L470 AbstractCegarLoop]: Abstraction has 46 states and 50 transitions. [2022-02-23 21:51:28,592 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-02-23 21:51:28,592 INFO L276 IsEmpty]: Start isEmpty. Operand 46 states and 50 transitions. [2022-02-23 21:51:28,593 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2022-02-23 21:51:28,593 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:28,593 INFO L514 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 21:51:28,621 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Forceful destruction successful, exit code 0 [2022-02-23 21:51:28,803 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:28,803 INFO L402 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:28,804 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:28,804 INFO L85 PathProgramCache]: Analyzing trace with hash 1739644753, now seen corresponding path program 1 times [2022-02-23 21:51:28,804 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:28,804 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [823436950] [2022-02-23 21:51:28,804 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:28,804 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:28,813 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:28,813 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1617645847] [2022-02-23 21:51:28,813 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:28,813 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:28,813 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:28,816 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) [2022-02-23 21:51:28,817 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Waiting until timeout for monitored process [2022-02-23 21:51:28,849 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-02-23 21:51:28,850 INFO L263 TraceCheckSpWp]: Trace formula consists of 159 conjuncts, 12 conjunts are in the unsatisfiable core [2022-02-23 21:51:28,852 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:29,031 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-02-23 21:51:29,032 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:29,267 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-02-23 21:51:29,268 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:29,268 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [823436950] [2022-02-23 21:51:29,268 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:29,268 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1617645847] [2022-02-23 21:51:29,268 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1617645847] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 21:51:29,268 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 21:51:29,268 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 16 [2022-02-23 21:51:29,268 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [745486712] [2022-02-23 21:51:29,268 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:29,269 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-02-23 21:51:29,269 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:29,269 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-02-23 21:51:29,269 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=56, Invalid=184, Unknown=0, NotChecked=0, Total=240 [2022-02-23 21:51:29,269 INFO L87 Difference]: Start difference. First operand 46 states and 50 transitions. Second operand has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-02-23 21:51:29,634 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:29,634 INFO L93 Difference]: Finished difference Result 76 states and 89 transitions. [2022-02-23 21:51:29,634 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 17 states. [2022-02-23 21:51:29,634 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) Word has length 57 [2022-02-23 21:51:29,635 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:29,635 INFO L225 Difference]: With dead ends: 76 [2022-02-23 21:51:29,635 INFO L226 Difference]: Without dead ends: 70 [2022-02-23 21:51:29,636 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 123 GetRequests, 99 SyntacticMatches, 0 SemanticMatches, 24 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 93 ImplicationChecksByTransitivity, 0.3s TimeCoverageRelationStatistics Valid=149, Invalid=501, Unknown=0, NotChecked=0, Total=650 [2022-02-23 21:51:29,636 INFO L933 BasicCegarLoop]: 35 mSDtfsCounter, 14 mSDsluCounter, 164 mSDsCounter, 0 mSdLazyCounter, 170 mSolverCounterSat, 33 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 199 SdHoareTripleChecker+Invalid, 203 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 33 IncrementalHoareTripleChecker+Valid, 170 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:29,636 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 199 Invalid, 203 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [33 Valid, 170 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 21:51:29,637 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 70 states. [2022-02-23 21:51:29,643 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 70 to 56. [2022-02-23 21:51:29,644 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 40 states have (on average 1.1) internal successors, (44), 40 states have internal predecessors, (44), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-02-23 21:51:29,644 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 64 transitions. [2022-02-23 21:51:29,644 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 64 transitions. Word has length 57 [2022-02-23 21:51:29,644 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:29,644 INFO L470 AbstractCegarLoop]: Abstraction has 56 states and 64 transitions. [2022-02-23 21:51:29,644 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.75) internal successors, (44), 16 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-02-23 21:51:29,645 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 64 transitions. [2022-02-23 21:51:29,646 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-02-23 21:51:29,646 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:29,646 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 5, 5, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 21:51:29,664 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Ended with exit code 0 [2022-02-23 21:51:29,862 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:29,862 INFO L402 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:29,863 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:29,863 INFO L85 PathProgramCache]: Analyzing trace with hash 1357898193, now seen corresponding path program 2 times [2022-02-23 21:51:29,863 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:29,863 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1040180152] [2022-02-23 21:51:29,863 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:29,863 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:29,870 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:29,870 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1387231716] [2022-02-23 21:51:29,870 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-02-23 21:51:29,870 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:29,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:29,876 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) [2022-02-23 21:51:29,885 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Waiting until timeout for monitored process [2022-02-23 21:51:29,927 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-02-23 21:51:29,928 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 21:51:29,928 INFO L263 TraceCheckSpWp]: Trace formula consists of 197 conjuncts, 6 conjunts are in the unsatisfiable core [2022-02-23 21:51:29,930 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:30,041 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 74 proven. 27 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-02-23 21:51:30,041 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:30,186 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 50 proven. 23 refuted. 0 times theorem prover too weak. 68 trivial. 0 not checked. [2022-02-23 21:51:30,186 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:30,186 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1040180152] [2022-02-23 21:51:30,186 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:30,186 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1387231716] [2022-02-23 21:51:30,186 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1387231716] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 21:51:30,186 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 21:51:30,186 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 7 [2022-02-23 21:51:30,187 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [572171199] [2022-02-23 21:51:30,187 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:30,187 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 7 states [2022-02-23 21:51:30,187 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:30,187 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 7 interpolants. [2022-02-23 21:51:30,187 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-02-23 21:51:30,188 INFO L87 Difference]: Start difference. First operand 56 states and 64 transitions. Second operand has 7 states, 7 states have (on average 5.857142857142857) internal successors, (41), 7 states have internal predecessors, (41), 7 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 7 states have call predecessors, (10), 7 states have call successors, (10) [2022-02-23 21:51:30,264 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:30,265 INFO L93 Difference]: Finished difference Result 85 states and 99 transitions. [2022-02-23 21:51:30,265 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-02-23 21:51:30,265 INFO L78 Accepts]: Start accepts. Automaton has has 7 states, 7 states have (on average 5.857142857142857) internal successors, (41), 7 states have internal predecessors, (41), 7 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 7 states have call predecessors, (10), 7 states have call successors, (10) Word has length 75 [2022-02-23 21:51:30,265 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:30,266 INFO L225 Difference]: With dead ends: 85 [2022-02-23 21:51:30,266 INFO L226 Difference]: Without dead ends: 66 [2022-02-23 21:51:30,266 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 142 SyntacticMatches, 2 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=25, Invalid=47, Unknown=0, NotChecked=0, Total=72 [2022-02-23 21:51:30,266 INFO L933 BasicCegarLoop]: 29 mSDtfsCounter, 7 mSDsluCounter, 109 mSDsCounter, 0 mSdLazyCounter, 51 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 7 SdHoareTripleChecker+Valid, 138 SdHoareTripleChecker+Invalid, 56 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 51 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:30,267 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [7 Valid, 138 Invalid, 56 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 51 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-02-23 21:51:30,267 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 66 states. [2022-02-23 21:51:30,275 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 66 to 61. [2022-02-23 21:51:30,275 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 61 states, 44 states have (on average 1.0909090909090908) internal successors, (48), 44 states have internal predecessors, (48), 12 states have call successors, (12), 6 states have call predecessors, (12), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-02-23 21:51:30,275 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 61 states to 61 states and 70 transitions. [2022-02-23 21:51:30,275 INFO L78 Accepts]: Start accepts. Automaton has 61 states and 70 transitions. Word has length 75 [2022-02-23 21:51:30,275 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:30,275 INFO L470 AbstractCegarLoop]: Abstraction has 61 states and 70 transitions. [2022-02-23 21:51:30,276 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 7 states, 7 states have (on average 5.857142857142857) internal successors, (41), 7 states have internal predecessors, (41), 7 states have call successors, (12), 2 states have call predecessors, (12), 2 states have return successors, (10), 7 states have call predecessors, (10), 7 states have call successors, (10) [2022-02-23 21:51:30,276 INFO L276 IsEmpty]: Start isEmpty. Operand 61 states and 70 transitions. [2022-02-23 21:51:30,276 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-02-23 21:51:30,276 INFO L506 BasicCegarLoop]: Found error trace [2022-02-23 21:51:30,277 INFO L514 BasicCegarLoop]: trace histogram [7, 6, 6, 6, 6, 6, 5, 5, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-02-23 21:51:30,307 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Ended with exit code 0 [2022-02-23 21:51:30,492 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:30,493 INFO L402 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-02-23 21:51:30,493 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-02-23 21:51:30,493 INFO L85 PathProgramCache]: Analyzing trace with hash -1692304622, now seen corresponding path program 3 times [2022-02-23 21:51:30,493 INFO L126 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-02-23 21:51:30,493 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [621691643] [2022-02-23 21:51:30,493 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-02-23 21:51:30,493 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-02-23 21:51:30,515 ERROR L252 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-02-23 21:51:30,515 INFO L338 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1239301] [2022-02-23 21:51:30,515 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-02-23 21:51:30,515 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:30,516 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-02-23 21:51:30,517 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) [2022-02-23 21:51:30,518 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Waiting until timeout for monitored process [2022-02-23 21:51:30,552 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-02-23 21:51:30,552 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-02-23 21:51:30,553 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 31 conjunts are in the unsatisfiable core [2022-02-23 21:51:30,554 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-02-23 21:51:31,002 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 21:51:31,006 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 21:51:31,007 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 21:51:35,709 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 49 proven. 1 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2022-02-23 21:51:35,709 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-02-23 21:51:35,958 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 21:51:36,747 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-02-23 21:51:46,983 INFO L134 CoverageAnalysis]: Checked inductivity of 141 backedges. 49 proven. 1 refuted. 0 times theorem prover too weak. 91 trivial. 0 not checked. [2022-02-23 21:51:46,984 INFO L144 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-02-23 21:51:46,984 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [621691643] [2022-02-23 21:51:46,984 WARN L317 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-02-23 21:51:46,984 INFO L338 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1239301] [2022-02-23 21:51:46,984 INFO L165 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1239301] provided 0 perfect and 2 imperfect interpolant sequences [2022-02-23 21:51:46,984 INFO L191 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-02-23 21:51:46,984 INFO L204 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 25 [2022-02-23 21:51:46,984 INFO L118 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [352045281] [2022-02-23 21:51:46,984 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-02-23 21:51:46,984 INFO L546 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-02-23 21:51:46,985 INFO L108 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-02-23 21:51:46,985 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-02-23 21:51:46,985 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=501, Unknown=1, NotChecked=0, Total=600 [2022-02-23 21:51:46,985 INFO L87 Difference]: Start difference. First operand 61 states and 70 transitions. Second operand has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2022-02-23 21:51:58,055 WARN L232 SmtUtils]: Spent 8.19s on a formula simplification. DAG size of input: 63 DAG size of output: 55 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-02-23 21:51:58,139 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-02-23 21:51:58,139 INFO L93 Difference]: Finished difference Result 61 states and 70 transitions. [2022-02-23 21:51:58,139 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-02-23 21:51:58,139 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 75 [2022-02-23 21:51:58,140 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-02-23 21:51:58,140 INFO L225 Difference]: With dead ends: 61 [2022-02-23 21:51:58,140 INFO L226 Difference]: Without dead ends: 0 [2022-02-23 21:51:58,141 INFO L932 BasicCegarLoop]: 0 DeclaredPredicates, 162 GetRequests, 126 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 281 ImplicationChecksByTransitivity, 16.8s TimeCoverageRelationStatistics Valid=237, Invalid=1094, Unknown=1, NotChecked=0, Total=1332 [2022-02-23 21:51:58,141 INFO L933 BasicCegarLoop]: 17 mSDtfsCounter, 22 mSDsluCounter, 226 mSDsCounter, 0 mSdLazyCounter, 283 mSolverCounterSat, 14 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 243 SdHoareTripleChecker+Invalid, 370 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 14 IncrementalHoareTripleChecker+Valid, 283 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 73 IncrementalHoareTripleChecker+Unchecked, 0.5s IncrementalHoareTripleChecker+Time [2022-02-23 21:51:58,141 INFO L934 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 243 Invalid, 370 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [14 Valid, 283 Invalid, 0 Unknown, 73 Unchecked, 0.5s Time] [2022-02-23 21:51:58,142 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-02-23 21:51:58,142 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-02-23 21:51:58,142 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 0 states, 0 states have (on average 0.0) internal successors, (0), 0 states have internal predecessors, (0), 0 states have call successors, (0), 0 states have call predecessors, (0), 0 states have return successors, (0), 0 states have call predecessors, (0), 0 states have call successors, (0) [2022-02-23 21:51:58,142 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-02-23 21:51:58,142 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 75 [2022-02-23 21:51:58,142 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-02-23 21:51:58,142 INFO L470 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-02-23 21:51:58,142 INFO L471 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2022-02-23 21:51:58,142 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-02-23 21:51:58,142 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-02-23 21:51:58,144 INFO L764 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-02-23 21:51:58,163 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (8)] Forceful destruction successful, exit code 0 [2022-02-23 21:51:58,355 WARN L452 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-02-23 21:51:58,357 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-02-23 21:52:03,309 INFO L854 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-02-23 21:52:03,309 INFO L861 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-02-23 21:52:03,309 INFO L861 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-02-23 21:52:03,309 INFO L861 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 10 12) the Hoare annotation is: true [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point L11(line 11) no Hoare annotation was computed. [2022-02-23 21:52:03,309 INFO L858 garLoopResultBuilder]: For program point L11-2(lines 10 12) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 10 12) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L861 garLoopResultBuilder]: At program point mainENTRY(lines 21 53) the Hoare annotation is: true [2022-02-23 21:52:03,310 INFO L861 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: true [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L25-1(line 25) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L854 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: (and (<= 0 main_~X~0) (<= main_~X~0 1)) [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L27-1(line 27) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L854 garLoopResultBuilder]: At program point L32-2(lines 32 47) the Hoare annotation is: (let ((.cse1 (* main_~Y~0 2)) (.cse3 (+ main_~X~0 main_~v~0)) (.cse5 (<= main_~X~0 1))) (or (let ((.cse4 (* main_~Y~0 main_~x~0))) (let ((.cse2 (* 2 .cse4))) (and (or (<= main_~x~0 main_~X~0) (and (let ((.cse0 (div (+ (div .cse3 (- 2)) main_~Y~0 .cse4) main_~X~0))) (= (+ main_~X~0 main_~v~0 (* (* .cse0 main_~x~0) 2)) (+ .cse1 (* .cse0 2) .cse2))) (or (forall ((main_~y~0 Int)) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ (* main_~y~0 2) (* main_~Y~0 2) (* 2 (* main_~Y~0 main_~x~0))))) (not (= main_~X~0 0))))) (<= main_~X~0 .cse1) (= (+ .cse1 .cse2) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (<= main_~Y~0 1) (<= 0 main_~X~0) .cse5 (<= (div main_~v~0 (- 2)) main_~Y~0)))) (and (< main_~v~0 .cse1) (<= 0 main_~Y~0) (= .cse3 (* main_~Y~0 4)) .cse5 (= main_~y~0 0)))) [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L32-3(lines 32 47) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L854 garLoopResultBuilder]: At program point L35(line 35) the Hoare annotation is: (let ((.cse1 (* main_~Y~0 2)) (.cse5 (<= main_~X~0 1))) (or (let ((.cse0 (* 2 main_~xy~0)) (.cse4 (* 2 (* main_~Y~0 main_~x~0))) (.cse2 (* 2 main_~yx~0)) (.cse3 (<= main_~x~0 main_~X~0))) (and (= (+ .cse0 main_~X~0 main_~v~0) (+ .cse1 .cse2)) (or .cse3 (forall ((main_~y~0 Int)) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ (* main_~y~0 2) (* main_~Y~0 2) (* 2 (* main_~Y~0 main_~x~0))))) (not (= main_~X~0 0))) (<= main_~X~0 .cse1) (= (+ .cse1 .cse4) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (<= main_~Y~0 1) (<= 0 main_~X~0) .cse5 (<= (div main_~v~0 (- 2)) main_~Y~0) (or (= (+ .cse0 (* main_~y~0 2) .cse4) (+ (* 2 (* main_~y~0 main_~x~0)) .cse2)) .cse3))) (and (= main_~xy~0 0) (< main_~v~0 .cse1) (<= 0 main_~Y~0) (= (+ main_~X~0 main_~v~0) (* main_~Y~0 4)) .cse5 (= main_~y~0 0) (= main_~yx~0 0)))) [2022-02-23 21:52:03,310 INFO L854 garLoopResultBuilder]: At program point L50(line 50) the Hoare annotation is: (let ((.cse0 (* main_~Y~0 2))) (or (and (= main_~x~0 0) (= main_~xy~0 0) (= (+ main_~X~0 main_~v~0) .cse0) (= main_~y~0 0) (= main_~yx~0 0)) (let ((.cse2 (* main_~y~0 2)) (.cse1 (* 2 (* main_~Y~0 main_~x~0)))) (and (= (+ .cse0 .cse1) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (<= main_~Y~0 1) (<= 0 main_~Y~0) (= (+ .cse2 .cse0 (* 2 main_~yx~0)) (+ (* 2 main_~xy~0) main_~X~0 main_~v~0)) (<= 0 main_~X~0) (<= main_~X~0 1) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ .cse2 .cse0 .cse1)))))) [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L35-1(lines 32 47) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L50-1(line 50) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L40(lines 40 45) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point mainFINAL(lines 21 53) no Hoare annotation was computed. [2022-02-23 21:52:03,310 INFO L858 garLoopResultBuilder]: For program point L40-2(lines 40 45) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point mainEXIT(lines 21 53) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L861 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 13 19) the Hoare annotation is: true [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point L14(lines 14 17) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point L15(lines 15 16) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point L14-2(lines 13 19) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 16) no Hoare annotation was computed. [2022-02-23 21:52:03,311 INFO L858 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 13 19) no Hoare annotation was computed. [2022-02-23 21:52:03,313 INFO L732 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1] [2022-02-23 21:52:03,314 INFO L180 ceAbstractionStarter]: Computing trace abstraction results [2022-02-23 21:52:03,318 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,319 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,330 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,330 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,338 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 23.02 09:52:03 BasicIcfg [2022-02-23 21:52:03,339 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-02-23 21:52:03,339 INFO L158 Benchmark]: Toolchain (without parser) took 39127.79ms. Allocated memory was 230.7MB in the beginning and 352.3MB in the end (delta: 121.6MB). Free memory was 204.9MB in the beginning and 247.6MB in the end (delta: -42.7MB). Peak memory consumption was 79.0MB. Max. memory is 8.0GB. [2022-02-23 21:52:03,339 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 230.7MB. Free memory is still 191.8MB. There was no memory consumed. Max. memory is 8.0GB. [2022-02-23 21:52:03,339 INFO L158 Benchmark]: CACSL2BoogieTranslator took 200.47ms. Allocated memory is still 230.7MB. Free memory was 204.7MB in the beginning and 204.7MB in the end (delta: -56.8kB). Peak memory consumption was 9.2MB. Max. memory is 8.0GB. [2022-02-23 21:52:03,339 INFO L158 Benchmark]: Boogie Preprocessor took 17.36ms. Allocated memory is still 230.7MB. Free memory was 204.7MB in the beginning and 203.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-02-23 21:52:03,340 INFO L158 Benchmark]: RCFGBuilder took 239.17ms. Allocated memory is still 230.7MB. Free memory was 203.3MB in the beginning and 192.5MB in the end (delta: 10.9MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-02-23 21:52:03,340 INFO L158 Benchmark]: IcfgTransformer took 13.25ms. Allocated memory is still 230.7MB. Free memory was 192.5MB in the beginning and 191.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 8.0GB. [2022-02-23 21:52:03,340 INFO L158 Benchmark]: TraceAbstraction took 38629.76ms. Allocated memory was 230.7MB in the beginning and 352.3MB in the end (delta: 121.6MB). Free memory was 190.8MB in the beginning and 247.6MB in the end (delta: -56.9MB). Peak memory consumption was 65.6MB. Max. memory is 8.0GB. [2022-02-23 21:52:03,341 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 230.7MB. Free memory is still 191.8MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 200.47ms. Allocated memory is still 230.7MB. Free memory was 204.7MB in the beginning and 204.7MB in the end (delta: -56.8kB). Peak memory consumption was 9.2MB. Max. memory is 8.0GB. * Boogie Preprocessor took 17.36ms. Allocated memory is still 230.7MB. Free memory was 204.7MB in the beginning and 203.3MB in the end (delta: 1.4MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 239.17ms. Allocated memory is still 230.7MB. Free memory was 203.3MB in the beginning and 192.5MB in the end (delta: 10.9MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 13.25ms. Allocated memory is still 230.7MB. Free memory was 192.5MB in the beginning and 191.4MB in the end (delta: 1.1MB). There was no memory consumed. Max. memory is 8.0GB. * TraceAbstraction took 38629.76ms. Allocated memory was 230.7MB in the beginning and 352.3MB in the end (delta: 121.6MB). Free memory was 190.8MB in the beginning and 247.6MB in the end (delta: -56.9MB). Peak memory consumption was 65.6MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 16]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 38.5s, OverallIterations: 8, TraceHistogramMax: 7, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 12.6s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 5.0s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 190 SdHoareTripleChecker+Valid, 1.1s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 180 mSDsluCounter, 1208 SdHoareTripleChecker+Invalid, 0.9s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 139 IncrementalHoareTripleChecker+Unchecked, 1013 mSDsCounter, 139 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 999 IncrementalHoareTripleChecker+Invalid, 1277 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 139 mSolverCounterUnsat, 195 mSDtfsCounter, 999 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 674 GetRequests, 524 SyntacticMatches, 7 SemanticMatches, 143 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 725 ImplicationChecksByTransitivity, 18.2s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=61occurred in iteration=7, InterpolantAutomatonStates: 105, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 23 StatesRemovedByMinimization, 5 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 11 LocationsWithAnnotation, 35 PreInvPairs, 58 NumberOfFragments, 383 HoareAnnotationTreeSize, 35 FomulaSimplifications, 687 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 11 FomulaSimplificationsInter, 2815 FormulaSimplificationTreeSizeReductionInter, 4.9s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.0s SsaConstructionTime, 0.2s SatisfiabilityAnalysisTime, 18.8s InterpolantComputationTime, 356 NumberOfCodeBlocks, 320 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 621 ConstructedInterpolants, 6 QuantifiedInterpolants, 3639 SizeOfPredicates, 39 NumberOfNonLiveVariables, 884 ConjunctsInSsa, 143 ConjunctsInUnsatCore, 13 InterpolantComputations, 2 PerfectInterpolantSequences, 637/746 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 32]: Loop Invariant [2022-02-23 21:52:03,351 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,351 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,351 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-02-23 21:52:03,351 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] Derived loop invariant: (((((((x <= X || (X + v + ((X + v) / -2 + Y + Y * x) / X * x * 2 == Y * 2 + ((X + v) / -2 + Y + Y * x) / X * 2 + 2 * (Y * x) && ((forall main_~y~0 : int :: 2 * (main_~y~0 * x) + X + v == main_~y~0 * 2 + Y * 2 + 2 * (Y * x)) || !(X == 0)))) && X <= Y * 2) && Y * 2 + 2 * (Y * x) == X * y * 2 + X + v) && Y <= 1) && 0 <= X) && X <= 1) && v / -2 <= Y) || ((((v < Y * 2 && 0 <= Y) && X + v == Y * 4) && X <= 1) && y == 0) RESULT: Ultimate proved your program to be correct! [2022-02-23 21:52:03,414 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (1)] Forceful destruction successful, exit code 0 Received shutdown request...