/usr/bin/java -Xmx8000000000 -Xss4m -jar ./plugins/org.eclipse.equinox.launcher_1.5.800.v20200727-1323.jar -data @noDefault -ultimatedata ./data --core.log.level.for.class de.uni_freiburg.informatik.ultimate.lib.smtlibutils.quantifier.QuantifierPusher=WARN -tc ../../../trunk/examples/toolchains/AutomizerCTransformed.xml -s ../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf -i ../../../trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound50.c -------------------------------------------------------------------------------- This is Ultimate 0.2.2-dev-34549b5 [2022-04-06 11:01:53,109 INFO L177 SettingsManager]: Resetting all preferences to default values... [2022-04-06 11:01:53,111 INFO L181 SettingsManager]: Resetting UltimateCore preferences to default values [2022-04-06 11:01:53,148 INFO L184 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2022-04-06 11:01:53,149 INFO L181 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2022-04-06 11:01:53,150 INFO L181 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2022-04-06 11:01:53,152 INFO L181 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2022-04-06 11:01:53,158 INFO L181 SettingsManager]: Resetting LassoRanker preferences to default values [2022-04-06 11:01:53,159 INFO L181 SettingsManager]: Resetting Reaching Definitions preferences to default values [2022-04-06 11:01:53,164 INFO L181 SettingsManager]: Resetting SyntaxChecker preferences to default values [2022-04-06 11:01:53,165 INFO L181 SettingsManager]: Resetting Sifa preferences to default values [2022-04-06 11:01:53,165 INFO L184 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2022-04-06 11:01:53,166 INFO L181 SettingsManager]: Resetting LTL2Aut preferences to default values [2022-04-06 11:01:53,166 INFO L181 SettingsManager]: Resetting PEA to Boogie preferences to default values [2022-04-06 11:01:53,167 INFO L181 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2022-04-06 11:01:53,170 INFO L181 SettingsManager]: Resetting ChcToBoogie preferences to default values [2022-04-06 11:01:53,171 INFO L181 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2022-04-06 11:01:53,172 INFO L181 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2022-04-06 11:01:53,174 INFO L181 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2022-04-06 11:01:53,177 INFO L181 SettingsManager]: Resetting CodeCheck preferences to default values [2022-04-06 11:01:53,178 INFO L181 SettingsManager]: Resetting HornVerifier preferences to default values [2022-04-06 11:01:53,180 INFO L181 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2022-04-06 11:01:53,181 INFO L181 SettingsManager]: Resetting RCFGBuilder preferences to default values [2022-04-06 11:01:53,182 INFO L181 SettingsManager]: Resetting Referee preferences to default values [2022-04-06 11:01:53,183 INFO L181 SettingsManager]: Resetting TraceAbstraction preferences to default values [2022-04-06 11:01:53,187 INFO L184 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2022-04-06 11:01:53,187 INFO L184 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2022-04-06 11:01:53,187 INFO L181 SettingsManager]: Resetting TreeAutomizer preferences to default values [2022-04-06 11:01:53,189 INFO L181 SettingsManager]: Resetting IcfgToChc preferences to default values [2022-04-06 11:01:53,189 INFO L181 SettingsManager]: Resetting IcfgTransformer preferences to default values [2022-04-06 11:01:53,190 INFO L184 SettingsManager]: ReqToTest provides no preferences, ignoring... [2022-04-06 11:01:53,190 INFO L181 SettingsManager]: Resetting Boogie Printer preferences to default values [2022-04-06 11:01:53,192 INFO L181 SettingsManager]: Resetting ChcSmtPrinter preferences to default values [2022-04-06 11:01:53,193 INFO L181 SettingsManager]: Resetting ReqPrinter preferences to default values [2022-04-06 11:01:53,193 INFO L181 SettingsManager]: Resetting Witness Printer preferences to default values [2022-04-06 11:01:53,194 INFO L184 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2022-04-06 11:01:53,194 INFO L181 SettingsManager]: Resetting CDTParser preferences to default values [2022-04-06 11:01:53,194 INFO L184 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2022-04-06 11:01:53,195 INFO L184 SettingsManager]: ReqParser provides no preferences, ignoring... [2022-04-06 11:01:53,195 INFO L181 SettingsManager]: Resetting SmtParser preferences to default values [2022-04-06 11:01:53,195 INFO L181 SettingsManager]: Resetting Witness Parser preferences to default values [2022-04-06 11:01:53,197 INFO L188 SettingsManager]: Finished resetting all preferences to default values... [2022-04-06 11:01:53,198 INFO L101 SettingsManager]: Beginning loading settings from /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/loopacceleration/qvasr/qvasr_64.epf [2022-04-06 11:01:53,226 INFO L113 SettingsManager]: Loading preferences was successful [2022-04-06 11:01:53,227 INFO L115 SettingsManager]: Preferences different from defaults after loading the file: [2022-04-06 11:01:53,227 INFO L136 SettingsManager]: Preferences of Boogie Procedure Inliner differ from their defaults: [2022-04-06 11:01:53,228 INFO L138 SettingsManager]: * Ignore calls to procedures called more than once=ONLY_FOR_SEQUENTIAL_PROGRAMS [2022-04-06 11:01:53,228 INFO L136 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2022-04-06 11:01:53,229 INFO L138 SettingsManager]: * Create parallel compositions if possible=false [2022-04-06 11:01:53,229 INFO L138 SettingsManager]: * Use SBE=true [2022-04-06 11:01:53,229 INFO L136 SettingsManager]: Preferences of CACSL2BoogieTranslator differ from their defaults: [2022-04-06 11:01:53,229 INFO L138 SettingsManager]: * Overapproximate operations on floating types=true [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * Check division by zero=IGNORE [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * Pointer to allocated memory at dereference=IGNORE [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * If two pointers are subtracted or compared they have the same base address=IGNORE [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * Check array bounds for arrays that are off heap=IGNORE [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * Check if freed pointer was valid=false [2022-04-06 11:01:53,230 INFO L138 SettingsManager]: * Use constant arrays=true [2022-04-06 11:01:53,231 INFO L138 SettingsManager]: * Pointer base address is valid at dereference=IGNORE [2022-04-06 11:01:53,231 INFO L136 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2022-04-06 11:01:53,231 INFO L138 SettingsManager]: * Size of a code block=SequenceOfStatements [2022-04-06 11:01:53,231 INFO L138 SettingsManager]: * SMT solver=External_DefaultMode [2022-04-06 11:01:53,231 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 11:01:53,231 INFO L136 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2022-04-06 11:01:53,231 INFO L138 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2022-04-06 11:01:53,232 INFO L138 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2022-04-06 11:01:53,232 INFO L138 SettingsManager]: * Trace refinement strategy=CAMEL [2022-04-06 11:01:53,232 INFO L138 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2022-04-06 11:01:53,232 INFO L138 SettingsManager]: * Compute Hoare Annotation of negated interpolant automaton, abstraction and CFG=true [2022-04-06 11:01:53,232 INFO L138 SettingsManager]: * Trace refinement exception blacklist=NONE [2022-04-06 11:01:53,233 INFO L138 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2022-04-06 11:01:53,234 INFO L136 SettingsManager]: Preferences of IcfgTransformer differ from their defaults: [2022-04-06 11:01:53,234 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-06 11:01:53,476 INFO L75 nceAwareModelManager]: Repository-Root is: /tmp [2022-04-06 11:01:53,499 INFO L261 ainManager$Toolchain]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2022-04-06 11:01:53,501 INFO L217 ainManager$Toolchain]: [Toolchain 1]: Toolchain selected. [2022-04-06 11:01:53,502 INFO L271 PluginConnector]: Initializing CDTParser... [2022-04-06 11:01:53,503 INFO L275 PluginConnector]: CDTParser initialized [2022-04-06 11:01:53,504 INFO L432 ainManager$Toolchain]: [Toolchain 1]: Parsing single file: /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound50.c [2022-04-06 11:01:53,552 INFO L220 CDTParser]: Created temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e18d6afbd/65981c2daaaf4b2abdb8a29cb9fe2f71/FLAG6f8b948d5 [2022-04-06 11:01:53,962 INFO L306 CDTParser]: Found 1 translation units. [2022-04-06 11:01:53,963 INFO L160 CDTParser]: Scanning /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound50.c [2022-04-06 11:01:53,971 INFO L349 CDTParser]: About to delete temporary CDT project at /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e18d6afbd/65981c2daaaf4b2abdb8a29cb9fe2f71/FLAG6f8b948d5 [2022-04-06 11:01:54,353 INFO L357 CDTParser]: Successfully deleted /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/data/e18d6afbd/65981c2daaaf4b2abdb8a29cb9fe2f71 [2022-04-06 11:01:54,355 INFO L299 ainManager$Toolchain]: ####################### [Toolchain 1] ####################### [2022-04-06 11:01:54,356 INFO L131 ToolchainWalker]: Walking toolchain with 5 elements. [2022-04-06 11:01:54,357 INFO L113 PluginConnector]: ------------------------CACSL2BoogieTranslator---------------------------- [2022-04-06 11:01:54,357 INFO L271 PluginConnector]: Initializing CACSL2BoogieTranslator... [2022-04-06 11:01:54,360 INFO L275 PluginConnector]: CACSL2BoogieTranslator initialized [2022-04-06 11:01:54,360 INFO L185 PluginConnector]: Executing the observer ACSLObjectContainerObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,361 INFO L205 PluginConnector]: Invalid model from CACSL2BoogieTranslator for observer de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator.ACSLObjectContainerObserver@2124f8b1 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54, skipping insertion in model container [2022-04-06 11:01:54,361 INFO L185 PluginConnector]: Executing the observer CACSL2BoogieTranslatorObserver from plugin CACSL2BoogieTranslator for "CDTParser AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,368 INFO L145 MainTranslator]: Starting translation in SV-COMP mode [2022-04-06 11:01:54,379 INFO L178 MainTranslator]: Built tables and reachable declarations [2022-04-06 11:01:54,508 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound50.c[597,610] [2022-04-06 11:01:54,523 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 11:01:54,528 INFO L203 MainTranslator]: Completed pre-run [2022-04-06 11:01:54,538 WARN L230 ndardFunctionHandler]: Function reach_error is already implemented but we override the implementation for the call at /storage/repos/ultimate/trunk/examples/svcomp/nla-digbench-scaling/bresenham-ll_valuebound50.c[597,610] [2022-04-06 11:01:54,545 INFO L210 PostProcessor]: Analyzing one entry point: main [2022-04-06 11:01:54,554 INFO L208 MainTranslator]: Completed translation [2022-04-06 11:01:54,555 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54 WrapperNode [2022-04-06 11:01:54,555 INFO L132 PluginConnector]: ------------------------ END CACSL2BoogieTranslator---------------------------- [2022-04-06 11:01:54,556 INFO L113 PluginConnector]: ------------------------Boogie Preprocessor---------------------------- [2022-04-06 11:01:54,556 INFO L271 PluginConnector]: Initializing Boogie Preprocessor... [2022-04-06 11:01:54,556 INFO L275 PluginConnector]: Boogie Preprocessor initialized [2022-04-06 11:01:54,564 INFO L185 PluginConnector]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,564 INFO L185 PluginConnector]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,569 INFO L185 PluginConnector]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,569 INFO L185 PluginConnector]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,575 INFO L185 PluginConnector]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,578 INFO L185 PluginConnector]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,578 INFO L185 PluginConnector]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,580 INFO L132 PluginConnector]: ------------------------ END Boogie Preprocessor---------------------------- [2022-04-06 11:01:54,580 INFO L113 PluginConnector]: ------------------------RCFGBuilder---------------------------- [2022-04-06 11:01:54,580 INFO L271 PluginConnector]: Initializing RCFGBuilder... [2022-04-06 11:01:54,581 INFO L275 PluginConnector]: RCFGBuilder initialized [2022-04-06 11:01:54,581 INFO L185 PluginConnector]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,586 INFO L173 SolverBuilder]: Constructing external solver with command: z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2022-04-06 11:01:54,594 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:01:54,607 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-06 11:01:54,609 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-06 11:01:54,637 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.init [2022-04-06 11:01:54,637 INFO L138 BoogieDeclarations]: Found implementation of procedure ULTIMATE.start [2022-04-06 11:01:54,638 INFO L138 BoogieDeclarations]: Found implementation of procedure reach_error [2022-04-06 11:01:54,638 INFO L138 BoogieDeclarations]: Found implementation of procedure assume_abort_if_not [2022-04-06 11:01:54,638 INFO L138 BoogieDeclarations]: Found implementation of procedure __VERIFIER_assert [2022-04-06 11:01:54,639 INFO L138 BoogieDeclarations]: Found implementation of procedure main [2022-04-06 11:01:54,639 INFO L130 BoogieDeclarations]: Found specification of procedure abort [2022-04-06 11:01:54,639 INFO L130 BoogieDeclarations]: Found specification of procedure __assert_fail [2022-04-06 11:01:54,641 INFO L130 BoogieDeclarations]: Found specification of procedure reach_error [2022-04-06 11:01:54,641 INFO L130 BoogieDeclarations]: Found specification of procedure #Ultimate.allocInit [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_nondet_int [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure assume_abort_if_not [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure __VERIFIER_assert [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure main [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.init [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure write~init~int [2022-04-06 11:01:54,642 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.start [2022-04-06 11:01:54,643 INFO L130 BoogieDeclarations]: Found specification of procedure write~int [2022-04-06 11:01:54,643 INFO L130 BoogieDeclarations]: Found specification of procedure read~int [2022-04-06 11:01:54,643 INFO L130 BoogieDeclarations]: Found specification of procedure ULTIMATE.dealloc [2022-04-06 11:01:54,690 INFO L234 CfgBuilder]: Building ICFG [2022-04-06 11:01:54,691 INFO L260 CfgBuilder]: Building CFG for each procedure with an implementation [2022-04-06 11:01:54,793 INFO L275 CfgBuilder]: Performing block encoding [2022-04-06 11:01:54,798 INFO L294 CfgBuilder]: Using the 1 location(s) as analysis (start of procedure ULTIMATE.start) [2022-04-06 11:01:54,799 INFO L299 CfgBuilder]: Removed 1 assume(true) statements. [2022-04-06 11:01:54,800 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:01:54 BoogieIcfgContainer [2022-04-06 11:01:54,800 INFO L132 PluginConnector]: ------------------------ END RCFGBuilder---------------------------- [2022-04-06 11:01:54,801 INFO L113 PluginConnector]: ------------------------IcfgTransformer---------------------------- [2022-04-06 11:01:54,801 INFO L271 PluginConnector]: Initializing IcfgTransformer... [2022-04-06 11:01:54,802 INFO L275 PluginConnector]: IcfgTransformer initialized [2022-04-06 11:01:54,805 INFO L185 PluginConnector]: Executing the observer IcfgTransformationObserver from plugin IcfgTransformer for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:01:54" (1/1) ... [2022-04-06 11:01:54,806 INFO L168 ansformationObserver]: Applying ICFG transformation LOOP_ACCELERATION_QVASR [2022-04-06 11:01:54,821 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:01:54 BasicIcfg [2022-04-06 11:01:54,821 INFO L132 PluginConnector]: ------------------------ END IcfgTransformer---------------------------- [2022-04-06 11:01:54,823 INFO L113 PluginConnector]: ------------------------TraceAbstraction---------------------------- [2022-04-06 11:01:54,823 INFO L271 PluginConnector]: Initializing TraceAbstraction... [2022-04-06 11:01:54,825 INFO L275 PluginConnector]: TraceAbstraction initialized [2022-04-06 11:01:54,825 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "CDTParser AST 06.04 11:01:54" (1/4) ... [2022-04-06 11:01:54,825 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f49b1a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:01:54, skipping insertion in model container [2022-04-06 11:01:54,825 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.cacsl2boogietranslator AST 06.04 11:01:54" (2/4) ... [2022-04-06 11:01:54,826 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f49b1a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 06.04 11:01:54, skipping insertion in model container [2022-04-06 11:01:54,826 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 06.04 11:01:54" (3/4) ... [2022-04-06 11:01:54,826 INFO L205 PluginConnector]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@f49b1a0 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 11:01:54, skipping insertion in model container [2022-04-06 11:01:54,826 INFO L185 PluginConnector]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.icfgtransformation CFG 06.04 11:01:54" (4/4) ... [2022-04-06 11:01:54,827 INFO L111 eAbstractionObserver]: Analyzing ICFG bresenham-ll_valuebound50.cqvasr [2022-04-06 11:01:54,830 INFO L203 ceAbstractionStarter]: Automizer settings: Hoare:true NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2022-04-06 11:01:54,830 INFO L162 ceAbstractionStarter]: Applying trace abstraction to program that has 1 error locations. [2022-04-06 11:01:54,893 INFO L339 AbstractCegarLoop]: ======== Iteration 0 == of CEGAR loop == AllErrorsAtOnce ======== [2022-04-06 11:01:54,899 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-06 11:01:54,899 INFO L341 AbstractCegarLoop]: Starting to check reachability of 1 error locations. [2022-04-06 11:01:54,944 INFO L276 IsEmpty]: Start isEmpty. Operand has 32 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 11:01:54,948 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-06 11:01:54,948 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:01:54,949 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:01:54,949 INFO L403 AbstractCegarLoop]: === Iteration 1 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:01:54,953 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:01:54,953 INFO L85 PathProgramCache]: Analyzing trace with hash -1563578423, now seen corresponding path program 1 times [2022-04-06 11:01:54,967 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:01:54,967 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1208444749] [2022-04-06 11:01:54,967 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:54,968 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:01:55,083 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:55,155 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 0 [2022-04-06 11:01:55,157 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:55,169 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 6 [2022-04-06 11:01:55,171 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:55,179 INFO L376 atingTraceCheckCraig]: Compute interpolants for subsequence at non-pending call position 12 [2022-04-06 11:01:55,181 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:55,194 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 11:01:55,195 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:01:55,195 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1208444749] [2022-04-06 11:01:55,195 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleSmtInterpolCraig [1208444749] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 11:01:55,196 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 11:01:55,196 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2022-04-06 11:01:55,197 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [801909206] [2022-04-06 11:01:55,198 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:01:55,201 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 3 states [2022-04-06 11:01:55,201 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:01:55,231 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 3 interpolants. [2022-04-06 11:01:55,232 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 11:01:55,234 INFO L87 Difference]: Start difference. First operand has 32 states, 20 states have (on average 1.35) internal successors, (27), 21 states have internal predecessors, (27), 6 states have call successors, (6), 4 states have call predecessors, (6), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) Second operand has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 11:01:55,304 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:01:55,304 INFO L93 Difference]: Finished difference Result 57 states and 74 transitions. [2022-04-06 11:01:55,305 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2022-04-06 11:01:55,307 INFO L78 Accepts]: Start accepts. Automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) Word has length 23 [2022-04-06 11:01:55,307 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:01:55,315 INFO L225 Difference]: With dead ends: 57 [2022-04-06 11:01:55,315 INFO L226 Difference]: Without dead ends: 27 [2022-04-06 11:01:55,317 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 10 GetRequests, 9 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2022-04-06 11:01:55,323 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 20 mSDsluCounter, 3 mSDsCounter, 0 mSdLazyCounter, 6 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 24 SdHoareTripleChecker+Valid, 34 SdHoareTripleChecker+Invalid, 11 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 6 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.0s IncrementalHoareTripleChecker+Time [2022-04-06 11:01:55,324 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [24 Valid, 34 Invalid, 11 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 6 Invalid, 0 Unknown, 0 Unchecked, 0.0s Time] [2022-04-06 11:01:55,336 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 27 states. [2022-04-06 11:01:55,363 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 27 to 27. [2022-04-06 11:01:55,365 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 27 states, 17 states have (on average 1.1764705882352942) internal successors, (20), 18 states have internal predecessors, (20), 6 states have call successors, (6), 4 states have call predecessors, (6), 3 states have return successors, (4), 4 states have call predecessors, (4), 4 states have call successors, (4) [2022-04-06 11:01:55,366 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 27 states to 27 states and 30 transitions. [2022-04-06 11:01:55,367 INFO L78 Accepts]: Start accepts. Automaton has 27 states and 30 transitions. Word has length 23 [2022-04-06 11:01:55,367 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:01:55,367 INFO L478 AbstractCegarLoop]: Abstraction has 27 states and 30 transitions. [2022-04-06 11:01:55,368 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 3 states, 3 states have (on average 4.0) internal successors, (12), 2 states have internal predecessors, (12), 2 states have call successors, (5), 3 states have call predecessors, (5), 2 states have return successors, (3), 2 states have call predecessors, (3), 2 states have call successors, (3) [2022-04-06 11:01:55,369 INFO L276 IsEmpty]: Start isEmpty. Operand 27 states and 30 transitions. [2022-04-06 11:01:55,370 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 24 [2022-04-06 11:01:55,370 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:01:55,370 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:01:55,371 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable0 [2022-04-06 11:01:55,372 INFO L403 AbstractCegarLoop]: === Iteration 2 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:01:55,373 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:01:55,373 INFO L85 PathProgramCache]: Analyzing trace with hash -1863481077, now seen corresponding path program 1 times [2022-04-06 11:01:55,373 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:01:55,374 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1909044813] [2022-04-06 11:01:55,374 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:55,374 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:01:55,402 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:01:55,402 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1927718467] [2022-04-06 11:01:55,402 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:55,402 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:55,402 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:01:55,413 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-06 11:01:55,422 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-06 11:01:55,477 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:55,479 INFO L263 TraceCheckSpWp]: Trace formula consists of 84 conjuncts, 13 conjunts are in the unsatisfiable core [2022-04-06 11:01:55,484 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:01:55,663 INFO L134 CoverageAnalysis]: Checked inductivity of 4 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 11:01:55,663 INFO L324 TraceCheckSpWp]: Omiting computation of backward sequence because forward sequence was already perfect [2022-04-06 11:01:55,664 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:01:55,664 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1909044813] [2022-04-06 11:01:55,664 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:01:55,665 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1927718467] [2022-04-06 11:01:55,668 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1927718467] provided 1 perfect and 0 imperfect interpolant sequences [2022-04-06 11:01:55,668 INFO L184 FreeRefinementEngine]: Found 1 perfect and 0 imperfect interpolant sequences. [2022-04-06 11:01:55,668 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [6] imperfect sequences [] total 6 [2022-04-06 11:01:55,669 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [91451471] [2022-04-06 11:01:55,670 INFO L85 oduleStraightlineAll]: Using 1 perfect interpolants to construct interpolant automaton [2022-04-06 11:01:55,671 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 6 states [2022-04-06 11:01:55,672 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:01:55,672 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 6 interpolants. [2022-04-06 11:01:55,673 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=9, Invalid=21, Unknown=0, NotChecked=0, Total=30 [2022-04-06 11:01:55,673 INFO L87 Difference]: Start difference. First operand 27 states and 30 transitions. Second operand has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 11:01:55,782 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:01:55,783 INFO L93 Difference]: Finished difference Result 39 states and 44 transitions. [2022-04-06 11:01:55,783 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2022-04-06 11:01:55,784 INFO L78 Accepts]: Start accepts. Automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) Word has length 23 [2022-04-06 11:01:55,784 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:01:55,786 INFO L225 Difference]: With dead ends: 39 [2022-04-06 11:01:55,786 INFO L226 Difference]: Without dead ends: 35 [2022-04-06 11:01:55,787 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 24 GetRequests, 18 SyntacticMatches, 0 SemanticMatches, 6 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 1 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=17, Invalid=39, Unknown=0, NotChecked=0, Total=56 [2022-04-06 11:01:55,789 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 10 mSDsluCounter, 69 mSDsCounter, 0 mSdLazyCounter, 61 mSolverCounterSat, 5 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.0s Time, 0 mProtectedPredicate, 0 mProtectedAction, 10 SdHoareTripleChecker+Valid, 91 SdHoareTripleChecker+Invalid, 66 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 5 IncrementalHoareTripleChecker+Valid, 61 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:01:55,789 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [10 Valid, 91 Invalid, 66 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [5 Valid, 61 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:01:55,790 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 35 states. [2022-04-06 11:01:55,795 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 35 to 34. [2022-04-06 11:01:55,796 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 34 states, 22 states have (on average 1.1363636363636365) internal successors, (25), 23 states have internal predecessors, (25), 7 states have call successors, (7), 5 states have call predecessors, (7), 4 states have return successors, (5), 5 states have call predecessors, (5), 5 states have call successors, (5) [2022-04-06 11:01:55,796 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 34 states to 34 states and 37 transitions. [2022-04-06 11:01:55,797 INFO L78 Accepts]: Start accepts. Automaton has 34 states and 37 transitions. Word has length 23 [2022-04-06 11:01:55,798 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:01:55,798 INFO L478 AbstractCegarLoop]: Abstraction has 34 states and 37 transitions. [2022-04-06 11:01:55,798 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 6 states, 5 states have (on average 2.4) internal successors, (12), 5 states have internal predecessors, (12), 2 states have call successors, (5), 2 states have call predecessors, (5), 1 states have return successors, (3), 1 states have call predecessors, (3), 1 states have call successors, (3) [2022-04-06 11:01:55,798 INFO L276 IsEmpty]: Start isEmpty. Operand 34 states and 37 transitions. [2022-04-06 11:01:55,800 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 33 [2022-04-06 11:01:55,800 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:01:55,801 INFO L499 BasicCegarLoop]: trace histogram [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:01:55,823 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-06 11:01:56,001 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable1,2 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:56,002 INFO L403 AbstractCegarLoop]: === Iteration 3 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:01:56,003 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:01:56,003 INFO L85 PathProgramCache]: Analyzing trace with hash -646008129, now seen corresponding path program 1 times [2022-04-06 11:01:56,003 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:01:56,003 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1308535296] [2022-04-06 11:01:56,003 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:56,003 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:01:56,025 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:01:56,026 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1252443056] [2022-04-06 11:01:56,026 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:56,026 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:56,026 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:01:56,027 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-06 11:01:56,059 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-06 11:01:56,078 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:56,079 INFO L263 TraceCheckSpWp]: Trace formula consists of 103 conjuncts, 17 conjunts are in the unsatisfiable core [2022-04-06 11:01:56,081 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:01:56,245 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 2 refuted. 0 times theorem prover too weak. 4 trivial. 0 not checked. [2022-04-06 11:01:56,245 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:01:56,365 INFO L134 CoverageAnalysis]: Checked inductivity of 8 backedges. 2 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-06 11:01:56,365 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:01:56,365 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1308535296] [2022-04-06 11:01:56,365 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:01:56,366 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1252443056] [2022-04-06 11:01:56,366 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1252443056] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:01:56,366 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:01:56,366 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 7] total 11 [2022-04-06 11:01:56,366 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [940888536] [2022-04-06 11:01:56,366 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:01:56,367 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 11 states [2022-04-06 11:01:56,367 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:01:56,367 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 11 interpolants. [2022-04-06 11:01:56,368 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=23, Invalid=87, Unknown=0, NotChecked=0, Total=110 [2022-04-06 11:01:56,368 INFO L87 Difference]: Start difference. First operand 34 states and 37 transitions. Second operand has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 11:01:56,622 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:01:56,622 INFO L93 Difference]: Finished difference Result 48 states and 54 transitions. [2022-04-06 11:01:56,622 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 12 states. [2022-04-06 11:01:56,622 INFO L78 Accepts]: Start accepts. Automaton has has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) Word has length 32 [2022-04-06 11:01:56,623 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:01:56,623 INFO L225 Difference]: With dead ends: 48 [2022-04-06 11:01:56,623 INFO L226 Difference]: Without dead ends: 42 [2022-04-06 11:01:56,624 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 67 GetRequests, 52 SyntacticMatches, 2 SemanticMatches, 13 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 11 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=44, Invalid=166, Unknown=0, NotChecked=0, Total=210 [2022-04-06 11:01:56,625 INFO L913 BasicCegarLoop]: 22 mSDtfsCounter, 14 mSDsluCounter, 101 mSDsCounter, 0 mSdLazyCounter, 168 mSolverCounterSat, 12 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 14 SdHoareTripleChecker+Valid, 123 SdHoareTripleChecker+Invalid, 180 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 12 IncrementalHoareTripleChecker+Valid, 168 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 11:01:56,625 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [14 Valid, 123 Invalid, 180 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [12 Valid, 168 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 11:01:56,626 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 42 states. [2022-04-06 11:01:56,631 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 42 to 41. [2022-04-06 11:01:56,631 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 28 states have (on average 1.1071428571428572) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 11:01:56,632 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-06 11:01:56,632 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 32 [2022-04-06 11:01:56,632 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:01:56,632 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-06 11:01:56,633 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 11 states, 9 states have (on average 2.7777777777777777) internal successors, (25), 10 states have internal predecessors, (25), 5 states have call successors, (8), 2 states have call predecessors, (8), 1 states have return successors, (5), 3 states have call predecessors, (5), 3 states have call successors, (5) [2022-04-06 11:01:56,633 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-06 11:01:56,634 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 40 [2022-04-06 11:01:56,634 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:01:56,634 INFO L499 BasicCegarLoop]: trace histogram [3, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:01:56,657 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (3)] Forceful destruction successful, exit code 0 [2022-04-06 11:01:56,856 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: 3 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true,SelfDestructingSolverStorable2 [2022-04-06 11:01:56,857 INFO L403 AbstractCegarLoop]: === Iteration 4 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:01:56,858 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:01:56,858 INFO L85 PathProgramCache]: Analyzing trace with hash -1661983408, now seen corresponding path program 1 times [2022-04-06 11:01:56,858 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:01:56,858 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [329841097] [2022-04-06 11:01:56,858 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:56,858 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:01:56,870 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:01:56,870 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1998983248] [2022-04-06 11:01:56,871 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:56,871 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:56,871 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:01:56,872 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-06 11:01:56,883 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-06 11:01:56,912 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:56,913 INFO L263 TraceCheckSpWp]: Trace formula consists of 119 conjuncts, 26 conjunts are in the unsatisfiable core [2022-04-06 11:01:56,915 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:01:57,237 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 6 proven. 4 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-06 11:01:57,237 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:01:57,676 INFO L134 CoverageAnalysis]: Checked inductivity of 15 backedges. 9 proven. 1 refuted. 0 times theorem prover too weak. 5 trivial. 0 not checked. [2022-04-06 11:01:57,676 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:01:57,676 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [329841097] [2022-04-06 11:01:57,676 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:01:57,676 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1998983248] [2022-04-06 11:01:57,677 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1998983248] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:01:57,677 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:01:57,677 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [14, 13] total 22 [2022-04-06 11:01:57,677 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [611920241] [2022-04-06 11:01:57,677 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:01:57,677 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 22 states [2022-04-06 11:01:57,678 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:01:57,689 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 22 interpolants. [2022-04-06 11:01:57,690 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=73, Invalid=389, Unknown=0, NotChecked=0, Total=462 [2022-04-06 11:01:57,690 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-04-06 11:01:58,333 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:01:58,333 INFO L93 Difference]: Finished difference Result 60 states and 68 transitions. [2022-04-06 11:01:58,334 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 26 states. [2022-04-06 11:01:58,334 INFO L78 Accepts]: Start accepts. Automaton has has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 39 [2022-04-06 11:01:58,335 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:01:58,335 INFO L225 Difference]: With dead ends: 60 [2022-04-06 11:01:58,335 INFO L226 Difference]: Without dead ends: 52 [2022-04-06 11:01:58,336 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 92 GetRequests, 57 SyntacticMatches, 1 SemanticMatches, 34 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 242 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=208, Invalid=1052, Unknown=0, NotChecked=0, Total=1260 [2022-04-06 11:01:58,337 INFO L913 BasicCegarLoop]: 20 mSDtfsCounter, 30 mSDsluCounter, 213 mSDsCounter, 0 mSdLazyCounter, 315 mSolverCounterSat, 21 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 31 SdHoareTripleChecker+Valid, 233 SdHoareTripleChecker+Invalid, 408 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 21 IncrementalHoareTripleChecker+Valid, 315 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 72 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 11:01:58,337 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [31 Valid, 233 Invalid, 408 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [21 Valid, 315 Invalid, 0 Unknown, 72 Unchecked, 0.2s Time] [2022-04-06 11:01:58,338 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 52 states. [2022-04-06 11:01:58,346 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 52 to 41. [2022-04-06 11:01:58,346 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 41 states, 28 states have (on average 1.1071428571428572) internal successors, (31), 28 states have internal predecessors, (31), 8 states have call successors, (8), 6 states have call predecessors, (8), 4 states have return successors, (6), 6 states have call predecessors, (6), 6 states have call successors, (6) [2022-04-06 11:01:58,347 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 41 states to 41 states and 45 transitions. [2022-04-06 11:01:58,347 INFO L78 Accepts]: Start accepts. Automaton has 41 states and 45 transitions. Word has length 39 [2022-04-06 11:01:58,348 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:01:58,348 INFO L478 AbstractCegarLoop]: Abstraction has 41 states and 45 transitions. [2022-04-06 11:01:58,348 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 22 states, 18 states have (on average 1.8888888888888888) internal successors, (34), 19 states have internal predecessors, (34), 6 states have call successors, (10), 2 states have call predecessors, (10), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-04-06 11:01:58,348 INFO L276 IsEmpty]: Start isEmpty. Operand 41 states and 45 transitions. [2022-04-06 11:01:58,349 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-04-06 11:01:58,349 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:01:58,349 INFO L499 BasicCegarLoop]: trace histogram [4, 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, 1, 1] [2022-04-06 11:01:58,375 INFO L540 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (4)] Forceful destruction successful, exit code 0 [2022-04-06 11:01:58,549 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable3,4 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:58,550 INFO L403 AbstractCegarLoop]: === Iteration 5 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:01:58,551 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:01:58,551 INFO L85 PathProgramCache]: Analyzing trace with hash -1381917339, now seen corresponding path program 1 times [2022-04-06 11:01:58,551 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:01:58,551 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [237070243] [2022-04-06 11:01:58,551 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:58,551 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:01:58,563 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:01:58,563 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1936983115] [2022-04-06 11:01:58,563 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:01:58,563 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:01:58,563 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:01:58,564 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-06 11:01:58,572 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-06 11:01:58,613 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:01:58,614 INFO L263 TraceCheckSpWp]: Trace formula consists of 136 conjuncts, 23 conjunts are in the unsatisfiable core [2022-04-06 11:01:58,616 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:01:58,744 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:01:58,747 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:02:01,532 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 14 proven. 2 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2022-04-06 11:02:01,532 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:02:01,794 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 11 proven. 5 refuted. 0 times theorem prover too weak. 17 trivial. 0 not checked. [2022-04-06 11:02:01,795 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:02:01,795 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [237070243] [2022-04-06 11:02:01,795 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:02:01,795 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1936983115] [2022-04-06 11:02:01,795 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1936983115] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:02:01,795 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:02:01,795 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 14 [2022-04-06 11:02:01,796 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1531090619] [2022-04-06 11:02:01,796 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:02:01,796 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 11:02:01,796 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:02:01,797 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 11:02:01,797 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=35, Invalid=147, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:02:01,797 INFO L87 Difference]: Start difference. First operand 41 states and 45 transitions. Second operand has 14 states, 10 states have (on average 2.9) internal successors, (29), 13 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-04-06 11:02:03,824 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:02:07,876 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:02:09,881 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:02:12,007 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:02:14,032 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:02:16,296 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:02:16,296 INFO L93 Difference]: Finished difference Result 56 states and 63 transitions. [2022-04-06 11:02:16,297 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 11:02:16,297 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 10 states have (on average 2.9) internal successors, (29), 13 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) Word has length 48 [2022-04-06 11:02:16,297 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:02:16,298 INFO L225 Difference]: With dead ends: 56 [2022-04-06 11:02:16,298 INFO L226 Difference]: Without dead ends: 50 [2022-04-06 11:02:16,298 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 81 SyntacticMatches, 2 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 50 ImplicationChecksByTransitivity, 4.5s TimeCoverageRelationStatistics Valid=66, Invalid=238, Unknown=2, NotChecked=0, Total=306 [2022-04-06 11:02:16,299 INFO L913 BasicCegarLoop]: 19 mSDtfsCounter, 28 mSDsluCounter, 102 mSDsCounter, 0 mSdLazyCounter, 125 mSolverCounterSat, 19 mSolverCounterUnsat, 5 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 10.2s Time, 0 mProtectedPredicate, 0 mProtectedAction, 29 SdHoareTripleChecker+Valid, 121 SdHoareTripleChecker+Invalid, 149 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 19 IncrementalHoareTripleChecker+Valid, 125 IncrementalHoareTripleChecker+Invalid, 5 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 10.3s IncrementalHoareTripleChecker+Time [2022-04-06 11:02:16,299 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [29 Valid, 121 Invalid, 149 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [19 Valid, 125 Invalid, 5 Unknown, 0 Unchecked, 10.3s Time] [2022-04-06 11:02:16,300 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 50 states. [2022-04-06 11:02:16,307 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 50 to 44. [2022-04-06 11:02:16,308 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 44 states, 30 states have (on average 1.1) internal successors, (33), 31 states have internal predecessors, (33), 9 states have call successors, (9), 6 states have call predecessors, (9), 4 states have return successors, (7), 6 states have call predecessors, (7), 7 states have call successors, (7) [2022-04-06 11:02:16,308 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 44 states to 44 states and 49 transitions. [2022-04-06 11:02:16,309 INFO L78 Accepts]: Start accepts. Automaton has 44 states and 49 transitions. Word has length 48 [2022-04-06 11:02:16,309 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:02:16,309 INFO L478 AbstractCegarLoop]: Abstraction has 44 states and 49 transitions. [2022-04-06 11:02:16,309 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 10 states have (on average 2.9) internal successors, (29), 13 states have internal predecessors, (29), 6 states have call successors, (9), 2 states have call predecessors, (9), 2 states have return successors, (7), 4 states have call predecessors, (7), 4 states have call successors, (7) [2022-04-06 11:02:16,309 INFO L276 IsEmpty]: Start isEmpty. Operand 44 states and 49 transitions. [2022-04-06 11:02:16,310 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 49 [2022-04-06 11:02:16,310 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:02:16,310 INFO L499 BasicCegarLoop]: trace histogram [4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:02:16,335 INFO L552 MonitoredProcess]: [MP /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true (5)] Ended with exit code 0 [2022-04-06 11:02:16,525 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable4,5 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:16,525 INFO L403 AbstractCegarLoop]: === Iteration 6 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:02:16,526 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:02:16,526 INFO L85 PathProgramCache]: Analyzing trace with hash -137152858, now seen corresponding path program 1 times [2022-04-06 11:02:16,526 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:02:16,526 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1647680221] [2022-04-06 11:02:16,526 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:02:16,527 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:02:16,538 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:02:16,538 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [302345998] [2022-04-06 11:02:16,538 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:02:16,538 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:16,538 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:02:16,539 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-06 11:02:16,540 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-06 11:02:16,589 INFO L136 AnnotateAndAsserter]: Conjunction of SSA is unsat [2022-04-06 11:02:16,590 INFO L263 TraceCheckSpWp]: Trace formula consists of 138 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 11:02:16,592 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:02:16,767 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 11 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 11:02:16,767 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:02:16,958 INFO L134 CoverageAnalysis]: Checked inductivity of 33 backedges. 6 proven. 11 refuted. 0 times theorem prover too weak. 16 trivial. 0 not checked. [2022-04-06 11:02:16,959 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:02:16,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1647680221] [2022-04-06 11:02:16,959 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:02:16,959 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [302345998] [2022-04-06 11:02:16,959 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [302345998] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:02:16,959 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:02:16,959 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 12 [2022-04-06 11:02:16,959 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [881686395] [2022-04-06 11:02:16,959 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:02:16,960 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 12 states [2022-04-06 11:02:16,960 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:02:16,960 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 12 interpolants. [2022-04-06 11:02:16,960 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=34, Invalid=98, Unknown=0, NotChecked=0, Total=132 [2022-04-06 11:02:16,960 INFO L87 Difference]: Start difference. First operand 44 states and 49 transitions. Second operand has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-04-06 11:02:17,135 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:02:17,136 INFO L93 Difference]: Finished difference Result 65 states and 75 transitions. [2022-04-06 11:02:17,136 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 11:02:17,136 INFO L78 Accepts]: Start accepts. Automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) Word has length 48 [2022-04-06 11:02:17,137 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:02:17,137 INFO L225 Difference]: With dead ends: 65 [2022-04-06 11:02:17,137 INFO L226 Difference]: Without dead ends: 59 [2022-04-06 11:02:17,138 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 99 GetRequests, 85 SyntacticMatches, 0 SemanticMatches, 14 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 27 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=59, Invalid=181, Unknown=0, NotChecked=0, Total=240 [2022-04-06 11:02:17,138 INFO L913 BasicCegarLoop]: 31 mSDtfsCounter, 5 mSDsluCounter, 123 mSDsCounter, 0 mSdLazyCounter, 180 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 5 SdHoareTripleChecker+Valid, 154 SdHoareTripleChecker+Invalid, 190 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 180 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.1s IncrementalHoareTripleChecker+Time [2022-04-06 11:02:17,139 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [5 Valid, 154 Invalid, 190 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 180 Invalid, 0 Unknown, 0 Unchecked, 0.1s Time] [2022-04-06 11:02:17,139 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 59 states. [2022-04-06 11:02:17,148 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 59 to 51. [2022-04-06 11:02:17,152 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 51 states, 36 states have (on average 1.1388888888888888) internal successors, (41), 36 states have internal predecessors, (41), 10 states have call successors, (10), 6 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-06 11:02:17,153 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 51 states to 51 states and 59 transitions. [2022-04-06 11:02:17,153 INFO L78 Accepts]: Start accepts. Automaton has 51 states and 59 transitions. Word has length 48 [2022-04-06 11:02:17,154 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:02:17,154 INFO L478 AbstractCegarLoop]: Abstraction has 51 states and 59 transitions. [2022-04-06 11:02:17,154 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 12 states, 12 states have (on average 3.0) internal successors, (36), 12 states have internal predecessors, (36), 8 states have call successors, (11), 2 states have call predecessors, (11), 1 states have return successors, (9), 7 states have call predecessors, (9), 7 states have call successors, (9) [2022-04-06 11:02:17,154 INFO L276 IsEmpty]: Start isEmpty. Operand 51 states and 59 transitions. [2022-04-06 11:02:17,157 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2022-04-06 11:02:17,158 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:02:17,158 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:02:17,180 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-06 11:02:17,358 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable5,6 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:17,358 INFO L403 AbstractCegarLoop]: === Iteration 7 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:02:17,359 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:02:17,359 INFO L85 PathProgramCache]: Analyzing trace with hash -545218702, now seen corresponding path program 2 times [2022-04-06 11:02:17,359 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:02:17,359 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1592708619] [2022-04-06 11:02:17,359 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:02:17,359 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:02:17,369 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:02:17,369 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [1636282249] [2022-04-06 11:02:17,369 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST1 [2022-04-06 11:02:17,369 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:17,369 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:02:17,370 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-06 11:02:17,374 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-06 11:02:17,412 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2022-04-06 11:02:17,413 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:02:17,414 INFO L263 TraceCheckSpWp]: Trace formula consists of 157 conjuncts, 9 conjunts are in the unsatisfiable core [2022-04-06 11:02:17,415 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:02:17,671 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 11:02:17,672 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:02:17,879 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 8 proven. 24 refuted. 0 times theorem prover too weak. 28 trivial. 0 not checked. [2022-04-06 11:02:17,879 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:02:17,879 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1592708619] [2022-04-06 11:02:17,879 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:02:17,880 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [1636282249] [2022-04-06 11:02:17,880 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [1636282249] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:02:17,880 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:02:17,880 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [8, 8] total 14 [2022-04-06 11:02:17,880 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [83517377] [2022-04-06 11:02:17,880 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:02:17,882 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 14 states [2022-04-06 11:02:17,882 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:02:17,882 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 14 interpolants. [2022-04-06 11:02:17,882 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=45, Invalid=137, Unknown=0, NotChecked=0, Total=182 [2022-04-06 11:02:17,883 INFO L87 Difference]: Start difference. First operand 51 states and 59 transitions. Second operand has 14 states, 14 states have (on average 3.142857142857143) internal successors, (44), 14 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-04-06 11:02:18,102 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:02:18,102 INFO L93 Difference]: Finished difference Result 78 states and 93 transitions. [2022-04-06 11:02:18,102 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2022-04-06 11:02:18,103 INFO L78 Accepts]: Start accepts. Automaton has has 14 states, 14 states have (on average 3.142857142857143) internal successors, (44), 14 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) Word has length 57 [2022-04-06 11:02:18,103 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:02:18,104 INFO L225 Difference]: With dead ends: 78 [2022-04-06 11:02:18,104 INFO L226 Difference]: Without dead ends: 72 [2022-04-06 11:02:18,104 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 116 GetRequests, 101 SyntacticMatches, 0 SemanticMatches, 15 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 41 ImplicationChecksByTransitivity, 0.1s TimeCoverageRelationStatistics Valid=64, Invalid=208, Unknown=0, NotChecked=0, Total=272 [2022-04-06 11:02:18,105 INFO L913 BasicCegarLoop]: 32 mSDtfsCounter, 8 mSDsluCounter, 198 mSDsCounter, 0 mSdLazyCounter, 266 mSolverCounterSat, 10 mSolverCounterUnsat, 0 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 0.1s Time, 0 mProtectedPredicate, 0 mProtectedAction, 8 SdHoareTripleChecker+Valid, 230 SdHoareTripleChecker+Invalid, 276 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 10 IncrementalHoareTripleChecker+Valid, 266 IncrementalHoareTripleChecker+Invalid, 0 IncrementalHoareTripleChecker+Unknown, 0 IncrementalHoareTripleChecker+Unchecked, 0.2s IncrementalHoareTripleChecker+Time [2022-04-06 11:02:18,105 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [8 Valid, 230 Invalid, 276 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [10 Valid, 266 Invalid, 0 Unknown, 0 Unchecked, 0.2s Time] [2022-04-06 11:02:18,106 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 72 states. [2022-04-06 11:02:18,117 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 72 to 56. [2022-04-06 11:02:18,117 INFO L82 GeneralOperation]: Start removeUnreachable. Operand has 56 states, 40 states have (on average 1.15) internal successors, (46), 40 states have internal predecessors, (46), 11 states have call successors, (11), 6 states have call predecessors, (11), 4 states have return successors, (9), 9 states have call predecessors, (9), 9 states have call successors, (9) [2022-04-06 11:02:18,118 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 56 states to 56 states and 66 transitions. [2022-04-06 11:02:18,118 INFO L78 Accepts]: Start accepts. Automaton has 56 states and 66 transitions. Word has length 57 [2022-04-06 11:02:18,118 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:02:18,118 INFO L478 AbstractCegarLoop]: Abstraction has 56 states and 66 transitions. [2022-04-06 11:02:18,119 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 14 states, 14 states have (on average 3.142857142857143) internal successors, (44), 14 states have internal predecessors, (44), 10 states have call successors, (13), 2 states have call predecessors, (13), 1 states have return successors, (11), 9 states have call predecessors, (11), 9 states have call successors, (11) [2022-04-06 11:02:18,119 INFO L276 IsEmpty]: Start isEmpty. Operand 56 states and 66 transitions. [2022-04-06 11:02:18,120 INFO L282 IsEmpty]: Finished isEmpty. Found accepting run of length 58 [2022-04-06 11:02:18,120 INFO L491 BasicCegarLoop]: Found error trace [2022-04-06 11:02:18,120 INFO L499 BasicCegarLoop]: trace histogram [5, 4, 4, 4, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [2022-04-06 11:02:18,144 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-06 11:02:18,339 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable6,7 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:18,340 INFO L403 AbstractCegarLoop]: === Iteration 8 === Targeting __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION === [__VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION] === [2022-04-06 11:02:18,340 INFO L144 PredicateUnifier]: Initialized classic predicate unifier [2022-04-06 11:02:18,340 INFO L85 PathProgramCache]: Analyzing trace with hash 494880272, now seen corresponding path program 3 times [2022-04-06 11:02:18,340 INFO L118 FreeRefinementEngine]: Executing refinement strategy CAMEL [2022-04-06 11:02:18,340 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleSmtInterpolCraig [1987889895] [2022-04-06 11:02:18,340 INFO L95 rtionOrderModulation]: Keeping assertion order NOT_INCREMENTALLY [2022-04-06 11:02:18,340 INFO L127 SolverBuilder]: Constructing new instance of SMTInterpol with explicit timeout -1 ms and remaining time -1 ms [2022-04-06 11:02:18,352 ERROR L245 FreeRefinementEngine]: Caught known exception: Unsupported non-linear arithmetic [2022-04-06 11:02:18,352 INFO L333 FreeRefinementEngine]: Using trace check IpTcStrategyModuleZ3 [71119025] [2022-04-06 11:02:18,352 INFO L93 rtionOrderModulation]: Changing assertion order to OUTSIDE_LOOP_FIRST2 [2022-04-06 11:02:18,352 INFO L173 SolverBuilder]: Constructing external solver with command: z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:02:18,352 INFO L189 MonitoredProcess]: No working directory specified, using /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 [2022-04-06 11:02:18,354 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-06 11:02:18,355 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-06 11:02:18,703 INFO L228 tOrderPrioritization]: Assert order OUTSIDE_LOOP_FIRST2 issued 2 check-sat command(s) [2022-04-06 11:02:18,703 INFO L229 tOrderPrioritization]: Conjunction of SSA is unsat [2022-04-06 11:02:18,705 INFO L263 TraceCheckSpWp]: Trace formula consists of 117 conjuncts, 31 conjunts are in the unsatisfiable core [2022-04-06 11:02:18,707 INFO L286 TraceCheckSpWp]: Computing forward predicates... [2022-04-06 11:02:19,791 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:02:19,795 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:02:19,797 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:02:40,734 WARN L232 SmtUtils]: Spent 9.92s on a formula simplification that was a NOOP. DAG size: 56 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:02:48,371 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 29 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-04-06 11:02:48,371 INFO L328 TraceCheckSpWp]: Computing backward predicates... [2022-04-06 11:02:55,394 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:02:57,699 WARN L907 QuantifierPusher]: no eliminatee completely removed, nonetheless the elimination was considered successful [2022-04-06 11:03:17,081 INFO L134 CoverageAnalysis]: Checked inductivity of 60 backedges. 29 proven. 1 refuted. 0 times theorem prover too weak. 30 trivial. 0 not checked. [2022-04-06 11:03:17,081 INFO L136 FreeRefinementEngine]: Strategy CAMEL found an infeasible trace [2022-04-06 11:03:17,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleSmtInterpolCraig [1987889895] [2022-04-06 11:03:17,081 WARN L310 FreeRefinementEngine]: Interpolation failed due to KNOWN_IGNORE: SMT_SOLVER_CANNOT_INTERPOLATE_INPUT [2022-04-06 11:03:17,081 INFO L333 FreeRefinementEngine]: Using interpolant generator IpTcStrategyModuleZ3 [71119025] [2022-04-06 11:03:17,081 INFO L157 FreeRefinementEngine]: IpTcStrategyModuleZ3 [71119025] provided 0 perfect and 2 imperfect interpolant sequences [2022-04-06 11:03:17,082 INFO L184 FreeRefinementEngine]: Found 0 perfect and 2 imperfect interpolant sequences. [2022-04-06 11:03:17,082 INFO L197 FreeRefinementEngine]: Number of different interpolants: perfect sequences [] imperfect sequences [17, 13] total 25 [2022-04-06 11:03:17,082 INFO L121 tionRefinementEngine]: Using interpolant automaton builder IpAbStrategyModuleStraightlineAll [1193049008] [2022-04-06 11:03:17,082 INFO L85 oduleStraightlineAll]: Using 2 imperfect interpolants to construct interpolant automaton [2022-04-06 11:03:17,082 INFO L554 AbstractCegarLoop]: INTERPOLANT automaton has 25 states [2022-04-06 11:03:17,082 INFO L100 FreeRefinementEngine]: Using predicate unifier PredicateUnifier provided by strategy CAMEL [2022-04-06 11:03:17,083 INFO L143 InterpolantAutomaton]: Constructing interpolant automaton starting with 25 interpolants. [2022-04-06 11:03:17,083 INFO L145 InterpolantAutomaton]: CoverageRelationStatistics Valid=98, Invalid=495, Unknown=7, NotChecked=0, Total=600 [2022-04-06 11:03:17,083 INFO L87 Difference]: Start difference. First operand 56 states and 66 transitions. Second operand has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2022-04-06 11:03:54,352 WARN L232 SmtUtils]: Spent 15.98s on a formula simplification. DAG size of input: 65 DAG size of output: 61 (called from [L 360] de.uni_freiburg.informatik.ultimate.lib.modelcheckerutils.smt.predicates.PredicateUnifier.getOrConstructPredicate) [2022-04-06 11:03:57,202 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:03:59,206 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:04:01,213 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.01s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:04:03,219 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 2.00s for a HTC check with result UNKNOWN. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:04:05,358 WARN L534 Checker$ProtectedHtc]: IncrementalHoareTripleChecker took 1.24s for a HTC check with result VALID. Formula has sorts [Bool, Int], hasArrays=false, hasNonlinArith=true, quantifiers [] [2022-04-06 11:04:05,452 INFO L144 Difference]: Subtrahend was deterministic. Have not used determinization. [2022-04-06 11:04:05,452 INFO L93 Difference]: Finished difference Result 62 states and 74 transitions. [2022-04-06 11:04:05,452 INFO L141 InterpolantAutomaton]: Switched to read-only mode: deterministic interpolant automaton has 23 states. [2022-04-06 11:04:05,452 INFO L78 Accepts]: Start accepts. Automaton has has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) Word has length 57 [2022-04-06 11:04:05,453 INFO L84 Accepts]: Finished accepts. some prefix is accepted. [2022-04-06 11:04:05,453 INFO L225 Difference]: With dead ends: 62 [2022-04-06 11:04:05,453 INFO L226 Difference]: Without dead ends: 0 [2022-04-06 11:04:05,454 INFO L912 BasicCegarLoop]: 0 DeclaredPredicates, 125 GetRequests, 89 SyntacticMatches, 1 SemanticMatches, 35 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 285 ImplicationChecksByTransitivity, 80.9s TimeCoverageRelationStatistics Valid=236, Invalid=1087, Unknown=9, NotChecked=0, Total=1332 [2022-04-06 11:04:05,455 INFO L913 BasicCegarLoop]: 16 mSDtfsCounter, 25 mSDsluCounter, 153 mSDsCounter, 0 mSdLazyCounter, 289 mSolverCounterSat, 18 mSolverCounterUnsat, 4 mSolverCounterUnknown, 0 mSolverCounterNotChecked, 11.8s Time, 0 mProtectedPredicate, 0 mProtectedAction, 27 SdHoareTripleChecker+Valid, 169 SdHoareTripleChecker+Invalid, 370 SdHoareTripleChecker+Unknown, 0 SdHoareTripleChecker+Unchecked, 0.0s SdHoareTripleChecker+Time, 18 IncrementalHoareTripleChecker+Valid, 289 IncrementalHoareTripleChecker+Invalid, 4 IncrementalHoareTripleChecker+Unknown, 59 IncrementalHoareTripleChecker+Unchecked, 11.8s IncrementalHoareTripleChecker+Time [2022-04-06 11:04:05,455 INFO L914 BasicCegarLoop]: SdHoareTripleChecker [27 Valid, 169 Invalid, 370 Unknown, 0 Unchecked, 0.0s Time], IncrementalHoareTripleChecker [18 Valid, 289 Invalid, 4 Unknown, 59 Unchecked, 11.8s Time] [2022-04-06 11:04:05,456 INFO L82 GeneralOperation]: Start minimizeSevpa. Operand 0 states. [2022-04-06 11:04:05,456 INFO L88 GeneralOperation]: Finished minimizeSevpa. Reduced states from 0 to 0. [2022-04-06 11:04:05,456 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-06 11:04:05,456 INFO L88 GeneralOperation]: Finished removeUnreachable. Reduced from 0 states to 0 states and 0 transitions. [2022-04-06 11:04:05,456 INFO L78 Accepts]: Start accepts. Automaton has 0 states and 0 transitions. Word has length 57 [2022-04-06 11:04:05,456 INFO L84 Accepts]: Finished accepts. word is rejected. [2022-04-06 11:04:05,456 INFO L478 AbstractCegarLoop]: Abstraction has 0 states and 0 transitions. [2022-04-06 11:04:05,456 INFO L479 AbstractCegarLoop]: INTERPOLANT automaton has has 25 states, 21 states have (on average 2.1904761904761907) internal successors, (46), 22 states have internal predecessors, (46), 7 states have call successors, (11), 2 states have call predecessors, (11), 3 states have return successors, (9), 5 states have call predecessors, (9), 5 states have call successors, (9) [2022-04-06 11:04:05,457 INFO L276 IsEmpty]: Start isEmpty. Operand 0 states and 0 transitions. [2022-04-06 11:04:05,457 INFO L282 IsEmpty]: Finished isEmpty. No accepting run. [2022-04-06 11:04:05,463 INFO L788 garLoopResultBuilder]: Registering result SAFE for location __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION (0 of 1 remaining) [2022-04-06 11:04:05,471 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-06 11:04:05,669 WARN L460 AbstractCegarLoop]: Destroyed unattended storables created during the last iteration: SelfDestructingSolverStorable7,8 /storage/repos/ultimate/releaseScripts/default/UAutomizer-linux/z3 -smt2 -in SMTLIB2_COMPLIANT=true [2022-04-06 11:04:05,671 INFO L343 DoubleDeckerVisitor]: Before removal of dead ends 0 states and 0 transitions. [2022-04-06 11:04:58,796 WARN L232 SmtUtils]: Spent 53.07s on a formula simplification. DAG size of input: 114 DAG size of output: 38 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 11:05:21,012 WARN L232 SmtUtils]: Spent 22.19s on a formula simplification. DAG size of input: 134 DAG size of output: 45 (called from [L 149] de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.HoareAnnotationComposer.combineInter) [2022-04-06 11:05:21,269 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-06 11:05:21,269 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initFINAL(line -1) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.initEXIT(line -1) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L885 garLoopResultBuilder]: At program point ULTIMATE.startENTRY(line -1) the Hoare annotation is: true [2022-04-06 11:05:21,270 INFO L885 garLoopResultBuilder]: At program point L-1(line -1) the Hoare annotation is: true [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startFINAL(line -1) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point ULTIMATE.startEXIT(line -1) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L885 garLoopResultBuilder]: At program point assume_abort_if_notENTRY(lines 10 12) the Hoare annotation is: true [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point L11(line 11) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point L11-2(lines 10 12) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L882 garLoopResultBuilder]: For program point assume_abort_if_notEXIT(lines 10 12) no Hoare annotation was computed. [2022-04-06 11:05:21,270 INFO L885 garLoopResultBuilder]: At program point mainENTRY(lines 21 53) the Hoare annotation is: true [2022-04-06 11:05:21,270 INFO L885 garLoopResultBuilder]: At program point L25(line 25) the Hoare annotation is: true [2022-04-06 11:05:21,271 INFO L882 garLoopResultBuilder]: For program point L25-1(line 25) no Hoare annotation was computed. [2022-04-06 11:05:21,271 INFO L878 garLoopResultBuilder]: At program point L27(line 27) the Hoare annotation is: (and (<= 0 main_~X~0) (<= main_~X~0 50)) [2022-04-06 11:05:21,271 INFO L882 garLoopResultBuilder]: For program point L27-1(line 27) no Hoare annotation was computed. [2022-04-06 11:05:21,271 INFO L878 garLoopResultBuilder]: At program point L32-2(lines 32 47) the Hoare annotation is: (let ((.cse0 (<= main_~x~0 main_~X~0))) (and (or .cse0 (forall ((main_~y~0 Int)) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ (* main_~y~0 2) (* main_~Y~0 2) (* 2 (* main_~Y~0 main_~x~0))))) (not (= main_~X~0 0))) (or .cse0 (forall ((main_~Y~0 Int)) (= (* 2 (* main_~y~0 main_~x~0)) (+ (* (* main_~X~0 main_~y~0) 2) (* main_~y~0 2))))) (= (+ (* main_~Y~0 2) (* 2 (* main_~Y~0 main_~x~0))) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (<= main_~Y~0 50) (<= 0 main_~Y~0) (<= 0 main_~X~0) (<= main_~X~0 50))) [2022-04-06 11:05:21,271 INFO L882 garLoopResultBuilder]: For program point L32-3(lines 32 47) no Hoare annotation was computed. [2022-04-06 11:05:21,271 INFO L878 garLoopResultBuilder]: At program point L35(line 35) the Hoare annotation is: (let ((.cse1 (* main_~Y~0 2)) (.cse0 (* 2 main_~xy~0)) (.cse4 (* 2 (* main_~Y~0 main_~x~0))) (.cse2 (* 2 main_~yx~0)) (.cse3 (<= main_~x~0 main_~X~0))) (and (= (+ .cse0 main_~X~0 main_~v~0) (+ .cse1 .cse2)) (or .cse3 (forall ((main_~y~0 Int)) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ (* main_~y~0 2) (* main_~Y~0 2) (* 2 (* main_~Y~0 main_~x~0))))) (not (= main_~X~0 0))) (= (+ .cse1 .cse4) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (<= main_~Y~0 50) (<= 0 main_~Y~0) (<= 0 main_~X~0) (<= main_~X~0 50) (or (= (+ .cse0 (* main_~y~0 2) .cse4) (+ (* 2 (* main_~y~0 main_~x~0)) .cse2)) .cse3))) [2022-04-06 11:05:21,271 INFO L878 garLoopResultBuilder]: At program point L50(line 50) the Hoare annotation is: (let ((.cse2 (* main_~y~0 2)) (.cse0 (* main_~Y~0 2)) (.cse1 (* 2 (* main_~Y~0 main_~x~0)))) (and (= (+ .cse0 .cse1) (+ (* (* main_~X~0 main_~y~0) 2) main_~X~0 main_~v~0)) (= (+ .cse2 .cse0 (* 2 main_~yx~0)) (+ (* 2 main_~xy~0) main_~X~0 main_~v~0)) (= (+ (* 2 (* main_~y~0 main_~x~0)) main_~X~0 main_~v~0) (+ .cse2 .cse0 .cse1)))) [2022-04-06 11:05:21,271 INFO L882 garLoopResultBuilder]: For program point L35-1(lines 32 47) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L50-1(line 50) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L40(lines 40 45) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point mainFINAL(lines 21 53) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L40-2(lines 40 45) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point mainEXIT(lines 21 53) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L885 garLoopResultBuilder]: At program point __VERIFIER_assertENTRY(lines 13 19) the Hoare annotation is: true [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L14(lines 14 17) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L15(lines 15 16) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point L14-2(lines 13 19) no Hoare annotation was computed. [2022-04-06 11:05:21,272 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertErr0ASSERT_VIOLATIONERROR_FUNCTION(line 16) no Hoare annotation was computed. [2022-04-06 11:05:21,273 INFO L882 garLoopResultBuilder]: For program point __VERIFIER_assertEXIT(lines 13 19) no Hoare annotation was computed. [2022-04-06 11:05:21,275 INFO L719 BasicCegarLoop]: Path program histogram: [3, 1, 1, 1, 1, 1] [2022-04-06 11:05:21,276 INFO L178 ceAbstractionStarter]: Computing trace abstraction results [2022-04-06 11:05:21,282 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,282 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,287 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,288 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,289 INFO L202 PluginConnector]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 06.04 11:05:21 BasicIcfg [2022-04-06 11:05:21,289 INFO L132 PluginConnector]: ------------------------ END TraceAbstraction---------------------------- [2022-04-06 11:05:21,289 INFO L158 Benchmark]: Toolchain (without parser) took 206933.40ms. Allocated memory was 192.9MB in the beginning and 252.7MB in the end (delta: 59.8MB). Free memory was 142.1MB in the beginning and 225.4MB in the end (delta: -83.3MB). Peak memory consumption was 115.0MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,289 INFO L158 Benchmark]: CDTParser took 0.12ms. Allocated memory is still 192.9MB. Free memory is still 158.5MB. There was no memory consumed. Max. memory is 8.0GB. [2022-04-06 11:05:21,290 INFO L158 Benchmark]: CACSL2BoogieTranslator took 198.31ms. Allocated memory is still 192.9MB. Free memory was 141.9MB in the beginning and 170.7MB in the end (delta: -28.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,290 INFO L158 Benchmark]: Boogie Preprocessor took 23.91ms. Allocated memory is still 192.9MB. Free memory was 170.7MB in the beginning and 169.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,290 INFO L158 Benchmark]: RCFGBuilder took 219.97ms. Allocated memory is still 192.9MB. Free memory was 169.1MB in the beginning and 157.8MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,290 INFO L158 Benchmark]: IcfgTransformer took 20.67ms. Allocated memory is still 192.9MB. Free memory was 157.8MB in the beginning and 156.5MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,291 INFO L158 Benchmark]: TraceAbstraction took 206466.24ms. Allocated memory was 192.9MB in the beginning and 252.7MB in the end (delta: 59.8MB). Free memory was 156.2MB in the beginning and 225.4MB in the end (delta: -69.2MB). Peak memory consumption was 129.9MB. Max. memory is 8.0GB. [2022-04-06 11:05:21,292 INFO L339 ainManager$Toolchain]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * CDTParser took 0.12ms. Allocated memory is still 192.9MB. Free memory is still 158.5MB. There was no memory consumed. Max. memory is 8.0GB. * CACSL2BoogieTranslator took 198.31ms. Allocated memory is still 192.9MB. Free memory was 141.9MB in the beginning and 170.7MB in the end (delta: -28.9MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * Boogie Preprocessor took 23.91ms. Allocated memory is still 192.9MB. Free memory was 170.7MB in the beginning and 169.1MB in the end (delta: 1.7MB). Peak memory consumption was 2.1MB. Max. memory is 8.0GB. * RCFGBuilder took 219.97ms. Allocated memory is still 192.9MB. Free memory was 169.1MB in the beginning and 157.8MB in the end (delta: 11.2MB). Peak memory consumption was 11.5MB. Max. memory is 8.0GB. * IcfgTransformer took 20.67ms. Allocated memory is still 192.9MB. Free memory was 157.8MB in the beginning and 156.5MB in the end (delta: 1.4MB). Peak memory consumption was 1.0MB. Max. memory is 8.0GB. * TraceAbstraction took 206466.24ms. Allocated memory was 192.9MB in the beginning and 252.7MB in the end (delta: 59.8MB). Free memory was 156.2MB in the beginning and 225.4MB in the end (delta: -69.2MB). Peak memory consumption was 129.9MB. Max. memory is 8.0GB. * Results from de.uni_freiburg.informatik.ultimate.boogie.preprocessor: - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] - GenericResult: Unfinished Backtranslation Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - StatisticsResult: ErrorAutomatonStatistics NumberErrorTraces: 0, NumberStatementsAllTraces: 0, NumberRelevantStatements: 0, 0.0s ErrorAutomatonConstructionTimeTotal, 0.0s FaulLocalizationTime, NumberStatementsFirstTrace: -1, TraceLengthAvg: 0, 0.0s ErrorAutomatonConstructionTimeAvg, 0.0s ErrorAutomatonDifferenceTimeAvg, 0.0s ErrorAutomatonDifferenceTimeTotal, NumberOfNoEnhancement: 0, NumberOfFiniteEnhancement: 0, NumberOfInfiniteEnhancement: 0 - PositiveResult [Line: 16]: call to reach_error is unreachable For all program executions holds that call to reach_error is unreachable at this location - StatisticsResult: Ultimate Automizer benchmark data CFG has 5 procedures, 32 locations, 1 error locations. Started 1 CEGAR loops. OverallTime: 206.4s, OverallIterations: 8, TraceHistogramMax: 5, PathProgramHistogramMax: 3, EmptinessCheckTime: 0.0s, AutomataDifference: 64.4s, DeadEndRemovalTime: 0.0s, HoareAnnotationTime: 75.6s, InitialAbstractionConstructionTime: 0.0s, PartialOrderReductionTime: 0.0s, HoareTripleCheckerStatistics: 9 mSolverCounterUnknown, 148 SdHoareTripleChecker+Valid, 22.9s IncrementalHoareTripleChecker+Time, 0 mSdLazyCounter, 140 mSDsluCounter, 1155 SdHoareTripleChecker+Invalid, 22.7s Time, 0 mProtectedAction, 0 SdHoareTripleChecker+Unchecked, 131 IncrementalHoareTripleChecker+Unchecked, 962 mSDsCounter, 100 IncrementalHoareTripleChecker+Valid, 0 mProtectedPredicate, 1410 IncrementalHoareTripleChecker+Invalid, 1650 SdHoareTripleChecker+Unknown, 0 mSolverCounterNotChecked, 100 mSolverCounterUnsat, 193 mSDtfsCounter, 1410 mSolverCounterSat, 0.0s SdHoareTripleChecker+Time, 9 IncrementalHoareTripleChecker+Unknown, PredicateUnifierStatistics: 0 DeclaredPredicates, 632 GetRequests, 492 SyntacticMatches, 6 SemanticMatches, 134 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 657 ImplicationChecksByTransitivity, 86.7s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=56occurred in iteration=7, InterpolantAutomatonStates: 103, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s DumpTime, AutomataMinimizationStatistics: 0.1s AutomataMinimizationTime, 8 MinimizatonAttempts, 43 StatesRemovedByMinimization, 6 NontrivialMinimizations, HoareAnnotationStatistics: 0.0s HoareAnnotationTime, 11 LocationsWithAnnotation, 29 PreInvPairs, 50 NumberOfFragments, 259 HoareAnnotationTreeSize, 29 FomulaSimplifications, 792 FormulaSimplificationTreeSizeReduction, 0.1s HoareSimplificationTime, 11 FomulaSimplificationsInter, 4653 FormulaSimplificationTreeSizeReductionInter, 75.5s HoareSimplificationTimeInter, RefinementEngineStatistics: TRACE_CHECK: 0.1s SsaConstructionTime, 0.5s SatisfiabilityAnalysisTime, 63.7s InterpolantComputationTime, 327 NumberOfCodeBlocks, 309 NumberOfCodeBlocksAsserted, 10 NumberOfCheckSat, 594 ConstructedInterpolants, 6 QuantifiedInterpolants, 3384 SizeOfPredicates, 50 NumberOfNonLiveVariables, 854 ConjunctsInSsa, 128 ConjunctsInUnsatCore, 14 InterpolantComputations, 2 PerfectInterpolantSequences, 339/426 InterpolantCoveringCapability, INVARIANT_SYNTHESIS: No data available, INTERPOLANT_CONSOLIDATION: No data available, ABSTRACT_INTERPRETATION: No data available, PDR: No data available, ACCELERATED_INTERPOLATION: No data available, SIFA: No data available, ReuseStatistics: No data available - AllSpecificationsHoldResult: All specifications hold 1 specifications checked. All of them hold - InvariantResult [Line: 32]: Loop Invariant [2022-04-06 11:05:21,297 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,297 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,298 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] [2022-04-06 11:05:21,298 WARN L418 cessorBacktranslator]: Identifier is quantified, using identity as back-translation of IdentifierExpression[main_~y~0,QUANTIFIED] Derived loop invariant: (((((((x <= X || (forall main_~y~0 : int :: 2 * (main_~y~0 * x) + X + v == main_~y~0 * 2 + Y * 2 + 2 * (Y * x))) || !(X == 0)) && (x <= X || (forall main_~Y~0 : int :: 2 * (y * x) == X * y * 2 + y * 2))) && Y * 2 + 2 * (Y * x) == X * y * 2 + X + v) && Y <= 50) && 0 <= Y) && 0 <= X) && X <= 50 RESULT: Ultimate proved your program to be correct! [2022-04-06 11:05:21,477 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...