/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/hard2_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-7390193 [2022-04-05 08:26:36,335 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-05 08:26:36,336 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-05 08:26:36,361 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-05 08:26:36,361 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-05 08:26:36,362 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-05 08:26:36,364 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-05 08:26:36,368 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-05 08:26:36,370 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-05 08:26:36,374 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-05 08:26:36,374 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-05 08:26:36,375 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-05 08:26:36,375 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-05 08:26:36,376 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-05 08:26:36,376 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-05 08:26:36,377 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-05 08:26:36,377 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-05 08:26:36,378 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-05 08:26:36,378 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-05 08:26:36,379 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-05 08:26:36,380 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-05 08:26:36,383 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-05 08:26:36,384 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-05 08:26:36,386 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-05 08:26:36,387 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-05 08:26:36,391 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-05 08:26:36,392 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-05 08:26:36,392 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-05 08:26:36,392 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-05 08:26:36,393 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-05 08:26:36,394 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-05 08:26:36,394 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-05 08:26:36,395 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-05 08:26:36,396 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-05 08:26:36,396 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-05 08:26:36,396 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-05 08:26:36,397 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-05 08:26:36,397 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-05 08:26:36,397 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-05 08:26:36,397 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-05 08:26:36,398 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-05 08:26:36,400 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-05 08:26:36,400 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-05 08:26:36,420 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-05 08:26:36,420 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-05 08:26:36,420 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-05 08:26:36,420 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-05 08:26:36,421 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-05 08:26:36,421 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-05 08:26:36,421 INFO L138 SettingsManager]: * Use SBE=true [2022-04-05 08:26:36,421 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-05 08:26:36,421 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-05 08:26:36,422 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-05 08:26:36,423 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 08:26:36,423 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-05 08:26:36,423 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-05 08:26:36,424 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-05 08:26:36,424 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-05 08:26:36,424 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-05 08:26:36,424 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-04-05 08:26:36,591 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-05 08:26:36,614 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-05 08:26:36,616 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-05 08:26:36,617 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-05 08:26:36,618 INFO L275 PluginConnector]: CDTParser initialized [2022-04-05 08:26:36,619 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/hard2_valuebound50.c [2022-04-05 08:26:36,679 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a6509c94/754a15ced90244f4a29b91165c17d46f/FLAG39f30a97c [2022-04-05 08:26:37,015 INFO L306 CDTParser]: Found 1 translation units. [2022-04-05 08:26:37,016 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/hard2_valuebound50.c [2022-04-05 08:26:37,019 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a6509c94/754a15ced90244f4a29b91165c17d46f/FLAG39f30a97c [2022-04-05 08:26:37,027 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/6a6509c94/754a15ced90244f4a29b91165c17d46f [2022-04-05 08:26:37,028 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-05 08:26:37,029 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-05 08:26:37,030 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-05 08:26:37,030 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-05 08:26:37,032 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-05 08:26:37,032 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,033 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@4514de90 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37, skipping insertion in model container [2022-04-05 08:26:37,033 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,037 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-05 08:26:37,047 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-05 08:26:37,163 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/hard2_valuebound50.c[526,539] [2022-04-05 08:26:37,172 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 08:26:37,176 INFO L203 MainTranslator]: Completed pre-run [2022-04-05 08:26:37,185 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/hard2_valuebound50.c[526,539] [2022-04-05 08:26:37,188 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-05 08:26:37,195 INFO L208 MainTranslator]: Completed translation [2022-04-05 08:26:37,196 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37 WrapperNode [2022-04-05 08:26:37,196 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-05 08:26:37,196 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-05 08:26:37,197 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-05 08:26:37,197 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-05 08:26:37,203 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,203 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,206 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,206 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,209 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,211 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,212 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,213 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-05 08:26:37,213 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-05 08:26:37,213 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-05 08:26:37,213 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-05 08:26:37,214 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,218 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-05 08:26:37,224 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:37,232 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-04-05 08:26:37,248 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-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-05 08:26:37,273 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-05 08:26:37,273 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-05 08:26:37,273 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-05 08:26:37,273 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-05 08:26:37,273 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-05 08:26:37,274 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-05 08:26:37,319 INFO L234 CfgBuilder]: Building ICFG [2022-04-05 08:26:37,320 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-05 08:26:37,430 INFO L275 CfgBuilder]: Performing block encoding [2022-04-05 08:26:37,434 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-05 08:26:37,435 INFO L299 CfgBuilder]: Removed 2 assume(true) statements. [2022-04-05 08:26:37,436 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:26:37 BoogieIcfgContainer [2022-04-05 08:26:37,436 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-05 08:26:37,437 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-05 08:26:37,437 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-05 08:26:37,452 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-05 08:26:37,454 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:26:37" (1/1) ... [2022-04-05 08:26:37,456 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-05 08:26:37,477 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 08:26:37 BasicIcfg [2022-04-05 08:26:37,477 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-05 08:26:37,478 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-05 08:26:37,478 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-05 08:26:37,493 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-05 08:26:37,494 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 05.04 08:26:37" (1/4) ... [2022-04-05 08:26:37,494 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@325093a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 08:26:37, skipping insertion in model container [2022-04-05 08:26:37,494 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 05.04 08:26:37" (2/4) ... [2022-04-05 08:26:37,495 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@325093a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 05.04 08:26:37, skipping insertion in model container [2022-04-05 08:26:37,495 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 05.04 08:26:37" (3/4) ... [2022-04-05 08:26:37,495 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@325093a6 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 08:26:37, skipping insertion in model container [2022-04-05 08:26:37,495 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 05.04 08:26:37" (4/4) ... [2022-04-05 08:26:37,496 INFO L111 eAbstractionObserver]: Analyzing ICFG hard2_valuebound50.cqvasr [2022-04-05 08:26:37,500 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-05 08:26:37,500 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-05 08:26:37,565 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-05 08:26:37,570 INFO L340 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 [2022-04-05 08:26:37,570 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-05 08:26:37,599 INFO L276 IsEmpty]: Start isEmpty. Operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) [2022-04-05 08:26:37,603 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-05 08:26:37,603 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:37,603 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:37,604 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:37,612 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:37,613 INFO L85 PathProgramCache]: Analyzing trace with hash -1625753047, now seen corresponding path program 1 times [2022-04-05 08:26:37,634 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:37,635 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [432472881] [2022-04-05 08:26:37,635 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:37,636 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:37,755 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:37,812 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:26:37,820 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:37,827 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 08:26:37,831 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:37,838 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:26:37,839 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:37,840 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [432472881] [2022-04-05 08:26:37,840 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [432472881] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:37,840 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:37,840 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-05 08:26:37,841 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [158412060] [2022-04-05 08:26:37,842 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:37,844 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-05 08:26:37,844 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:37,862 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-05 08:26:37,863 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-05 08:26:37,864 INFO L87 Difference]: Start difference. First operand has 35 states, 19 states have (on average 1.5263157894736843) internal successors, (29), 20 states have internal predecessors, (29), 10 states have call successors, (10), 4 states have call predecessors, (10), 4 states have return successors, (10), 10 states have call predecessors, (10), 10 states have call successors, (10) Second operand has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 08:26:37,911 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:37,911 INFO L93 Difference]: Finished difference Result 61 states and 95 transitions. [2022-04-05 08:26:37,912 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-05 08:26:37,913 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-05 08:26:37,913 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:37,917 INFO L225 Difference]: With dead ends: 61 [2022-04-05 08:26:37,917 INFO L226 Difference]: Without dead ends: 30 [2022-04-05 08:26:37,919 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 7 GetRequests, 6 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-04-05 08:26:37,921 INFO L913 BasicCegarLoop]: 35 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 10 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 28 SdHoareTripleChecker+Valid, 38 SdHoareTripleChecker+Invalid, 19 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 10 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:37,922 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [28 Valid, 38 Invalid, 19 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 10 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:26:37,931 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 30 states. [2022-04-05 08:26:37,945 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 30 to 30. [2022-04-05 08:26:37,945 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 30 states, 16 states have (on average 1.25) internal successors, (20), 17 states have internal predecessors, (20), 10 states have call successors, (10), 4 states have call predecessors, (10), 3 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 08:26:37,946 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 30 states to 30 states and 38 transitions. [2022-04-05 08:26:37,947 INFO L78 Accepts]: Start accepts. Automaton has 30 states and 38 transitions. Word has length 17 [2022-04-05 08:26:37,947 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:37,947 INFO L478 AbstractCegarLoop]: Abstraction has 30 states and 38 transitions. [2022-04-05 08:26:37,948 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 3.6666666666666665) internal successors, (11), 2 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 2 states have return successors, (2), 2 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 08:26:37,948 INFO L276 IsEmpty]: Start isEmpty. Operand 30 states and 38 transitions. [2022-04-05 08:26:37,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 18 [2022-04-05 08:26:37,948 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:37,948 INFO L499 BasicCegarLoop]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:37,948 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-05 08:26:37,949 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:37,949 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:37,949 INFO L85 PathProgramCache]: Analyzing trace with hash 861759786, now seen corresponding path program 1 times [2022-04-05 08:26:37,949 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:37,949 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1261415565] [2022-04-05 08:26:37,949 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:37,950 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:37,962 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,001 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:26:38,002 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,006 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 08:26:38,007 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,010 INFO L134 CoverageAnalysis]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:26:38,010 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:38,010 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1261415565] [2022-04-05 08:26:38,010 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1261415565] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:38,010 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:38,011 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 08:26:38,011 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [265383208] [2022-04-05 08:26:38,011 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:38,012 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 08:26:38,012 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:38,012 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 08:26:38,013 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:26:38,013 INFO L87 Difference]: Start difference. First operand 30 states and 38 transitions. Second operand has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 08:26:38,132 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:38,132 INFO L93 Difference]: Finished difference Result 43 states and 55 transitions. [2022-04-05 08:26:38,132 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:26:38,132 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) Word has length 17 [2022-04-05 08:26:38,133 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:38,135 INFO L225 Difference]: With dead ends: 43 [2022-04-05 08:26:38,136 INFO L226 Difference]: Without dead ends: 41 [2022-04-05 08:26:38,141 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 13 GetRequests, 5 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:26:38,143 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 37 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 109 mSolverCounterSat, 27 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 41 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 136 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 27 IncrementalHoareTripleChecker+Valid, 109 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:38,146 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [41 Valid, 45 Invalid, 136 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [27 Valid, 109 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:26:38,149 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 41 states. [2022-04-05 08:26:38,157 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 41 to 34. [2022-04-05 08:26:38,157 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 19 states have (on average 1.2105263157894737) internal successors, (23), 20 states have internal predecessors, (23), 10 states have call successors, (10), 5 states have call predecessors, (10), 4 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 08:26:38,158 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 41 transitions. [2022-04-05 08:26:38,158 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 41 transitions. Word has length 17 [2022-04-05 08:26:38,158 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:38,158 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 41 transitions. [2022-04-05 08:26:38,159 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 1.8333333333333333) internal successors, (11), 4 states have internal predecessors, (11), 2 states have call successors, (4), 3 states have call predecessors, (4), 1 states have return successors, (2), 1 states have call predecessors, (2), 1 states have call successors, (2) [2022-04-05 08:26:38,159 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 41 transitions. [2022-04-05 08:26:38,159 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 23 [2022-04-05 08:26:38,159 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:38,159 INFO L499 BasicCegarLoop]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:38,159 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1 [2022-04-05 08:26:38,160 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:38,160 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:38,160 INFO L85 PathProgramCache]: Analyzing trace with hash 325569287, now seen corresponding path program 1 times [2022-04-05 08:26:38,160 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:38,160 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1430947250] [2022-04-05 08:26:38,160 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:38,161 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:38,178 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,207 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-05 08:26:38,209 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,212 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-05 08:26:38,213 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,215 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 13 [2022-04-05 08:26:38,216 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,219 INFO L134 CoverageAnalysis]: Checked inductivity of 2 backedges. 2 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2022-04-05 08:26:38,219 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:38,219 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1430947250] [2022-04-05 08:26:38,219 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1430947250] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:38,220 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:38,220 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-05 08:26:38,220 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [560411705] [2022-04-05 08:26:38,220 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:38,220 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-05 08:26:38,220 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:38,221 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-05 08:26:38,221 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:26:38,221 INFO L87 Difference]: Start difference. First operand 34 states and 41 transitions. Second operand has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-05 08:26:38,366 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:38,366 INFO L93 Difference]: Finished difference Result 47 states and 58 transitions. [2022-04-05 08:26:38,366 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:26:38,367 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 22 [2022-04-05 08:26:38,367 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:38,368 INFO L225 Difference]: With dead ends: 47 [2022-04-05 08:26:38,368 INFO L226 Difference]: Without dead ends: 45 [2022-04-05 08:26:38,370 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 15 GetRequests, 7 SyntacticMatches, 0 SemanticMatches, 8 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=28, Invalid=62, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:26:38,373 INFO L913 BasicCegarLoop]: 28 mSDtfsCounter, 32 mSDsluCounter, 17 mSDsCounter, 0 mSdLazyCounter, 115 mSolverCounterSat, 26 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 36 SdHoareTripleChecker+Valid, 45 SdHoareTripleChecker+Invalid, 141 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 26 IncrementalHoareTripleChecker+Valid, 115 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:38,375 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [36 Valid, 45 Invalid, 141 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [26 Valid, 115 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:26:38,376 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 45 states. [2022-04-05 08:26:38,385 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 45 to 38. [2022-04-05 08:26:38,386 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 38 states, 22 states have (on average 1.1818181818181819) internal successors, (26), 23 states have internal predecessors, (26), 10 states have call successors, (10), 6 states have call predecessors, (10), 5 states have return successors, (8), 8 states have call predecessors, (8), 8 states have call successors, (8) [2022-04-05 08:26:38,387 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 38 states to 38 states and 44 transitions. [2022-04-05 08:26:38,388 INFO L78 Accepts]: Start accepts. Automaton has 38 states and 44 transitions. Word has length 22 [2022-04-05 08:26:38,388 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:38,388 INFO L478 AbstractCegarLoop]: Abstraction has 38 states and 44 transitions. [2022-04-05 08:26:38,388 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 6 states have (on average 2.3333333333333335) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (5), 3 states have call predecessors, (5), 1 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-05 08:26:38,388 INFO L276 IsEmpty]: Start isEmpty. Operand 38 states and 44 transitions. [2022-04-05 08:26:38,389 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 28 [2022-04-05 08:26:38,389 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:38,389 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:38,390 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable2 [2022-04-05 08:26:38,390 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:38,391 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:38,391 INFO L85 PathProgramCache]: Analyzing trace with hash -1461652409, now seen corresponding path program 1 times [2022-04-05 08:26:38,391 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:38,392 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [872983831] [2022-04-05 08:26:38,392 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:38,392 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:38,409 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:38,409 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [80781350] [2022-04-05 08:26:38,409 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:38,409 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:38,410 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:38,416 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-04-05 08:26:38,417 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-04-05 08:26:38,455 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,456 INFO L263 TraceCheckSpWp]: Trace formula consists of 90 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 08:26:38,459 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:38,587 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 4 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-05 08:26:38,587 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:26:38,587 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:38,587 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [872983831] [2022-04-05 08:26:38,587 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:38,588 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [80781350] [2022-04-05 08:26:38,588 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [80781350] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:38,588 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:38,588 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:26:38,588 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1673625945] [2022-04-05 08:26:38,588 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:38,588 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:26:38,589 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:38,589 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:26:38,589 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:26:38,589 INFO L87 Difference]: Start difference. First operand 38 states and 44 transitions. Second operand has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 08:26:38,626 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:38,626 INFO L93 Difference]: Finished difference Result 66 states and 84 transitions. [2022-04-05 08:26:38,627 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:26:38,627 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) Word has length 27 [2022-04-05 08:26:38,627 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:38,627 INFO L225 Difference]: With dead ends: 66 [2022-04-05 08:26:38,627 INFO L226 Difference]: Without dead ends: 52 [2022-04-05 08:26:38,628 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 27 GetRequests, 23 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:26:38,628 INFO L913 BasicCegarLoop]: 40 mSDtfsCounter, 8 mSDsluCounter, 88 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 128 SdHoareTripleChecker+Invalid, 50 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:38,629 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 128 Invalid, 50 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:26:38,629 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-05 08:26:38,633 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 52. [2022-04-05 08:26:38,633 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 52 states, 29 states have (on average 1.1724137931034482) internal successors, (34), 31 states have internal predecessors, (34), 16 states have call successors, (16), 7 states have call predecessors, (16), 6 states have return successors, (13), 13 states have call predecessors, (13), 13 states have call successors, (13) [2022-04-05 08:26:38,634 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 52 states to 52 states and 63 transitions. [2022-04-05 08:26:38,634 INFO L78 Accepts]: Start accepts. Automaton has 52 states and 63 transitions. Word has length 27 [2022-04-05 08:26:38,634 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:38,634 INFO L478 AbstractCegarLoop]: Abstraction has 52 states and 63 transitions. [2022-04-05 08:26:38,635 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 2.8) internal successors, (14), 4 states have internal predecessors, (14), 2 states have call successors, (6), 2 states have call predecessors, (6), 1 states have return successors, (4), 2 states have call predecessors, (4), 2 states have call successors, (4) [2022-04-05 08:26:38,635 INFO L276 IsEmpty]: Start isEmpty. Operand 52 states and 63 transitions. [2022-04-05 08:26:38,635 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 35 [2022-04-05 08:26:38,635 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:38,635 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:38,655 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-04-05 08:26:38,851 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:38,851 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:38,852 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:38,852 INFO L85 PathProgramCache]: Analyzing trace with hash 1008917278, now seen corresponding path program 1 times [2022-04-05 08:26:38,852 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:38,852 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [174077817] [2022-04-05 08:26:38,852 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:38,852 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:38,861 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:38,861 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1203811208] [2022-04-05 08:26:38,861 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:38,861 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:38,861 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:38,862 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-04-05 08:26:38,863 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-04-05 08:26:38,893 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:38,894 INFO L263 TraceCheckSpWp]: Trace formula consists of 101 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-05 08:26:38,895 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:38,982 INFO L134 CoverageAnalysis]: Checked inductivity of 18 backedges. 6 proven. 0 refuted. 0 times theorem prover too weak. 12 trivial. 0 not checked. [2022-04-05 08:26:38,982 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:26:38,983 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:38,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [174077817] [2022-04-05 08:26:38,983 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:38,983 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1203811208] [2022-04-05 08:26:38,983 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1203811208] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:38,983 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:38,983 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:26:38,983 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [99621175] [2022-04-05 08:26:38,983 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:38,984 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:26:38,984 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:38,984 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:26:38,984 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=7, Invalid=13, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:26:38,984 INFO L87 Difference]: Start difference. First operand 52 states and 63 transitions. Second operand has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-05 08:26:39,023 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:39,023 INFO L93 Difference]: Finished difference Result 65 states and 80 transitions. [2022-04-05 08:26:39,023 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:26:39,023 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 34 [2022-04-05 08:26:39,024 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:39,024 INFO L225 Difference]: With dead ends: 65 [2022-04-05 08:26:39,024 INFO L226 Difference]: Without dead ends: 58 [2022-04-05 08:26:39,024 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 34 GetRequests, 30 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=11, Invalid=19, Unknown=0, NotChecked=0, Total=30 [2022-04-05 08:26:39,025 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 9 mSDsluCounter, 66 mSDsCounter, 0 mSdLazyCounter, 55 mSolverCounterSat, 3 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 12 SdHoareTripleChecker+Valid, 97 SdHoareTripleChecker+Invalid, 58 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 3 IncrementalHoareTripleChecker+Valid, 55 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:39,025 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [12 Valid, 97 Invalid, 58 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [3 Valid, 55 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:26:39,026 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 58 states. [2022-04-05 08:26:39,030 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 58 to 57. [2022-04-05 08:26:39,030 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 57 states, 33 states have (on average 1.1818181818181819) internal successors, (39), 35 states have internal predecessors, (39), 16 states have call successors, (16), 8 states have call predecessors, (16), 7 states have return successors, (14), 13 states have call predecessors, (14), 14 states have call successors, (14) [2022-04-05 08:26:39,030 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 57 states to 57 states and 69 transitions. [2022-04-05 08:26:39,030 INFO L78 Accepts]: Start accepts. Automaton has 57 states and 69 transitions. Word has length 34 [2022-04-05 08:26:39,031 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:39,031 INFO L478 AbstractCegarLoop]: Abstraction has 57 states and 69 transitions. [2022-04-05 08:26:39,031 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.2) internal successors, (16), 4 states have internal predecessors, (16), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-05 08:26:39,031 INFO L276 IsEmpty]: Start isEmpty. Operand 57 states and 69 transitions. [2022-04-05 08:26:39,032 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 45 [2022-04-05 08:26:39,032 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:39,032 INFO L499 BasicCegarLoop]: trace histogram [6, 5, 5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:39,048 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Ended with exit code 0 [2022-04-05 08:26:39,248 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:39,248 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:39,249 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:39,249 INFO L85 PathProgramCache]: Analyzing trace with hash -1762200840, now seen corresponding path program 1 times [2022-04-05 08:26:39,249 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:39,249 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [2090431041] [2022-04-05 08:26:39,249 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:39,249 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:39,256 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:39,256 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [668012140] [2022-04-05 08:26:39,256 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:39,257 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:39,257 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:39,257 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-04-05 08:26:39,258 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-04-05 08:26:39,290 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:39,290 INFO L263 TraceCheckSpWp]: Trace formula consists of 123 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-05 08:26:39,292 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:39,406 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 4 refuted. 0 times theorem prover too weak. 40 trivial. 0 not checked. [2022-04-05 08:26:39,406 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:39,489 INFO L134 CoverageAnalysis]: Checked inductivity of 54 backedges. 10 proven. 0 refuted. 0 times theorem prover too weak. 44 trivial. 0 not checked. [2022-04-05 08:26:39,490 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:39,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [2090431041] [2022-04-05 08:26:39,490 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:39,490 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [668012140] [2022-04-05 08:26:39,490 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [668012140] provided 1 perfect and 1 imperfect interpolant sequences [2022-04-05 08:26:39,490 INFO L184 FreeRefinementEngine]: Found 1 perfect and 1 imperfect interpolant sequences. [2022-04-05 08:26:39,490 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [6] total 7 [2022-04-05 08:26:39,490 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [936569820] [2022-04-05 08:26:39,490 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:39,491 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:26:39,491 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:39,491 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:26:39,491 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=13, Invalid=29, Unknown=0, NotChecked=0, Total=42 [2022-04-05 08:26:39,491 INFO L87 Difference]: Start difference. First operand 57 states and 69 transitions. Second operand has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-05 08:26:39,542 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:39,543 INFO L93 Difference]: Finished difference Result 69 states and 84 transitions. [2022-04-05 08:26:39,543 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:26:39,543 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) Word has length 44 [2022-04-05 08:26:39,545 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:39,548 INFO L225 Difference]: With dead ends: 69 [2022-04-05 08:26:39,548 INFO L226 Difference]: Without dead ends: 67 [2022-04-05 08:26:39,549 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 88 GetRequests, 80 SyntacticMatches, 2 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-05 08:26:39,551 INFO L913 BasicCegarLoop]: 36 mSDtfsCounter, 8 mSDsluCounter, 76 mSDsCounter, 0 mSdLazyCounter, 47 mSolverCounterSat, 1 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 11 SdHoareTripleChecker+Valid, 112 SdHoareTripleChecker+Invalid, 48 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 1 IncrementalHoareTripleChecker+Valid, 47 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:39,551 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [11 Valid, 112 Invalid, 48 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [1 Valid, 47 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:26:39,552 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 67 states. [2022-04-05 08:26:39,564 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 67 to 64. [2022-04-05 08:26:39,565 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 64 states, 37 states have (on average 1.162162162162162) internal successors, (43), 40 states have internal predecessors, (43), 18 states have call successors, (18), 9 states have call predecessors, (18), 8 states have return successors, (16), 14 states have call predecessors, (16), 16 states have call successors, (16) [2022-04-05 08:26:39,565 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 64 states to 64 states and 77 transitions. [2022-04-05 08:26:39,566 INFO L78 Accepts]: Start accepts. Automaton has 64 states and 77 transitions. Word has length 44 [2022-04-05 08:26:39,566 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:39,566 INFO L478 AbstractCegarLoop]: Abstraction has 64 states and 77 transitions. [2022-04-05 08:26:39,566 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 3.0) internal successors, (15), 4 states have internal predecessors, (15), 2 states have call successors, (7), 2 states have call predecessors, (7), 1 states have return successors, (5), 2 states have call predecessors, (5), 2 states have call successors, (5) [2022-04-05 08:26:39,566 INFO L276 IsEmpty]: Start isEmpty. Operand 64 states and 77 transitions. [2022-04-05 08:26:39,567 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 65 [2022-04-05 08:26:39,567 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:39,567 INFO L499 BasicCegarLoop]: trace histogram [9, 8, 8, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:39,585 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Ended with exit code 0 [2022-04-05 08:26:39,768 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:39,768 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:39,768 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:39,769 INFO L85 PathProgramCache]: Analyzing trace with hash -1382136022, now seen corresponding path program 1 times [2022-04-05 08:26:39,769 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:39,769 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1992770302] [2022-04-05 08:26:39,769 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:39,769 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:39,779 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:39,779 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [487192715] [2022-04-05 08:26:39,779 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:39,779 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:39,779 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:39,789 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-04-05 08:26:39,791 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-04-05 08:26:39,841 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:39,843 INFO L263 TraceCheckSpWp]: Trace formula consists of 163 conjuncts, 25 conjunts are in the unsatisfiable core [2022-04-05 08:26:39,849 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:40,161 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-05 08:26:40,161 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:41,052 INFO L134 CoverageAnalysis]: Checked inductivity of 135 backedges. 16 proven. 7 refuted. 0 times theorem prover too weak. 112 trivial. 0 not checked. [2022-04-05 08:26:41,052 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:41,053 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1992770302] [2022-04-05 08:26:41,053 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:41,053 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [487192715] [2022-04-05 08:26:41,053 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [487192715] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:41,053 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:41,053 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-05 08:26:41,053 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1032776593] [2022-04-05 08:26:41,053 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:41,054 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 08:26:41,054 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:41,054 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 08:26:41,054 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=24, Invalid=66, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:26:41,054 INFO L87 Difference]: Start difference. First operand 64 states and 77 transitions. Second operand has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-05 08:26:44,910 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:44,910 INFO L93 Difference]: Finished difference Result 154 states and 210 transitions. [2022-04-05 08:26:44,911 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2022-04-05 08:26:44,911 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) Word has length 64 [2022-04-05 08:26:44,911 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:44,912 INFO L225 Difference]: With dead ends: 154 [2022-04-05 08:26:44,912 INFO L226 Difference]: Without dead ends: 125 [2022-04-05 08:26:44,913 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 131 GetRequests, 116 SyntacticMatches, 3 SemanticMatches, 12 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 9 ImplicationChecksByTransitivity, 3.4s TimeCoverageRelationStatistics Valid=50, Invalid=132, Unknown=0, NotChecked=0, Total=182 [2022-04-05 08:26:44,913 INFO L913 BasicCegarLoop]: 46 mSDtfsCounter, 36 mSDsluCounter, 152 mSDsCounter, 0 mSdLazyCounter, 326 mSolverCounterSat, 71 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.5s Time, 0 mProtectedPredicate, 0 mProtectedAction, 42 SdHoareTripleChecker+Valid, 198 SdHoareTripleChecker+Invalid, 397 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 71 IncrementalHoareTripleChecker+Valid, 326 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.6s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:44,913 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [42 Valid, 198 Invalid, 397 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [71 Valid, 326 Invalid, 0 Unknown, 0 Unchecked, 0.6s Time] [2022-04-05 08:26:44,914 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 125 states. [2022-04-05 08:26:44,936 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 125 to 113. [2022-04-05 08:26:44,936 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 113 states, 67 states have (on average 1.2238805970149254) internal successors, (82), 71 states have internal predecessors, (82), 33 states have call successors, (33), 13 states have call predecessors, (33), 12 states have return successors, (31), 28 states have call predecessors, (31), 31 states have call successors, (31) [2022-04-05 08:26:44,937 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 113 states to 113 states and 146 transitions. [2022-04-05 08:26:44,937 INFO L78 Accepts]: Start accepts. Automaton has 113 states and 146 transitions. Word has length 64 [2022-04-05 08:26:44,937 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:44,937 INFO L478 AbstractCegarLoop]: Abstraction has 113 states and 146 transitions. [2022-04-05 08:26:44,938 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 3.0) internal successors, (30), 9 states have internal predecessors, (30), 7 states have call successors, (21), 2 states have call predecessors, (21), 1 states have return successors, (18), 5 states have call predecessors, (18), 5 states have call successors, (18) [2022-04-05 08:26:44,938 INFO L276 IsEmpty]: Start isEmpty. Operand 113 states and 146 transitions. [2022-04-05 08:26:44,938 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 76 [2022-04-05 08:26:44,938 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:44,939 INFO L499 BasicCegarLoop]: trace histogram [11, 10, 10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:44,955 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-04-05 08:26:45,139 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:45,139 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:45,140 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:45,140 INFO L85 PathProgramCache]: Analyzing trace with hash -1085940318, now seen corresponding path program 1 times [2022-04-05 08:26:45,140 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:45,140 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1033040] [2022-04-05 08:26:45,140 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:45,140 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:45,153 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:45,154 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1827772931] [2022-04-05 08:26:45,154 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:45,154 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:45,154 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:45,160 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-04-05 08:26:45,160 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-04-05 08:26:45,226 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:45,228 INFO L263 TraceCheckSpWp]: Trace formula consists of 183 conjuncts, 37 conjunts are in the unsatisfiable core [2022-04-05 08:26:45,229 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:45,620 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 66 proven. 11 refuted. 0 times theorem prover too weak. 132 trivial. 0 not checked. [2022-04-05 08:26:45,621 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:26:45,824 INFO L134 CoverageAnalysis]: Checked inductivity of 209 backedges. 68 proven. 2 refuted. 0 times theorem prover too weak. 139 trivial. 0 not checked. [2022-04-05 08:26:45,824 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:45,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1033040] [2022-04-05 08:26:45,824 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:45,824 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1827772931] [2022-04-05 08:26:45,824 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1827772931] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:26:45,825 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:26:45,825 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 9] total 15 [2022-04-05 08:26:45,825 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1897218774] [2022-04-05 08:26:45,825 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:26:45,825 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 15 states [2022-04-05 08:26:45,825 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:45,826 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 15 interpolants. [2022-04-05 08:26:45,826 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=52, Invalid=158, Unknown=0, NotChecked=0, Total=210 [2022-04-05 08:26:45,826 INFO L87 Difference]: Start difference. First operand 113 states and 146 transitions. Second operand has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) [2022-04-05 08:26:46,097 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:46,097 INFO L93 Difference]: Finished difference Result 169 states and 219 transitions. [2022-04-05 08:26:46,098 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-05 08:26:46,098 INFO L78 Accepts]: Start accepts. Automaton has has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) Word has length 75 [2022-04-05 08:26:46,098 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:46,099 INFO L225 Difference]: With dead ends: 169 [2022-04-05 08:26:46,099 INFO L226 Difference]: Without dead ends: 115 [2022-04-05 08:26:46,100 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 151 GetRequests, 133 SyntacticMatches, 3 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 19 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=65, Invalid=207, Unknown=0, NotChecked=0, Total=272 [2022-04-05 08:26:46,100 INFO L913 BasicCegarLoop]: 34 mSDtfsCounter, 46 mSDsluCounter, 100 mSDsCounter, 0 mSdLazyCounter, 301 mSolverCounterSat, 85 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 59 SdHoareTripleChecker+Valid, 134 SdHoareTripleChecker+Invalid, 386 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 85 IncrementalHoareTripleChecker+Valid, 301 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:46,100 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [59 Valid, 134 Invalid, 386 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [85 Valid, 301 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-05 08:26:46,101 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 115 states. [2022-04-05 08:26:46,109 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 115 to 101. [2022-04-05 08:26:46,109 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 101 states, 61 states have (on average 1.1639344262295082) internal successors, (71), 64 states have internal predecessors, (71), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 22 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-05 08:26:46,110 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 101 states to 101 states and 121 transitions. [2022-04-05 08:26:46,110 INFO L78 Accepts]: Start accepts. Automaton has 101 states and 121 transitions. Word has length 75 [2022-04-05 08:26:46,110 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:46,110 INFO L478 AbstractCegarLoop]: Abstraction has 101 states and 121 transitions. [2022-04-05 08:26:46,110 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 15 states, 12 states have (on average 2.9166666666666665) internal successors, (35), 11 states have internal predecessors, (35), 7 states have call successors, (21), 2 states have call predecessors, (21), 2 states have return successors, (19), 7 states have call predecessors, (19), 5 states have call successors, (19) [2022-04-05 08:26:46,110 INFO L276 IsEmpty]: Start isEmpty. Operand 101 states and 121 transitions. [2022-04-05 08:26:46,111 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 85 [2022-04-05 08:26:46,111 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:46,111 INFO L499 BasicCegarLoop]: trace histogram [13, 12, 12, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:46,145 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (6)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:46,334 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:46,334 INFO L403 AbstractCegarLoop]: === Iteration 9 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:46,334 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:46,334 INFO L85 PathProgramCache]: Analyzing trace with hash 1480109990, now seen corresponding path program 1 times [2022-04-05 08:26:46,334 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:46,334 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1882440601] [2022-04-05 08:26:46,335 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:46,335 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:46,348 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:46,348 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1550884448] [2022-04-05 08:26:46,348 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:46,348 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:46,348 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:46,353 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-04-05 08:26:46,354 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-04-05 08:26:46,389 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:26:46,389 INFO L263 TraceCheckSpWp]: Trace formula consists of 196 conjuncts, 4 conjunts are in the unsatisfiable core [2022-04-05 08:26:46,391 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:46,556 INFO L134 CoverageAnalysis]: Checked inductivity of 303 backedges. 81 proven. 0 refuted. 0 times theorem prover too weak. 222 trivial. 0 not checked. [2022-04-05 08:26:46,557 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-05 08:26:46,557 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:26:46,557 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1882440601] [2022-04-05 08:26:46,557 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:26:46,557 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1550884448] [2022-04-05 08:26:46,557 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1550884448] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-05 08:26:46,557 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-05 08:26:46,557 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [5] imperfect sequences [] total 5 [2022-04-05 08:26:46,557 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [822109448] [2022-04-05 08:26:46,557 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-05 08:26:46,558 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 5 states [2022-04-05 08:26:46,558 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:26:46,558 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 5 interpolants. [2022-04-05 08:26:46,558 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:26:46,558 INFO L87 Difference]: Start difference. First operand 101 states and 121 transitions. Second operand has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-05 08:26:46,605 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:26:46,605 INFO L93 Difference]: Finished difference Result 115 states and 136 transitions. [2022-04-05 08:26:46,605 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:26:46,606 INFO L78 Accepts]: Start accepts. Automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) Word has length 84 [2022-04-05 08:26:46,606 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:26:46,606 INFO L225 Difference]: With dead ends: 115 [2022-04-05 08:26:46,606 INFO L226 Difference]: Without dead ends: 103 [2022-04-05 08:26:46,607 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 83 GetRequests, 80 SyntacticMatches, 0 SemanticMatches, 3 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=10, Invalid=10, Unknown=0, NotChecked=0, Total=20 [2022-04-05 08:26:46,607 INFO L913 BasicCegarLoop]: 52 mSDtfsCounter, 14 mSDsluCounter, 30 mSDsCounter, 0 mSdLazyCounter, 29 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 19 SdHoareTripleChecker+Valid, 82 SdHoareTripleChecker+Invalid, 41 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 29 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-05 08:26:46,607 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [19 Valid, 82 Invalid, 41 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 29 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-05 08:26:46,608 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 103 states. [2022-04-05 08:26:46,617 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 103 to 103. [2022-04-05 08:26:46,618 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 103 states, 63 states have (on average 1.1428571428571428) internal successors, (72), 64 states have internal predecessors, (72), 26 states have call successors, (26), 14 states have call predecessors, (26), 13 states have return successors, (24), 24 states have call predecessors, (24), 24 states have call successors, (24) [2022-04-05 08:26:46,620 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 103 states to 103 states and 122 transitions. [2022-04-05 08:26:46,620 INFO L78 Accepts]: Start accepts. Automaton has 103 states and 122 transitions. Word has length 84 [2022-04-05 08:26:46,620 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:26:46,620 INFO L478 AbstractCegarLoop]: Abstraction has 103 states and 122 transitions. [2022-04-05 08:26:46,620 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 5 states, 5 states have (on average 4.6) internal successors, (23), 5 states have internal predecessors, (23), 5 states have call successors, (16), 2 states have call predecessors, (16), 2 states have return successors, (14), 5 states have call predecessors, (14), 5 states have call successors, (14) [2022-04-05 08:26:46,620 INFO L276 IsEmpty]: Start isEmpty. Operand 103 states and 122 transitions. [2022-04-05 08:26:46,621 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 95 [2022-04-05 08:26:46,621 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:26:46,621 INFO L499 BasicCegarLoop]: trace histogram [14, 13, 13, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:26:46,640 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (7)] Forceful destruction successful, exit code 0 [2022-04-05 08:26:46,840 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable8,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:46,841 INFO L403 AbstractCegarLoop]: === Iteration 10 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:26:46,841 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:26:46,841 INFO L85 PathProgramCache]: Analyzing trace with hash -233495842, now seen corresponding path program 2 times [2022-04-05 08:26:46,841 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:26:46,841 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [368665535] [2022-04-05 08:26:46,841 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:26:46,841 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:26:46,847 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:26:46,847 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1494092688] [2022-04-05 08:26:46,847 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 08:26:46,847 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:26:46,847 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:26:46,851 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-04-05 08:26:46,852 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-04-05 08:26:46,902 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 08:26:46,902 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:26:46,903 INFO L263 TraceCheckSpWp]: Trace formula consists of 225 conjuncts, 39 conjunts are in the unsatisfiable core [2022-04-05 08:26:46,905 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:26:47,347 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-05 08:26:47,348 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:27:09,021 INFO L134 CoverageAnalysis]: Checked inductivity of 362 backedges. 26 proven. 24 refuted. 0 times theorem prover too weak. 312 trivial. 0 not checked. [2022-04-05 08:27:09,021 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:27:09,021 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [368665535] [2022-04-05 08:27:09,022 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:27:09,022 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1494092688] [2022-04-05 08:27:09,022 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1494092688] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:27:09,022 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:27:09,022 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 16 [2022-04-05 08:27:09,022 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [2095979822] [2022-04-05 08:27:09,022 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:27:09,022 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 16 states [2022-04-05 08:27:09,022 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:27:09,023 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 16 interpolants. [2022-04-05 08:27:09,023 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=60, Invalid=180, Unknown=0, NotChecked=0, Total=240 [2022-04-05 08:27:09,023 INFO L87 Difference]: Start difference. First operand 103 states and 122 transitions. Second operand has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2022-04-05 08:27:20,640 WARN L232 SmtUtils]: Spent 11.27s on a formula simplification. DAG size of input: 192 DAG size of output: 88 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-05 08:27:26,006 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:27:26,006 INFO L93 Difference]: Finished difference Result 228 states and 305 transitions. [2022-04-05 08:27:26,008 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2022-04-05 08:27:26,008 INFO L78 Accepts]: Start accepts. Automaton has has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) Word has length 94 [2022-04-05 08:27:26,008 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:27:26,009 INFO L225 Difference]: With dead ends: 228 [2022-04-05 08:27:26,009 INFO L226 Difference]: Without dead ends: 177 [2022-04-05 08:27:26,010 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 192 GetRequests, 170 SyntacticMatches, 3 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 17 ImplicationChecksByTransitivity, 18.7s TimeCoverageRelationStatistics Valid=114, Invalid=306, Unknown=0, NotChecked=0, Total=420 [2022-04-05 08:27:26,010 INFO L913 BasicCegarLoop]: 61 mSDtfsCounter, 94 mSDsluCounter, 244 mSDsCounter, 0 mSdLazyCounter, 764 mSolverCounterSat, 198 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 4.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 105 SdHoareTripleChecker+Valid, 305 SdHoareTripleChecker+Invalid, 962 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 198 IncrementalHoareTripleChecker+Valid, 764 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 4.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:27:26,011 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [105 Valid, 305 Invalid, 962 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [198 Valid, 764 Invalid, 0 Unknown, 0 Unchecked, 4.1s Time] [2022-04-05 08:27:26,011 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 177 states. [2022-04-05 08:27:26,031 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 177 to 166. [2022-04-05 08:27:26,031 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 166 states, 100 states have (on average 1.21) internal successors, (121), 104 states have internal predecessors, (121), 49 states have call successors, (49), 17 states have call predecessors, (49), 16 states have return successors, (47), 44 states have call predecessors, (47), 47 states have call successors, (47) [2022-04-05 08:27:26,032 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 166 states to 166 states and 217 transitions. [2022-04-05 08:27:26,032 INFO L78 Accepts]: Start accepts. Automaton has 166 states and 217 transitions. Word has length 94 [2022-04-05 08:27:26,032 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:27:26,032 INFO L478 AbstractCegarLoop]: Abstraction has 166 states and 217 transitions. [2022-04-05 08:27:26,033 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 16 states, 16 states have (on average 2.5) internal successors, (40), 15 states have internal predecessors, (40), 11 states have call successors, (31), 2 states have call predecessors, (31), 1 states have return successors, (28), 9 states have call predecessors, (28), 9 states have call successors, (28) [2022-04-05 08:27:26,033 INFO L276 IsEmpty]: Start isEmpty. Operand 166 states and 217 transitions. [2022-04-05 08:27:26,034 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 111 [2022-04-05 08:27:26,034 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:27:26,034 INFO L499 BasicCegarLoop]: trace histogram [17, 16, 16, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:27:26,050 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-04-05 08:27:26,250 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable9,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:26,251 INFO L403 AbstractCegarLoop]: === Iteration 11 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:27:26,251 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:27:26,251 INFO L85 PathProgramCache]: Analyzing trace with hash 411415430, now seen corresponding path program 1 times [2022-04-05 08:27:26,251 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:27:26,251 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [353577605] [2022-04-05 08:27:26,251 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:27:26,251 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:27:26,257 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:27:26,258 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [81930424] [2022-04-05 08:27:26,258 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:27:26,258 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:26,258 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:27:26,258 INFO L229 MonitoredProcess]: Starting monitored process 9 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:27:26,259 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Waiting until timeout for monitored process [2022-04-05 08:27:26,323 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-05 08:27:26,324 INFO L263 TraceCheckSpWp]: Trace formula consists of 254 conjuncts, 14 conjunts are in the unsatisfiable core [2022-04-05 08:27:26,326 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:27:26,588 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-05 08:27:26,588 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:27:27,269 INFO L134 CoverageAnalysis]: Checked inductivity of 540 backedges. 32 proven. 28 refuted. 0 times theorem prover too weak. 480 trivial. 0 not checked. [2022-04-05 08:27:27,269 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:27:27,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [353577605] [2022-04-05 08:27:27,269 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:27:27,269 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [81930424] [2022-04-05 08:27:27,269 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [81930424] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:27:27,269 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:27:27,270 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 10 [2022-04-05 08:27:27,270 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [147222191] [2022-04-05 08:27:27,270 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:27:27,271 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 10 states [2022-04-05 08:27:27,271 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:27:27,277 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 10 interpolants. [2022-04-05 08:27:27,277 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=20, Invalid=70, Unknown=0, NotChecked=0, Total=90 [2022-04-05 08:27:27,277 INFO L87 Difference]: Start difference. First operand 166 states and 217 transitions. Second operand has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) [2022-04-05 08:27:27,466 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:27:27,466 INFO L93 Difference]: Finished difference Result 182 states and 239 transitions. [2022-04-05 08:27:27,466 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:27:27,467 INFO L78 Accepts]: Start accepts. Automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) Word has length 110 [2022-04-05 08:27:27,467 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:27:27,471 INFO L225 Difference]: With dead ends: 182 [2022-04-05 08:27:27,471 INFO L226 Difference]: Without dead ends: 174 [2022-04-05 08:27:27,471 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 220 GetRequests, 207 SyntacticMatches, 4 SemanticMatches, 9 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 5 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=24, Invalid=86, Unknown=0, NotChecked=0, Total=110 [2022-04-05 08:27:27,473 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 6 mSDsluCounter, 260 mSDsCounter, 0 mSdLazyCounter, 229 mSolverCounterSat, 0 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 324 SdHoareTripleChecker+Invalid, 229 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Valid, 229 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:27:27,473 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 324 Invalid, 229 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [0 Valid, 229 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:27:27,473 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 174 states. [2022-04-05 08:27:27,488 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 174 to 174. [2022-04-05 08:27:27,489 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 174 states, 104 states have (on average 1.2019230769230769) internal successors, (125), 108 states have internal predecessors, (125), 53 states have call successors, (53), 17 states have call predecessors, (53), 16 states have return successors, (51), 48 states have call predecessors, (51), 51 states have call successors, (51) [2022-04-05 08:27:27,489 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 174 states to 174 states and 229 transitions. [2022-04-05 08:27:27,489 INFO L78 Accepts]: Start accepts. Automaton has 174 states and 229 transitions. Word has length 110 [2022-04-05 08:27:27,490 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:27:27,490 INFO L478 AbstractCegarLoop]: Abstraction has 174 states and 229 transitions. [2022-04-05 08:27:27,490 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 10 states, 10 states have (on average 4.2) internal successors, (42), 9 states have internal predecessors, (42), 7 states have call successors, (37), 2 states have call predecessors, (37), 1 states have return successors, (34), 7 states have call predecessors, (34), 7 states have call successors, (34) [2022-04-05 08:27:27,490 INFO L276 IsEmpty]: Start isEmpty. Operand 174 states and 229 transitions. [2022-04-05 08:27:27,491 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 124 [2022-04-05 08:27:27,491 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:27:27,491 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:27:27,508 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (9)] Forceful destruction successful, exit code 0 [2022-04-05 08:27:27,706 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 9 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable10 [2022-04-05 08:27:27,707 INFO L403 AbstractCegarLoop]: === Iteration 12 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:27:27,707 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:27:27,707 INFO L85 PathProgramCache]: Analyzing trace with hash 564418017, now seen corresponding path program 2 times [2022-04-05 08:27:27,707 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:27:27,707 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1119013550] [2022-04-05 08:27:27,707 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:27:27,707 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:27:27,714 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:27:27,714 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [486912965] [2022-04-05 08:27:27,714 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-05 08:27:27,714 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:27,714 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:27:27,715 INFO L229 MonitoredProcess]: Starting monitored process 10 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:27:27,716 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Waiting until timeout for monitored process [2022-04-05 08:27:27,762 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-05 08:27:27,762 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:27:27,763 INFO L263 TraceCheckSpWp]: Trace formula consists of 283 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 08:27:27,765 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:27:27,929 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 102 proven. 42 refuted. 0 times theorem prover too weak. 546 trivial. 0 not checked. [2022-04-05 08:27:27,929 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:27:28,229 INFO L134 CoverageAnalysis]: Checked inductivity of 690 backedges. 63 proven. 15 refuted. 0 times theorem prover too weak. 612 trivial. 0 not checked. [2022-04-05 08:27:28,229 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:27:28,230 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1119013550] [2022-04-05 08:27:28,230 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:27:28,230 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [486912965] [2022-04-05 08:27:28,230 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [486912965] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:27:28,230 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:27:28,230 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [6, 6] total 9 [2022-04-05 08:27:28,230 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [477045648] [2022-04-05 08:27:28,230 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:27:28,230 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 08:27:28,230 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:27:28,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 08:27:28,231 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-05 08:27:28,231 INFO L87 Difference]: Start difference. First operand 174 states and 229 transitions. Second operand has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) [2022-04-05 08:27:28,307 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:27:28,308 INFO L93 Difference]: Finished difference Result 203 states and 266 transitions. [2022-04-05 08:27:28,308 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 5 states. [2022-04-05 08:27:28,308 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) Word has length 123 [2022-04-05 08:27:28,308 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:27:28,309 INFO L225 Difference]: With dead ends: 203 [2022-04-05 08:27:28,309 INFO L226 Difference]: Without dead ends: 136 [2022-04-05 08:27:28,310 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 245 GetRequests, 235 SyntacticMatches, 3 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 6 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=27, Invalid=45, Unknown=0, NotChecked=0, Total=72 [2022-04-05 08:27:28,310 INFO L913 BasicCegarLoop]: 64 mSDtfsCounter, 5 mSDsluCounter, 121 mSDsCounter, 0 mSdLazyCounter, 105 mSolverCounterSat, 6 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 6 SdHoareTripleChecker+Valid, 185 SdHoareTripleChecker+Invalid, 111 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 6 IncrementalHoareTripleChecker+Valid, 105 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:27:28,310 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [6 Valid, 185 Invalid, 111 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [6 Valid, 105 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:27:28,310 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 136 states. [2022-04-05 08:27:28,322 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 136 to 136. [2022-04-05 08:27:28,322 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 136 states, 82 states have (on average 1.1585365853658536) internal successors, (95), 86 states have internal predecessors, (95), 37 states have call successors, (37), 17 states have call predecessors, (37), 16 states have return successors, (35), 32 states have call predecessors, (35), 35 states have call successors, (35) [2022-04-05 08:27:28,323 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 136 states to 136 states and 167 transitions. [2022-04-05 08:27:28,323 INFO L78 Accepts]: Start accepts. Automaton has 136 states and 167 transitions. Word has length 123 [2022-04-05 08:27:28,323 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:27:28,323 INFO L478 AbstractCegarLoop]: Abstraction has 136 states and 167 transitions. [2022-04-05 08:27:28,323 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 5.222222222222222) internal successors, (47), 9 states have internal predecessors, (47), 9 states have call successors, (38), 2 states have call predecessors, (38), 2 states have return successors, (36), 9 states have call predecessors, (36), 9 states have call successors, (36) [2022-04-05 08:27:28,323 INFO L276 IsEmpty]: Start isEmpty. Operand 136 states and 167 transitions. [2022-04-05 08:27:28,324 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 125 [2022-04-05 08:27:28,324 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:27:28,324 INFO L499 BasicCegarLoop]: trace histogram [19, 18, 18, 4, 4, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:27:28,341 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (10)] Forceful destruction successful, exit code 0 [2022-04-05 08:27:28,540 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable11,10 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:28,541 INFO L403 AbstractCegarLoop]: === Iteration 13 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:27:28,541 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:27:28,541 INFO L85 PathProgramCache]: Analyzing trace with hash -1567600662, now seen corresponding path program 3 times [2022-04-05 08:27:28,541 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:27:28,541 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1071901676] [2022-04-05 08:27:28,541 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:27:28,541 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:27:28,556 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:27:28,556 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1238897271] [2022-04-05 08:27:28,556 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 08:27:28,556 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:28,556 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:27:28,572 INFO L229 MonitoredProcess]: Starting monitored process 11 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:27:28,604 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Waiting until timeout for monitored process [2022-04-05 08:27:28,643 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 08:27:28,643 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:27:28,644 INFO L263 TraceCheckSpWp]: Trace formula consists of 178 conjuncts, 24 conjunts are in the unsatisfiable core [2022-04-05 08:27:28,646 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:27:28,912 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:27:28,944 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:27:28,972 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-05 08:27:29,060 INFO L134 CoverageAnalysis]: Checked inductivity of 699 backedges. 142 proven. 2 refuted. 0 times theorem prover too weak. 555 trivial. 0 not checked. [2022-04-05 08:27:29,060 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:27:39,106 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:27:39,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1071901676] [2022-04-05 08:27:39,106 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:27:39,106 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1238897271] [2022-04-05 08:27:39,106 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1238897271] provided 0 perfect and 1 imperfect interpolant sequences [2022-04-05 08:27:39,106 INFO L184 FreeRefinementEngine]: Found 0 perfect and 1 imperfect interpolant sequences. [2022-04-05 08:27:39,106 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9] total 9 [2022-04-05 08:27:39,106 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [507918562] [2022-04-05 08:27:39,106 INFO L85 oduleStraightlineAll]: Using 1 imperfect interpolants to construct interpolant automaton [2022-04-05 08:27:39,107 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 9 states [2022-04-05 08:27:39,107 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:27:39,107 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 9 interpolants. [2022-04-05 08:27:39,107 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=122, Unknown=0, NotChecked=0, Total=156 [2022-04-05 08:27:39,107 INFO L87 Difference]: Start difference. First operand 136 states and 167 transitions. Second operand has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-05 08:27:39,215 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:27:39,216 INFO L93 Difference]: Finished difference Result 142 states and 172 transitions. [2022-04-05 08:27:39,216 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 7 states. [2022-04-05 08:27:39,216 INFO L78 Accepts]: Start accepts. Automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) Word has length 124 [2022-04-05 08:27:39,216 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:27:39,217 INFO L225 Difference]: With dead ends: 142 [2022-04-05 08:27:39,217 INFO L226 Difference]: Without dead ends: 138 [2022-04-05 08:27:39,217 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 133 GetRequests, 117 SyntacticMatches, 3 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=45, Invalid=165, Unknown=0, NotChecked=0, Total=210 [2022-04-05 08:27:39,219 INFO L913 BasicCegarLoop]: 25 mSDtfsCounter, 16 mSDsluCounter, 75 mSDsCounter, 0 mSdLazyCounter, 106 mSolverCounterSat, 9 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 100 SdHoareTripleChecker+Invalid, 115 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Valid, 106 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:27:39,219 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 100 Invalid, 115 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [9 Valid, 106 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:27:39,220 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 138 states. [2022-04-05 08:27:39,230 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 138 to 118. [2022-04-05 08:27:39,231 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 118 states, 73 states have (on average 1.1095890410958904) internal successors, (81), 73 states have internal predecessors, (81), 29 states have call successors, (29), 17 states have call predecessors, (29), 15 states have return successors, (27), 27 states have call predecessors, (27), 27 states have call successors, (27) [2022-04-05 08:27:39,232 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 118 states to 118 states and 137 transitions. [2022-04-05 08:27:39,233 INFO L78 Accepts]: Start accepts. Automaton has 118 states and 137 transitions. Word has length 124 [2022-04-05 08:27:39,233 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:27:39,233 INFO L478 AbstractCegarLoop]: Abstraction has 118 states and 137 transitions. [2022-04-05 08:27:39,233 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 9 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 8 states have internal predecessors, (25), 3 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (9), 4 states have call predecessors, (9), 3 states have call successors, (9) [2022-04-05 08:27:39,234 INFO L276 IsEmpty]: Start isEmpty. Operand 118 states and 137 transitions. [2022-04-05 08:27:39,234 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 128 [2022-04-05 08:27:39,234 INFO L491 BasicCegarLoop]: Found error trace [2022-04-05 08:27:39,235 INFO L499 BasicCegarLoop]: trace histogram [20, 19, 19, 4, 4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:27:39,251 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (11)] Forceful destruction successful, exit code 0 [2022-04-05 08:27:39,451 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 11 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable12 [2022-04-05 08:27:39,451 INFO L403 AbstractCegarLoop]: === Iteration 14 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-05 08:27:39,451 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-05 08:27:39,451 INFO L85 PathProgramCache]: Analyzing trace with hash 1333998901, now seen corresponding path program 3 times [2022-04-05 08:27:39,452 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-05 08:27:39,452 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1102799470] [2022-04-05 08:27:39,452 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-05 08:27:39,452 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-05 08:27:39,458 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-05 08:27:39,458 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1570709688] [2022-04-05 08:27:39,458 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-05 08:27:39,458 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-05 08:27:39,458 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-05 08:27:39,459 INFO L229 MonitoredProcess]: Starting monitored process 12 with /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (exit command is (exit), workingDir is null) [2022-04-05 08:27:39,460 INFO L327 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Waiting until timeout for monitored process [2022-04-05 08:27:39,495 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 4 check-sat command(s) [2022-04-05 08:27:39,495 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-05 08:27:39,495 INFO L263 TraceCheckSpWp]: Trace formula consists of 158 conjuncts, 12 conjunts are in the unsatisfiable core [2022-04-05 08:27:39,511 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-05 08:27:39,704 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-04-05 08:27:39,704 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-05 08:27:39,913 INFO L134 CoverageAnalysis]: Checked inductivity of 765 backedges. 90 proven. 4 refuted. 0 times theorem prover too weak. 671 trivial. 0 not checked. [2022-04-05 08:27:39,913 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-05 08:27:39,913 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1102799470] [2022-04-05 08:27:39,913 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-05 08:27:39,913 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1570709688] [2022-04-05 08:27:39,914 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1570709688] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-05 08:27:39,914 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-05 08:27:39,914 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 8] total 12 [2022-04-05 08:27:39,914 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1636007946] [2022-04-05 08:27:39,914 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-05 08:27:39,914 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-05 08:27:39,914 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-05 08:27:39,914 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-05 08:27:39,915 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=31, Invalid=101, Unknown=0, NotChecked=0, Total=132 [2022-04-05 08:27:39,915 INFO L87 Difference]: Start difference. First operand 118 states and 137 transitions. Second operand has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) [2022-04-05 08:27:40,049 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-05 08:27:40,049 INFO L93 Difference]: Finished difference Result 126 states and 143 transitions. [2022-04-05 08:27:40,050 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 8 states. [2022-04-05 08:27:40,050 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) Word has length 127 [2022-04-05 08:27:40,050 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-05 08:27:40,051 INFO L225 Difference]: With dead ends: 126 [2022-04-05 08:27:40,051 INFO L226 Difference]: Without dead ends: 0 [2022-04-05 08:27:40,051 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 257 GetRequests, 243 SyntacticMatches, 1 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=51, Invalid=159, Unknown=0, NotChecked=0, Total=210 [2022-04-05 08:27:40,051 INFO L913 BasicCegarLoop]: 24 mSDtfsCounter, 17 mSDsluCounter, 125 mSDsCounter, 0 mSdLazyCounter, 149 mSolverCounterSat, 17 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 21 SdHoareTripleChecker+Valid, 149 SdHoareTripleChecker+Invalid, 166 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 17 IncrementalHoareTripleChecker+Valid, 149 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-05 08:27:40,051 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [21 Valid, 149 Invalid, 166 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [17 Valid, 149 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-05 08:27:40,052 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-05 08:27:40,052 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-05 08:27:40,052 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-04-05 08:27:40,052 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-05 08:27:40,052 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 127 [2022-04-05 08:27:40,052 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-05 08:27:40,052 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-05 08:27:40,052 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 10 states have (on average 3.3) internal successors, (33), 9 states have internal predecessors, (33), 4 states have call successors, (17), 2 states have call predecessors, (17), 2 states have return successors, (16), 6 states have call predecessors, (16), 4 states have call successors, (16) [2022-04-05 08:27:40,052 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-05 08:27:40,052 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-05 08:27:40,054 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-05 08:27:40,072 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (12)] Forceful destruction successful, exit code 0 [2022-04-05 08:27:40,255 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 12 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable13 [2022-04-05 08:27:40,256 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-05 08:27:51,490 WARN L232 SmtUtils]: Spent 10.55s on a formula simplification. DAG size of input: 144 DAG size of output: 16 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-05 08:27:56,747 INFO L878 garLoopResultBuilder]: At program point ULTIMATE.initENTRY(line -1) the Hoare annotation is: (and (= |#NULL.offset| |old(#NULL.offset)|) (= |old(#NULL.base)| |#NULL.base|)) [2022-04-05 08:27:56,747 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-04-05 08:27:56,747 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-04-05 08:27:56,747 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-05 08:27:56,747 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-05 08:27:56,747 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-04-05 08:27:56,747 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-04-05 08:27:56,747 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 11 13) the Hoare annotation is: true [2022-04-05 08:27:56,747 INFO L882 garLoopResultBuilder]: For program point L12(line 12) no Hoare annotation was computed. [2022-04-05 08:27:56,748 INFO L882 garLoopResultBuilder]: For program point L12-2(lines 11 13) no Hoare annotation was computed. [2022-04-05 08:27:56,748 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 11 13) no Hoare annotation was computed. [2022-04-05 08:27:56,748 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 22 61) the Hoare annotation is: true [2022-04-05 08:27:56,748 INFO L885 garLoopResultBuilder]: At program point L26(line 26) the Hoare annotation is: true [2022-04-05 08:27:56,748 INFO L882 garLoopResultBuilder]: For program point L26-1(line 26) no Hoare annotation was computed. [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L34-2(lines 34 42) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-04-05 08:27:56,748 INFO L882 garLoopResultBuilder]: For program point L52-2(lines 22 61) no Hoare annotation was computed. [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L35(line 35) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L44-1(lines 44 56) the Hoare annotation is: (and (<= 1 main_~B~0) (= (+ (* main_~d~0 main_~q~0) main_~r~0) main_~A~0) (<= 1 main_~p~0) (= main_~B~0 main_~d~0)) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L45(line 45) the Hoare annotation is: (and (= (* main_~B~0 main_~p~0) main_~d~0) (<= 1 main_~p~0) (= main_~B~0 1) (= (+ (* main_~B~0 main_~q~0) main_~r~0) main_~A~0)) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L35-1(line 35) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L58(line 58) the Hoare annotation is: (let ((.cse0 (= main_~B~0 main_~d~0))) (or (and (= main_~B~0 1) .cse0 (= main_~p~0 1)) (and (<= 1 main_~B~0) (= (+ (* main_~d~0 main_~q~0) main_~r~0) main_~A~0) (<= 1 main_~p~0) .cse0))) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L45-1(line 45) the Hoare annotation is: (let ((.cse1 (* main_~B~0 main_~q~0))) (let ((.cse0 (div main_~p~0 2)) (.cse2 (= (+ .cse1 main_~r~0) main_~A~0))) (or (and (<= 1 .cse0) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse1 main_~r~0)) (= main_~B~0 1) .cse2) (and (= (let ((.cse3 (div main_~d~0 2))) (+ (div .cse3 2) main_~A~0 .cse3)) (+ .cse1 main_~r~0 (* main_~B~0 (div .cse0 2)) (* main_~B~0 .cse0))) (<= 1 main_~B~0) .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1))))) [2022-04-05 08:27:56,748 INFO L878 garLoopResultBuilder]: At program point L36(line 36) the Hoare annotation is: (let ((.cse3 (* main_~B~0 main_~q~0))) (let ((.cse0 (= main_~q~0 0)) (.cse1 (= main_~B~0 1)) (.cse2 (= (+ .cse3 main_~r~0) main_~A~0))) (or (and .cse0 .cse1 .cse2 (= main_~B~0 main_~d~0) (= main_~p~0 1)) (and (= (* main_~B~0 2) main_~d~0) (= main_~p~0 2) .cse0 .cse1 .cse2) (and (<= 1 (div (div main_~p~0 2) 2)) (= (+ main_~A~0 main_~d~0) (+ (* main_~B~0 main_~p~0) .cse3 main_~r~0)) .cse0 .cse1 .cse2)))) [2022-04-05 08:27:56,748 INFO L882 garLoopResultBuilder]: For program point L59(line 59) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L46(lines 44 56) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L37(lines 34 42) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 22 61) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L52(lines 52 55) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 22 61) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 14 20) the Hoare annotation is: true [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L15(lines 15 18) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L16(lines 16 17) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point L15-2(lines 14 20) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 17) no Hoare annotation was computed. [2022-04-05 08:27:56,749 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 14 20) no Hoare annotation was computed. [2022-04-05 08:27:56,751 INFO L719 BasicCegarLoop]: Path program histogram: [3, 3, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-05 08:27:56,753 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-05 08:27:56,769 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 05.04 08:27:56 BasicIcfg [2022-04-05 08:27:56,769 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-05 08:27:56,770 INFO L158 Benchmark]: Toolchain (without parser) took 79740.42ms. Allocated memory was 242.2MB in the beginning and 383.8MB in the end (delta: 141.6MB). Free memory was 190.6MB in the beginning and 229.3MB in the end (delta: -38.7MB). Peak memory consumption was 207.3MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,770 INFO L158 Benchmark]: CDTParser took 0.11ms. Allocated memory is still 242.2MB. Free memory was 206.8MB in the beginning and 206.7MB in the end (delta: 146.8kB). There was no memory consumed. Max. memory is 8.0GB. [2022-04-05 08:27:56,770 INFO L158 Benchmark]: CACSL2BoogieTranslator took 165.87ms. Allocated memory is still 242.2MB. Free memory was 190.3MB in the beginning and 218.5MB in the end (delta: -28.1MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,772 INFO L158 Benchmark]: Boogie Preprocessor took 16.16ms. Allocated memory is still 242.2MB. Free memory was 218.5MB in the beginning and 217.0MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,773 INFO L158 Benchmark]: RCFGBuilder took 223.30ms. Allocated memory is still 242.2MB. Free memory was 217.0MB in the beginning and 206.5MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,773 INFO L158 Benchmark]: IcfgTransformer took 40.34ms. Allocated memory is still 242.2MB. Free memory was 206.5MB in the beginning and 205.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,773 INFO L158 Benchmark]: TraceAbstraction took 79291.10ms. Allocated memory was 242.2MB in the beginning and 383.8MB in the end (delta: 141.6MB). Free memory was 204.9MB in the beginning and 229.3MB in the end (delta: -24.4MB). Peak memory consumption was 221.1MB. Max. memory is 8.0GB. [2022-04-05 08:27:56,776 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.11ms. Allocated memory is still 242.2MB. Free memory was 206.8MB in the beginning and 206.7MB in the end (delta: 146.8kB). There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 165.87ms. Allocated memory is still 242.2MB. Free memory was 190.3MB in the beginning and 218.5MB in the end (delta: -28.1MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 16.16ms. Allocated memory is still 242.2MB. Free memory was 218.5MB in the beginning and 217.0MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * RCFGBuilder took 223.30ms. Allocated memory is still 242.2MB. Free memory was 217.0MB in the beginning and 206.5MB in the end (delta: 10.5MB). Peak memory consumption was 10.5MB. Max. memory is 8.0GB. * IcfgTransformer took 40.34ms. Allocated memory is still 242.2MB. Free memory was 206.5MB in the beginning and 205.5MB in the end (delta: 1.0MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 79291.10ms. Allocated memory was 242.2MB in the beginning and 383.8MB in the end (delta: 141.6MB). Free memory was 204.9MB in the beginning and 229.3MB in the end (delta: -24.4MB). Peak memory consumption was 221.1MB. Max. memory is 8.0GB. * 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: 17]: 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, 35 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 79.2s, OverallIterations: 14, TraceHistogramMax: 20, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 22.2s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 16.5s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 0 mSolverCounterUnknown, 419 SdHoareTripleChecker+Valid, 5.6s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 348 mSDsluCounter, 1942 SdHoareTripleChecker+Invalid, 5.3s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 0 IncrementalHoareTripleChecker+Unchecked, 1374 mSDsCounter, 467 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 2392 IncrementalHoareTripleChecker+Invalid, 2859 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 467 mSolverCounterUnsat, 568 mSDtfsCounter, 2392 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 0 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 1596 GetRequests, 1452 SyntacticMatches, 22 SemanticMatches, 122 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 123 ImplicationChecksByTransitivity, 23.3s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=174occurred in iteration=11, InterpolantAutomatonStates: 100, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.2s AutomataMinimizationTime, 14 MinimizatonAttempts, 75 StatesRemovedByMinimization, 8 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 15 LocationsWithAnnotation, 128 PreInvPairs, 188 NumberOfFragments, 455 HoareAnnotationTreeSize, 128 FomulaSimplifications, 522 FormulaSimplificationTreeSizeReduction, 0.7s HoareSimplificationTime, 15 FomulaSimplificationsInter, 13560 FormulaSimplificationTreeSizeReductionInter, 15.8s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.4s SatisfiabilityAnalysisTime, 37.0s InterpolantComputationTime, 962 NumberOfCodeBlocks, 840 NumberOfCodeBlocksAsserted, 22 NumberOfCheckSat, 1578 ConstructedInterpolants, 0 QuantifiedInterpolants, 16014 SizeOfPredicates, 26 NumberOfNonLiveVariables, 1954 ConjunctsInSsa, 198 ConjunctsInUnsatCore, 21 InterpolantComputations, 7 PerfectInterpolantSequences, 6338/6540 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: 34]: Loop Invariant Derived loop invariant: (((((q == 0 && B == 1) && B * q + r == A) && B == d) && p == 1) || ((((B * 2 == d && p == 2) && q == 0) && B == 1) && B * q + r == A)) || ((((1 <= p / 2 / 2 && A + d == B * p + B * q + r) && q == 0) && B == 1) && B * q + r == A) RESULT: Ultimate proved your program to be correct! [2022-04-05 08:27:56,818 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...